Breaking RSA: Shor's Quantum Algorithm
Is it so — with cryptography comes power, with codebreaking comes the unprecedented future of humankind; - admin -
BREAKING RSA - MILLER'S ALGORITHM
RSA is a public-key cryptosystem algorithm, named after its three inventors: Rivest, Shamir, and Adleman. RSA is very widely used in encrypted communication today.
Earlier, in 1973, Clifford Cocks, a British mathematician, described a similar algorithm. With the computing power of that time, the algorithm was deemed infeasible and was never tested. However, the invention was only published in 1997 because it had been classified as top secret.
The RSA algorithm was patented by MIT in the United States in 1983 (Registration No. 4,405,829). The patent expired on September 21, 2000. However, because the algorithm had been published before the patent registration, the protection was almost worthless outside the United States. Moreover, had Clifford Cocks's work been published earlier, the RSA patent could not have been registered.
Victor Saul Miller, an American mathematician at CCR (Communications Research Center) under the Institute for Defense Analyses in Princeton, New Jersey, USA, proposed Miller's algorithm to break RSA by prime factorization.
Miller's algorithm for breaking RSA consists of the following steps:
- Step 1: Choose a random number a < N.
- Step 2: Find GCD(a, N); Euclid's algorithm can be used for this step.
- Step 3: If GCD(a, N) ≠ 1, then p = GCD(a, N) and q = N / p.
- Step 4: Otherwise find the period r of the function f(x) = a^x mod N, i.e., f(x+r) = f(x).
- Step 5: If r is odd, go back to the first step. If r is even: r2 = r/2 is an integer
- Step 6: If a^r2 ≡ −1 (mod N), go back to the first step.
- Step 7: found: p = GCD(a^r2 + 1, N) and q = GCD(a^r2 - 1, N).
p and q are exactly the keys to decrypt the public N
However, step 4 — finding the period r of the function f(x) = a^x mod N — consumes enormous computing resources. The semiprimes in modern RSA encryption usually have 200 decimal digits or more. For such large semiprimes, Miller's algorithm typically needs a huge amount of time to factor — up to thousands of years with the computing power of a Level-1 civilization on the Kardashev scale — while Earth is currently at level 0.75, meaning RSA is still safe.
BREAKING RSA - SHOR'S QUANTUM ALGORITHM
However, when Shor proposed his quantum algorithm, running Miller's algorithm on a quantum computer became possible in a much shorter time, theoretically allowing RSA to be broken at quantum speed. A door opened to a new horizon: applied quantum computing, inspiring new inventors to seek treasures in the land of knowledge, and at the same time triggering post-quantum cryptography inventions — cryptography that resists quantum computing.
Shor's quantum algorithm basically develops from Miller's algorithm for breaking RSA as described above. It focuses on solving Step 4: finding the period r of the function f(x) = a^x mod N, i.e., f(x+r) = f(x).
The main idea is to apply the Quantum Fourier Transform to the function f(x) to find the period r;
We all know — or maybe you don't — that the Fourier transform analyzes signals in the frequency domain, and frequency is the inverse of period; therefore the Quantum Fourier Transform of f(x) immediately reveals the period r;
The Quantum Fourier Transform of f(x) essentially treats f(x) as an m-bit digital signal that can carry N = 2^m different values, transformed in the complex domain by an [n, n] matrix (with n = logN = m*log2); each qubit holds the information of one element; one qubit represents every possible state — instead of the 0:1 of an ordinary bit — and can be physically implemented as the state of an elementary particle with its Schrödinger equation;
Implementing Shor's algorithm in the value domain N requires about O((n^2)(log n)(log log n)) qubits
That is, to implement:
- breaking 512-bit RSA needs 17,672 qubits,
- breaking 1024-bit RSA needs 93,656 qubits,
- breaking 4096-bit RSA needs 2,303,108 qubits,
Sycamore
On October 23, 2019, Google CEO Sundar Pichai personally wrote an article introducing the quantum computer for the future. He affirmed that Sycamore took only 200 seconds to solve a problem so hard that today's most powerful supercomputer would need thousands of years. Sycamore became the first quantum computer to achieve "quantum supremacy" and has 53 qubits (designed with 54 qubits, but 1 qubit was faulty).
if we take the unit as one 53-qubit Sycamore machine (hereafter called S53Q), then to implement:
- breaking 512-bit RSA needs 333 S53Q machines,
- breaking 1024-bit RSA needs 1,767 S53Q machines,
- breaking 4096-bit RSA needs 43,455 S53Q machines,
If you can estimate the cost of one S53Q machine, then you know: it would take 43,455 such machines to deliberately decrypt a single email you just sent, because RSA now generally uses 4096 bits. Google has not disclosed Sycamore 53Q's development cost, but the admin estimates each qubit in that machine costs about 100 million dollars, not to mention unquantifiable value 
And that is all it takes: the standard algorithm already exists, S53Q has demonstrated feasibility — just pour in enough resources and voilà, a bright future emerges instead of spending billions of years breaking RSA with impossible old-computing approaches.
The above calculations are rough estimates for implementing Shor's algorithm; in the future, even more efficient algorithms may be invented. Nevertheless, with the theoretical basis and the achievement of the first quantum computer, we have every right to be excited about a future of quantum computing with unprecedented power — a new era of humankind.
For more information about RSA, you can see the wiki: https://vi.wikipedia.org/wiki/RSA_(mã_hóa)
For more information about Shor's algorithm, you can see the wiki: https://vi.wikipedia.org/wiki/Thuật_toán_Shor or consult specialized documents; to deeply understand Shor's algorithm, some basic knowledge of quantum mechanics is needed; if supported and with time, the admin will write another article on that topic.
[See more: The Cryptography Series]
Part 1: Breaking Enigma - Alan Turing
The video below introduces Shor's algorithm for breaking RSA in more detail, by PBS in the Infinite Series: