Notes - The RSA Algorithm

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

• 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⁹⁰⁰⁷ ≡ 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

Back to ToC