15.3 How to Save the Last Move in Chess 245Next, Alice extends the four digits describing her move to a prime number
p= 1163...with 200 digits. She also generates another primeqwith 201
digits and computes the productN=pq(this would take rather long on
paper, but is trivial using a personal computer). The result is a number
with 400 or 401 digits; she sends this number to Bob.
Next morning, she sends both prime factorspandqto Bob. He recon-
structs Alice’s move from the first four digits of the smaller prime. To make
sure that Alice was not cheating, he should check thatpandqare primes
and that their product isN.
Let us argue that this protocol does the job.
First, Alice cannot change her mind overnight. This is because the num-
berNcontains all the information about her move: This is encoded as the
first four digits of the smaller prime factor ofN. So Alice commits herself
to the move when sendingN.
But exactly because the numberNcontains all the information about
Alice’s move, Bob seems to have the advantage, and he indeed would have
if he had unlimited time or unbelievably powerful computers. What he has
to do is to find the prime factors of the numberN. But sinceNhas 400
digits (or more), this is a hopelessly difficult task with current technology.
Can Alice cheat by sending a different pair (p′,q′) of primes the next
morning? No, because Bob can easily compute the productp′q′, and check
that this is indeed the numberNthat was sent the previous night. (Note
the role of theuniquenessof prime factorization, Theorem 6.3.1.)
All the information about Alice’s move is encoded in the first 4 digits of
the smaller prime factorp. We could say that the rest ofpand the other
prime factorqserve as a “deposit box”: This box hides this information
from Bob, and it can be opened only if the appropriate key (the factoriza-
tion ofN) is available. The crucial ingredient of this scheme iscomplexity:
the computational difficulty to find the factorization of an integer.
With the spread of electronic communication in business, many solutions
of traditional correspondence and trade must be replaced by electronic
versions. We have seen an electronic “deposit box” above. Other schemes
(similar or more involved) can be found for electronic passwords, autho-
rization, authentication, signatures, watermarking, etc. These schemes are
extremely important in computer security, cryptography, automatic teller
machines, and many other fields. The protocols are often based on simple
number theory; in the next section we discuss (a very simplified version of)
one of them.
15.3.1Motivated by the one-time pad method, Alice suggests the following
protocol for saving the last move in their chess game: In the evening, she encrypts
her move (perhaps with other text added, to make it reasonably long) using
a randomly generated 0-1 sequence as the key (just like in the one-time pad
method). The next morning she sends the key to Bob, so that he can decrypt the
message. Should Bob accept this suggestion?