We are going to crack the RSA by finding the period of the ciphertext. Let m be the message, c the ciphertext, e the encoding number and N=pq such that
From Period Finding and the RSA post, the period of a ciphertext is defined as the smallest number r such that
First we prepare QBits at the state where is the number of bits of . The number of bits can be computed using the formula:
We also prepare QBits for the output register.
So initially we have the following setup:
The output register will contain the output of the operator:
We now apply the Hadarmard gate to the input register and apply the operator :
The Hadamard gates transform the state into a superposition of all possible values of the period while the operator transforms the output QBits as superposition of all possible values of .
Next we make a measurement of the output QBits. This will give us a number which corresponds to all states whose value of is of the form since
since by definition of a period.
Therefore, after the measurement, the input state is now
where m is the smallest integer such that .
We will then apply the quantum Fourier transform to state . The Quantum Fourier Transform is defined by its action on an arbitrary
Applying the Fourier Transform to the state ,
Now if we make a measurement of this new state, the probability of getting a value of y is the probability amplitude multiplied by it’s complex conjugate:
The factors in underbrace evaluates to 1 when multiplied and we’re left with
Using the formula
we can write the summation in underbrace as
We’d like to know at what value of y the expression above is maximum. We can use the following formula to simplify above summations:
If we let
this reduces the summations to:
Therefore, the probability of getting a specific y is
Here is a plot of the function for m=4:
Notice that the graph attains its maximums when the values of f are integer values, that is when
Since y is an integer value, this means that the value of y must be close to . We can use a theorem in Number theory which states that if is a rational number that approximates a real number x and
we can approximate x using continued fraction expansion of p/q. In fact, if we find a y that is within 1/2 of one of the values, we have
and dividing both sides by , we get
which satisfies the theorem. We can therefore expand via continued fraction expansion and continue until we find a denominator that is less that . We then test whether r could be our period if it satisfies
If it satisfies the above, then r is the period. It’s just a matter of computing , the inverse of modulo r satisfying
Having computed , we can then decrypt the ciphertext using
In our example in period finding, let’s suppose that the quantum computer gave us the following number
We can expand the fraction as a continued fractions as follows:
We can stop until since . So we use the first expansion where and testing it
which confirms that is a period. Using in the equation
and solving for (which is the inverse of e modulo 58) we get
We can now get the original message using
which agrees with our original message.
How lucky do we need to get in order for the state to collapse to one of these y values close to ? Let’s evaluate the probability for
where is the distance of the closest y to . Since , we have
We can approximate the denominator using the small angle approximation of sine:
Since m is the smallest integer such that , then
We can use this to approximate
Since , we can see from the graph below that the line joining (0,0) and , whose equation is is less that the value of the sine function at that interval, that is,
Using this inequality, we can get a lower bound of the probability of getting a specific y value to be
Since there are r of these ‘s, the probability of getting any one of these ‘s is therefore:
which means that there is 40% probability of the state to collapse to a value of y that will give us the correct period.
We have just seen how a quantum computer can be used to crack the RSA. We have exploited the fact that the measurement will give us a value of y that is near with high probability. We then computed for the period using the continued fraction expansion of . With the period computed, it’s becomes straightforward to decrypt the ciphertext.