They propose a method to decrypt RSA-2048 keys
A group of researchers from various scientific centers and universities Chinese I proposedn a new way of optimizingr the RSA key parameter factorization process in quantum computers.
According to investigators, the method they developed allows the use of a quantum computer with 372 qubits to decrypt RSA-2048 keys. By 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 4000 qubits.
It is worth mentioning that the method is still only theoretical, it has not been tested in practice and generates skepticism among some cryptographers.
RSA encryption is based on the exponentiation operation modulo a large number. The public key contains the modulus and the degree. The module is formed based on two random prime numbers that only the owner of the private key knows. Quantum computers make it possible to efficiently solve the problem of decomposing a number into prime factors, which can be used to synthesize a private key from a public one.
Hitherto it was believed that, given the current development of quantum computers, RSA keys with a size of 2048 bits cannot be cracked for a long time, since using the classical Shor algorithm, a quantum computer with millions of qubits requires a lot of time to factor a 2048-bit RSA key.
The method proposed by Chinese researchers casts doubt on this assumption. and, if confirmed, it makes it possible to crack RSA-2048 keys not in systems of the distant future, but in already existing quantum computers.
The method is based on the Schnorr fast factorization algorithm. proposed in 2021, which enables 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 only worked for RSA keys with small modulo values (an integer that must be decomposed into prime numbers). The algorithm was found to be inadequate for factoring large numbers. Chinese researchers claim that with the help of quantum methods they were able to circumvent the limitation of Schnorr's algorithm.
Skepticism from some cryptographers is due to the fact that the article by the Chinese researchers demonstrates applying your method only to small numbers, roughly the same order that Schnorr's algorithm works for. Despite claims that the size limit has been exceeded, no proof or details have yet been provided. In practice, the method is shown to factor 48-bit integers using a 10-qubit quantum computer.
Shor's algorithm has seriously challenged the security of information based on public key cryptosystems. However, to break the widely used RSA-2048 scheme requires millions of physical qubits, which is well beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining classical lattice reduction with a quantum fuzzy optimization algorithm (QAOA).
The number of qubits required is O(logN/loglogN), which is sublinear in the integer bit length N, making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers of up to 48 bits with 10 superconducting qubits, the largest integer factored in a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is needed to challenge RSA-2048 using our algorithm. Our study shows great promise to accelerate the application of today's noisy quantum computers and paves the way for factoring large integers of realistic cryptographic significance.
It is mentioned that the assumption that 372 physical qubits will be enough to factor an RSA-2048 key is theoretical, so it is very likely that the quantum method based on Schnorr's algorithm has the same scaling problems and does not work when factoring numbers. big.
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 today.
Finally, if you are interested in being able to know more about it, you can consult the details in the following link.