- Public Key Cryptosystem
- Presented by Diffie-Hellman
- Goal - allow Alice to send a message to Bob without previous contact and without the use of a courier to exchange a key but protect the message from Eve a potential attacker
- The RSA Algorithm
- Bob chooses secret primes p and q and computes n = pq
- Bob chooses e with gcd(e, (p-1)(q-1)) = 1
- Bob computes d with de ≡ 1 (mod(p-1)(q-1))
- Bob makes n and e public, and keeps p, q, d secret
- Alice encrypts m as c ≡ m
^{e}(mod n) and sends c to Bob - Bob decrypts by computing m ≡ c
^{d}(mod n) - Example of the RSA Algorithm
- p = 885320963, q = 238855417
- n = p * q = 211463707796206571
- Let the encryption exponent be e = 9007
- Let the sample message m be 30120
- c ≡ m
^{e}≡ 30120^{9007}≡ 113535859035722866 (mod n) - Where c stands for the ciphertext Alice is sending to Bob
- Bob knows p and q so he knows (p-1)(q-1) then he uses the extended euclidean algorithm to compute d such that de ≡ 1 mod (p-1)(q-1)
- d = 116402471153538991
- Bob computes c
^{d}≡ 113535859035722866^{116402471153538991 }≡ 30120 (mod n) to obtain the original message

## Thursday, December 5, 2013

### Notes - The RSA Algorithm

The following are notes from Introduction to Cryptography with Coding Theory.

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment