RSA key: can quantum computers break the algorithm?

The RSA key is currently one of the most popular asymmetric cryptographic algorithms with a public key used to securely exchange information on the Internet. The most important feature of this key is providing encryption security based on the difficulty of factoring large complex numbers.

The use of an asymmetric pair of a public and private key is very common, as it is simple to generate. In addition, it is a very safe algorithm, because the decomposition of a very large number n to obtain p and q, requires enormous computing power.

As I was writing about the potential of quantum computing and the current stage of development of this tech in my recent Medium post, I asked myself many questions about the superpowers that quantum computers would bring to the table.

Take this:

Can quantum computers change our perception of the security of encrypted information transfer on the Internet? In other words: can one break the RSA key using a quantum computer?

“Hold my beer”, one might say, knowing that quantum computers are actually even closer than around the corner.
“Hold your horses”, is my answer, because even though close, they are not as close as we would like them to be.

Let’s find out

(And be warned — some math’s ahead! However, don’t worry — these are simple examples to illustrate RSA concept (hands-on approach)).
Modern computers are very good at multiplying virtually any numbers. However, if we have a very large number and want to break it down into the product of two prime numbers — this becomes a very complicated and time-consuming task. With commonly used 2048-bit keys, the time it takes to break such a large number into two prime numbers (hundreds of digits) is counted in billions of years.

Here’s the math, step by step:

Just a sample of the calculation procedure required (on low numbers)

And here’s an example of an RSA-768 key that was broken in 2009:

RSA-768 = n-number from step 3: 123018668453011775513049495 838496272077285356959533479 21973224521517264005 072636575187452021997864693 899564749427740638459251925 57326303453731548268 507917026122142913461670429 214311602221240479274737794 08066535141959745985 6902143413

RSA-768= n-number, as the product of two primes: 334780716989568987860441698 482126908177047949837137685 689124313889828837938780022 876147116525317430877378144 67999489 (p) * 3674604366679959042824463 379962795263227915816434308 764267603228381573966651127 923337341714339681027009279 8736308917 (q)

25 years of calculations

Let’s try to find the key using a quantum computer. We know that the computer’s power increase is exponential. Adding each qubit doubles performance. In addition, the quantum computer performs all calculations in parallel.

According to researchers’ estimates, a 2048-bit RSA key can be cracked using a quantum computer in 25 years.

The number of qubits needed to do this in 8 hours is … about 20 million (including additional qubits for superposition noise corrections — see below). Currently, the largest quantum computers operate (and that with problems) on 70 (yes, only seventy) qubits. Therefore, it is clear that the current level of technology is still nowhere near RSA-breaking point.

The noise

A quantum computer’s power doubles after adding each qubit. In theory, this is true, but in practice the matter is more complex. Quantum computers require for their operation an environment that will not generate interference. A qubit stays in superposition until it is measured. If a fault occurs, an involuntary measurement may follow. Such a random measurement will introduce noise into any measurements performed. To limit this level of erroneous readings and interference, quantum computers are cooled to around absolute zero, and very low pressure is maintained.
In addition, programming a quantum computer with microwave-length waves or light beams (i.e., setting the appropriate initial parameters) is not only problematic, but also time consuming. Despite the use of such sophisticated measures, maintaining qubit stability for a long time is not possible. “Coherence time” is the time of a quantum state’s stability, so that it can be read unambiguously. Current values ​​of coherence time are already approaching the millisecond level. This is a significant improvement, because even a decade ago coherence time was measured in nanoseconds.
As if that was not enough, to obtain reliable results, individual tests must be carried out many times, so that the results can be given to statistical treatment. With the above in mind, the quantum computer’s power lies not only in the number of qubits, but also in its interference resistance. If there are a lot of disturbances, many more tests must be performed to obtain reliable results.
Therefore, it is also important to limit the level of interference. Only the optimization of both dimensions can take processing to a new level.

The turning point: still far away

Quantum computers will be creeping into our lives in the coming years. The technology is at its initial stage, and we can currently talk about their potential in the future rather than about current opportunities. However, keep in mind the words of Raymond Kurzweil, one of the currently most respected artificial intelligence and technological development gurus. He is an active promoter of the idea that human development is also based on exponential technological growth (we invent something, then use this invention to build another innovation, which will be used to accelerate development, etc.)
In one of his books, the hypothesis was put forward that humanity will experience more technological changes in 50 years (from 2000 to 2050) than in the previous 14,000 years of human history. In his opinion, we are heading towards the so-called technological singularity, a hypothetical point in the future development of our civilization, at which technological progress will become so rapid that all human predictions will become obsolete.

The turning point in this area would be the creation of an artificial intelligence which is intellectually superior to human intelligence. Such an artificial intelligence could develop even more efficient AIs, triggering an avalanche change in technology. One of the foundations for this development is the progress in the coming new generations of quantum computers, on which the new generation of AIs can be based.
However, as long as we don’t arrive at the technological singularity, it can be said with high probability that in the next 20 years our commonly used asymmetric cryptographic keys will remain secure.

If any readers are interested in directly programming a quantum computer, I recommend using the website provided by IBM: https://quantum-computing.ibm.com. There, free of charge, you can program one of their several-qubit quantum computers. This can be done by writing a program in Python, or — much more conveniently, at least at the beginning — using well-explained block diagrams.