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(xA,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(yB,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(xp–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.