RSA Encryption

Math 242 Modern Computational Math, spring 2021

Modular Exponentiation

Here is our module from Monday that efficiently computes (b^e) (mod m).

modPow[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   (* return the result *)
]

Fermat’s Little Theorem and Primality Testing -- we’ll get to this on Friday

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]) less than n and compute

((Subscript[a, i])^(n-1))       (mod n)    for each    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]

Let’s implement a prime-testing algorithm based on Fermat’s Little Theorem:

fermatPrime[n_,m_]:=Module[{a},
(* Select m random values of a in the range 2, ..., n-1. If (a^(n-1)) ≡ 1 (mod n) for each of these values of a then return True. Otherwise return False. *)
Do[
a=RandomInteger[{2,n-1}];
If[modPow[a,n-1,n]≠1,Return[False,Module]]
,m];
True  (* return True, since n is probably prime *)
]

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?

Try it with some known primes:

fermatPrime[104393,10]

fermatPrime[282174488599599500573849980909,30]

Also try it with composites:

fermatPrime[282174488598,10]

fermatPrime[1853020188851841,10]

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 we can use Mathematica’s ExtendedGCD function to find the multiplicative inverse of a (mod n). ExtendedGCD[a,n] returns {g, {s, t}} such that gcd(a,n) = g = s a+t n.

For example: If a=3 and n=17, then ExtendedGCD[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 ExtendedGCD[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, obtaining 12. Thus, 12 is the multiplicative inverse of 10 mod 17.

ExtendedGCD[10,17]

Mod[-5*10,17]

Mod[12*10,17]

Now let’s implement a modular inverse function. This function accepts two arguments a and n, and returns the inverse of a mod n. Assume that a and n are relatively prime (no common factor larger than 1).

modInverse[a_, n_]:=Module[{g,s,t},
{g,{s,t}}=ExtendedGCD[a,n];
If[g≠1,Print["ERROR: integers not relatively prime in modInverse"];Return[]];
If[s<0,s+=n];
s (* return value *)
]

Test it out:

modInverse[10,17]

modInverse[44,97]

44*86

Mod[3784,97]

Computing your 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.

p=

q=

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.

n=p*q

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.

λ=LCM[p-1,q-1]

Choose your encryption key

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

e=

GCD[e,λ]

Determine your decryption key

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

d=modInverse[e,λ]

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 a numerical message m to obtain a cypher c.

m=

c=modPow[m,e,n]

Now decrypt your cypher c to recover the message m:

modPow[c,d,n]