- Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits. [See note 1].
- Compute n = pq and (φ) phi = (p-1)(q-1).
- Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1. [See note 2].
- Compute the secret exponent d, 1 < d < phi, such that
ed ≡ 1 (mod phi). [See note 3].
- The public key is (n, e) and the private key is (n, d). The values of p, q, and phi should also be kept secret.
We are given the public key (n, e)= (77, 7)
- n is known as the modulus.
- e is known as the public exponent or encryption exponent.
- d is known as the secret exponent or decryption exponent.
Now p and q are primes such that pq=n, so p=11, q=7 (the order does not
matter). So phi = 60.
We know e=7, so we seek a d such that ed=1 mod 60, well d=9 will do,
and so the private key is (77, 9).