RSA Cryptosystem

Math for CS · Axiom Academy

How two strangers can exchange secrets in public — using nothing but modular arithmetic. 1. The Setup: Public Key vs Private Key RSA gives every user two keys that are mathematically linked: Anyone who knows (n, e) can encrypt a message addressed to you. Only the holder of d can decrypt it. The trick is choosing n , e , and d so this asymmetry works. 2. Key Generation (the 5-step ritual) Pick two large primes p and q (in real RSA each is about 1024 bits long). Compute the modulus n = pq . This becomes part of the public key. Compute Euler's totient . This is the count of integers in that are coprime to n . Pick a public exponent e with and . In practice e = 65537 is almost universal. Compute the private exponent using the extended Euclidean algorithm. Publish (n, e) . Destroy p , q , and . Keep d in a vault. Now suppose Alice wants to send a message m (an integer with (n, e) . That's the entire algorithm. Encryption is one modular exponentiation with the public exponent; decryption is one modular exponentiation with the private exponent. Both operations are fast on a modern CPU even when n has 2048 bits. 4. Why it Works (Euler's Theorem) We need to show for every message m . Since d is the inverse of e modulo , we know for some integer k . Therefore Real RSA uses 1024-bit primes, but the math is identical with toy values. Let's pick p = 11 and q = 13 . So Bob's public key is (143, 7) and his private key is 103 . And — we recovered the original message.

This is the written version of the interactive lesson above. See the full Math for CS course.