Sequentia Explores: The Mathematics of Crypto
Part III: Historical Ciphers & the Dawn of Cryptanalysis
Lecture 25: The RSA Algorithm (Part 1): How Prime Numbers Create Your Keys
In our last lecture, we used the analogy of a special lockbox with two keys—a public “locking” key and a private “unlocking” key—to understand the breakthrough of asymmetric cryptography. This concept, born from the idea of a trapdoor one-way function, solves the key exchange problem.
But how do we actually create such a magical lockbox using mathematics?
Today, we take our first deep dive into a real-world, revolutionary public-key system: the RSA algorithm. Named after its inventors—Ron Rivest, Adi Shamir, and Leonard Adleman—RSA was one of the first practical public-key cryptosystems and remains in widespread use today.
In this lecture, we will focus exclusively on the key generation process. We’ll see, step-by-step, how the mathematical tools we’ve gathered (prime numbers and Euler’s totient function) are used to construct the public and private keys, creating the trapdoor at the heart of the system.
Let’s follow along as Alice generates her key pair.
Step 1: Choose Two Large, Secret Prime Numbers (p and q)
This is the foundational secret. Alice starts by selecting two distinct, very large prime numbers.
- For our toy example: Let’s use small, simple primes so we can follow the math.
- p = 61
- q = 53
- In the real world: p and q would be enormous, perhaps 300 digits long each, found using probabilistic primality tests like the Fermat test we discussed. Alice keeps these two primes absolutely secret. They are the core of her private key.
Step 2: Calculate the Modulus (n)
Alice now multiplies her two secret primes together to create the modulus, n.
n = p × q
- For our example:
- n = 61 × 53 = 3233
This number n will be part of the public key. It is publicly known. Notice that for anyone else in the world (like Eve), n is just a number. But because Alice chose p and q to be huge primes, it is computationally infeasible for Eve to factor n back into its original components p and q. This is the one-way function in action!
Step 3: Calculate Euler’s Totient Function (φ(n))
Now Alice uses a tool from our toolkit: Euler’s totient function. As we learned in Lecture 14, for a number n that is the product of two distinct primes p and q, the formula is wonderfully simple:
φ(n) = (p – 1) × (q – 1)
- For our example:
- φ(3233) = (61 – 1) × (53 – 1)
- φ(3233) = 60 × 52 = 3120
This value, φ(n), is the “magic number” that governs the RSA mathematical universe. It is kept secret. Notice that calculating φ(n) is incredibly easy for Alice because she knows p and q. For Eve, who only knows n, calculating φ(n) is just as hard as factoring n. This is the trapdoor.
Step 4: Choose the Public Exponent (e)
Alice now needs to choose her public exponent, e. This number will also be part of the public key. It must satisfy two conditions:
- 1 < e < φ(n)
- e and φ(n) must be coprime (i.e., GCD(e, φ(n)) = 1).
- For our example: We need to find an e between 1 and 3120 that is coprime to 3120. Common choices for e are small prime numbers. A very popular choice in real systems is e = 65537 (because it has some nice binary properties that speed up encryption). For our small example, let’s just pick a small prime that works. Let’s try e = 17.
- Is GCD(17, 3120) = 1? Yes, since 17 is prime and doesn’t divide 3120.
- So, Alice chooses e = 17.
Step 5: Calculate the Private Exponent (d)
This is the final, crucial step. Alice must calculate her private exponent, d. This number is the modular multiplicative inverse of e modulo φ(n).
This means d must satisfy the equation:
d × e ≡ 1 (mod φ(n))
- For our example: We need to find d such that d × 17 ≡ 1 (mod 3120).
- This is solved using the Extended Euclidean Algorithm, another tool from our toolkit (which we’ll explore in more detail later). It’s a straightforward process for a computer.
- Running the algorithm for our numbers gives us: d = 2753.
- Let’s check: (2753 × 17) = 46801. Now, 46801 mod 3120.
- 46801 = 15 × 3120 + 1. The remainder is 1! It works.
- The number d is the core of the private key and must be kept absolutely secret.
The Keys are Forged!
Alice is now done. She has created her key pair:
- Public Key: The pair of numbers (n, e)
- In our example: (3233, 17)
- Alice can publish this for the world to see.
- Private Key: The pair of numbers (n, d)
- In our example: (3233, 2753)
- Alice must guard this with her life. The original primes p and q, and φ(n), are also part of the secret information used to generate d.
Summary of the Trapdoor:
- Everyone knows n and e. Encrypting a message involves an operation using these public numbers.
- Only Alice knows d (and the original p and q). Decrypting a message requires d.
- The security: To find d, Eve would need to know φ(n). To find φ(n), she would need to know p and q. To find p and q, she would have to factor the massive public number n, which is computationally infeasible.
We have successfully used our mathematical tools to construct a system where the public and private keys are intrinsically linked, yet the private key cannot be derived from the public one. We have forged our two different keys for the magical lockbox.
In our next lecture, RSA (Part 2), we will see exactly how Bob uses Alice’s public key (n, e) to encrypt a message, and how Alice uses her private key (n, d) to decrypt it, using the power of modular exponentiation and Euler’s Theorem.
