Ross Anderson - Security Engineering

		= 5	(mod 7)
=	25	4	(mod 7)
	4 x 5	6	(mod 7)
	6 x 5	2	(mod 7)
	2 x 5	3	(mod 7)
	3 x 5	1	(mod 7)

Figure 5.17 : Example of discrete logarithm calculations

Imagine we're back in ancient Rome, that Anthony wants to send a secret to Brutus, and the only communications channel available is an untrustworthy courier (say, a slave belonging to Caesar). Anthony can take the message, put it in a box, padlock it, and get the courier to take it to Brutus. Brutus could then put his own padlock on it too, and have it taken back to Anthony. He in turn would remove his padlock, and have it taken back to Brutus, who would now at last open it.

Exactly the same can be done using a suitable encryption function that commutes, that is, has the property that . Alice can take the message and encrypt it with her key to get which she sends to Bob. Bob encrypts it again with his key getting . But the commutativity property means that this is just , so Alice can decrypt it using her key getting . She sends this to Bob and he can decrypt it with , finally recovering the message .

How can a suitable commutative encryption be implemented? The one-time pad does indeed commute, but is not suitable here. Suppose Alice chooses a random key and sends Bob while Bob returns and Alice finally sends him , then an attacker can simply exclusive-or these three messages together; as = 0 for all , the two values of and both cancel out, leaving the plaintext .

The discrete logarithm problem comes to the rescue. If the discrete log problem based on a primitive root modulo is hard, then we can use discrete exponentiation as our encryption function. For example, Alice encodes her message as the primitive root , chooses a random number , calculates modulo and sends it, together with , to Bob. Bob likewise chooses a random number and forms modulo p, which he passes back to Alice. Alice can now remove her exponentiation: using Fermat's theorem, she calculates and sends it to Bob. Bob can now remove his exponentiation, too, and so finally gets hold of . The security of this scheme depends on the difficulty of the discrete logarithm problem. In practice, it can be tricky to encode a message as a primitive root; but there's a simpler way to achieve the same effect.