RSA algorithm with example

RSA (Rivest-Shamir-Adleman, 1977) is a public-key (asymmetric) cryptosystem. It uses a pair of keys: a public key (e, n) to encrypt and a private key (d, n) to decrypt. Its security depends on the difficulty of factoring a large number n = p × q into its primes.

Algorithm

Key generation

1. Choose two large distinct primes p and q.
2. Compute n = p × q.
3. Compute φ(n) = (p − 1)(q − 1).
4. Choose e with 1 < e < φ(n) and gcd(e, φ(n)) = 1.
5. Compute d such that d × e ≡ 1 (mod φ(n)).
6. Public key = (e, n); private key = (d, n).

Encryption: C = Mᵉ mod n (M < n) Decryption: M = Cᵈ mod n

Example

Take p = 7, q = 13.

Public key = (5, 91), private key = (29, 91).

Encrypt M = 9: C = 9⁵ mod 91. 9^1 = 9, 9^2 = 81, 9^4 = 9 (all mod 91); 5 = 1 + 4, so 9^5 = 9 × 9 mod 91 = 81. C = 81.

Decrypt: M = 81²⁹ mod 91. 81^1 = 81, 81^2 = 9, 81^4 = 81, 81^8 = 9, 81^16 = 81 (all mod 91); 29 = 1 + 4 + 8 + 16, so 81^29 = 81 × 81 × 9 × 81 mod 91 = 9. M = 9, the original message.

Sender: M=9 --(e=5,n=91)--> C=81 ----> Receiver: C=81 --(d=29,n=91)--> M=9

Answer: public key (5, 91), private key (29, 91); ciphertext 81; decrypted message 9.

Notes

• Real RSA uses primes of 1024 bits or more (n of 2048 bits).
• Used for key exchange and digital signatures (sign with the private key, verify with the public key).