244 15. A Glimpse of Complexity and Cryptography
15.2.2At one time, Arthur made the mistake of using the one-time pad shifted:
The first bit of the plain text he encoded using the second bit of the pad, the
second bit of the plain text he encoded using the third bit of the pad etc. He
noticed his error after he sent the message off. Being afraid that Bela would
not understand his message, he encoded it again (now correctly) using the same
one-time pad, and sent it to Bela by another courier, explaining what happened.
Caligula intercepted both messages, and was able to recover the plain text.
How?
15.2.3The Kings were running low on one-time pads, and so Bela had to use
the same pad to encode his reply as they used for Arthur’s message. Caligula
intercepted both messages, and was able to reconstruct both plain texts. How?
15.3 How to Save the Last Move in Chess
Modern cryptography started in the late 1970’s with the idea that it is not
only lack of information that can protect our message against an unautho-
rized eavesdropper, but also thecomputational complexityof processing it.
The idea can be illustrated by the following simple example.
Alice and Bob are playing chess over the phone. They want to interrupt
the game for the night; how can they do it so that the person to move should
not get the improper advantage of being able to think about his move the
whole night? At a tournament, the last move is not made on the board,
only written down, put in an envelope, and deposited with the referee. The
next morning, the envelope is opened, and the other player learns what
the move was as his clock begins to run. But now the two players have no
referee, no envelope, no contact other than the telephone line. The player
making the last move (say, Alice) has to send Bob some message. The
next morning (or whenever they continue the game) she has to give some
additional information, some “key,” which allows Bob to reconstruct the
move. Bob should not be able to reconstruct Alice’s move without the key;
Alice should not be able to change her mind overnight and modify her
move.
Surely, this seems to be impossible! If she gives enough information the
first time to uniquely determine her move, Bob will know the move too
soon; if the information given the first time allows several moves, then she
can think about it overnight, figure out the best among these, and give the
remaining information, the “key,” accordingly.
If we measure information in the sense of classical information theory,
then there is no way out of this dilemma. But complexity comes to our help:
it is not enough tocommunicateinformation, it must also beprocessed.
So here is a solution to the problem, using elementary number theory!
(Many other schemes can be designed.) Alice and Bob agree to encode
every move as a 4-digit number (say, ‘11’ means ‘K’, ‘6’ means ‘f’, and ‘3’
means itself, so ‘1163’ means ‘Kf3’). So far, this is just notation.