“This destroys the RSA cryptosystem.”
That is the last sentence in the abstract of a new, preliminary, dense mathematical paper published by renowned mathematician Claus Peter Schnorr. If this turns out to be true, it will mean bad news for anybody who relies on the underpinnings of encryption – which is everyone!
The paper, posted as a pre-print, meaning it is a draft paper that must undergo academic peer review, claims it has found an algorithm that significantly speeds up a particular kind of mathematical problem called factorization. Factorization is the process of finding two numbers that, when multiplied together, provide the given number. For example, calculating 23 x 29 is easy. (Try it yourself.) But factorizing 437 – finding the two numbers that multiply together to make 437 – will take anybody a bit of time. (It’s 19 x 23 by the way.)
Schnorr claims that he has found a way to significantly speed up the calculation needed to perform factorization – a claim that is currently widely disputed. Supposedly, his method will factor a number with roughly 260 digits about ten trillion times faster than previous methods.
Does Math Matter?
Factorization is the mathematical puzzle on which a specific encryption method called RSA is based. RSA is used in many encryption systems on the Internet and elsewhere. Schnorr’s method supposedly makes these systems vulnerable. Essentially the method allows someone to guess the secret encryption keys being used in a given communication. For instance, roughly half a billion TLS certificates used for securing web traffic would no longer be secure. There are also many other systems – credit cards, payment terminals, security systems – that rely on RSA for security. As a result, the social impact of being able to crack RSA would be huge.
Fortunately a lot of protocols on the Internet support what is called algorithm agility. Algorithm agility is the ability to swap one cryptographic method for another, allowing a seamless transition between different types of cryptographic methods for encrypting things. The Internet would be able to adapt to Schnorr’s new discovery by changing the building blocks we use in cryptographic communication. In practice, deploying those building blocks is a completely different matter; some systems are more agile than others. There would be many places that would be left vulnerable for a long time because people can’t or don’t know how to upgrade them.
Learn more about Encryption and why it matters.
Wake-Up Call
It is likely that nation state actors with access to supercomputers can already factor RSA keys that are about 340 digits long, but at high cost. It takes an initial investment of billions of dollars and a couple of hours per key. If Schnorr’s method works, it might enable factorization of RSA by actors with fewer resources. One could see bitcoin miners turning their computing infrastructure towards the much more profitable breaking of RSA keys.
Even if the claim in Schnorr’s paper gets scaled back after academic peer review – the essence of the scientific process is that one publishes one’s ideas early and tries to get them proven or disproven, which is what is happening here – this serves as a wake-up call. RSA will, at some point, crumble, as will all cryptographic methods in time. For example, we know that functional quantum computers will be able to crack RSA keys easily as well as a few other commonly used cryptographic schemes. But the development of quantum computers at the scale needed to do this is an engineering quest that will likely take decades. That means we still have time to gradually phase out RSA for updated crypto algorithms that are safe from known attacks, such as those that can be orchestrated with quantum computing.
What Can We Learn from This?
Cryptography and encryption are not static technology and knowledge. They are constantly evolving based on the current state of the art. It takes effort to keep our digital environment secure. To deal with known threats, mathematicians, engineers, producers of software and hardware, and system and network engineers must work together to evaluate new knowledge and design then implement what comes next. It takes work from all of these people to maintain our digital security.
We should invest in the skills and capabilities to keep our digital environment safe by investing in encryption and the systems that rely on it. However, some countries, such as Australia, are investing in laws and policies that undermine encryption. As we can see, cryptography does not age well. We have a hard enough time designing secure systems that will stand the test of time.
In the meantime, we must wait and see if the assertions in Schnorr’s paper hold up to the mathematical community’s challenges. We will be watching the conversation intently.
Help champion a safer Internet for all. Join the Global Encryption Coalition.
Image by Nick Hillier via Unsplash