Researcher Claims to Crack RSA-2048 With Quantum Computer

•
November 1, 2023    

A scientist claims to have developed an inexpensive system for using quantum computing to crack RSA, which is the world’s most commonly used public key algorithm.

See Also: Live Webinar | Generative AI: Myths, Realities and Practical Use Cases

The response from multiple cryptographers and security experts is: Sounds great if true, but can you prove it? “I would be very surprised if RSA-2048 had been broken,” Alan Woodward, a professor of computer science at England’s University of Surrey, told me.

The scientist making the claim is Ed Gerck. According to his profile on LinkedIn, where he also posted his announcement of the RSA crack, he’s a quantum computing developer at a firm he founded called Planalto Research in Mountain View, California, among other jobs.

“Quantum computing has become a reality. We broke the RSA-2048 key,” Gerck said.

Many cryptographers believe that the most viable approach to this problem will involve using a quantum algorithm developed by Peter Shor in 1994 to find the prime factors of an integer, once a sufficiently powerful quantum computer is built to run the algorithm against the likes of RSA-2048.

“Breaking RSA is usually attempted by using Shor’s algorithm in a quantum computer but there are no quantum computers in existence that can produce enough gates to implement Shor’s algorithm that would break 2048 keys,” Woodward said.

Gerck said all his “QC computations were done in a commercial cellphone, or a commercial Linux desktop,” at a capital cost of less than $1,000. “No cryogenics or special materials were used.”

Reached for comment, Gerck shared a preprint of his research paper, titled “QC Algorithms: Faster Calculation of Prime Numbers” and co-authored with Ann Gerck. An abstract for the paper is available online. In it, the researchers write that instead of using Shor’s algorithm to crack the keys, they employed a system based on quantum mechanics that can be run using off-the-shelf hardware.

I asked Gerck if this was theoretical, or if they had cracked RSA-2048 in a real-world setting, if they planned to demonstrate this to any quantum computing experts who might vouch for their findings, and when their peer-reviewed findings would be published.

He responded, “We broke a public RSA-2048. We cannot risk impersonation.”

Woodward, after reviewing the Gercks’ research paper, said it appears to be “all theory proving various conjectures – and those proofs are definitely in question.”

He added, “I’ll believe they have done this when people can send them RSA modulus to factor and they send back two primes. Until I see that, I’m just confused and not convinced they’ve done what they claim in the headlines.”

Anton Guzhevskiy, the chief operating officer at Australian cybersecurity firm ThreatDefence, also challenged Gerck to prove his claims. “I’ve shared an RSA-2048 public key and a corresponding private key encrypted by this public key. If you can decrypt the private key, you can sign some piece of text with it, which will prove that you are in possession of the private key,” he said in a response to Gerck’s post on LinkedIn. “Can you do it?”

“There is a publication delay, and I do not control that,” Gerck responded.

Counting Down to Q-Day

If Gerck’s claim is true, it is unwelcome news for any government and organization still using RSA to encrypt sensitive data. Security experts say multiple governments have been intercepting sensitive communications to later subject them to so-called “playback attacks,” once they have a technique for decrypting the encrypted data.

Here’s how quantum computers might do that: Generating an RSA private key involves multiplying two different large prime numbers to generate a key that is used to encrypt data. These so-called trapdoor algorithms make encryption easy but decryption difficult.

Using classical computers, which process data sequentially, brute-force cracking a strong key would require an enormous amount of time – perhaps hundreds if not trillions of years. But a big enough quantum computer, because it can use qubits to process data in parallel, could be used to easily crack even large keys generated using algorithms such as RSA in days if not hours.

Powerful quantum computers do not exist today, but experts believe they may become viable in a number of years.

Because of the risk playback attacks pose to civilian and military communications, as well as critical national infrastructure, the U.S. National Security Agency has told organizations involved in maintaining national security systems that they should be planning their transition to the Commercial National Security Algorithm Suite 2.0. This is a set of quantum-resistant algorithms approved for eventual NSS use (see: US Government Picks Quantum-Resistant Encryption Algorithms).

Based on when NSA cryptographers believe quantum computing will pose a threat to public key cryptography, the U.S. government has mandated dates by which it wants to see CNSA 2.0 compliance be in place:

The NSA guidance for custom applications and legacy equipment is to update or replace them by 2033.

Technology giants, including cloud providers, have already begun transitioning to post-quantum cryptography. In August, the Chromium Project adopted a hybrid cryptographic algorithm – X25519Kyber768 – for Chrome and Google Servers. As of Aug. 15, the latest version of Chrome includes a quantum hybrid key agreement mechanism. Amazon Web Services, Cloudflare, IBM and Microsoft are among the cloud providers also researching and updating products for post-quantum cryptography.