[ Pobierz całość w formacie PDF ]

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
118
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 to communicate
information, it must also be processed.
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.
Next, Alice extends the four digits describing her move to a prime number p = 1163...
with 200 digits. She also generates another prime q with 201 digits and computes the
product N = 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 factors p and q to Bob. He reconstructs Alice s
move from the first four digits of the smaller prime. To make sure that Alice was not
cheating, he should check that p and q are primes and that their product is N.
Let us argue that this protocol does the job.
First, Alice cannot change her mind overnight. This is because the number N contains
all the information about her move: this is encoded as the first four digits of the smaller
prime factor of N. So Alice commits herself to the move when sending N.
But exactly because the number N contains 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
number N. But since N has 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 product p q , and check that this is indeed the number
N that was sent the previous night. (Note the role of the uniqueness of prime factorization,
Theorem 8.1.)
All the information about Alice s move is encoded in the first 4 digits of the smaller
prime factor p. We could say that the rest of p and the other prime factor q serve as
a  deposit box : they hide this information from Bob, and can be opened only if the
appropriate key (the factorization of N) is available. The crucial ingredient of this scheme
is complexity: 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 elec-
tronic  deposit box above. Other schemes (similar or more involved) can be found for
electronic passwords, authorization, authentication, signatures, watermarking, etc. These
schemes are extremely important in computer security, cryptography, automatic teller ma-
chines, 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.
119
16.2 How to verify a password without learning it?
In a bank, a cash machine works by name and password. This system is safe as long as the
password is kept in secret. But there is one week point in security: the computer of the
bank must store the password, and the administrator of this computer may learn it and
later misuse it. [ Pobierz całość w formacie PDF ]