October 2017 – Spherical Cows In A Vacuum

RSA Encryption and Quantum Computing

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

$c=m^e \mod N$

From Period Finding and the RSA post, the period of a ciphertext is defined as the smallest number r such that

$c^r \equiv \mod N$

First we prepare $n=2n_0$ QBits at the state $\left|0\right\rangle$ where $n_0$ is the number of bits of $N=pq$ . The number of bits can be computed using the formula:

$\lceil \log_2(N) \rceil$

We also prepare $n_0$ QBits for the output register.

So initially we have the following setup:

$\underbrace{\left|00\ldots 0\right\rangle}_{n\text{ times}} \otimes \underbrace{\left|00\ldots0\right\rangle}_{n_0\text{ times}}$

The output register will contain the output of the operator:

$\mathbf{U}_f \left|x\right\rangle\left|0\right\rangle = \left|x\right\rangle\left|f(x)\right\rangle$

where

$f(x) = c^x \mod N$

We now apply the Hadarmard gate to the input register and apply the operator $\mathbf{U}_f$ :

$\displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} \left|x\right\rangle\left|f(x)\right\rangle$

The Hadamard gates transform the state into a superposition of all possible values of the period while the operator $\mathbf{U}_f$ transforms the output QBits as superposition of all possible values of $c^x\mod N$ .

Next we make a measurement of the output QBits. This will give us a number $f_0$ which corresponds to all states whose value of $\left|x\right\rangle$ is of the form $x_0+kr$ since

$\begin{array}{rl} c^{x_0+kr} & \equiv c^{x_0}c^{kr} \mod N \\ & \equiv c^{x_0}(c^{r})^k \mod N \\ & \equiv c^{x_0} \mod N \end{array}$

since $(c^{r})^k \equiv 1 \mod N$ by definition of a period.

Therefore, after the measurement, the input state is now

$\displaystyle \left|\Psi\right\rangle = \frac{1}{\sqrt{m}} \sum_{k=0}^{m-1} \left|x_0 + kr\right\rangle$

where m is the smallest integer such that $x_0 + mr \ge 2^{n}$ .

We will then apply the quantum Fourier transform to state $\left|\Psi\right\rangle$ . The Quantum Fourier Transform is defined by its action on an arbitrary $\left|x\right\rangle$

$\displaystyle \mathbf{U}_{\mathbf{FT}}\left|x\right\rangle = \frac{1}{2^{n/2}} \sum_{y=0}^{2^n-1} e^{2\pi ixy/2^n}\left|y\right\rangle$

Applying the Fourier Transform to the state $\left|\Psi\right\rangle$ ,

$\begin{array}{rl} \displaystyle \mathbf{U}_{\mathbf{FT}} \frac{1}{\sqrt{m}} \sum_{k=0}^{m-1}\left|x_0 + kr\right\rangle &= \displaystyle \frac{1}{\sqrt{m}} \sum_{k=0}^{m-1}\mathbf{U}_{\mathbf{FT}} \left|x_0 + kr\right\rangle\\ &= \displaystyle \frac{1}{\sqrt{m}} \sum_{k=0}^{m-1} \frac{1}{2^{n/2}} \sum_{y=0}^{2^n-1} e^{2\pi i(x_0+kr)y/2^n}\left|y\right\rangle\\ &= \displaystyle \frac{1}{\sqrt{m}} \sum_{k=0}^{m-1} \frac{1}{2^{n/2}} \sum_{y=0}^{2^n-1} e^{2\pi ix_0y/2^n}e^{2\pi ikry/2^n}\left|y\right\rangle\\ &= \displaystyle \sum_{y=0}^{2^n-1} \underbrace{e^{2\pi ix_0y/2^n} \frac{1}{\sqrt{2^n m}} \sum_{k=0}^{m-1} e^{2\pi ikry/2^n}}_{\text{probability amplitude}}\left|y\right\rangle \end{array}$

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:

$\displaystyle \Big[\underbrace{e^{2\pi ix_0y/2^n} } \frac{1}{\sqrt{2^n m}} \sum_{k=0}^{m-1} e^{2\pi ikry/2^n}\Big]\Big[\underbrace{e^{-2\pi ix_0y/2^n} } \frac{1}{\sqrt{2^n m}} \sum_{k=0}^{m-1} e^{-2\pi ikry/2^n}\Big]$

The factors in underbrace evaluates to 1 when multiplied and we’re left with

$\displaystyle \frac{1}{2^n m}\Big| \underbrace{\sum_{k=0}^{m-1} e^{2\pi ikry/2^n}}\Big|^2$

Using the formula

$e^{i\theta} = \cos(\theta) + i\sin(\theta)$

we can write the summation in underbrace as

$\displaystyle \Big(\sum_{k=0}^{m-1} \cos(2\pi kry/2^n)\Big)^2 + \Big(\sum_{k=0}^{m-1} \sin(2\pi kry/2^n)\Big)^2$

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:

$\displaystyle \sum_{k=0}^{m-1} \cos(2\pi fk) = \frac{\cos(\pi f(m-1)) \sin(\pi fm)}{\sin(\pi f)}\\ \displaystyle \sum_{k=0}^{m-1} \sin(2\pi fk) = \frac{\sin(\pi f(m-1)) \sin(\pi fm)}{\sin(\pi f)}$

If we let

$f = ry/2^n$

this reduces the summations to:

$\displaystyle \Big(\sum_{k=0}^{m-1} \cos(2\pi kry/2^n)\Big)^2 + \Big(\sum_{k=0}^{m-1} \sin(2\pi kry/2^n)\Big)^2$

$\begin{array}{rl} &=\displaystyle \frac{\cos^2(\pi f(m-1)) \sin^2(\pi fm)}{\sin^2(\pi f)} + \frac{\sin^2(\pi f(m-1))\sin^2(\pi fm))}{\sin^2(\pi f)}\\ &= \displaystyle \frac{\sin^2(\pi fm)}{\sin^2(\pi f)}\Big[\underbrace{\cos^2(\pi f(m-1)) + \sin^2(\pi f(m-1))}_{\text{= 1}}\Big]\\ &= \displaystyle \frac{\sin^2(\pi fm)}{\sin^2(\pi f)} \end{array}$

Therefore, the probability of getting a specific y is

$p(y) = \displaystyle \frac{1}{2^nm} \displaystyle \frac{\sin^2(\pi fm)}{\sin^2(\pi f)}$

Here is a plot of the function $\sin^2(\pi fm)/\sin^2(\pi f)$ for m=4:

Notice that the graph attains its maximums when the values of f are integer values, that is when

$\displaystyle f = j= \frac{ry}{2^n} \text{ where } j= 1, 2, 3, 4, \ldots, r$

Since y is an integer value, this means that the value of y must be close to $j2^n/r$ . We can use a theorem in Number theory which states that if $p/q$ is a rational number that approximates a real number x and

$\displaystyle \Big|\frac{p}{q} - x\Big| \le \frac{1}{2q}$

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 $j2^n/r$ values, we have

$\displaystyle \left| y-j\frac{2^n}{r}\right| \le \displaystyle \frac{1}{2}\\$

and dividing both sides by $2^n$ , we get

$\displaystyle \left| \frac{y}{2^n}-\frac{j}{r}\right| \le \displaystyle \frac{1}{2^{n+1}}$

which satisfies the theorem. We can therefore expand $y/2^n$ via continued fraction expansion and continue until we find a denominator $r$ that is less that $2^{n_0}$ . We then test whether r could be our period if it satisfies

$\displaystyle c^r \equiv 1$

If it satisfies the above, then r is the period. It’s just a matter of computing $d^\prime$ , the inverse of $e$ modulo r satisfying

$\displaystyle ed^\prime \equiv 1 \mod r$

Having computed $d^\prime$ , we can then decrypt the ciphertext using

$m = c^{d^\prime} \mod N$

In our example in period finding, let’s suppose that the quantum computer gave us the following number

$y=1446311$

We can expand the fraction $y/2^n = 1446311/16777216$ as a continued fractions as follows:

$\displaystyle \frac{y}{2^n} = \frac{1446311}{16777216} = \frac{1}{11 + \displaystyle \frac{1}{1+\displaystyle\frac{1}{1+\displaystyle\frac{1}{1}}}} = \frac{5}{58}$

$\displaystyle \frac{y}{2^n} = \frac{1446311}{16777216} = \frac{1}{11 + \displaystyle \frac{1}{1+\displaystyle\frac{1}{1+\displaystyle\frac{1}{\displaystyle\frac{1}{6886}}}}} = \frac{34433}{399423}$

We can stop until $q=58$ since $q=58 < 2^{n_0} = 2^{12} = 4096$ . So we use the first expansion where $q=58$ and testing it

$\begin{array}{rl} \displaystyle c^{58} \mod 3127 &= \displaystyle 794^{58} \mod 3127\\ &= \displaystyle 1 \mod 3127 \end{array}$

which confirms that $q=58$ is a period. Using $r=58$ in the equation

$\displaystyle ed^\prime = m\times r + 1$

and solving for $d^\prime$ (which is the inverse of e modulo 58) we get

$\displaystyle d^\prime = 25$

We can now get the original message using

$\displaystyle 0794^{25} \mod 3127 = 1907$

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 $j2^n/r$ ? Let’s evaluate the probability for

$y_j=\displaystyle j\frac{2^n}{r} \pm \delta_j$

where $\delta_j$ is the distance of the closest y to $j2^n/r$ . Since $f = ry/2^n$ , we have

$\begin{array}{rl} p(y_j) = \displaystyle \frac{1}{2^nm}\frac{\sin^2(\pi fm)}{\sin^2(\pi f)} &= \displaystyle \frac{1}{2^nm} \frac{\sin^2(\pi mr\displaystyle\frac{y}{2^n})}{\sin^2(\pi r\displaystyle\frac{y}{2^n}) }\\ &= \displaystyle \frac{1}{2^nm} \frac{\sin^2\Big[\displaystyle\frac{\pi mr}{2^n}(j\frac{2^n}{r} \pm \delta_j)\Big]}{\sin^2\Big[\displaystyle\frac{\pi r}{2^n}(j\frac{2^n}{r} \pm \delta_j)\Big] }\\ &= \displaystyle \frac{1}{2^nm} \frac{\sin^2\Big[\displaystyle j\pi m \pm \frac{\pi m r\delta_j}{2^n})\Big]}{\sin^2\Big[\displaystyle j\pi \pm \frac{\pi r\delta_j}{2^n}\Big] }\\ &= \displaystyle \frac{1}{2^nm} \frac{\sin^2\Big[\displaystyle \frac{\pi m r\delta_j}{2^n})\Big]}{\sin^2\Big[\displaystyle \frac{\pi r\delta_j}{2^n}\Big] } \end{array}$

We can approximate the denominator using the small angle approximation of sine:

$\sin(x) \approx x$

to get

$\displaystyle p(y_j) = \displaystyle \frac{1}{2^nm} \frac{\sin^2\Big[\displaystyle \frac{\pi m r\delta_j}{2^n})\Big]}{\left[\displaystyle \frac{\pi r\delta_j}{2^n}\right]^2}$

Since m is the smallest integer such that $x_0 + mr \ge 2^{n}$ , then

$m = \displaystyle \left\lceil\frac{2^n}{r}\right\rceil$

We can use this to approximate

$\displaystyle m\frac{r}{2^n} \approx 1$

to get

$p(y_j) = \displaystyle \frac{1}{2^nm} \frac{\sin^2(\displaystyle \pi\delta_j)}{\left(\displaystyle \frac{\pi\delta_j}{m}\right)^2}$

Since $0 \le \delta_j \le 1/2$ , we can see from the graph below that the line joining (0,0) and $(\pi/2,1)$ , whose equation is $2x/\pi$ is less that the value of the sine function at that interval, that is,

$\displaystyle \frac{2x}{\pi} \le \sin(x)$

Using this inequality, we can get a lower bound of the probability of getting a specific y value to be

$\begin{array}{rl} p(y_j) = \displaystyle \frac{1}{2^nm} \frac{\sin^2(\displaystyle \pi\delta_j)}{\left(\displaystyle \frac{\pi \delta_j}{m}\right)^2} &\ge \displaystyle \frac{1}{2^nm} \left(\frac{\displaystyle \frac{2\pi\delta_j}{\pi}}{\displaystyle \frac{\pi \delta_j}{m}}\right)^2\\ &= \displaystyle \frac{1}{2^nm} \left( \frac{2m}{\pi}\right)\\ &= \displaystyle \frac{m}{2^n}\frac{4}{\pi^2}\\ &= \displaystyle \frac{1}{r}\frac{4}{\pi^2} \end{array}$

Since there are r of these $y_j$ ‘s, the probability of getting any one of these $y_j$ ‘s is therefore:

$p(y) = \displaystyle \frac{4}{\pi^2} \approx 0.405$

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 $j2^n/r$ with high probability. We then computed for the period using the continued fraction expansion of $y/2^n$ . With the period computed, it’s becomes straightforward to decrypt the ciphertext.

Period Finding and the RSA

In the previous post, we learned how to decrypt RSA by getting the factors of the big number N and computing for the inverse of e (the encoding number) modulo N. There is also another way to decrypt an RSA encrypted message. This is when you are able to get the period of the ciphertext. If c is the ciphertext, the period r is the smallest integer that satisfies:

$c^r \equiv 1 \mod N$

Once we get the period, we compute for $d^\prime$ , the inverse of e modulo r:

$ed^\prime \equiv 1 \mod r$

The inverse can then be used to decrypt the ciphertext:

$m=c^{d^\prime}$

In our previous example, we encrypted the message

THIS IS A SECRET MESSAGE

using public key p=53, q=59, N=pq=3127 and e=7 and private key d=431. The “plain text” is

1907 0818 2608 1826 0026 1804 0217 0419 2612 0418 1800 0604

and the ciphertext is:

0794 1832 1403 2474 1231 1453 0268 2223 0678 0540 0773 1095

Let’s compute the period of the first block of our ciphertext:

$0794^r \equiv 1 \mod 3127$

Using the python script below, we can compute the period

for r in range(1,100):
   p=pow(794,r,N)
   if p == 1:
     print "%d %d" % (r,p)

The result of running the above program gives r=58. We can then compute $d^\prime$ using the following equation:

$ed^\prime = m\times r + 1$

The above equation is satisfied when m=3 and $d^\prime = 25$ . Using this value of $d^\prime$ , we can compute for

$\begin{array}{rl} m&=0794^{25} \mod 3127 \\ &= 1907 \end{array}$

which gives us the original message!

However, unlike using the private key, you need to compute the period r and $d^\prime$ for every block of the ciphertext (unless the ciphertext is composed of only one block). However, that should not stop a cracker from deciphering all the blocks.

How RSA Encryption Works

Alice and Bob live in different parts of the world. They want to communicate with each other but they don’t want anyone to know the messages they exchange. In order to protect the message, they need to encrypt their message. Bob comes up with a secret key that will allow both of them to encrypt and decrypt their messages so that when they send it via email they will be confident that no one can read the message if ever someone (like Eve) intercepted the message. However, they have a dilemma. How will Bob send the encryption key to Alice ? If he sends the key and Eve intercepts it, then Eve will be able to decrypt the messages both Alice and Bob exchange and know what they are up to.

Bob should be able to send the key to Alice encrypted so that Eve will not be able to read it. In order to do this, Bob will have to create a second key to encrypt the key he wants to send to Alice. The problem now is how will Alice decrypt the message (which is the encrypted key) if she does not have the second key?

This is where RSA encryption is used. Suppose we want to encrypt a message using RSA, what we’ll do is find 2 large prime numbers p and q and get their product N = pq. We will need another number e, which we will use to encode the message into a ciphertext. The set of numbers N and e is called the public key which Alice can send to Bob via email. Bob will use these numbers to encrypt the secret key before sending to Alice.

We will represent a textual message like “THIS IS A SECRET MESSAGE” into numbers. To accomplish this, we need to map letters into numbers like the following:

$\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z & \\\hline 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10& 11& 12& 13& 14& 15& 16& 17& 18& 19& 20& 21& 22& 23& 24& 25& 26\\ \hline \end{tabular}$

Using the above mapping, we can write ‘THIS IS A SECRET MESSAGE’ as:

19 7 8 18 26 8 18 26 0 26 18 4 2 17 4 19 26 12 4 18 18 0 6 4

If a number is less than 10, we pad it with a zero to the left. The message then becomes:

19 07 08 18 26 08 18 26 00 26 18 04 02 17 04 19 26 12 04 18 18 00 06 04

To conserve some space, we can group the numbers into groups of 4:

1907 0818 2608 1826 0026 1804 0217 0419 2612 0418 1800 0604

Now for each $M$ number above, we will encode it using the formula:

$\displaystyle C = M^e \mod N$

What is this mod operation? The above says that we raise M to the exponent e, divide the result by N and get the remainder. For example, if M=10, e=7 and N=17 we have

$10^7=10000000$

Now divide the result by 17 and get the remainder:

$10000000 / 7 = 588235 \text { Remainder } 5$

Therefore

$10^7 \mod 17 = 5$

In python we can get the answer using the pow function:
>>> pow(10,7,17)
5

Let’s say we choose p = 53, q=59 and e = 7. This gives us $N=pq = 53\times 59 = 3127$ . To encode 1907, we do

$\displaystyle C=1907^7 \mod 3127 = 0794$

The number 0794 is now the ciphertext. It is the number we give to the recipient of the message. We can use python to generate the ciphertext above.

for n in ("1907","0818","2608","1826","0026","1804","0217","0419","2612","0418","1800","0604"):
   print pow(int(n),7,3127)

Doing this for all numbers we get:

0794 1832 1403 2474 1231 1453 0268 2223 0678 0540 0773 1095

When the recipient gets this message, she can decipher it using a key which she keeps private to herself. The key d is the inverse of e modulo $(p-1)(q-1)$ . The key d is called the private key. We can retrieve the original message using the formula:

$\displaystyle M = C^d$

The number d can be calculated using the following formula:

$ed \mod (p-1)(q-1) \equiv 1$

Using python we can compute for d using the following program:

>>> p=53
>>> q=59
>>> e=7
>>> NN = (p-1)*(q-1)
>>> for d in range(1,NN):
...   x = e*d % NN
...   if x == 1:
...     print 'd = ', d
... 
d =  431

Using d = 431 and applying the decipher formula to the first block, we get

$\displaystyle M = 0794^{431} \mod 3127 = 1907$

which is our original message!

We now apply this to the entire ciphertext

0794 1832 1403 2474 1231 1453 0268 2223 0678 0540 0773 1095

using the python program below:

for n in ("0794","1832","1403","2474","1231","1453","0268","2223","0678","0540","0773","1095"):
   print pow(int(n),431,N)

we get

1907 0818 2608 1826 0026 1804 0217 0419 2612 0418 1800 0604

which is our original full message! It’s just a matter of mapping these numbers back to letters to get the message text.

Using this mechanism, Alice will send 2 numbers N and e to Bob which he will use to encrypt the secret key and send to Alice. When Alice receives the encrypted secret key, she will use her private key d to decrypt it and get the secret key. After that, they can now start using the secret key to encrypt messages between them.