Math 455.1  •  5 April 2009

RSA encryption system

Copyright © 2009 by Murray Eisenberg.  All rights  reserved.

A tiny example

Character encoding and decoding for Alice and Bob

Here we use the convention of coding A as 0, B as 1, etc., and Z as 25 and not using any punctuation at all.

The alphabet:

alph=Characters["ABCDEFGHIJKLMNOPQRSTUVWXYZ"];

Tests for characters and numbers in range:

letterQ[ch_]:=MemberQ[alph,ch]
inRangeQ[n_]:=IntegerQ[n]&&0≤n≤25

Encoding function:

toNumber[ch_?letterQ]:=First@First@Position[alph,ch]-1
SetAttributes[toNumber,Listable]

Decoding function:

toCharacter[n_?inRangeQ]:=alph[[n+1]]
SetAttributes[toCharacter,Listable]

"Cipher Bureau" chooses Bob's keys

Pick two primes (typically having 100's of decimal digits):

p=43;q=59;                          (* secret! *)

n=p q

Pick e relatively prime to (p-1)(q-1) . (Typically, e is prime and (2^e)>n.)

e=13;

ϕ=(p-1)(q  -1)

Check:

GCD[e, ϕ]

Bob's public key will be:

{n,e}

d=PowerMod[e,-1,ϕ]

Bob's private key will be:

{n,d}

Alice encrypts using Bob's public key

msg = "TAKEAXE";

Encode into blocks

Blocks j to be a large as possible, but j < n = 2537.  So group two-digit letter codes into four-digit blocks j.

Is the message length even or odd?

Mod[StringLength[msg], 2]

The length is odd, so we need to append a character to make it even:

msg = StringJoin[msg, "Z"]

The encoding of the individual characters is given by toNumber as individual integers in {0, 1, 2, …, 25}:

ptxt = toNumber[Characters[msg]]

We need to combine consecutive pairs of these integers.  Here's how to start:

ptxt = Partition[ptxt, 2]

Some of the integers have only one digit, which we must therefore precede with a 0 before combining these pairs into four-digit numbers. Here's a way to do what we need:

to4Digits[{j_,k_}]:=100 j+k

plaintext =Map[to4Digits,ptxt]

Here's the entire encoding process in this example, encapsulated into a single function:

encode[txt_] := Map[to4Digits,Partition[toNumber[Characters[txt]],2]]

encode[msg]

Do you find the definition of encode above hard to read because of all the nested brackets? I do! You can make it a bit easier to read by exploiting Mathematica's prefix notation for one-argument functions:

encode[txt_]:=Map[to4Digits,Partition[toNumber @ Characters[txt],2]]

encode[msg]

You can make the definition of encode even easier to read by using the notation /@ for Map.  The notation f /@ expr is shorthand for Map[f, expr].

encode[txt_] := to4Digits/@Partition[toNumber @ Characters[txt],2]

encode[msg]

Encrypt

The encryption function for this RSA cipher, to be applied to integers < n, is given by:

encrypt[a_]:=Mod[(a^e),n]

ciphertext=encrypt/@plaintext

That is the encrypted message that Alice transmits to Bob.

Bob decrypts using his own private key

ciphertext

Decrypt

The RSA decryption function uses Bob's private key (n, d), where d is the multiplicative inverse of e modulo n.

decrypt[b_]:=Mod[(b^d),n]

decrypted=decrypt/@ciphertext

Decode

Decoding those plaintext numbers into characters by hand is straightforward. Doing it on the computer takes some work manipulating lists. We need to separate each number into its corresponding pair of numbers in the range 0, 1, 2, …, 25 (and then use toCharacter). The difficulty is that some of the decrypted numbers are 4-digits in length whereas others are 2-digit or 3-digit.

Here's one way to reconstitute the needed numbers.

blocks =IntegerDigits/@decrypted
blocks=Map[PadLeft[#,4]&,blocks]
nums=Partition[Flatten[blocks],2]
FromDigits/@nums

Or, obtain the same result more directly like this, working first on a single 4-digit ciphertext number:

separate[k_]:={Quotient[k,100],Mod[k,100]}

nums=Flatten[Map[separate,decrypted]]

Finally, decode each pair of digits into a character and join the individual characters into a string:

StringJoin@toCharacter[nums]

Here's the entire decoding process encapsulated in a function (using the second approach preceding):

decode[digits_] := StringJoin[toCharacter[Flatten[Map[separate,digits]]]]

decode[decrypted]

The nested brackets make that hard to read.  You can simplify it by using repeatedly the prefix notation f @ g[args]  as an abbreviation for f[g[args]].  (In other words, f @ g denotes the composition of f after g.)  Here's the simplified version:

decode[digits_] := StringJoin@toCharacter@Flatten[ separate/@ digits]

decode[decrypted]

Generating large primes for real examples

We want to define a function nextPrime such that nextPrime[n] gives the next prime p > num.

A recursive definition seems like an obvious way to proceed, and indeed it's quite easy to program.(Exercise: Do it!) However, the gaps between one large prime and the next can be quite big, so trying to find the next prime after a given one could involve a deeper nesting of recursive calls than Mathematica permits. For this reason, we give here instead a procedural definition.

nextPrime[n_Integer]:=Module[{k=n},While[!PrimeQ[k],k++];Return[k]
]

What a call nextPrime[n] does is this: For each k starting at k=n, the number k is tested to see if it's prime and, if so, it's returned by the function; if it's not, then k is incremented by one —that's what the expression k++ does—and the process continues.

i=RandomInteger[{(10^99),(10^100)}]
p=nextPrime[i]

How big a prime is that?

Length[IntegerDigits[p]]

k=RandomInteger[{(10^99),(10^100)}]
q=nextPrime[k]

Are p and q really primes? (Recall that PrimeQ guarantees its answer as correct only for fairly small n, at least those  n<(10^16). Otherwise, it only has a high probability of giving a correct result.) To obtain a guarantee of of primality, use the resource-hogging function ProvablePrimeQ from the package NumberTheory`PrimeQ`.

Needs["PrimalityProving`"]

ProvablePrimeQ[p]

ProvablePrimeQ[q]

Finding multiplicative inverse d of e

This is from the original, simpler example than the one that would use the primes generated above

The keys

p =43;q=59;n = p q

e=13;

ϕ=(p-1)(q -1)

Find multiplicative inverse d of e mod (p - 1)(q - 1)

Method 1: use PowerMod

PowerMod[e,-1,ϕ]

Method 2: use Euclidean algorithm

First carry out the Euclidean algorithm itself to find the GCD. (You may want to do it with paper and pencil, although the process would be quite error-prone for a more realistic example with large numbers.) To begin, find the successive quotients and remainders:

r0=ϕ;r1=e;

{q1=Quotient[r0,r1],r2=Mod[r0,r1]}

{q2=Quotient[r1,r2],r3=Mod[r1,r2]}

{q3=Quotient[r2,r3],r4 =Mod[r2,r3]}

{q4=Quotient[r3,r4],r5=Mod[r3,r4]}

Next, solve for each remainder and "go back up" to express the gcd as an integral linear combination of the original numbers r0 = ϕ and r1 = e:

Clear[r0,r1,r2,r3,r4,r5]

{q1,q2,q3,q4}

Simplify[r5//.{ r5->r3-r4 q4,r4->r2-r3 q3,r3->r1-r2 q2,r2->r0-r1 q1}]

Recall that r0 is ϕ and r1 is e.Thus
	1=gcd(ϕ,e)=-5 ϕ+937 e.
This means that 
	937e ≡ 1  (mod ϕ). 
Hence the desired multiplicative inverse of e modulo ϕ is:

d=937;