Researchers report running a protocol to break RSA – what does this mean for information security on the Internet?
Noa Feldman, Davidson Institute website, the educational arm of the Weizmann Institute of Science
The quantum computing revolution is advancing at a cautious but promising pace. New companies are entering the field and budgets are being directed to developing the technology. Whenever this technology is mentioned, one of the significant potential uses of the quantum computer is always mentioned – cracking codes, and in particular RSA encryption, which is used to protect a variety of everyday online activities such as email correspondence, banking communications, and even sending classified information over military or business networks.
recently Scientists from China announced That they have managed to create and run the protocol needed to break RSA ciphers. This progress from the initial development stage to a working and usable quantum computer should be of great concern to anyone who values their privacy, relies on banking systems, or trusts the encrypted military communications necessary to protect their security – that is, all of us. Do we really have good reason to worry?
A cipher that is very difficult to break
RSA encryption, named after its developers, Ron Rivest, Adi Shamir, and Leonard Edelman, is based on the multiplication of two very large prime numbers. It is easy to multiply two prime numbers, but it is difficult to reverse the operation, that is, to decompose the result into its two prime factors. How difficult is it? The number of operations required to decompose a number into prime factors increases at an increasing rate (exponential rate) the higher the number. If the numbers are very large, the amount of calculations required by a classical (regular) computer to decompose the number into its factors will take an unreasonable amount of time. Therefore, we can say that the product of the two numbers hides the prime numbers, and they can be used as a virtual key to encrypt the information. A full explanation of the encryption mechanism We have already given in the past.For our purposes, it is sufficient to understand that in order to break the encryption, a very large number must be decomposed into its prime factors.
To perform such a decomposition, one can exploit a simple mathematical phenomenon that exists when multiplying numbers – the ability Identify periodicity in multiplication PDF file and extract the factors from it. But since it's a huge number, the task of finding the cycle in a number is also too complicated for a regular computer.
A periodic function. In red: the cycle. On a regular computer, we would have to sample the function over a wide enough range to detect a cycle. This process is difficult and time-consuming, and cannot be relied upon to break the encryption | Diagram: Noa Feldman
This is where the advantage of a quantum computer comes in. The basic building blocks of quantum computers have quantum properties. A key quantum property is that the physical state of the components behaves like a wave or a collection of waves. Because of this behavior, which is based on periodic waves, quantum computers are sensitive to periodicity. In fact, they are expected to excel at a mathematical operation called Fourier decomposition, which is used, among other things, to process wave signals and find their periodicity.
How good is a quantum computer expected to be at detecting periodicity? Instead of an exponential amount of computations relative to the size of the factored number, a quantum computer could be satisfied with a much more moderate growth rate called "polynomial time," or more precisely, this number to the power of three. Due to the difference in the rate of growth of the required computation time, a quantum computer is expected to be much faster for large numbers.
The quantum computer is expected to be fast and efficient enough to factor numbers so that the operation will no longer be difficult. And if it is not very difficult, we will no longer be able to rely on it for encryption. Anyone who can factor large numbers will gain access to a huge amount of private or secret information that has been encrypted to prevent it from falling into the wrong hands.
The rate of increase in the required computation time. In red: the order of magnitude of the classical computation time; in green: the quantum computation time, already at 60 there is a significant advantage for the quantum computer, and in encryption these are much larger numbers | Diagram: Noa Feldman
cause for concern
Now we can return to the question we asked at the beginning: is there any reason to worry? First, let's look at the current state of quantum computing technology. In order to break encryption, a quantum computer needs to be large enough, meaning it has enough basic information units to hold large enough numbers in its working memory. In this case, "large enough" numbers are numbers of the order of magnitude of the number we want to decrypt. A typical number used in RSA encryption today contains 4,096 bits – the basic information units in regular computers. This means that a quantum computer would need to be made up of several thousand qubits (quantum bits) – the basic quantum information units.
The quantum computers currently being developed by the largest and richest labs are still far from that goal. Google’s Quantum Labs has a basic computer with 105 qubits; IBM has a little over a thousand. The Chinese scientists claimed to have successfully run a code-breaking protocol on a computer from a company called D-Wave, which consists of XNUMX qubits. Note that a higher number of qubits does not necessarily indicate a more advanced computer, as each company focuses on different functions and other improvements to the technology.
And that's not all – the algorithm will also need a mechanism to protect against errors, that is, from noise and mistakes. This requires a combination of powerful hardware, which makes few errors, with a strong error-correction protocol. In recent months, it seems that Google's quantum labs have also made significant progress In the field of hardware and also In the field of software This is a significant step, but it is still in the development stages, and is not currently used on existing computers.
In addition, error correction also requires a larger number of qubits to back up the information in case it is lost due to an error. Common correction protocols require the use of nine or more qubits than the minimum necessary, which only widens the gap between what is available and what is desired.
So, currently, it is impossible to break encryption using a quantum computer. However, it is difficult to predict what will happen in the coming years. Experts estimate that it will take about another ten years to build quantum computers that are large and stable enough to break encryption. This is just an educated guess, of course, and experts are very divided. Some claim that within a few years, quantum computing technology will achieve this goal, while others believe that it will never happen. Meanwhile, in other places, new encryption methods are already being developed that a quantum computer will not be able to break. The most promising ones use a quantum computer in the encryption process to create stronger encryption.
Of course, cracking codes is not the only use that is expected for quantum computers. Long before the technology is ripe for cracking codes, it will already be possible to use quantum computers to research advanced materials and innovative drugs. How long will this take? It is difficult to say. As in many fields, technological development does not progress in a straight line, and it is difficult to determine when the moment will come when decades of development will culminate in a stable and useful product. The many achievements recorded in the past year give hope that the pace of development is indeed accelerating, and in the coming years we will be able to begin to reap the fruits of quantum computing.
More of the topic in Hayadan:
