Agreeing on a secret in public
Tonight's idea
Alice and Bob want a shared secret number, but they can only talk in public, and Eve hears every word. A cipher is no help yet: it needs a key, and the key is exactly what they lack.
In public they agree on a prime, \(p = 23\), and a base, \(g = 5\). Alice picks a secret number \(a\) and shouts \(A = 5^a \bmod 23\), where \(\bmod 23\) means "the remainder after dividing by 23" (clock arithmetic). Bob picks a secret \(b\) and shouts \(B = 5^b \bmod 23\).
Alice computes \(B^a \bmod 23\) and Bob computes \(A^b \bmod 23\). They get the same number, by the exponent laws:
\(B^a = (5^b)^a = 5^{ab} = (5^a)^b = A^b\), and taking remainders along the way does not change the final remainder.
Eve knows 23, 5, 8 and 19. To get the secret she needs \(a\) or \(b\): which power of 5 leaves remainder 8? With \(p = 23\) she can try all 22 powers in a minute. Real systems use a prime of about 600 digits. Going forwards, from \(a\) to \(5^a \bmod p\), is still quick (see the stretch); going backwards, nobody knows a shortcut, and the search is hopeless. That one-way gap is the whole idea. Diffie and Hellman published it in 1976, and a version of it runs every time your browser opens a secure connection.
Watch one: \(a = 6\), \(b = 15\)
Alice needs \(5^6 \bmod 23\). Multiply by 5 and take the remainder each time, so the numbers stay small:
\[5,\; 25 \to 2,\; 10,\; 50 \to 4,\; 20,\; 100 \to 8.\]
So \(A = 8\). Bob finds \(B = 5^{15} \bmod 23 = 19\) the same way. Alice now computes \(19^6 \bmod 23\): \(19^2 = 361 \to 16\), then \(19^4 = 16^2 = 256 \to 3\), then \(19^6 = 3 \times 16 = 48 \to 2\). Bob computes \(8^{15} \bmod 23\) and also gets 2. The shared secret is 2.
For contrast, a code that needs its key handed over in secret: mathdetours.com/demos/vigenere.html.
Your turn
- Continue the chain in the example to list \(5^1, 5^2, \ldots, 5^8 \bmod 23\). Check that \(5^6\) gives 8.
- A smaller room: \(p = 11\), \(g = 2\). Alice's secret is \(a = 4\), Bob's is \(b = 8\). Find what each shouts, then compute the shared secret both ways and check they agree.
- Be Eve. With \(p = 11\) and \(g = 2\) you overhear \(A = 9\) and \(B = 7\). List the powers of 2 mod 11 until you find \(a\) and \(b\), then compute the secret.
- Now \(p = 7\). (a) List \(2^1, 2^2, \ldots, 2^6 \bmod 7\) and \(3^1, 3^2, \ldots, 3^6 \bmod 7\). (b) If Alice and Bob used \(g = 2\), how many different numbers could ever be shouted? Why is that good news for Eve? (c) Which base should they use, and what makes it better?
Stretch: powering fast
Compute \(5^2, 5^4, 5^8, 5^{16} \bmod 23\) by squaring the previous answer each time. Then find \(5^{20} \bmod 23\) with one more multiplication. A 600-digit exponent has about 2,000 binary digits. Roughly how many multiplications does Alice need, instead of \(10^{600}\)?
Answers
- \(5, 2, 10, 4, 20, 8, 17, 16\). (Continued, the list reaches every remainder from 1 to 22 before returning to 1 at \(5^{22}\).)
- \(A = 2^4 \bmod 11 = 16 \bmod 11 = 5\). \(B = 2^8 \bmod 11\): \(2^4 \to 5\), so \(2^8 \to 25 \to 3\). Alice: \(3^4 = 81 \to 4\). Bob: \(5^8 = (5^4)^2\); \(5^4 = 625 \to 9\), and \(81 \to 4\). Secret 4.
- Powers of 2 mod 11: \(2, 4, 8, 5, 10, 9, 7, 3, 6, 1\). So \(a = 6\) and \(b = 7\). Secret: \(7^6 \bmod 11\), with \(7^2 \to 5\), \(7^4 \to 3\), \(7^6 \to 15 \to 4\). Check: \(9^7 \bmod 11 = 4\) too.
- (a) Powers of 2: \(2, 4, 1, 2, 4, 1\). Powers of 3: \(3, 2, 6, 4, 5, 1\). (b) Only three numbers (2, 4, 1) can ever be shouted, so Eve needs at most three guesses to find an exponent that works. (c) Use \(g = 3\): its powers hit every remainder from 1 to 6, so there are six possibilities instead of three. A base whose powers reach everything is called a generator; 5 is a generator mod 23, which is why the list in question 1 goes on for 22 steps.
Stretch. \(5^2 \to 2\), \(5^4 \to 4\), \(5^8 \to 16\), \(5^{16} \to 256 \to 3\). Then \(5^{20} = 5^{16} \times 5^4 \to 3 \times 4 = 12\). Each squaring doubles the exponent, so about 2,000 squarings reach a 2,000-bit exponent, plus at most 2,000 extra multiplications to fill in the binary digits: around 4,000 multiplications of 600-digit numbers, which a phone does in a blink. Eve, with no shortcut, faces something like \(10^{600}\) trials.