Introduction to Public Key Encryption

Private key ciphers

In order to secure private communication, cryptographic ciphers have been around for thousands of years. One of the more famous ones was used by Julius Caesar and is called the Caesar Cipher. It involves the substitution of the letters of the alphabet by that same alphabet but shifted. Below is an example.

(* Consider the letters of the alphabet (lower case) *)
alphabet=CharacterRange["a","z"]

Now we construct a shifted alphabet

shiftedalphabet=RotateLeft[alphabet,3]

The cipher is the algorithm that tells us how the two are related, i.e.

cipher=Thread[alphabet->shiftedalphabet]

This list, here called a cipher, tells us how each letter of the alphabet is substituted. So if we  construct a message written in the original alphabet, the Caesar Cipher substitutes each letter according to the rule "cipher".

ceasar[inputstring_]:=StringReplace[inputstring,cipher]

julius=ceasar["You blocks,you stones,you worse than senseless things!
O you hard hearts,you cruel men of Rome, knew you not Pompey?"]

So the list "julius" now contains the encrypted message, but how does the recipient know how to decipher it? They need an algorithm, or cipher, to decode the message. That is, someone must tell the recipients beforehand what the cipher is, and such a system is called a private key system. Here the "key" is the algorithm for encryption. Knowing that private key, we can undo this message.

uncipher=Thread[shiftedalphabet->alphabet]

StringReplace[julius,uncipher]

Private key crypto-systems have some obvious pitfalls, this is called the key distribution problem

Requires direct communication between user and sender of key, and is compromised by eavesdropping, etc.

Substitution keys are very easy to decrypt even without the key (e.g. Mary Queen of Scots).

ClearAll["Global`*"]

Public key (RSA) encryption

Rivest, Shamir, Adleman

Alice and Bob want to communicate in a secure manner. Instead of sending Bob a private key (which can be compromised) she follows this protocol

She chooses two prime numbers p and q, so that p≠q. (A prime number can only be factored into itself and 1)

She computes the modulus n = p q. A number that is a product of two primes is called semi-prime, so n is semi-prime.

She computes the totient  ϕ = (p-1)(q-1).

She chooses the public-key exponent, e, an arbitrary number. It must satisfy  1  < e <  ϕ.   But e, ϕ are not allowed to have common factors (co-prime).

She chooses a number d (the private key) so that  d e = 1 Mod[ϕ]  (Note: d should be an integer if it isn’t try another value for e)

After Alice completes this checklist she publishes her public-key which is simply the pair (n,e). But she keeps q, ϕ, d  private.

Now Bob wants to send Alice a secure message.  He goes on the internet and finds her public key (n,e) which she published for all to see. Let’s say Bob has a string of characters M="wassup" that he wants to send. He converts that string into an integer, he does this through the means of a conversion function N=f(M).  Given the string of characters M and the function f, the latter maps M into an integer N. It is important that f is invertible, i.e. given N we can apply (f^(-1))(N)  to get a unique M.

Having constructed N, Bob looks at the public key  e, n  and constructs

C = (N^e) Mod n

The number C is the cipher, and he sends that number to Alice, (By the way, others are also listening and were able to get Bob's number C). 

Alice simply takes her private key (not shared by anyone!) and evaluates

(C^d)  Mod n

she claims that this is equal to N and she uses Bob's public table for  ((f )^(-1)) to find the original message M.

Why does this work ?

Some results from number theory:

Theorem I:    Fermat's Little Theorem

Let p be  a prime number, then

(a^(p-1)) Mod p = 0  if  p divides a

(a^(p-1)) Mod p = 1  if  p does not divide a

Examples:

fermat[a_,p_]:=Mod[a^(p-1),p]

Table[fermat[a,3],{a,1,20}];
ListPlot[%,Filling->Axis]

Theorem II:

p ≠ q  are prime numbers and

if   x = a Mod p and  x = a Mod q   then  x = a Mod p q


Proof:  Since x = a Mod p this implies that  x = a + K p  where K is an integer
            Since x = a Mod q   "       "        "      x = a + L q     "       L      "
            
            therefore 0 = K p - L q  but  since  p,q are prime K = M q and L = M p where M is some integer.
            Now, since x = a + L q = a + M p q, which implies that
            x = a Mod p q     QED

Theorem III:

Modular arithmetic allows the following identity

(x y) Mod n  = (x Mod n) (y Mod n)  Mod n

Lets take a few examples.

x=5;
y=7;
n=3;

Mod[x y,n]
Mod[x,n]
Mod[y,n]
Mod[x y,n]==Mod[Mod[x,n] Mod[y,n],n]

Using these theorems we take Bob's value C = (N^e) Mod n;   Alice then creates 

(C^d) Mod n  = (  (N^e) Mod n  (N^e) Mod n ... (N^e) Mod n )  Mod n  =  (N^ed)  Mod n.  Let us first evaluate

(N^(e d)) Mod p = (N^(1 + k (p-1)(q-1) )) Mod p    

Why ?  Remember, Alice chose de = 1 Mod ϕ = 1 Mod (p-1)(q-1) which implies
that  de = 1 + k (p-1)(q-1)  where k is an integer. 

Therefore

(N^(e d)) Mod p = N [ (N^(k(q-1)))((]  )^(p-1)) Mod p = ( N Mod p) (  [ (N^(k(q-1)))((]  )^(p-1)) Mod p)  Mod p

Now lets use Theorem I  to state that

[(N^(k(q-1)))]^(p-1)  Mod p = 0  if p divides N
[(N^(k(q-1)))((] )^(p-1)) Mod p = 1  if p does not divide N

so in Case I,  (N^ed) Mod p = 0 Mod p  
                      but  0 = N Mod p  therefore
                     (N^ed) Mod p = N Mod p

in case II  

(N^(e d)) Mod p =  ( N Mod p ) Mod p =  N Mod p  so in either case we have

(N^(e d)) Mod p = N Mod p

Since we proved the above for p, we can do the same to show that

(N^(e d)) Mod q = N Mod q

We now use Theorem II  to equate

(N^ed) Mod p q = N Mod p = N Mod q  or

(N^ed) Mod n =  N Mod n, but if  N < n  this is the same as
(N^ed) Mod n =  N    QED

Thus Alice can re-constitute the value N Mod n, which is Bob's original message (which can then be transcribed using his function (f^(-1)))

Let's look at a specific example. First Alice produces her public key as described above.

(* Alice chooses 2 prime numbers, p, q that are not co-prime *)

p=23;
q=11;

(* she constructs the modulus *)
n=p q

(* then the totient *)
ϕ = (p-1)(q-1)

(* choose e, it cannot have a common factor with ϕ *)
e=31;
?GCD
GCD[ϕ,e]

(* Alice constructs her private exponent d which is a solution of the equation  e d = 1 Mod[ϕ] *)
(* Mathematiac has a routine that lets you solve the above equation for d, the Modular inverse of e *)
?PowerMod

d=PowerMod[e,-1,ϕ]

(* Alice now publishes her public key *)

key={n,e}

(* Bob uploads Alice's key he then wants to send the number N = 199 to Alice encrypted *)

Bobsmessage=199;
Bobsmessage^e
Cnum=Mod[%,n]

(* So Alice, as well eavesdroppers, have access to this number *)
(* But Alice uses her exponent d to construct N *)

Cnum^d
Alicesmessage=Mod[%,n]

Thus Alice easily obtains Bob's original message,

Bobsmessage
Alicesmessage

However the eavesdroppers are hard at work. They know the public key n,e, and all they need to do is factor n it in order to get p,q as well as the totient. With the totient they can easily solve the equation

d e = 1 Mod ϕ

for exponent d (the Modular inverse of e ).  With knowledge of the totient, the eavesdroppers employ Alice’s algorithm in order to find N.  So why is this encryption scheme secure?

Answer: It is  difficult to factor a number n if it is very large. Indeed, as the number of digits in n increase, known classical algorithms require computer resources (e.g. time, memory) that scale as a power of n. At a certain point, for very large n, available technology is not able to perform the required task. Therefore, ensuring the security of an encrypted message.

Examples:

?FactorInteger

?Timing

Timing[FactorInteger[15]]

Timing[FactorInteger[1698532224795]]

Timing[FactorInteger[745237738484848484858585858820303836464646464646698532224795]]

Note the time resources required by Mathematica as the number to be factored grows in size.