Diffie–Hellman key exchange

define an operation X that satisfies

1. Associative: a X b X c = a X (b X c)
2. Commutative: a X b = b X a
3. No (or very difficult) reverse operation. e.g. If we know a and (a X b), it’s impossible to calculate b

Key Exchange (very simplified)

        C   : common knowledge, public
        a   : secret bits, private to ALICE
        b   : secret bits, private to BOB


        ALICE                           BOB
        + a                             + b
            |                           |
            |      send A:= a X C       |
            |-------------------------->|
            |                           |
            |      send B:= b X C       |
            |<--------------------------|
            |                           |
calc.       |                           | calc.
s := B x a  |                           | s := A X b
            |                           |
            |                           |
                B x a == b X C x a
                      == a x C x b
                      == A x b

After the key exchange,

• both ALICE and BOB calculate s := a X b X C (property 1 and 2). And they can use s as a symmetric key.
• Attacker knows C, a X C, b X C. But can’t calculate a, b nor a X b X C (property 3)