What Is RSA Encryption?
The Rivest-Shamir-Adleman (RSA) cryptosystem solved the problem of how to encrypt data so that it could only be decrypted by the intended recipient. In 1977, the co-creators—Ron Rivest, Adi Shamir, and Leonard Adleman—proposed an elegant solution based on a new way to use encryption keys. Simply put, encryption keys are very large values used in the mathematical processes that are applied to the data to encrypt it. The breakthrough that RSA brought to the world of cryptography was the use of private and public keys.
We should also mention Clifford Cocks, the chief mathematician at the U.K.’s Government Communication Headquarters (GCHQ) who applied public and private key encryption/decryption to cryptography in 1973. The information was classified and remained secret. It was only declassified in 1997. Great minds obviously do think alike.
The public key/private key sequence is to obtain the intended recipient’s public key and use it in the encryption process along with your private key. The recipient can then decrypt the data using their private key and your public key. Public keys can be safely made public, and private keys are kept securely private. And because the recipient doesn’t need to be a human, any system, service, or device that makes its public key known in a certified, authenticated fashion can use RSA encryption. This allows system-to-system communications to be encrypted.
A public key certificate is used to certify the identity of the owner of the public key. Two common examples of public key certificates are Secure Socket Layer and Transport Layer Certificates (SSL/TLS). Public keys can be transmitted between people who want to communicate, or they can be retrieved from key servers such as the OpenPGP key server.
Secure Shell (SSH), OpenPGP, S/MIME, and SSL/TSL all use RSA encryption, and all browsers use it. Some cryptocurrencies use it. Practically the whole of the e-commerce world depends on RSA in one way or another. Anything that threatens the integrity of the RSA cryptosystem needs to be looked at carefully.
RELATED: How to Use OpenPGP Encryption for Emails in Thunderbird
Threats to RSA Cryptography
A central element of the encryption algorithms is irreversibility. The mathematical transforms that are performed on the data must be irreversible for all practical purposes.
The RSA scheme uses very large numbers that are the product of multiplying two large prime numbers together. Taking two prime numbers and multiplying them together is trivial and computationally cheap. It doesn’t take much processing power or time to perform that action. But being handed the resulting product and with no prior knowledge trying to work out—via factoring—which two prime numbers were used is computationally expensive.
Factoring gets much harder very quickly as the numbers become larger. It would take such a prohibitive time—some estimates run to trillions of years—to crack this type of encryption. This provides a safe pseudo-irreversibility. It’s not really irreversible, but it would take so long to do it, that it might as well be genuinely irreversible.
The advent of quantum computing brings a threat to this type of encryption. Quantum computers show promise to be able to do the integer factorization required to determine the two prime numbers in an extremely short time. It is predicted that a quantum computer running a derivative of Shor’s Algorithm would be able to find the prime numbers within acceptably short periods of time—perhaps even within hours.
It’s expected to take 25 years or more before a quantum computer capable of doing that exists. That might be fine for some information that is encrypted now—the usefulness of the information might have expired by then. But some of what is being encrypted now will still need to be protected and private in 25 (or even more) years from now. For example, some government and security communications will still be sensitive even then.
Errors in the implementation of the RSA have caused issues in the past. The theoretical RSA has to be rendered into a working software implementation before it can be useful—and complex software will often contain bugs. There have been tweaks and replacements to the algorithms used in the RSA cryptosystem as flaws have been found in the implementations. Old versions have been deprecated and superseded by new versions.
There have been claims that back doors have been introduced into the RSA algorithms because of coercion by, or cooperation with, national security agencies. These accusations have never been proven, but flaws that effectively provided back doors have been found and subsequently addressed.
What Is the New Threat?
Professor Claus Peter Schnorr is a retired mathematician and cryptographer. He was a professor at the Department of Mathematics and Computer Science at Johann Wolfgang Goethe University in Frankfurt am Main.
A preprint of a paper by Schnorr (preprint means that it is in late development but not yet peer-reviewed) proposes a new method of factoring prime integers on today’s computing platforms at a greatly accelerated rate. The paper is titled “Fast Factoring Integers by SVP Algorithms.” SVP stands for shortest vector problem. The abstract ends with the provocative sentence “This destroys the RSA cryptosystem.”
By condensing a very complicated piece of work into a simple statement, what this propounds is an improvement by an order of magnitude in the speed of factoring. The speed gain would be achieved by using a refinement of some of Schnorr’s earlier work. Obviously, a revolutionary reduction in factoring integers would have a significant impact on the RSA cryptosystem. That is, if the theoretical paper is factually correct and if a practical implementation can bear out the hypothesis.
The paper promotes a factoring method using mathematical structures called lattices. Professor Schnorr is a widely recognized expert in this field and its application to cryptography. The paper claims that the new technique is dramatically faster than the General Number Field Sieve (GNFS) algorithm, which is considered to be the fastest current technique for factoring large numbers.
An Analysis of the Threat
Schorr’s paper is theoretical in nature. There are no timings or results from implementations. The theoretical speed gains over the GNFS sound impressive on paper, but do the theory and mathematics withstand scrutiny by those who actually understand this at the level required to meaningfully comment on it?
Dr. Léo Ducas is a researcher in the cryptography group at the Centrum Wiskunde & Informatica (CWI). The CWI is the national research institute for mathematics and computer science in the Netherlands. Ducas completed his Ph.D. in 2013 on “Lattice Based Signatures: Attacks, Analysis and Optimization.” He has worked with lattices throughout his career. He’s also a cryptographer, so he is eminently capable of reviewing Schnorr’s paper.
Even better for our purposes, Dr. Léo Ducas is a programmer. If you fancy a turn at Cryptris, his asymmetric cryptography game, go right ahead. His academic source code is scattered across GitHub. Some of it sits in his own repository, while much more resides in the repositories of other multi-author projects that he’s worked on.
He’s performed a review and analysis of Schnorr’s paper. He has also created an implementation of Schnorr’s algorithms as a SageMath script. He’s named it SchnorrGate. Ducas also points to a discussion on the cryptography StackExchange. This examines a mistake in one of the formulas in the paper which, if used as printed, produces highly inaccurate results. With this formula corrected, Schnorr’s factoring method does work, but at a much slower rate than he predicts.
Ducas’ findings from his SageMath tests corroborate this. They illustrate that Schnorr’s factoring algorithms do work, but much more slowly than the best methods already available today.
We Can All Breathe Again
The RSA lives to encrypt another day. But what would have happened if the claims in the paper had turned out to be true? Well, chaos, initially, and then, the adoption of a new cryptosystem.
Perhaps the era of Elliptic-Curve Cryptography (ECC) would have arrived.
