Public Key Encryption
the RSA
algorithm
To design a set of encryption and decryption keys, you choose three integers: p, q, and m, where p and q are primes. For example,
p = 2, q = 11, m = 2.
Then compute an intermediate number c = m·(p – 1)(q – 1) + 1, which gives c = 21 in this case. Choose a factor A of c such as A = 7. This is part of the public encryption key. The other part is N = p·q, or N = 22 here.
You give all your friends the numbers A and N to encrypt messages to you. They perform the encryption as follows: They express the message as a series of numbers which are all less than N. Let x be one of those numbers. The number x is encrypted to form a number y by the following process:
y(x) = mod(x^{A},N)
where mod(e,N) is the remainder after as many Ns as possible are subtracted from e. For example, mod(47,22) = 3. For our example with A = 7 and N = 22, encrypting x from 0 to 21 gives the following results:
x |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
y(x) |
0 |
1 |
18 |
9 |
16 |
3 |
8 |
17 |
2 |
15 |
10 |
11 |
12 |
7 |
20 |
5 |
14 |
19 |
6 |
13 |
4 |
21 |
You receive the message as a series of ys. You decrypt each y back to its original x by using a decryption key, which you keep secret. The decryption key is N (which everybody knows) and B = c/A, which only you can calculate because only you (the designer of the keys) knows the number c = m·(p – 1)(q – 1) + 1. The decryption algorithm is
x(y) = mod(y^{B},N).
where B = 21/7 = 3 in our example. We can show that this algorithm, applied to y from 0 to 21 gives back the original xs:
y |
0 |
1 |
18 |
9 |
16 |
3 |
8 |
17 |
2 |
15 |
10 |
11 |
12 |
7 |
20 |
5 |
14 |
19 |
6 |
13 |
4 |
21 |
x(y) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
The reason that the decryption algorithm "undoes" the encryption algorithm depends on Fermat's Little Theorem, which states that mod(x^{p–1},p) = 1 for all integers x when p is prime. For instance, for p = 7 and x = 2, mod(64,7) = 1. Public key encryption becomes effective as the primes p and q become so large that it is practically impossible to factor N to recover p and q. Then no one can discover B from knowledge of A and N.
Problem: A sender encodes a message in 7-bit ASCII, putting them end-to-end to form one long series of 1s and 0s. Then he forms groups of 5-bit numbers and encrypts them using the public key A = 7 and N = 33. He puts the 5-bit encrypted number end-to-end to form one long series of 1s and 0s, and he sends this encrypted message. You intercept the message and see (scroll to the right):
01101101100110101000100111010100000111111100000100110101000100011111000101000110000010011001100101110100110011101100110110010101000110101111000111100010011110011010000100000100010111011110101100111001
Suppose you know the public key A = 7 and N = 33. Can you figure out the secret key B and decrypt the message? (ASCII code below)
32 = space 33 = ! 34 = " 35 = # 36 = $ 37 = % 38 = & 39 = ' 40 = ( 41 = ) 42 = * 43 = + 44 = , 45 = - 46 = . 47 = / |
48 = 0 49 = 1 50 = 2 51 = 3 52 = 4 53 = 5 54 = 6 55 = 7 56 = 8 57 = 9 58 = : 59 = ; 60 = < 61 = = 62 = > 63 = ? |
64 = @ 65 = A 66 = B 67 = C 68 = D 69 = E 70 = F 71 = G 72 = H 73 = I 74 = J 75 = K 76 = L 77 = M 78 = N 79 = O |
80 = P 81 = Q 82 = R 83 = S 84 = T 85 = U 86 = V 87 = W 88 = X 89 = Y 90 = Z 91 = [ 92 = \ 93 = ] 94 = ^ 95 = _ |
96 = ' 97 = a 98 = b 99 = c 100 = d 101 = e 102 = f 103 = g 104 = h 105 = i 106 = j 107 = k 108 = l 109 = m 110 = n 111 = o |
112 = p 113 = q 114 = r 115 = s 116 = t 117 = u 118 = v 119 = w 120 = x 121 = y 122 = z 123 = { 124 = | 125 = } 126 = ~ 127 = blank |
More difficult problem: A message in 7-bit ASCII is encrypted with the public key A = 2821 and N = 16850989 resulting in the following encrypted message (scroll to the right):
111110010110010101010111010001001110001000101110000010010101001101101001000010110010000001010111110011110011001101100000000011101100101101001110010101011001011101011010100011101010110010011000100111000111100101111111
How many bits at a time were encrypted for this N? Find the secret key B, and decrypt the message. Use the fact that
mod(d·e,N) = mod[mod(d,N)·mod(e,N),N]
to keep your computer from overflowing when raising y to a large power.