• Choose random semi-prime n = p * q

  • Choose random e: gcd(e, (p-1)(q-1)) = 1

  • d: ed = 1 mod (p-1)(q-1)

Public key: (e, n)

Private key: (d, n)

Encrypt: E(M) = M^e mod n

Decrypt: D(C) = C^d mod n


D(E(M)) = M is proved based on Fermat's little theorem or Euler's theorem.

(p-1)(q-1) is the Euler's totient number for n (number of integers less than n co-prime with it).

Knowing p and q, it's trivial to compute d from e. Not knowing: supposedly hard.

Attacks and Stuff

RSA Problem


DER: binary format; modulo concatenated with exponent.

PEM: base64-encoded DER.

Last updated