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.

Modular Exponentiation (from Wednesday)

The module modPow2 quickly computes (b^e) (mod m) for large values of b, e, and m. Using repeated squaring and reduction mod m, the following code avoids both the memory and time limitations of the other implementations that we discussed last time.

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

modPow2[base_, exponent_, modulus_]:=Module[{b=base,e=exponent,result},
result=1;
b=Mod[b,modulus];
While[e > 0,
If[Mod[e,2]==1,
result = Mod[(result*b),modulus];
];
e=Floor[e/2];
b=Mod[b*b,modulus];
];
result
]

Note that modPow2 runs quickly even for b, e, and m on the order of (10^30):

b=890347234619344432737102638265;
e=128835602385546329457121138672;
m=405795467345732909767236552341;
modPow2[b,e,m]

Fermat’s Little Theorem and Primality Testing

Fermat’s Little Theorem says that if p is prime and a is not divisible by p, then (a^(p-1))≡1 mod p.

This simple observation provides a way to test if an arbitrary number n is prime. To do so, pick some values (Subscript[a, 1]), (Subscript[a, 2]), ..., (Subscript[a, m]) (not divisible by n) and compute

((Subscript[a, i])^(n-1))mod n    for    i=1, 2, ..., m.

If all of these are 1, then n is probably prime.

Here is a brief demonstration. Note that 97 is prime.

Mod[#^96,97]&/@Range[2,96]

However, 93 is not prime, and the modular powers (mostly) are not equal to 1.

Mod[#^92,93]&/@Range[2,92]

Write your own Module to implement the following prime-testing algorithm:

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.

fermatPrime[n_,m_]:=Module[{a,p=True},



]

Implement this and test it well. One way to test this is to use your best sieve algorithm to generate a large list of primes. Then apply fermatPrime to some or all of these. Does it correctly identify them as prime? Can you find any values for which fermatPrime does not work?

Known primes:

fermatPrime[104393,4]

fermatPrime[282174488599599500573849980909,6]

Try it with composites:

fermatPrime[282174488599599,6]

Greatest Common Divisor (GCD)

The greatest common divisor (GCD) 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.

Furthermore, 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

And here is an implementation of gcdExtended:

gcdExtended[a_,b_] := Module[{r,s,t,i,q},
r[0]=a;r[1]=b;
s[0]=1;s[1]=0;
t[0]=0;t[1]=1;
i=1;
While[r[i]>0,
r[i+1]=Mod[r[i-1],r[i]];
q=Floor[r[i-1]/r[i]];
s[i+1]=s[i-1]-q*s[i];
t[i+1]=t[i-1]-q*t[i];
i=i+1;
];
{r[i-1],s[i-1],t[i-1]}
]

Let’s try it out with a=35 and b=147:

gcdExtended[35,147]

Indeed, 7 is the GCD of 35 and 147, and 7=-4(35)+1(147).

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.

If integers a and n, are relatively prime, then our gcdExtended function provides a means of finding the multiplicative inverse of a (mod n).

For example: If a=3 and n=17, then gcdExtended[a, n] returns {1, 6, -1}. This tells us that 1=6(3)-1(17), or equivalently, 3(6)≡1(mod 17). This means 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 to -5. Thus, 12 is the multiplicative inverse of 10 mod 17.

Now, implement a modular inverse function using gcdExtended.

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[{g,r,s},



]

Test it out:

modInverse[10,17]

Encryption Keys

Choose two primes

Use your fermatPrime function to find two prime numbers p and q with 30 digits each. 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”.