Diffie-Hellman: agreeing on a secret over a public channel (1976)

Diffie and Hellman showed that two people can reach the same secret by exchanging only public values: each raises the other’s public element to their own private exponent, and both arrive at g**(a*b). An eavesdropper sees g**a and g**b but would need a discrete logarithm to continue.

What to look for

Both parties compute the same shared element without ever sending it. Then a man in the middle substitutes his own public value: the arithmetic still works, but Alice now shares a secret with Mallory. Agreement on a secret is not authentication of the other person.

The history behind this experiment: Breakthroughs in Cryptography. See Exercises: cryptography for a worked solution to the exercise.

Agree on a shared group element

Neither party sends the shared value. Both reach g**(a*b) modulo p.

import matplotlib.pyplot as plt

import blockchainkit as bk

group = bk.crypto.DHGroup()  # p = 23, q = 11, g = 2: tiny, so every value is visible.
alice_secret, bob_secret = 3, 7
alice_public = group.public(alice_secret)
bob_public = group.public(bob_secret)
shared = group.shared(bob_public, alice_secret)
assert shared == group.shared(alice_public, bob_secret)
print(f"Public values: {alice_public}, {bob_public}; shared element: {shared}")

Public values: 8, 13; shared element: 12

Authentication is a separate problem

Mallory substitutes her own public value. Alice now shares a secret with Mallory, not Bob. Real protocols authenticate the exchange and use a KDF.

mallory_secret = 4
alice_mallory = group.shared(group.public(mallory_secret), alice_secret)
assert alice_mallory == group.shared(alice_public, mallory_secret)
assert alice_mallory != shared
print("After key substitution, Alice's shared element is", alice_mallory)

After key substitution, Alice's shared element is 2

The same exchange in a group too large to search by hand

big = bk.crypto.TEACHING_GROUP
a, b = 0x1234_5678_9ABC, 0x0FED_CBA9_8765
assert big.shared(big.public(b), a) == big.shared(big.public(a), b)

Exponentiation scrambles the subgroup

fig, ax = plt.subplots(figsize=(7, 3.8))
exponents = list(range(1, group.q))
ax.scatter(exponents, [group.public(x) for x in exponents], color="#2563eb")
ax.set(
    xlabel="private exponent x", ylabel="public element g**x mod p", title="DH in a tiny subgroup"
)
fig.tight_layout()

Exercise

Exhaustively recover Alice’s exponent from her public value. Why does this experiment say nothing about the cost for a carefully chosen large group?