RSA Encryption

Here, we summarize a naive version of the RSA cryptosystem. This version of RSA should not be used; it is very broken, as you will show in exercises one through four. Consult wikipedia for more detail.

• KeyGen:
  • Choose two random primes p and q.
  • Let n = pq be the modulus.
  • Select a random encryption exponent e such that the greatest common denominator of e and (p-1)(q-1) is 1 (that is, e and (p-1)(q-1) are relatively prime).
  • Let the decryption exponent d be e^-1 mod (p-1)(q-1).
  • Return the public key pk = (n, e) and the secret key sk = d.
• Enc(pk = (n, e), m), where m is a message to be encrypted:
  • Return the ciphertext c = m^e mod n.
• Dec(sk = d, c), where c is a ciphertext to be decrypted:
  • Return the recovered message m = c^d mod n.

To see how RSA can be used correctly, take a look at the sections starting here in the RSA description in Wikipedia.