The RSA Algorithm

Number Theory · Axiom Academy

A complete walkthrough of public-key cryptography using modular arithmetic and number theory 1. Key Generation: Choosing Primes p and q The first step in RSA is to select two distinct prime numbers, p and q. These primes should be large (typically hundreds of digits) to ensure security, but we'll use small examples for clarity. Next, we compute n = pq, which becomes part of both the public and private keys. The number n is called the modulus . 2. Computing φ(n) and Choosing the Public Exponent e We need to compute Euler's totient function: φ(n) = (p-1)(q-1). This counts the number of integers less than n that are coprime to n. Now we choose a public exponent e such that: gcd(e, φ(n)) = 1 (e and φ(n) are coprime) 3. Finding the Private Exponent d The private exponent d is the modular multiplicative inverse of e modulo φ(n). In other words, we need to find d such that: This can be found using the Extended Euclidean Algorithm. For our example: 4. Encryption: Converting Message to Ciphertext To encrypt a message m (where 0 ≤ m < n), we compute the ciphertext c using the public key (n, e): Let's encrypt the message m = 5 using our public key (143, 7): 5. Decryption: Recovering the Original Message To decrypt the ciphertext c, the recipient uses their private key (n, d) to compute: Let's decrypt our ciphertext c = 47 using the private key (143, 103): We successfully recovered the original message! Public Key: (n, e) = (143, 7) - used for encryption

This is the written version of the interactive lesson above. See the full Number Theory course.