246 15. A Glimpse of Complexity and Cryptography
15.3.2Alice modifies her suggestion as follows: instead of the random 0-1 se-
quence, she offers to use a random, but meaningful text as the key. For whom
would this be advantageous?
15.4 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 secret. But there is one weak point:
The computer of the bank must store the password, and the administrator
of this computer may learn it and later misuse it.
Complexity theory provides a scheme whereby the bank can verify that
the customer does indeed know the password—without storing the pass-
word itself! At first glance this looks impossible—just as the problem with
filing the last chess move was. And the solution (at least the one we discuss
here) uses the same kind of construction as our telephone chess example.
Suppose that the password is a 100-digit prime numberp(this is, of
course, too long for everyday use, but it illustrates the idea best). When
the customer chooses the password, he chooses another primeqwith 101
digits, forms the productN=pqof the two primes, and tells the bank the
numberN. When the teller machine is used, the customer tells his name
and the passwordp. The computer of the bank checks whether or notpis
a divisor ofN; if so, it acceptspas a proper password. The division of a
200 digit number by a 100 digit number is a trivial task for a computer.
Let us assume that the system administrator learns the numberNstored
along with the files of our customer. To use this in order to impersonate
the customer, he has to find a 100-digit number that is a divisor ofN;
but this is essentially the same problem as finding the prime factorization
ofN, and this is hopelessly difficult. So—even though all the necessary
information is contained in the numberN—the computational complexity
of the factoring problem protects the password of the customer!
15.5 How to Find These Primes
In our two simple examples of “modern cryptography,” as well as in almost
all the others, one needs large prime numbers. We know that there are
arbitrarily large primes (Theorem 6.4.1), but are there any with 200 digits,
starting with 1163 (or any other 4 given digits)? Maple found (in a few
seconds on a laptop!) the smallest such prime number: