Cryptography, Security

The RSA problem

The RSA algorithm is heavily relied upon to secure communication on the Internet. Primarily this is done in the form of certificates used to secure SSL/TLS connections as is done to secure the HTTPS protocol. But would you believe that the RSA algorithm cannot be shown mathematically to be secure? It’s true! This fact is known as the RSA problem.

To understand why the RSA problem exists, it is necessary to understand how the RSA algorithm works. It turns out there’s not that much to it. RSA is a public/private key encryption algorithm, also known as an asymmetric key encryption algorithm. With a public/private key pair, a value can be encrypted using the public key and can only decrypted using the corresponding private key. I’ll first explain how to generate and use an RSA public/private key pair and then attempt to describe the mathematics behind why it works. Once that’s out of the way, it will be possible to explain the challenge of mathematically proving that the RSA algorithm is secure.

To generate an RSA public/private key pair, you first choose two large prime numbers. Let’s call them p and q. The product of p and q we’ll call n. Using p and q, knowing they are prime, we can easily compute φ(n) = (pq)(q – 1) where φ is Euler’s totient function. Next, we’ll choose an exponent which we’ll call e, which is less than φ(n) and coprime with φ(n). Next we’ll calculate the multiplicative modualar inverse of e (mod φ(n)), which we’ll call d. The combination of n and e is the public key. The combination of n and d is the private key.

To encrypt a value m, which must be less than n, using the public key we calculate

c = me (mod n)

To decrypt c using the private key we can obtain the original value m by calculating

m = cd (mod n)

Why does this work? The answer lies in Euler’s theorem. Euler’s theorem proves that for any coprime integers a and n,

aφ(n) ≡ 1 (mod n)

If you’re not familiar with modular congruence, this states that if you divide aφ(n) by n, the remainder will be 1.

What we need to do is show that (me)dm (mod n). Note that (me)d can also be written as med.

Since we chose d such that ed ≡ 1 (mod φ(n)), we can also say that ed = 1 + hφ(n) where h is some positive integer. Therefore

medm1 + hφ(n)m(mhφ(n)) ≡ m(mφ(n))h (mod n)

Now, using Euler’s theorem we can convert the last term into

m(1)hm (mod n)

which is what we intended to show. As long as m is a positive integer less than n then m is equal to the least positive member of the congruence class of (me)d (mod n), meaning m is the remainder when dividing by n. Note that if m is too small then me may be less than n and it may be possible to derive m from me by taking the eth root of me.

So what’s the problem? The problem is that the security of the RSA algorithm rests on an unproven assumption. The assumption is that it is easier to find two very large prime numbers than it is to factor their product. It turns out it’s very easy to find large primes, or rather to find very large integers that are very likely prime. For example, choosing two random 512-bit numbers that are likely prime can be done in a small fraction of a second with a modern computer. However, using the most efficient currently known integer factorization algorithm, factoring the 1024-bit product of those two primes would take many thousands of CPU-years of computation.

But why does the complexity of factorizing the product of two primes matter with respect to the security of RSA? The reason is that if the two primes chosen, p and q can be obtained by factoring their product, n, which is part of the public key, then it becomes trivial to calculate φ(n), and then it becomes trivial to calculate d. Being able to easily calculate d given n means that the private key can easily be recovered from the public key. Being able to easily recover the private key from the public key would completely invalidate the security of the RSA algorithm.

So, again, what’s the problem? It takes far longer to factor the product of two large prime numbers than it takes to choose them. We’re safe using RSA, right? Well, the problem is that while the currently known algorithms for factoring the product of two large primes take far longer to factor than it takes to choose them, nobody has so far been able to prove that a much faster algorithm doesn’t exist. That doesn’t mean that one does exist, just that we can’t say for sure that one does not.

In fact, at least one such algorithm is known to exist, but it is currently impractical to implement on the scale necessary to defeat RSA. The algorithm is known as Shor’s algorithm and it relies on quantum computers able to process numbers as large as n, which currently do not exist for values of n currently used in RSA public keys. Quantum computers are getting more and more powerful all the time, however, so it’s a good bet that the days of RSA are numbered since eventually quantum computers will be able to factor numbers large enough to make the use of RSA impractical.