Fujitsu experts have conducted a study that may serve as a response to the threat of cracking RSA keys using quantum computers. According to the company, this danger is extremely exaggerated. Running the algorithm on a 39-qubit simulator showed that many years would pass before the real threat to RSA encryption appeared.

The Fujitsu team was working on a version of Shor's algorithm, which allows quantum computing to factor large numbers into prime factors. As part of the experiment, it was possible to factorize 96 integers of the RSA type (the product of two different odd primes) from N=15 to N=511, and confirm that a general-purpose program can generate correct quantum circuits.

Then the experts used the program to generate a quantum circuit simulator, with the help of which they decomposed several RSA keys from 10 to 25 bits into prime factors and estimated the required quantum circuit resources to crack a 2048-bit key. According to calculations, to factorize the RSA-2048 number, approximately 10 thousand qubits and 2.25 trillion gates associated with them (logical elements) will be required. At the same time, a fault-tolerant quantum computer with such an architecture will have to work for 104 days.

Based on the calculations, the Fujitsu team concluded that many more years will pass before RSA keys of cryptographically significant length are cracked using Shor's algorithms, since the emergence of a system with 10 thousand qubits or classical computers to simulate it is a matter of a rather distant future.

The Fujitsu study is a response to a recent paper by Chinese scientists who claim it is possible to crack the RSA-2048 key with a quantum system based on just 372 qubits. The Chinese used a real quantum computer based on 10 superconducting qubits to prove the concept. They claim to have tested an algorithm that speeds up factorization by a factor. Whether Fujitsu specialists used such optimization or not is not reported. The Fujitsu team was working on an ARM-based Fugaku supercomputer, which may have limited its specialists in choosing algorithms.

Later this week, a more detailed report on the work is expected to be presented at the Symposium on Cryptography and Information Security 2023 conference. Perhaps we will find out more details.