How RSA uses integers to secure the world’s secrets.
If you read my non-technical introduction to public key cryptography, or have seen the setup but never the details, you may be left with the question: How do we actually create an asymmetric encryption scheme? In this article, I will introduce you to one of the simplest, most beautiful, and most widely used answers. The algorithm is called RSA, and it is used to protect millions of secrets every day.
Before we get started, let’s recall our objective. We want to send data to a stranger via the internet, but the data we want to send is top secret. We need to encrypt our data in such a way that the receiver can decrypt our message, but no one else can. We can’t communicate with the recipient to agree on an encryption scheme. Like any data, we can store our information as a series of numbers. Surprisingly, the answer can be found using modular arithmetic.
Modular arithmetic.
RSA uses a mathematical technique called modular arithmetic. Most high school curricula in the United States don’t teach this, but they should. The ideas are simple and the technique is powerful. Computers run entirely on modular arithmetic, and high school students would be better served learning modular arithmetic than memorizing the unit circle.
Remember division with remainder? That’s what modular arithmetic is all about. Every elementary schooler learns (although they might not phrase it in this way), that given two positive whole numbers a and b, they can divide b into a with a remainder. In other words, they can find whole numbers q and r such that
The remainder, r, can be made smaller than b. If you divide 104 into groups of 7 and you have 12 left over, then you can just make another group of 7. Then you’ll have 5 left over, and so your remainder is 5.
Modular arithmetic is just simple arithmetic, except that you add and multiply remainders after dividing out some fixed number. If you want an every day example, ask yourself what month comes 5 months after October? You might count out on your fingers, or you might reason as follows: October is the 10th month of the year, so 2 months after October is December. After December, the counting restarts, so we count our remaining 3 months starting from 1. That leaves us at the 3rd month of the next year, so March is 5 months after October. More succinctly you could think — 5 months after the 10th month is the 15th month, but there are only 12 months, so the 15th month is just the 3rd month in disguise. See the modular arithmetic? You did the following arithmetic — 10 + 5 = 15 = 12(1) + 3 ≡ 3 (mod 12). You added the numbers of months, but took the remainder modulo 12 to get the appropriate month. That’s what the ≡ sign together with (mod 12) means — 12(1) + 3 is the same as 5 modulo 12. You could do this with any two numbers, and you would always get a number between 1 and 12. We can use this to do addition on the numbers 1,2,…,12 in a way that we always get another number between 1 and 12. We can even do multiplication the same way. For example, we can take 4(14) = 64 = 12(5) + 4, and so we say that 4(14) ≡ 4 (mod 12).
Modular arithmetic can behave weirdly, and this is what makes it perfect for cryptography. For example, it is a tried and true rule of regular arithmetic that if ab = 0 then either a = 0 or b= 0. Not true for arithmetic modulo 12. Why not? Try working out what 6 × 6 is modulo 12 and you’ll see the answer.
An even harder question arises when we want to take “modular roots”. What’s the square root of 49? Well, 7 or -7, right? What’s the square root of 49 modulo 12? Hopefully 7, right? Right. We can just check, first by noting that 49 = 12(4) + 1, so 49 is 1 modulo 12. Also, 7² = 49 so 7² is 1 modulo 12. But, it turns out this isn’t the only answer. We can just start checking for other possibilities, and eventually we find that 5² = 25 = 12(2) + 1. So 5 is also a square root of 49 modulo 12. It gets better. Another check shows that 11² = 121 = 12(10) + 1, so 11 is a square root of 49 modulo 12. But, wait — there’s more! We almost forgot the most obvious answer: 49 is just 1 modulo 12, and 1² = 1, so 1 is another square root of 49 modulo 12.
The key point is this:
Finding roots modulo some number N is hard. Really hard.
The algorithm.
It turns out that in just the right situation, the problem described above becomes much less difficult. During the 18th century, the mostly-and-then-entirely blind mathematician Leonhard Euler proved that in certain situations, finding roots modulo N is easy. His idea involves greatest common divisors, or GCDs. The greatest common divisor of two whole numbers x and y is the largest number that divides both of them. If d is that number, we write gcd(x,y) = d. Euler proved that if p and q are odd prime numbers, and g= gcd((p-1)(q-1)), then for any a satisfying gcd(a,pq) = 1, we have
Wrapping your head around this equation might take some work, but it suffices to understand this: if we have two large prime numbers p and q, and we take N = pq, then this equation gives us an easy way to find numbers a satisfying the equation above modulo N. In fact, we can do even better. Using this equation, we can solve for an eth root modulo N for any e with gcd(e,(p-1)(q-1)) = 1. Here’s how:
Set-up: Start with some odd prime numbers, which we’ll call p and q. Multiply them together to get N = pq. Take e to be some number with gcd(e,(p-1)(q-1)) = 1. We want to find an x whose eth power modulo N is c.
Step 2: We find d with de ≡ 1 (mod (p-1)(q-1)). You’ll have to trust me on this, but this is why we need the condition that we need gcd(e,(p-1)(q-1)) = 1. If you haven’t seen it before this won’t make sense, but it turns out this condition is exactly what we need for such a d to exist.
Step 3: We notice that since de ≡ 1 (mod (p-1)(q-1), de is one more than some multiple of (p-1)(q-1). Say de = 1 + k(p-1)(q-1). Let’s suppose c ≡ 1 (mod N) for simplicity, then raise c to the dth power and see what happens:
Whew! We were able to solve the equation in the case that c ≡ 1 (mod N). Not only this, but it turns out that the same solution works for any c. Even better, this solution is unique. These facts are not obvious, but they don’t require any big ideas that haven’t already played a part in our story.
Now that we’re through the most technical part, how do we use the math to encrypt our messages? The table below, which I’ve copied from Hoffstein, Pipher, and Silverman’s An Introduction to Mathematical Cryptopgraphy, illustrates the algorithm nicely. In this table, Bob is would like to receive a message from Alice (for some reason it is standard practice in cryptography to use Bob and Alice in examples).
Verification.
Do you see where we used all those computations in the table above? When Bob decrypts Alice’s message, what he is really doing is finding an eth root of c modulo N. In the context of the algorithm e is the encryption exponent, and c is the encrypted text (sometimes called the ciphertext — hence c). Bob receives c, and knows e, so he just has to find the eth root of c and voila! the original message m.
But is this secure? Everyone else in the world knows e as well, so why can’t everyone else decrypt Alice’s message as well? To find the answer, remember that the security of this algorithm relies on information asymmetry. Bob needs to know something that not everyone does, and this extra information is what will make decryption easy for Bob but hard for everyone else. So what is the asymmetry in the table above? It’s the primes p and q that Bob used to create N = pq. Bob picked these privately, and he didn’t make them public. Everyone in the world knows what N is, but without knowing what p and q are, no one else can find the number d such that de ≡ 1 (mod (p-1)(q-1)), and this is what makes the algorithm so beautiful: if p and q are large enough, even knowing N it is computationally impossible to find p and q. I say “computationally’’ impossible, because of course p and q exist, and maybe we can find them by just guessing (or equivalently, maybe we’ll win the lottery, probably about 20 times in a row), but there is no known way to find them systematically in a reasonable amount of time. In fact, we can choose p and q so that N is so large that by some estimates, it would take over 450000 core-years to factor N. For comparison, I’m writing this is on a good quality state-of-the-art laptop, and I have 8 cores. That means you would need 56,250 of copies my laptop running together continuously for a year to factor N. That’s pretty good security.
Before I leave you, I would be remiss not to mention the small asterisk in the above success story. In theory, a quantum computer can factor integers faster. Much, much… much faster. That’s why cryptographers are racing to develop quantum-secure algorithms as fast as governments, companies, and academics are racing to build quantum computers. But that is all a very long story, which I will have to leave for another time…
