RSA key: can quantum computers break the algorithm?
Published on Jan 24, 2020

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 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.

Written by

Jan Anisimowicz

Go To Expert Spotlight Page

This Article Tags

All Tags

Our Customers Success Stories

How we boosted a COVID-19 vaccine production by digitally enhancing manufacturing operations

In response to an unprecedented global pandemic, our client – one of the pharma industry leaders- set out to develop, test, mass produce and organize the global distribution of a COVID-19 vaccine.

How to manage national resources to fight COVID-19 in the cloud?

Availability of ICUs is one of the key factors to keep the death toll as low as possible. ICU-M has been one of the reasons Germany has been managing the pandemic relatively well, keeping the number of deaths per 1M population at the low end compared with other EU states.

Bringing a global pharma company out of the dark via a Single Source of Truth (SSOT)

To get the full picture of the global market situation, companies use various sources of data. But to effectively control and steer business activity at all levels on global scale they need a centralized and trustworthy data source.

How to restore effective sales in animal pharma ensuring high quality and reliability of data

Our solutions cover all aspects of customer and sales transactions processing for life science industry companies carrying out their sales activity on many markets in cooperation with wholesalers, distributors and retailers.

Can proper data management help restart a shutdown pharma production plant?

Introducing rigorous quality assurance and management tools into data integration to enable the fastest possible resumption of a production plant’s functioning shut down due to issues with ERP system implementation.

How we helped Boehringer-Ingelheim stabilize their data ecosystem

Data governance, data management and data quality are the basis for the effective integration of IT systems, especially when the organization implements new solutions.

How we made the slow and inaccurate CEESA reporting in an animal pharma company much faster and much more accurate

Abundance of data can have enormous potential for business, but it can also be a source of problems. With large-scale operations – and this is where international animal pharma players operate – automation and advanced analytical methods become essential to building value from data insights.

Improving the workflow of Randstadt’s HR with an employee self-service solution

Low-code is the perfect tool for creating scalable solutions that ensure employee empowerment and self-service for simple activities and tasks. This can significantly relieve HR departments of the overload of administrative matters.

See how we used low-code to enable our pharma client to stay transparent and compliant with European legislation

End-to-end, flexible low-code based solution integrated with all the peripheral systems in company to meet rigorous transparency regulations for the pharma industry.

Replacing Excel sheets with AdaptiveGRC modules to improve internal audit

Emails and Excel sheets are passé. Digital audit needs improved flow of information, managing audit recommendations and enforcing their implementation clearly synchronized on a multi-level structure.

{
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 a large number into two prime numbers (hundreds of digits) is counted in billions of years.

Latest Articles

Let`s Talk About a Solution

Questions?We’re here to answer them.

Our engineers, top specialists, and consultants will help you discover solutions tailored to your business. From simple support to complex digital transformation operations – we help you do more.





    We will only use the collected data for the following purposes:

    The Controller of your personal data is C&F S.A. with its headquarters in Warsaw, ul. Domaniewska 50, 02-672 Warszawa, Poland. We ask for your consent to the processing of your personal data collected using the form above. We may also collect other data as specified in our Privacy Policy.