Steps in Public Key Encryption

Preparation

  1. Choose arbitrary large primes \(p,q\).
  2. Compute \(N = p\cdot q\).
  3. Choose arbitrary exponent \(e\) relatively prime1 to \((p-1)(q-1)\).
  4. Compute \(d = e^{-1}\mod (p-1)(q-1) \).
  5. Publicly release \(N, e\) for encryption, keep \(d\) private for decryption.

Encryption

  1. Convert message into a positive integer \(m\le N\).
  2. Compute \(c=m^e\mod N\).
  3. Send recipient \(c\).

Decryption

  1. Compute \(m=c^d\mod N\)
  1. "is relatively prime to" is equivalent to "shares no common factors with"