by Neal R. Wagner
Copyright © 2001 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
Imagine that person A (``Alice'') wants to establish secure communication with a distant individual B (``Bob''). Alice and Bob have made no previous arrangements and can only communicate over a public channel that anyone can listen in on. Another person (``Boris'') listens to all their communications and has more computing power than they have. Also Alice and Bob have no special secret methods not known to Boris. However, Boris can only listen in and cannot change messages. In spite of all this, it is still possible for the two of them to establish secure communication that Boris cannot understand. This surprising technique was developed by R.C. Merkle before the introduction of true public key cryptography. It helps prepare students of cryptography for even more surprising methods.
Alice and Bob must be able to create ``puzzles'' that are hard but not impossible to solve. For example, they could agree that all but the low 50 bits of a 128-bit AES key would be zero bits. Then they could encrypt two blocks of information with this key. A brute-force breaking of the ``puzzle'' would mean trying 249 keys on the average. The encrypted information would also start with a block of zero bits, so that they can tell when the puzzle is broken. Suppose it takes Alice and Bob an hour of computer time to break one of these puzzles. It is important to emphasize that Boris also knows exactly how the puzzles are constructed. Suppose Boris has a much more powerful computer and can break a puzzle in just one minute.
Bob creates 14400 of these puzzles, each containing a 128-bit random key in one block and a sequence number identifying the puzzle (a number from 1 to 14400 in binary with leading zeros to make it 128 bits long). Bob transmits all of these puzzles to Alice, in random order. Alice chooses one puzzle at random and breaks it in one hour. She then keeps the random key and sends the sequence number back to Bob. (Boris listens in to this sequence number, but it does him no good because he doesn't know which number goes with which puzzle.) Bob has saved the content of the puzzles (or has generated them pseudo-randomly) so that he can look up the sequence number and find the same random key that Alice has. Boris, their opponent, must break half of the puzzles on the average to recover the common key that Alice and Bob are using. Even with his much faster machines, it still takes Boris 14400/2 minutes or 5 days on the average to break Alice and Bob's system. Thus Alice and Bob get 5 days of secret communications. If they want more time, say 50days, then Bob just needs to send ten times as many messages initially, that is, 144000. If the disparity between their computing power and that of the listeners is even greater, then again Bob must simply send more puzzles initially.
If Boris can actually alter messages (change or inject or delete them) as well as listening in, then he might pretend to be Alice and communicate with Bob, or vice versa. In this case Alice and Bob must be able to describe shared experiences or to communicate shared information to one another to be sure they are not communicating with a stranger (Boris).
If Boris can intercept and change all messages between Alice and Bob, then he could answer both Alice's and Bob's requests to communicate, and pretend to be each to the other. Once Boris has secure communication established with both Alice and Bob, he could relay messages back and forth between them, translating between the two cryptosystems. Then even if they authenticated each other, he would still be listening in. This is called a man-in-the-middle attack. In this extreme case, the method does not work. This shows the great care that must be taken with cryptographic protocols.
Alice and Bob still want to communicate securely, without having set it up ahead of time, but they would like a simpler and more mathematical system. The ground rules are the same as above: Boris listens in, knows everything they know, and has more computing power.
If they each had their own secret commuting cipher, say Alice had EA and Bob had EB, then, using a common public integer a, Alice could send EA(a) to Bob, and Bob could send EB(a) to Alice. Then Alice computes EA(EB(a)) and Bob computes EB(EA(a)). Because the two ciphers commute, these quantities are the same. The two people can use this common value or a portion of it to make up a secret key for conventional crytography. If Boris can't break the cipher, he has no way of knowing this secret value.
Actually, in this system, all that is needed is secret commuting one-way functions, a topic for a later section.
It is a fact that cryptosystems almost never commute. The next secion describes the only exception I know of.
One can imagine a cryptosystem in which a fixed number is raised to a power equal to the plaintext modulo a fixed prime, yielding the ciphertext. (There is a cryptosystem called the Pohlig-Hellman System similar to this but a bit more complicated.) So one fixes a (large) prime p and an integer a that is a generator for multiplication in the field Zp. (For this generator, see the section on Fermat's Theorem in the ``Favorites'' chapter.) From a message M, calculate a ciphertext C by:
C = aM mod p
If the quantities above were ordinary real numbers, and the equation were C = aM, then solving for M would give M = logaC, the ``logarithm base a of C''. Because of this notation from real numbers, one also refers to M above as the ``discrete logarithm of C to base a modulo p''. It turns out that it seems to be hard computationally to calculate discrete logarithms, even knowing C, a, and p. Using a brute force approach, one could just try all possible values of M, but there are ways to do better than this, including a ``meet-in-the-middle'' approach described below. But if the prime p is large and random, there is no efficient algorithm.
With this system, Alice and Bob work with a large public prime p, and a public generator a. Alice chooses a secret integer A, while Bob chooses a secret B. Alice sends aA mod p to Bob, and Bob sends aB mod p to Alice. Then in secret, Alice computes (aB)A mod p = a(B*A) mod p. Similarly in secret, Bob computes (aA)B mod p = a(A*B) mod p, and these two quantities are the same, a common secret value that they can use for further communication. Boris listening in cannot compute either A or B, and cannot discover this common secret.
Just as with the Merkle puzzles, if Boris can do more than listen in on the communcations, he could pretend to be Alice to Bob or vice versa, and he could even use a man-in-the-middle attack to make Alice and Bob think they are communicating in secret when they are not. There are more elaborate methods involving autheticated public keys that both Alice and Bob have, and these methods allow them to establish a common secret key even in the presence of an active opponent like Boris.
In order to set up a practical system as above, first choose a ``large enough'' random integer n (where the size needed depends on how fast the computers have become and on whether there has been progress in computing discrete logs). Then test the numbers n, n+1, n+2, etc., until the next prime q is found. Finally test 2*q + 1 to see if it is prime. If it is not a prime, start over again with another random n. Finally, one will have a prime p with the property that p - 1 = 2*q, for a slightly smaller prime q. In order to get a generator, choose an a at random, or start with a = 2. Check this a to see if a2 mod p = 1 or if aq mod p = 1. When an a doesn't satify either of these, one knows the value is a generator, and can be used for key distibution. (A random a would also probably work, but not for sure.)