Could RSA-2048 Be Cracked By 2025?
Could RSA-2048 Be Cracked By 2025?
One highlight for me of 2022 was the publishing of the Post Quantum Cryptography (PQC) standards by NIST. These were Kyber for Key Exchange and Public Key Encryption, and Dilithium for Digital Signatures. Both of these methods use lattice cryptography, and which is robust against quantum computer attacks. Unfortunately, all of our existing public key methods — RSA, ECC and discrete logs — are not robust against a quantum computer attack, and must be replaced, soon.
We must thus now look at a migration away from our existing methods towards quantum robust methods. What is unknown is the time scale for this migration. But, the US is starting to move on this and asking public sector agencies to identify the places where traditional public key encryption methods are used and to look towards a migration strategy.
But, now a paper has just been published that perhaps speeds up the migration process [here][1]:
In the paper, it is quoted that:
We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm.
The worrying part of this statement is that there are companies that are creating quantum computers that are likely to release 1,000 qubit+ processors by 2025. Previously, it was thought that RSA-2048 would need millions of physical qubits to crack it.
The paper focuses on 2K RSA cracking, but another risk would be if ECC was crackable, as this would mean that our key exchange methods (with ECDH) and digital wallets for cryptocurrency could be cracked. Obviously, the word “challenge” is a little vague, and there is no real benchmark defined about how costly it would be for a quantum computer to actually crack RSA-2048.
There are, though, some doubts about the paper, as the method is not based on Shor’s method [3], but on one defined by Peter Schnorr [1] (and which was subsequently withdrawn):
Also, sublinear does not relate to sublinear time, but to the number of Qubit circuits. No practical evaluation of the time it would take to crack the modulus is given in the paper.
Cracking with lattices
In RSA, we create a modulus (N) by multiplying two random prime numbers (p and q). If we can factorize this modulus into p and q, we easily break RSA. One of the most popular methods for factorizing a modulus is using lattice methods. This includes the LLL method and which was created by AK Lenstra, HW Lenstra, Jr., and L Lovasz in 1982. If you want to see it in operation, try here:
https://asecuritysite.com/ecc/ecd
Conclusions
If RSA-2048 were to be cracked, virtually all of the Internet would be untrustworthy. Currently, most of the digital certificates used on the Internet have 2,048-bit RSA public keys, so these could be compromised if broken.
But, there are doubts about the methodology of the paper, especially since it is based on a paper that was recently withdrawn.
In conclusion, though, we need to start our migration, soon (if not now)!
References
[1] Yan, B., Tan, Z., Wei, S., Jiang, H., Wang, W., Wang, H., … & Long, G. L. (2022). Factoring integers with sublinear resources on a superconducting quantum processor. arXiv preprint arXiv:2212.12372.
[2] Schnorr, C. P. (2021). Fast factoring integers by SVP algorithms, corrected. Cryptology ePrint Archive.
[3] Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124–134). IEEE.