Applying prime factorisation in Mathematica:
RSA encryption functions

Ivan Cnop
Vrije Universiteit Brussel
icnop@vub.ac.be

Introduction

In this text,we let students write their own RSA code. This code is due to Rivest, Shamir and Adleman and universally used.
Some instructions use list operations. The usage of list programming is limited in this notebook to the very simple Range, Length and Select commands that perform exactly what their name suggests. No hidden programming is necessary.
For the theoretical background it is useful to try out the Ugroups text first.
It is recommended to start a new session with Mathematica Kernel.

Products of 2 primes

How do we recognise that a number is the product of exactly two prime numbers? 
Let us start with numbers we can factor by hand and check how  Mathematica does this.

Introductory example

FactorInteger[94]//TableForm

Length[%]

FactorInteger[96]//TableForm

FactorInteger[9] // TableForm

Length[%]

Now that we know primes are found in the first column, we select this first column by   First[Transpose[  ]]

First[Transpose[FactorInteger[91]]]

and the "good" integer are those which are exactly this product:

Times @@ First[Transpose[FactorInteger[91]]]

Here is a list of the smallest prime factors

Table[
      First[First[Transpose[FactorInteger[n]]]], {n, 2, 200}]

Here is a list of all prime factors,without multiplicity, as is used in the computation of the Euler phi function.

Table[First[Transpose[FactorInteger[n]]], {n, 2, 200}] // 
      TableForm

Selection of a number close to  10000

\(Remark : \ 
      we\ will\ see\ in\ the\ following\ section\ \((about\ Partitioning\ into\ blocks)\) 
        why\ it\ is\ useful\ to\ have\ a\ number\ slightly\ more\ than\ a\ power\ of\ 10. \ \)
\(The\ examples\ here\ are\ kept\ very\ small\ compared\ to\ the\ numbers\ \((close\ to\ \ \ 10\^60\ \ )\)\ used\ in\ the\ actual\ application . \ 
Here\ is\ how\ \*""" 
      good \*"""\ is\ \(\(programmed\)\(:\)\)\)

Clear[good]

good[n_] := 
      If[Length[FactorInteger[n]] == 2 && 
          Times @@ First[Transpose[FactorInteger[n]]] == n, True, 
        False]

In the list of all numbers from 9000 to a little over 10000 we select the last "good" ones by

Select[Range[9000, 10020], good];

Take[%, -5]

FactorInteger[%] // TableForm

Selection of complementary exponents

The pair 43 and  233 seem to be a good choice

p = 43; q = 233; n = p q

m = (p - 1) (q - 1)

FactorInteger[m] // TableForm

Look for invertible elements modulo  m  : these are precisely the ones relatively prime with  m  .

relPrime[k_]:=GCD[k, m]==1

invertibles = Select[Range[m], relPrime];

Length[%]

If we loopup de full list, we see 509 is a member. Look for the inverse of 509: the product has t o be 1 . 
Its position in the list of invertibles is

Position[Map[Mod[509 #, m] &, invertibles], 1]

This number is

invertibles[[1326]]

Mod[4805 509, m]

Avoid choosing self-invertible elements since it is bad practice to make choices that enable guessing the inverse

Position[Mod[(((invertibles))^2), m], 
      1]

These are

Select[Range[m], relPrime][[Flatten[%]]]

Length[%]

Therefore 2785 is a bad choice since

Mod[2785 2785, m]

We have found all such numbers.

Testing powers

Mod[100^4805, n]

Mod[%^509, n]

Mod[333^4805, n]

Mod[%^509, n]

Maybe it is better to choose 509 for encoding messages, and its inverse 4805 for decoding.
Choosing a decoding key in the middle of invertibles discourages running all first few thousand powers to crack the code.

Mod[2407^509, n]

Mod[%^4805, n]

Partitioning a number in blocks size 4 ( < 10000 )

Building a program

t = (3^200)

Clear[more]

\(more[{l_List, m_Integer}] := 
	
      If[m == 0, {l, 
          m}, 
		{Prepend[l, Mod[m, 10000]], \((m - Mod[m, 10000])\)/
            10000}]\)

more[more[{{}, t}]]

message = 
      First[Nest[more, {{}, t}, IntegerPart[Log[10000, t]] + 1]]

Send:

Mod[message^509, n]

Decode:

Mod[%^4805, n]

Plus @@ ((10000^Range)[0, Length[%] - 1] . Reverse[%])

% == t

Timing[Mod[message^509, n]]

Seems FAST!

Remark: the "PowerMod" command is even faster and useful for large powers.

General basis

Choose basis smaller than n

basis = 10001

Clear[more]

\(more[{l_List, m_Integer}] := 
	
      If[m == 0, {l, 
          m}, 
		{Prepend[l, Mod[m, basis]], \((m - Mod[m, basis])\)/
            basis}]\)

message = 
      First[Nest[more, {{}, t}, IntegerPart[Log[basis, t]] + 1]]

Send:

Mod[%^509, n]

Mod[%^4805, n]

Plus @@ ((basis^Range)[0, Length[%] - 1] . Reverse[%])

% == t

Different choices

basis = 994

message = 
      First[Nest[more, {{}, t}, IntegerPart[Log[basis, t]] + 1]]

Send:

Mod[%^509, n]

Mod[%^4805, n]

Plus @@ ((basis^Range)[0, Length[%] - 1] . Reverse[%])

% == t

If messages are  binary , use blocks which are a power of 2

basis = 4096

message = 
      First[Nest[more, {{}, t}, IntegerPart[Log[basis, t]] + 1]]

Send:

Mod[%^509, n]

Decode:

Mod[%^4805, n]

Check:

Plus @@ ((basis^Range)[0, Length[%] - 1] . Reverse[%])

% == t

Conclusion:

Both sending and receiving messages is handled by computing large powers.
The number  n  and the encrypting key (exponent) is made public so that senders can send encrypted messages, changing basis occasionally. 
The receiver knows   p, q, and the decripting key (exponent), which is the inverse of the encrypting key modulo (p-1) (q-1). 
To crack a code one needs to know the prime number decompostion of   n .

Exercises

Repeat with    n   somewhat bigger than   100000   and basis a power of  2

basis = 2^16

splitting binary message  in 16 bit blocks. 
Remark: do NOT write the complete multiplaction table .
Try to crack the code of your classmates.

Guessing how the PowerMod command works

Compare

Timing[Mod[(123456789^238145), 17]]

Timing[PowerMod[123456789, 238145, 17]]

Look up in the Help and other documentation which rules apply when working with Mod and powers.