Breaking RSA Encryption using Shor’s Algorithm!

Introduction

RSA (Rivest–Shamir–Adleman) encryption has been long in use now and has a nimiety of applications, even as far as being used by government agencies.

Now, RSA encryption makes use of the fact that some problems are elementary to solve one way but not so trivial to solve the other way. For example, if I ask you, what is the prime factor of 701,111 it is not so trivial to answer even with a calculator, but if I ask you the result of 907 x 773 it is pretty trivial to calculate it to 701,111. RSA encryption uses the same technique except the numbers are a lot larger, just the key is 647 digits long[1]. RSA relies on factoring being impossible for large enough integers.

The best classical algorithm in the market would take super polynomial time to factorize the product of two primes, but quantum computers can do it in a polynomial time with the help of techniques such as Quantum Fourier Transform and Modular Exponentiation.

So, let us look at how we can do the same.

Here we will be using Shor’s algorithm for factoring in polynomial time. Quick trivia: Shor’s algorithm was created by Shor after he was said that his Quantum Phase Estimation algorithm has no application. Now we will be turning our factoring problem into a period finding problem in polynomial time. Now, all we need to show is if we can compute the period of ax mod N efficiently, we can factor efficiently.

Period Finding

The first thing to note is that the function f(x)= ax mod N is periodic where a and N are positive integers, a is less than N, and no common factors exist. Since at x=0, f(x)=1, let r be the period such that ar mod N=1.

Let us confirm this by plotting the graph with a and N to be 3 and 35, respectively.

Now, to effectively find this period r we are going to implement Quantum Phase Estimation (QPE) on the unitary operator.

U |y = |ay mod N

Let us start with state 1, and a and N equal to 3 and 35, respectively. So,

U|1⟩=|3⟩

U2|1⟩=|9⟩

U3|1⟩=|27⟩

.

.

.

U(r−1) |1⟩=|12⟩

Ur|1⟩=|1⟩

So, a superposition of all such states in this cycle |u0 ⟩ would be the eigenstate of U [2]

On calculating the eigenvalue of u0 it comes out to be 1 which is a trivial solution. Now what would be interesting is that the phase changes with the basis state. Specifically, let us look at the case where the kth state is proportional to k.

This eigenvalue interests us as it contains r which is to be calculated. We can generalize u1 as us where

We now have unique eigenstates for s where 0 < s ≤ r-1.

Now, very conveniently, on the summation of all these eigenstates, the basis states cancel out leaving only |1⟩ behind.

So, all we must do is use the basis state |1⟩, as it is the superposition of all these eigenstates, and find the QPE on U using the state |1⟩. The phase comes out to be:

Φ=s/r

Where s is a random integer between 0 and r-1. We use continued fractions on Φ to find r [3]. Below is a circuit diagram visualization.

Modular Exponentiation [4]

Creating U2^j gates by repeating U gates makes no sense as it will impose stress on the algorithm and hence, we will not be able to compute in polynomial time.

So, we need a way to create an operator

such that it grows polynomially with j. Here we can implement a classical algorithm called repeated squaring to calculate exponential. Since our exponents are of the form 2j, the algorithm becomes very simple and can be achieved in polynomial time, ultimately rendering the problem of repetition of U gates to create U2^j abscond. Implementation of the same in qiskit is attached below.

Factoring

Now, onto our ulterior goal of factoring, we first check if the number is even or of the form ab before using Shor’s algorithm, but we know that we are dealing with large prime numbers, so let’s jump onto that case.

Let us choose 21, whose factors are 3 and 7.

First step is to choose our a which is a random no. between 1 and 21.

Calculating phase s/r where:

And s is random integer between 0 and r-1.

If we have r, we might be able to find a factor of N as

Now we want our r even so that we can split it into the form

If our r is not even, we select a different a. This is done as it becomes highly probable that the Highest Common Factor (HCF or GCD) of either ar/2-1 and N or ar/2+1 and N is a factor of N.

We continue to check until nontrivial solution to the problem is found.

Implementation

Let us Briefly discuss the implementation on IBM’s Qiskit.

So, working with 21, we need a 5-bit system to represent 21. Therefore, we will be using 10 qubits to solve this problem.

First 5 qubits, i.e. the first register will be initialized to |0⟩⊗n which we will be measuring in the end. The last qubit is appended with a Pauli-X gate to create an ancilla register in state |1⟩. Now our objective is to generalize Unitary so that we can bring it into the form |ay mod N⟩. To achieve this, we will be using Swap and X gates to create the desired remainder. For example, if we are using 13, 13 mod 21 is 13, so to create 13, we will swap the position of [5,6], [6,7],[7,8], and [8,9] followed by not gates in q[6]-q[9]. This would be followed by the .control() function to make the gates into the controlled form using the q[j] qubit and giving us the final U gate.

To create U gates of the form U2^j we will be repeating the U gates 2j times and be using modular exponentiation to bring this to a polynomial-time algorithm. Then using the inbuilt QFT function in Qiskit, we will apply the inverse Fourier Transform and measure the first 5 qubits to determine the phase. Once the phase is determined, all that is left is to make use of classical techniques as mentioned above to calculate the final factors.

Conclusion

And this is how we factor a number into its prime constituents. Now we can intercept a public key, factorize it, and be able to decode the message encrypted on it. This possibility of breaking through the most famous cryptography has motivated people to come up with post-quantum cryptography and even make use of quantum algorithms to encrypt messages. Attached below is a collab notebook link which you can run on the cloud to try and play around with Qiskit implementation of the Shor’s algorithm. So, go out, experiment, and keep on learning. Curious to learn more? Then go ahead and click on the ‘Yes I am curious‘ button.

Link to Collab Notebook: https://github.com/profdv004/Shor-s-Algorithm.git

References

[1] Josh Lake, “What is RSA encryption and how does it work?” (Comparitech, 2018)

[2] Qiskit Textbook, Shor’s Algorithm

[3] M. Nielsen and I. Chuang, “Quantum Computation and Quantum Information, Cambridge Series on Information and the Natural Sciences”(Cambridge University Press, Cambridge, 2000). (Page 633)

[4] T. Zhou, “Study on Several Fast Algorithm of Modular Exponentiation in RSA,” 2011 (International Conference on Network Computing and Information Security, Guilin, 2011), pp. 374-377

You must be logged in to post a comment.