Breaking RSA - Shor's Algorithm

Modern information security, as it exists in most companies, relies on the assumption that large numbers cannot be factored by a computer. In the not-so-distant future, this assumption will fail. Research and development has shown many times that quantum computers can factor huge numbers on a time scale that will render modern data encryption practically useless.

Let me try and explain in a little more detail why this is so scary.

Let’s say you wanted to break 2048-bit RSA with your home computer to steal someone’s cryptocurrency. To accomplish this with a classical machine could take about a thousand years (if you’re lucky). Especially considering Bitcoin has dropped in value by about 50% in the last two years alone, this is not a cost-effective use of time; a hacker is better off hanging up his/her black hat and getting a desk job. In other words, your data is safe from hackers with access to classical computers alone.

Now let’s assume that quantum computers are available to the malicious agent after your hard-earned Crypto. If your wallet is once again secured with 2048-bit RSA, then it could take a quantum computer running Shor’s Algorithm just a few minutes to break that encryption. (I only say ‘could’ instead of ‘would’ because there is a possibility that Shor’s algorithm doesn’t produce the right answer on the first try, but if that’s the case, we just run Shor’s until we get the right answer. It only takes a few minutes, after all.)

Shor’s is probably the most famous quantum algorithm that exists. It leverages the fact that quantum computers can run on multiple values simultaneously to calculate the factors of a huge number in exponentially less time than any classical algorithm. This insane speedup is what will render current encryption standards obsolete.

In case you’re curious, here’s a very brief rundown of how Shor’s algorithm works. There are many in-depth descriptions of the algorithm online so for a more in-depth guide, I would suggest a quick Google search.

The steps to compute the prime factors of some large number, N, using Shor’s algorithm are as follows:

- Transform the problem to one of finding the period of a modulus function, namely the period of the function f(x) = ax (mod N). This can be done on a classical computer without any quantum components. The steps to transform the problem are (roughly) as follows

First, ‘guess’ some (odd) number a < N. This guess may not work. If the guess is determined to be invalid later in the algorithm, then the algorithm returns to this step to generate another guess.

Second determine the greatest common denominator (GCD) of (a) and (N). This is easily accomplished in polynomial time on a classical computer.

Finally, the function f(x) = ax (mod N)can be used in the next steps to find the prime factors of N

- Put qubits in state of evenly weighted superposition using Hadamard gates

Compute, into the output register, the value of ax (mod N)where a is the guess from earlier and x is controlled by the i’th qubit, taking on the value 2i.

- Find the period, r, of ax (mod N). This can be accomplished by applying the Quantum Fourier Transform (QFT) to the output register and measuring. This will result, with a high probability, in a number, α, which can be used along with N to find the period of ax (mod N). There are classical methods to find the period, r, once a valid α is found.

- Once a (valid) period, r, is obtained, then there is a high probability that at least one solution of GCD(ar/21,N) is a factor of N. This step is best performed on a classical computer with the Euclidean algorithm, a classical method for finding greatest common divisors between integers.

Quantum Thought’s sister company, QuSecure, has developed a quantum-proof blockchain that we are excited to take to market in the near future. Stay tuned for more updates from the quantum world.