Key Generation

Generate two random primes, p and q, e.g p=3, q=11.

Compute n = pq, n = 3 * 11 = 33.

Compute phi = (p1)(q1) = (31)(111) = 20

Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1, e.g e = 7, gcd(7, 20) = 1

Compute the secret exponent d, 1 < d < phi, such that (e * d) mod phi = 1, (7 * d) mod 20 = 1, d = 3
 The public key is (7, 33) and the private key (3, 33).
Encrypt

m = 2

c = 2^7 mod 33 = 29
Decrypt

c = 29

m = 29 ^ 3 mod

n is known as the modulus.

e is known as the public exponent or encryption exponent or just the exponent.

d is known as the secret exponent or decryption exponent.