A group of researchers from several Chinese scientific centers and universities proposed a new way to optimize the factorization process of RSA-key parameters on quantum computers. According to the researchers, the method they developed makes it possible to get by with a quantum computer with 372 qubits to crack the RSA-2048 keys. In comparison, the IBM Osprey, the most powerful quantum processor currently built, contains 433 qubits, and by 2026 IBM plans to build a Kookaburra system with 4,000 qubits. However, the method is still only theoretical, has not been tested in practice and causes skepticism among some cryptographers.
RSA encryption is based on the operation of exponentiation modulo a large number. The public key contains the modulus and degree. The module is formed on the basis of two random prime numbers, which are known only to the owner of the private key. Quantum computers make it possible to effectively solve the problem of decomposing a number into prime factors, which can be used to synthesize a private key based on a public one.
Until now, it was believed that, given the current development of quantum computers, RSA keys with a size of 2048 bits will not be able to be cracked for a long time, since when using the classical Shor algorithm, a quantum computer with millions of qubits is required to factorize a 2048-bit RSA key. The method proposed by Chinese researchers casts doubt on this assumption and, if confirmed, allows cracking RSA-2048 keys not on systems of the distant future, but on already existing quantum computers.
The method is based on the Schnorr fast factorization algorithm proposed in 2021, which makes it possible to achieve a drastic reduction in the number of operations when selecting on conventional computers. However, in practice, the algorithm turned out to be of little use for cracking real keys, since it worked only for RSA keys with small modulus values (an integer that needs to be decomposed into prime numbers). The algorithm turned out to be unsuitable for factorization of large numbers. Chinese researchers claim that with the help of quantum methods, they were able to bypass the limitation of the application of the Schnorr algorithm.
The skepticism of some cryptographers is due to the fact that an article by Chinese researchers demonstrates the application of their method only with small numbers, approximately the same order for which the Schnorr algorithm works. Despite claims that the size limit has been overcome, evidence and details have yet to be provided. In practice, the method is shown to factorize 48-bit integers using a 10-qubit quantum computer.
The assumption that 372 physical qubits will be enough to factorize an RSA-2048 key is theoretical, so there is a good chance that the quantum method based on the Schnorr algorithm has the same scaling problems and will not work when factoring large numbers. If the problem with scaling is really solved, then the security of cryptoalgorithms based on the complexity of factoring large prime numbers will be undermined not in the long term, as expected, but already at the present time.