Thursday, December 5, 2013

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 ≡ me (mod n) and sends c to Bob
    • Bob decrypts by computing m ≡ cd (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  ≡ me ≡ 301209007 ≡ 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 cd ≡ 113535859035722866116402471153538991 ≡ 30120 (mod n) to obtain the original message

No comments:

Post a Comment