Recent reports suggest that the very commonly used RSA encryption algorithm has significant security flaws. I couldn’t find a good explanation of the mathematical problem that causes these flaws online, but I think I’ve worked it out below.

The security of RSA keys rests on the difficulty of factorising the product (usually called n) of two large primes (usually called p and q). Multiplying p and q together is a very quick operation, but working out which p and q were multipled multiplied together to make a given n is very time consuming. 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 multiplied together to make 60557843.

In cryptography, n is the public key and is made widely available, whereas p and q make up the private key and must be kept secret. Public keys are usually published to keyservers (here’s mine) and this means that they can be freely downloaded.

Researchers from the Ecole Polytechnique Fédérale de Lausanne in Switzerland downloaded 11.4 million RSA keys and discovered that a number of RSA public keys share a prime factor; that is, they have a different n with one overlapping p or q. This is problematic because finding the greatest common denominator 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 information we can find the other prime numbers very quickly.

This should not be a problem, because the prime numbers used in encryption are very large (usually hundreds or thousands of digits) and the chance of a “collision” is very small. But if the system used by the computer for generating prime numbers is not truly random then two computers using the same system are likely to produce the same prime numbers and these collisions become far more likely; the researchers found that about 0.38% (1 in 263) of keys were “faulty” in this way.

In conclusion, the problem exists not with the RSA algorithm itself but with the pseudo-random number generators used in RSA systems. Those generating encryption keys should ensure they use a hardware random number generator, one that uses a truly random process such as radioactive decay, to generate their random numbers.