SecretKeyExchange

<b>Merkle's idea</b> (1970s). Alice makes a large set $\{(i,x_i)\mid i=1,2,\dots,n\}$, where each $x_i$ is a secret key to be used for a cryptosystem (TDES, say). She then encodes each individual pair $(i,x_i)$ using a known method with a random key resulting in $c_i$. Finally, she sends the whole set $\{c_i\mid i=1,2,\dots,n\}$ to Bob, and inform him the encoding method used for making $c_i$'s. Certainly, Eve receives all the information as well. Now Bob picks randomly one $c_i$. He spends some time to decode it using brute force, and obtains the pair $(i,c_i)$. He then inform Alice that he will use the key associated to the serial number $i$ (namely, $c_i$) to encode a message for her. When Alice receives the message, she simply uses $c_i$ to decode it. Note that Eve cannot know the serial number $i$ without decoding $c_i$ (it is not marked on the face of $c_i$!), and so she has to decode, in the worst case, ALL $c_i$'s by brute force to find $x_i$ that Bob has chosen.

<b>Diffie-Hellman-merkle key agreement.</b> This method uses Discrete Logarithm to realize Merkle's idea. First Alice and Bob agree upon (publicly) a prime $p$, and a primitive element $g$ for the field $\mathbb Z_p$. Thus, $\{g, g^2\bmod p, \dots, g^{p-1}\bmod p\}$ is exactly the set $\{1,2,\dots,p-1\}$. Now, Alice chooses an $a\in\{1,2,\dots,p-1\}$ randomly, and Bob chooses a $b\in\{1,2,\dots,p-1\}$. Then they compute $g^a\bmod p$, $c$ say, and $g^b\bmod p$, $d$ say, and exchange the results (publicly). With the numbers exchanged, they then compute $d^a\equiv g^{ba}\bmod p$ and $c^b\equiv g^{ab}\bmod p$; and they only exchange the opinion whether they agree with the number $g^{ab}\bmod p$ as the key or not. If not, the process gets repeated till an agreement is reached.

In this process, Alice and Bob each only computes powers modulo $p$ twice, which is rather easy even when $p$ is large. But if Eve wants to get the numbers $a$ and $b$ from $c$ and $d$, she has to solve the discrete logarithms $g^x\equiv c\pmod p$ and $g^x\equiv d\pmod p$. There is still no good way of solving these equations yet. Of course, Eve can do it using brute force by making the table $a_1=g$, $a_2\equiv g^2\pmod p$, $\dots$, $a_{p-1}\equiv g^{p-1}\pmod p$. But this is not feasible when $p$ is large.