Quantum Computer Cracks 22-bit RSA Encryption

Researchers at Shanghai University in China have used a quantum computer to factor a 22-bit integer in the RSA encryption algorithm. This was reported by Earth citing the study.

“Using the [device] D-Wave Advantage, we successfully factored a 22-bit RSA integer, demonstrating the potential of quantum machines for solving cryptographic problems,” the authors write.

Previously, the algorithm resisted attempts to crack it on the same class of equipment.

Although 22-bit keys are not secure by modern standards and can be factored on classical systems, this is currently the largest number obtained using quantum annealing.

Most modern security systems use 2048-bit encryption, and the largest key cracked by traditional methods is only 829 bits (RSA-250). It was decrypted after several weeks of computations on a supercomputer.

For the factorization of the 22-bit RSA, scientists used the same method as in the successful decryption of the Present, Gift-64, and Rectangle algorithms in October 2024. They described the breakthrough as “the first instance where a real quantum computer poses a significant threat to several full-scale structured algorithms.”

Methodology

The 22-bit key is trivially small compared to industrial-level RSA, but the test is significant because the approach scales beyond past research, which was limited to 19 bits and required more qubits per variable.

According to the article, reducing the coefficients of local field and coupling in the Ising model decreases noise levels, allowing annealing to more frequently achieve correct coefficients and pointing the way to larger keys.

Universal gate-based quantum machines operate using Shor’s algorithm, which theoretically can “break” RSA by finding the period of modular exponentiation in polynomial time. However, such devices struggle with error correction and require a large number of qubits.

To optimize the process, Chinese scientists applied annealing instead of Shor’s method. Thus, they changed the type of task for the computer from finding the period of a number to finding the value itself. This strategy allows them to bypass current qubit number limitations, but it comes at the cost of exponential scaling, hence only a 22-bit modulus was achieved.

The Threat is Already Here

RSA with a large key remains secure, but the research indicates that advancements in hardware and computation optimization already pose a threat.

Most enterprises, including banks and other encryption-dependent structures, have yet to update their cryptographic resources, Earth journalists write. Moreover, many are unaware of which algorithms their systems depend on.

Organizations that have stored confidential data, medical records, financial files, and diplomatic cables for decades may be most affected if they wait for the emergence of a full-scale quantum computer.

Although the cracking of the 22-bit RSA was based on extensive pre- and post-processing, and annealing required many runs to find the correct values, cryptographers recommend that companies and institutions begin developing plans to transition to new algorithms.

Furthermore, “intermediate” breaches of encryption systems may already pose a significant security threat. Therefore, it is recommended to apply combined data protection methods.

Back in April, Tether predicted the hacking and return of bitcoins associated with Satoshi Nakamoto.