RSA Encryption Algorithm, a simple example

Joe Wilkinson

The security of RSA Encryption depends on these principles:
that any data - text, numbers, pictures, etc. can be represented as numbers
that very large numbers are very difficult to factorise
that a mathematical process exists to allow encrypting and decrypting numbers
This page takes you through the process - the links above take you to explanations.
To download an Excel spreadsheet to play with the process pick here - Zipped version, for speed or for download malfunctions

Required Numbers for the Process

First two prime numbers are chosen. The lowest ones that show the whole process are 7 and 11
From these are calculated their product, and also their "decremented_product", i.e the product of each decremented by 1
 
prime1
7
prime2
11
n = prime1 * prime2
77
dp = decremented_product
60

Public key calculation:

The "keys" used to lock and unlock the data are pairs of numbers, (e,n) and (d,n) where "e" stands for encryption and "d" for decryption.
'e' is a number chosen to be less than, and which shares no factors with, the decremented_product, dp=60
It is often prime but does not have to be; clearly no even number will do, however. In this case the value 13 works
So the receiver has created a public key (13, 77) and publishes it to the world

Using this public key anyone encrypt messages using the process below and safely transmit them to the receiver.  No one can decrypt the message unless they can calculate the private key, which requires them to know the factors, because they must use the value dp. So the message is secure until the value of 'n' is factorised, when the messages can be decrypted. (In this case, of course factorising 77 is easy).

Private key calculation:

n =77, is known but to calculate 'd', the prime factors of 'n': 7 and 11 are needed to get the product because
'd' is an integer that obeys the equation: d*e MOD dp = 1,
in this case: d * 13 MOD 60 = 1
This equation says that if d is multipled by e and divided by the value dp, the remainder is 1.
In this case the smallest value of d which which does this is 37 since
37 * 13 = 481
and
481/60 = 8, remainder 1

Encrypting a message,

Now we have calculated n, dp, e and d.
Messages sent to the receiver are encrypted by the transmitter according to the formula:
C = M^e MOD n
where M represents a message unit (e.g a byte) and C the corresponding Cypher unit.
i.e. each byte is raised to the power e, and the remainder found when the result is divided by n
Done directly in Excel only the numbers between 0 and 5 work. This is because 6^13 is too big for Excel to be able to process as a whole number, and therefore the MOD function does not work.
(For real messages some very large numbers must be calculated, but as shown below in decrypting, there is a way of keeping the values manageable by doing the calculation in stages).

For example the Message 12345 is broken into Message units:
 

Message Units
1
2
3
4
5
M^13
1
8192
1594323
67108864
1220703125
M^13 MOD 77
1
30
38
53
26
OutGoing
1
30
38
53
26

And these are then sent. Note that neither 0 nor 1 cannot be encrypted, since raising either to any positive integer power does not change them.

To decrypt the message the reverse has to be done. Trying this directly in Excel does not work; if 6^13 is too big, then 30^37 is much too big and gives a #NUM error!.
 

Incoming
1
30
38
53
26
=M^37
1
4.50 E+54
2.83 E+58
6.28 E+63
2.25 1E+52
M^37 MOD 77
1
#NUM!
#NUM!
#NUM!
#NUM!
However, since it is a MODULUS process it can be tackled in stages, but each time finding the remainder after division by 77. The full table looks like this:
 
Incoming
1
30
38
53
26
=M^2
1
900
1444
2809
676
=M^2 MOD 77
1
53
58
37
60
=M^3 MOD 77
1
50
48
36
20
=M^4 MOD 77
1
37
53
60
58
=M^5 MOD 77
1
32
12
23
45
=M^6 MOD 77
1
36
71
64
15
=M^7 MOD 77
1
2
3
4
5
=M^8 MOD 77
1
60
37
58
53
=M^9 MOD 77
1
29
20
71
69
=M^10 MOD 77
1
23
67
67
23
=M^11 MOD 77
1
74
5
9
59
=M^12 MOD 77
1
64
36
15
71
=M^13 MOD 77
1
72
59
25
75
=M^14 MOD 77
1
4
9
16
25
=M^15 MOD 77
1
43
34
1
34
=M^16 MOD 77
1
58
60
53
37
=M^17 MOD 77
1
46
47
37
38
=M^18 MOD 77
1
71
15
36
64
=M^19 MOD 77
1
51
31
60
47
=M^20 MOD 77
1
67
23
23
67
=M^21 MOD 77
1
8
27
64
48
=M^22 MOD 77
1
9
25
4
16
=M^23 MOD 77
1
39
26
58
31
=M^24 MOD 77
1
15
64
71
36
=M^25 MOD 77
1
65
45
67
12
=M^26 MOD 77
1
25
16
9
4
=M^27 MOD 77
1
57
69
15
27
=M^28 MOD 77
1
16
4
25
9
=M^29 MOD 77
1
18
75
16
3
=M^30 MOD 77
1
1
1
1
1
=M^31 MOD 77
1
30
38
53
26
=M^32 MOD 77
1
53
58
37
60
=M^33 MOD 77
1
50
48
36
20
=M^34 MOD 77
1
37
53
60
58
=M^35 MOD 77
1
32
12
23
45
=M^36 MOD 77
1
36
71
64
15
=M^37 MOD 77
1
2
3
4
5

The last line gives back the original message, .
 

decrypted
1
2
3
4
5
Now dowload the Excel Spreadsheet and investigate more values