Not all messages encrypted with the RSA algorithm can be decrypted. This post will show why this is possible and why it does not matter in practice.
RSA in a nutshell
RSA encryption starts by finding two large primes, p and q. These primes are kept secret, but their product n = pq is made public.
You publish an invitation for anyone to send you encrypted messages by turning their message into a number m < n and computing
c = me mod n
where e is a number you announce along with n. That is, your public key consists of the pair (n, e).
When someone sends you c, you can decrypt it by computing
m = cd mod n
where d is your decryption key. You can compute d, and the rest of the world cannot, because you know the factors of n. The private key d is computed by solving
ed = 1 mod φ(n)
where φ(n) is the number of positive integers less than n and relatively prime to n. For distinct primes p and q we have
φ(pq) = (p − 1)(q − 1).
Nobody else knows p and q, and so they don’t know φ(n), and they cannot compute d. It is conceivable that there’s a way to compute d that requires less work than factoring n, but nobody has found such an algorithm.
The reason d works as a decryption key is Euler’s theorem. This is the heart of the RSA cryptosystem. Euler’s theorem says that if a is relatively prime to n, then
aφ(n) = 1 mod n.
Because
c = me mod n
it follows that
cd = med = mφ(n)+1 = m mod n.
Exception
Everything above is valid, except we’ve glossed over a requirement of Euler’s theorem: m must be relatively prime to n. If m is not relatively prime to n the decryption algorithm will not work.
For a tiny example, assume n = 10. There are four positive numbers less than 10 and relatively prime to 10, namely 1, 3, 7, and 9, and so φ(10) = 4. If m is a number that ends in 1, 3, 7, or 9 and you raise it to the 4th power you get a number ending in 1. This is a concrete example of Euler’s theorem. But if m is any number that does not end in 1, 3, 7, or 9, then m4 will not end in 1.
Most of the numbers less than 10 are not relatively prime to 10. But the values of n used in RSA encryption are enormous, and nearly all numbers less than n are relatively prime to n.
An RSA modulus n only has two factors: p and q. So if m is not relatively prime to n, then m is a multiple of p or q. This is extremely unlikely to happen by chance, as unlikely as guessing the factorization of n.
In practice the primes p and q have at least 1024 bits. In that case the odds of creating a message m that is not relatively prime to pq are on the order of 1 in 10308.
So while the chance of sending a message than cannot be decrypted is vanishingly small, it is possible. So why not warn people about the possibility? Because then you’d be giving away your private key! You’d have to reveal the secret factors p and q in order to tell people what messages to avoid.
You could check that your message m is relatively prime to n before encrypting it. This can be done efficiently using the Euclidean algorithm. If you find that m is not relatively prime to n, then you’ve discovered one of the factors of n and so you’ve broken the encryption.
Related posts
The post RSA encrypted messages that cannot be decrypted first appeared on John D. Cook.