RSA Encryption Cracked Easily (Sometimes)

A large chunk of the global economy now rests on public key cryptography. We generally agree that with long enough keys, it is infeasible to crack things encoded that way. Until such time as it isn’t, that is. Researchers published a paper a few years ago where they cracked a large number of keys in a very short amount of time. It doesn’t work on any key, as you’ll see in a bit, but here’s the interesting part: they used an undescribed algorithm to crack the codes in a very short amount of time on a single-core computer. This piqued [William Kuszmaul’s] interest and he found some follow up papers that revealed the algorithms in question. You can read his analysis, and decide for yourself how badly this compromises common algorithms.

The basis for public key cryptography is that you multiply two large prime numbers to form a product and post it publicly. Because it is computationally difficult to find prime factors of large numbers, this is reasonably secure because it is difficult to find those prime numbers that are selected randomly.

However, the random selection leads to an unusual attack. Public keys, by their very nature, are available all over the Internet. Most of them were generated with the same algorithm and random number generation isn’t actually totally random. That means some keys share prime factors and finding a common factor between two numbers isn’t nearly as difficult.

In fact, that’s the heart of the problem. Factoring a 232-digit number took about 1,500 years of computing time. But finding common factors between two numbers is much easier. However, the original research paper mentioned they found common factors for 36 trillion pairs of keys in a matter of hours. That was faster than [William] expected.

Before you get too alarmed, the researches looked at 6.2 million keys and were able to crack fewer than 13,000. Not exactly a gaping security hole, unless you are one of the 13,000, of course. However, the entire post highlights two things: first, speeding up algorithms is usually more efficient than making faster computersm, and second, you never know when your carefully crafted encryption is going to be rendered worthless by a better algorithm.

It is widely thought that quantum computing will significantly change what you’ll have to do to be secure. We’ve seen before where an implementation of an algorithm is a weak point.