15.2 Classical Cryptography 243First, he has to convert it to 0’s and 1’s. It is not clear that medieval kings
had the knowledge to do so, but the reader should be able to think of
various ways: using ASCII codes, or Unicodes of the letters, for example.
But we want to keep things simple, so we just number the letters from 1 to
26, and then write down the binary representation of the numbers, putting
0’s in front so that we get a string of length 5 for each letter. Thus we have
“00001” for A, “00010” for B, etc. We use “00000” for “space.” The above
message becomes
00001100101001000001000110101100000011010111101110001000000111001
This might look cryptic enough, but Caligula (or rather one of the excellent
Greek scientists he keeps in his court as slaves) could easily figure out what
it stands for. To encrypt it, Arthur adds the one-time pad to the message
bit-by-bit. To the first bit of the message (which is 0) he adds the first
bit of the pad (1) and writes down the first bit of the encoded message:
0 ⊕1 = 1. He computes the second, third, etc., bits similarly: 0⊕1=1,
0 ⊕0 = 0, 0⊕0=0,1⊕0 = 1, 1⊕1=0,.... (Note that he uses this
strange addition from the 2-element field, for which 1⊕1 = 0.) Another
way of saying what King Arthur does is the following: if thek-th bit of the
pad is 1, he flips thek-th bit of the text; else, he leaves it as it was.
So Arthur computes the encoded message:
11001011101011000111010010001000101111100101000010000110110111011
He sends this to King Bela, who, using the one-time pad, can easily flip
back the appropriate bits, and recover the original message.
But Caligula does not know the one-time pad (nor do his excellent scien-
tists), so he has no idea about which bits were flipped, and so he is helpless.
The message is safe.
It can be expensive to make sure that the sender and the receiver both
have such a common key; but note that the key can be sent at a safer time
and by a completely different method than the message (moreover, it may
be possible to agree on a key even without actually passing it; but this
would lead us too far into cryptography).
Once the Kings managed to pass the key to each other, it is tempting
to reuse it; after all, if Bela encrypts his reply by the same pad, it is still
completely random-looking. In solving exercises 15.2.2 and 15.2.3 you will
see that this is not a good idea, along with some other weaknesses of the
one-time pad method.
15.2.1For the following message, the kings used substitution code. Caligula
intercepted the message and quite easily broke it. Can you do it too?
U GXUAY LS ZXMEKW AMG TGGTIY HMD TAMGXSD LSSY,
FEG GXSA LUGX HEKK HMDIS. FSKT