public key encryption

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,

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:

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

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