RSA Algorithm
Key Generation
-
Generate two random primes, p and q, e.g p=3, q=11.
-
Compute n = pq, n = 3 * 11 = 33.
-
Compute phi = (p-1)(q-1) = (3-1)(11-1) = 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