RSA Encryption Cracked

It has long been known that even the best encryption system can be broken more easily if its users don’t do a good job. Sometimes what constitutes a good job can be difficult to work out.

In World War II the cracking of the German Enigma code was made easier by the way messages always started in the same way – providing some known plain text to compare against the encrypted text. So it is with RSA, and in this case the unexpected problem is that too many people and devices use the same methods of generating random primes.

This is an odd story, especially so because it harks back to a paper from 2012. RSA encryption is important because it is the basis of the public key cryptography framework that we all use. So is it cracked, or isn’t it?

This has hit the headlines now because of a post by William Kuszmaul on his blog Algorithm Soup – highly recommended. It explains the ideas in detail so here I will concentrate on the more general ideas and implications.

The RSA cypher uses two large random primes p and q and user makes available their product online pk=p*q for everyone to see and use. The value of pk is the public key and it is used to encrypt a message to send.

To decrypt the message you need to know p and q and factoring pk is hard. A recent attempt to factor a 232-decimal digit key took 1,500 years of computation. Keys of 512 bits can be factored in weeks, but we use 1024-bit and 4096-bit keys and, while some speculate that factoring 1024-bit keys is possible, 4096-bit keys are still assumed to be very safe.

So RSA is safe? Well, not if we all use the same prime numbers it isn’t. You might think it unlikely that we would use the same numbers, but this ignores the way that these large primes are generated. Typically a random number generator is used to create a value that is then tested for primeness and this can be done reasonably quickly.

The problem is that the random number generators we use tend to be the same and they aren’t as random as we might like. To improve the randomness you have to start off the generator using a selected seed and often the same seed is used repeatedly. In other words, a great many public keys share a prime.

Why is this a weakness?

This is where the surprise comes in for any non-number theory expert. If two public keys share a prime then this prime is a common divisor and, the surprise is that, it is easier to find the greatest common denominator of two numbers than it is to factor a number.

Finding a common divisor takes time proportional to the number of digits. Once you have the common divisor you can read messages sent by any of the public keys.

Add to this the fact that the researchers, Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung and Christophe Wachter, have implemented a fast greatest common divisor algorithm and you can see that RSA poorly implemented might have a problem.

They collected over 6 million public keys and managed to crack 12,934 of them. What is more, the computation was done on a single-core CPU in a matter of hours. Interestingly they didn’t include details of their fast algorithm in the paper.

Presumably they were worried that it might be used to crack keys for evil purposes.

However, it seems that another group did publish details of their fast algorithm, which involved multiplying all the keys together to produce a really big number and then finding the greatest common divisor.

This really is faster! It was also reported that most of the crackable keys came from embedded applications, such as routers, firewalls and so on. Clearly manufacturers tended to use the same random number generator.

So what is the solution?

Easy – either make sure your public key doesn’t share a prime with any related keys or, much better, use a strong random number generator that has a lot of entropy in it. The good news is that RSA isn’t cracked – but you have to do it right.

What is interesting is that it seems that cracking one public key is difficult, but given some sharing of primes, cracking multiple public keys is easier. Are there any similar loopholes?

More Information

• Algorithm Soup
• Ron was wrong, Whit is right
• Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices

Credit: iProgrammer

Last updated on June 21st, 2023