Mathematics of RSA Encryption

Math 242 Modern Computational Math

The RSA algorithm is widely used for encrypting messages. The ideas are based in number theory: modular arithmetic, notions related to greatest common divisors, and some interesting theorems.

Greatest Common Divisor (GCD)

The greatest common divisor of two numbers a and b is a number k which:

Is a common divisor. That is, k divides both a and b; we sometimes write this as k|a and k|b.

Is largest among all common divisors. That is, if j divides both a and b, then j⩽k.

As far back as Euclid, people have been computing GCDs. In fact, Euclid had an algorithm for doing so. In modern terms, the Euclidean algorithm goes like this:

Set (Subscript[r, 0])= a  and (Subscript[r, 1])=b. (Assume a>b.)
Set i=1.
While (Subscript[r, i])≠ 0 :
    Define (Subscript[r, i+1]) as the remainder after dividing (Subscript[r, i-1]) by (Subscript[r, i]). That is, (Subscript[r, i+1])=(Subscript[r, i-1])-(Subscript[q, i])(Subscript[r, i]), where 0⩽ (Subscript[r, i+1])<(Subscript[r, i]). 
    i=i+1
Return (Subscript[r, i-1]), which is the GCD of a and b.

Note that at each iteration of the loop, (Subscript[r, i+1]) = Mod[(Subscript[r, i-1]),(Subscript[r, i])]. Since the values of (Subscript[r, i]) are decreasing, eventually (Subscript[r, i])=0. At that point, (Subscript[r, i-1]) is the GCD of a and b.

Here is a Mathematica implementation:

gcd[a_,b_]:=Module[{r,i},
r[0]=a;
r[1]=b;
i=1;
While[r[i]>0,
r[i+1]=Mod[r[i-1],r[i]];
i++;
];
r[i-1] (* return value *)
]

Try it out:

gcd[68,12]

Enhanced Euclidean Algorithm

The GCD of a and b can be written as a linear combination of a and b. That is, there exist integers s and t such that gcd(a,b) = s a+t b.

For example, 3=gcd(24,9), and also 3=(-1)24+3(9).

The values s and t are determined by the Euclidean algorithm. Just keep track of the quotients and remainders at each step:
6 = 24-2(9)
3=9-1(6)
0=6-2(3)
So 3 is the gcd. Then, back substitute to obtain:
3=9-1(6)=9-1(24-2(9))=-1(24)+3(9)

The extended Euclidean algorithm is a modification of the Euclidean algorithm that keeps track of the values s and t. Here is the function specification:

Function: gcdExtended
Arguments: positive integers a, b
Return: r, s, t, where r = gcd(a,b) = s a+t b

Here is the pseudocode:

(Subscript[r, 0])=a ,  (Subscript[r, 1])=b
   (Subscript[s, 0])=1 ,  (Subscript[s, 1])=0
   (Subscript[t, 0])=0,  (Subscript[t, 1])=1
   i=1
   while (Subscript[r, i])>0:
      (Subscript[r, i+1])=Mod[(Subscript[r, i-1]),(Subscript[r, i])]
      q=Floor[(Subscript[r, i-1])/(Subscript[r, i])]    (i.e. (Subscript[r, i+1])=(Subscript[r, i-1])-q (Subscript[r, i]))
      (Subscript[s, i+1])= (Subscript[s, i-1])-q (Subscript[s, i])
      (Subscript[t, i+1])=  (Subscript[t, i-1])-q (Subscript[t, i])
      i=i+1   
   then (Subscript[r, i-1])=gcd(a,b)=(Subscript[s, i-1])a+(Subscript[t, i-1])b

Now implement your own module gcdExtended that performs the extended Euclidean algorithm. Use the pseudocode above.

gcdExtended[a_,b_] := Module[{},




]

Test your gcdExtended module.

Modular Inverses

If a b≡1 mod n, then a and b are called multiplicative inverses mod n.

For example, 3 and 5 are multiplicative inverses mod 7.

Note that if a b≡1 mod n, then n divides a b-1. Thus, there exists an integer k such that a b-1=k n, or a b-k n=1. This means that gcd(a,n)=1. In other words, a and n are relatively prime.

For pairs of relatively prime integers a and n, our gcdExtended function provides a means of finding multiplicative inverses mod n.

For example: If a=3 and n=17, then gcdExtended[a, n] returns {1, 6, -1}. This tells us that 6 is the multiplicative inverse of 3 mod 17.

For another example: If a=10 and n=17, then gcdExtended[a, n] returns {1, -5, 3}. This tells us that -5 is the multiplicative inverse of 10 mod 17. We don’t really want negative values, so add 17. Thus, 12 is the multiplicative inverse of 10 mod 17.

Now, implement a modular inverse function using gcd2.

Function: modInverse
Arguments: relatively prime integers a and n
Return: integer b in {1, 2, ..., n-1} such that a b≡ 1 (mod n)

modInverse[a_,n_]:=Module[{},




]

Test it out:

modInverse[10,17]

Fast modular powers

We previously wrote a function that quickly computes (b^e) (mod m), according to the following specification.

Module: modPow2
    Arguments: base, exponent, modulus
    Return: (base^exponent) mod modulus

Copy your modPow2 function into this notebook.

Primality Testing

We previously wrote a function that uses Fermat’s Little Theorem to test whether or not a number is prime.

Module: fermatPrime
Arguments: n, m
Return: Select m random values of a in the range 2,...,n-1. If for each of these, (a^(n-1))≡1 mod n, then return True. Otherwise return False.

Copy your fermatPrime function into this notebook.

Encryption Keys

Choose two primes

Use your fermatPrime function to find two prime numbers p and q of at least 30 digits. These primes are private values.

Compute their product

Compute n=p q. Note that it’s easy to multiply p and q, but very hard to factor n. (You can try it with Mathematica’s FactorInteger function.) This number will be public.

Compute the totient function of n

Compute λ = λ(n)=lcm(p-1, q-1). Here, lcm is the least common multiple, which you can compute using Mathematica’s LCM function. The value λ is private.

Choose your encryption key

Find a value e such that gcd(e,λ) = 1. This value doesn’t need to be huge — four digits or so is good. This value will be public.

Determine your decryption key

Compute the modular inverse of e mod λ. Call this value d. This value is private.

Public and Private Keys

Your public key is the pair (e,n). Share this on the RSA Forum on Moodle, so that others can send you encrypted messages. Your private key is d. Don’t share it outside of your own Mathematica notebooks.

Encrypting and Decrypting

A message is simply a number m. The encryption of m is simply the value (m^e) mod n, where e and n are as defined above.

If c=(m^e) (mod n) is an encrypted message, then the decryption of c is simply m=(c^d) mod n.

Try it! Encrypt and decrypt some numerical messages.