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:
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.
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.