RSA Encryption Algorithm, a simple example.pdf

(34 KB) Pobierz
RSA Encryption Algorithm, by spreadsheet - Joe Wilkinson
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
prime2
n
= prime1 * prime2
dp
= decremented_product
7
11
77
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:
file:///C|/Documents%20and%20Settings/mwood/Desktop/...20Encryption%20Algorithm,%20a%20simple%20example.htm (1 of 4)8/1/2006 1:56:28 AM
RSA Encryption Algorithm, by spreadsheet - Joe Wilkinson
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
M^13
M^13 MOD 77
OutGoing
1
1
1
1
2
8192
30
30
3
1594323
38
38
4
5
67108864 1220703125
53
53
26
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
=M^37
M^37 MOD 77
1
1
1
30
4.50 E+54
#NUM!
38
2.83 E+58
#NUM!
53
6.28 E+63
#NUM!
26
2.25 1E+52
#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:
file:///C|/Documents%20and%20Settings/mwood/Desktop/...20Encryption%20Algorithm,%20a%20simple%20example.htm (2 of 4)8/1/2006 1:56:28 AM
RSA Encryption Algorithm, by spreadsheet - Joe Wilkinson
Incoming
=M^2
=M^2 MOD 77
=M^3 MOD 77
=M^4 MOD 77
=M^5 MOD 77
=M^6 MOD 77
=M^7 MOD 77
=M^8 MOD 77
=M^9 MOD 77
=M^10 MOD 77
=M^11 MOD 77
=M^12 MOD 77
=M^13 MOD 77
=M^14 MOD 77
=M^15 MOD 77
=M^16 MOD 77
=M^17 MOD 77
=M^18 MOD 77
=M^19 MOD 77
=M^20 MOD 77
=M^21 MOD 77
=M^22 MOD 77
=M^23 MOD 77
=M^24 MOD 77
=M^25 MOD 77
=M^26 MOD 77
=M^27 MOD 77
=M^28 MOD 77
=M^29 MOD 77
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
30
900
53
50
37
32
36
2
60
29
23
74
64
72
4
43
58
46
71
51
67
8
9
39
15
65
25
57
16
18
38
1444
58
48
53
12
71
3
37
20
67
5
36
59
9
34
60
47
15
31
23
27
25
26
64
45
16
69
4
75
53
2809
37
36
60
23
64
4
58
71
67
9
15
25
16
1
53
37
36
60
23
64
4
58
71
67
9
15
25
16
26
676
60
20
58
45
15
5
53
69
23
59
71
75
25
34
37
38
64
47
67
48
16
31
36
12
4
27
9
3
file:///C|/Documents%20and%20Settings/mwood/Desktop/...20Encryption%20Algorithm,%20a%20simple%20example.htm (3 of 4)8/1/2006 1:56:28 AM
RSA Encryption Algorithm, by spreadsheet - Joe Wilkinson
=M^30 MOD 77
=M^31 MOD 77
=M^32 MOD 77
=M^33 MOD 77
=M^34 MOD 77
=M^35 MOD 77
=M^36 MOD 77
=M^37 MOD 77
1
1
1
1
1
1
1
1
1
30
53
50
37
32
36
2
1
38
58
48
53
12
71
3
1
53
37
36
60
23
64
4
1
26
60
20
58
45
15
5
The last line gives back the original message, .
decrypted
1
2
3
4
5
Now dowload the
Excel Spreadsheet
and investigate more values
file:///C|/Documents%20and%20Settings/mwood/Desktop/...20Encryption%20Algorithm,%20a%20simple%20example.htm (4 of 4)8/1/2006 1:56:28 AM

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin