Factoring and RSA (Rivest-Shamir-Adleman) encryption

Shor’s algorithm is used to factor large integers much more efficiently than any known classical algorithm. Factoring is not just of interest to Mathematicians, however, because the difficulty of factoring is at the heart of the popular RSA method of encrypting sensitive information sent via the internet (or some other public channel).  While RSA is not the only method use to encrypt information, my understanding is that some version of Shor’s algorithm can be used to crack other encryption methods such as Diffie-Hellman. RSA stands for the names of its inventors, Rivest, Shamir and Adleman. 

This handout is written as a Mathematica notebook. In part of it, the RSA algorithm is implemented. Parameters are chosen, and random messages are generated. These are encrypted,  the encrypted messages are decrypted, and a check is made that the original message is recovered. It you have Mathematica you can run this notebook and verify that the RSA algorithm works. 

We suppose that Bob wants to receive a message from Alice on the internet (a public channel). Anything sent on a public channel can be intercepted by others. How can Bob and Alice agree on a coding scheme and then send each other coded messages which can be decoded by the other person but not by anyone "sniffing" on the internet? This has to be accomplished by only sending messages down the public channel.

I will now describe the RSA encryption scheme for doing this.  It uses  a result of  number theory which I will quote but not prove. 

To receive the message from Alice, Bob picks two large prime numbers p and q, and sends to Alice, on the public channel, their product 

	N = p q
	
but not p and q separately. N is taken to be large enough, typically a few thousand bits, that it cannot be factored on a classical computer.

You might ask how can one choose the large prime numbers p and q.  If one selects a large integer N at random it can be shown that the probability that it is prime is about 1/ln N. Hence, even if N has, say, 400 digits (around 1000 bits) you only have to take test a few hundred to a thousand random integers to typically find a prime number.  But can one efficiently test if a number is prime?  It turns out that one can, even though, if the number is found to be not prime, there is no known efficient classical algorithm to determine the prime factors. The website http://mathworld.wolfram.com/PrimalityTest.html explains how the test for primality is done in Mathematica. 

Bob also sends a large "encoding number” c which has no factors in common with (p-1)(q-1). If there are no factors in common the greatest common divisor (GCD) is 1.  The GCD of two integers is easily determined by Euclid’s algorithm discussed at the end.  According to Appendix J of Quantum Computer Science by N.D. Mermin, the probability that two large random integers have no common factors is greater that 1/2, so it is not difficult to find a suitable value for c. 

Hence the public key (available to everyone) is N and c.

Since Bob knows both p and q, and hence (p-1)(q-1), he can also determine the integer d such that

                 c  d   ≡ 1 ( mod (p-1)(q-1) ) .

What is the mod function? The value of a mod b is the result after one subtracts (or adds) the appropriate multiple of b to a to get a value which lies in the range 0 to b-1. If a is positive, one subtracts a multiple of b (possibly 0) so the mod function is simply the remainder after integer division. Hence, for example,  9 mod 5 = 4 because 9/5 = 1 remainder 4. If a is negative one has to add a multiple of b, so, for example, (-13) mod 5 = 2 (since -13 + (3x5) = 2).

The above equation, c d = 1 mod (something), looks strange at first.  If c is an integer we normally think that its inverse should be a fraction. However, here d is also an integer, and the product of two integers can give 1 if we use modular arithmetic. For example if c = 5 and d = 3 then c d = 15, and c d mod 7 = 1 (since 15 = (7x2) + 1). 

The algorithm for computing d in the equation above is efficient and an extension of Euclid’s algorithm. Euclid’s algorithm and the necessary extension are given at the end of this notebook and in Appendix J of Quantum Computer Science by N.D. Mermin. It turns out that d is unique.  Hence Alice, and anyone else sniffing on the public channel, knows N and c (but not p, and q, and hence not d).

The private key (known only to Bob) is p and q (and hence d). 

Alice breaks up her message into chunks of each containing a number of bits less than the number of bits of the integer N. Each chunk is then a binary number less than N. Let's denote by a the numerical value of one chunk.

                 a is the original message
 
Using the values of N and c that Bob has sent, she computes

                  b ≡  (a^c) ( mod N )         (b is the encoded message)

b, which is the encoded message and is another large integer, is sent down the public channel from Alice to Bob. 

Bob knows not only c and N, in addition to the encoded message b, but also the value of d. Here number theory kicks in and shows that the original (unencoded) message a is given by

               a ≡ (b^d) (mod N)     (the original message is recovered)

For a proof of this result see the book by Mermin. Bob can compute it because he knows d, but anyone sniffing on the public channel does not. 

However, if a third person, traditionally called Eve, listening on the public channel, could factor N (which is sent down the public channel) into its factors p and q, she would then have (p-1)(q-1) and, since c is also sent down the public channel, she could determine d where c d = 1 (mod (p-1)(q-1)) using the algorithm given at the end and in Mermin’s Appendix J.  Hence she could find the original unencrypted message a from a ≡ (b^d) (mod N).

Example 1:
Let's go through an example. I will take

                    p = 7, q = 13, so N = 91

For the encoding integer I take c = 11, which has no factors in common with (p-1)(q-1) = 6x12 = 72.  As shown at the end of this notebook,  using the extended Euclid algorithm also discussed in appendix J of Mermin's book, Quantum Computer Science,  one has d = 59. (Let's verify this: 11 x 59 = 649 = (9 x 72) + 1.)

The Mathematica code below sets these values, checks that p and q are prime while N is not, and that c d ≡ 1 (mod (p-1)(q-1)). (Note: in Mathematica commands I use n rather than N because N has a special meaning in Mathematica.) The code then generates a message a by computing a random integer between 0 and N-1, and next computes the encoded message b from b ≡  (a^c) ( mod N ). It then computes (b^d) (mod N) and checks that it gives back the original message a. 

If you have Mathematica you can run the code several times (each time a different random value for the message a will be generated) and see that the original message is always returned.

p=7; q = 13; c = 11; d = 59; n = p*q

We check that p and q are  prime.  The Mathematica command PrimeQ[p] returns True if p is prime and False if it is not.

PrimeQ[p]

PrimeQ[q]

PrimeQ[n]

We check that c d ≡ 1 Mod ((p - 1) (q - 1)).

Mod[c * d, (p-1)*(q-1)]

We generate a random message.

mess = Random[Integer, n-1]

We compute the encoded message.

encodedmess =Mod[ mess^c, n]

We decode the encoded message and check that we recover the original message.

recoveredmess = Mod[encodedmess^d, n]

recoveredmess == mess

Hence the message was successfully decoded.

Example 2:
Now I give another example with somewhat larger numbers, p = 61, q = 53, so N = p q = 3233.  I take c = 17, check that it has no factors in common with n, and verify that d = 2753.  I check that c d ≡ 1 mod ((p-1)(q-1)) and encode the message a using b ≡ (a^c) (mod N), and finally decode the encrypted message b using a ≡ (b^d) (mod N).

p = 61; q = 53;  n = p * q

c= 17;

GCD[c, (p-1)(q-1)]

d = 2753;

Mod [c d, (p-1)(q-1)]

message = Random[Integer, n-1]

encodedmess = Mod[ message^c, n]

decodedmessage = Mod[encodedmess^d, n]

decodedmessage ==  message

Hence the message was successfully decoded.

The Euclidean Algorithm

We want to efficiently find the Greatest Common Divisor (GCD) of two integers. This is the largest factor that they have in common. As a simple example, the GCD of 24 and 9 is 3.

Suppose we want the GCD of two numbers (Subscript[a, 0]) and (Subscript[b, 0]) with (Subscript[a, 0]) > (Subscript[b, 0]). We proceed iteratively. At each stage, the new value of a is equal to the old value of b, and the new value of b is equal to the remainder when the old value of a is divided by the old value of b, i.e.

	(Subscript[a, n+1]) = (Subscript[b, n]) 
	(Subscript[b, n+1]) = (Subscript[a, n]) - [(Subscript[a, n])  / (Subscript[b, n])] (Subscript[b, n])    which is the same as     (Subscript[b, n+1]) = (Subscript[a, n]) mod  (Subscript[b, n])

where [... ] means the integer part of the quantity in brackets.  (Subscript[a, n]) and (Subscript[b, n]) decrease at successive iterations and maintain the inequality (Subscript[a, n]) >(Subscript[b, n]).  Also (Subscript[a, n]) and (Subscript[b, n]) have the same common factors as (Subscript[a, 0]) and (Subscript[b, 0]). Eventually we get to a stage where (Subscript[b, n+1]) = 0. This means that (Subscript[a, n]) is divisible by (Subscript[b, n]) so (Subscript[b, n]) is the greatest common divisor. 

As an example for (Subscript[a, 0]) = 24, (Subscript[b, 0]) = 9:

	n       (Subscript[a, n])                (Subscript[b, n])
	-----------------------
	0       24            9
	1          9            6
	2          6            3
	3          3            0
	
Hence the GCD of 24 and 9 is (Subscript[b, 2]) (= 3).

Extension of the Euclidean Algorithm to find an inverse modulo an integer

Given a and c which have no common factors and where c < a, we want to find d where

 c d = 1 mod a

The greatest common divisor of c and a is 1 (since by assumption they have no common factors).  We go through the Euclid algorithm

	(Subscript[a, n+1]) = (Subscript[c, n]) 
	(Subscript[c, n+1]) = (Subscript[a, n]) - [(Subscript[a, n])  / (Subscript[c, n])] (Subscript[c, n])

until we get to a stage where (Subscript[c, n]) = 1,  the greatest common divisor. One can then obtain d by working backwards through the iterations. This is best shown by an example.  We take p = 7, q = 13, as in example 1 above, so we have a = (p-1)(q-1) = 72 and hence we initialize (Subscript[a, 0]) = 72. We also take c = 11 (again as in the example 1) which has no factors in common with a, and so initialize (Subscript[c, 0])= 11.  Hence the Euclid algorithm proceeds as follows

	n       (Subscript[a, n])                (Subscript[c, n])
	-----------------------
	0       72            11           (Subscript[a, 0])= a,    (Subscript[c, 0])= c   (the initial values)
	1        11             6           (Subscript[a, 1]) = (Subscript[c, 0]),     (Subscript[c, 1]) = (Subscript[a, 0]) - 6(Subscript[c, 0])
	2          6             5           (Subscript[a, 2])= (Subscript[c, 1]),    (Subscript[c, 2])=(Subscript[a, 1])- (Subscript[c, 1])
	3          5              1          (Subscript[a, 3]) = (Subscript[c, 2]),   (Subscript[c, 3])= (Subscript[a, 2]) - (Subscript[c, 2]) = 1  ((Subscript[c, 3])= 1 so we stop).
	
Hence, working backwards, 

             1 = (Subscript[a, 2]) - (Subscript[c, 2]) =  (Subscript[c, 1]) - ((Subscript[a, 1])- (Subscript[c, 1])) = 2(Subscript[c, 1])- (Subscript[a, 1])=  2((Subscript[a, 0]) - 6(Subscript[c, 0])) - (Subscript[c, 0]) = 2(Subscript[a, 0]) - 13(Subscript[c, 0]) = 2 a - 13 c. 

We want to take this mod a. Now  -13 c  mod a = (-13 + a) c  mod a = 59 c mod a because c is an integer and any integer multiple of a is ignored when evaluating an expression mod a. (recall a = 72). Hence
 
           1 = 2a - 13 c = 2a + 59 c  mod a = 59 c  mod a,
                  
again ignoring an integer multiple of a.  Hence d = 59, as stated in example 1 above.