Understanding the problem with RSA

Recent reports suggest that the very commonly used RSA encryp­tion algorithm has sig­ni­ficant security flaws. I couldn’t find a good explan­a­tion of the math­em­at­ical problem that causes these flaws online, but I think I’ve worked it out below.

The security of RSA keys rests on the dif­fi­culty of fac­tor­ising the product (usually called n) of two large primes (usually called p and q). Mul­tiplying p and q together is a very quick oper­a­tion, but working out which p and q were mul­tipled mul­ti­plied together to make a given n is very time con­suming. If you don’t believe me, see how quickly you can multiply 3259 and 6553; and compare this with the time it takes you to work out which two prime numbers were mul­ti­plied together to make 60557843.

In cryp­to­graphy, n is the public key and is made widely avail­able, whereas p and q make up the private key and must be kept secret. Public keys are usually pub­lished to key­servers (here’s mine) and this means that they can be freely downloaded.

Researchers from the Ecole Poly­tech­nique Fédérale de Lausanne in Switzer­land down­loaded 11.4 million RSA keys and dis­covered that a number of RSA public keys share a prime factor; that is, they have a dif­ferent n with one over­lap­ping p or q. This is prob­lem­atic because finding the greatest common denom­in­ator of two numbers is a very quick process when compared with the time taken for prime factorisation.

If we take 60557843 (from above) and compare it with, for example, 15381367 we can very quickly find that they share 7741 as a factor, and with that piece of inform­a­tion we can find the other prime numbers very quickly.

This should not be a problem, because the prime numbers used in encryp­tion are very large (usually hundreds or thou­sands of digits) and the chance of a “col­li­sion” is very small. But if the system used by the computer for gen­er­ating prime numbers is not truly random then two com­puters using the same system are likely to produce the same prime numbers and these col­li­sions become far more likely; the researchers found that about 0.38% (1 in 263) of keys were “faulty” in this way.

In con­clu­sion, the problem exists not with the RSA algorithm itself but with the pseudo-random number gen­er­ators used in RSA systems. Those gen­er­ating encryp­tion keys should ensure they use a hardware random number gen­er­ator, one that uses a truly random process such as radio­active decay, to generate their random numbers.