Codex @codex  0

In a specified finite cyclic group $G=⟨g⟩$, the discrete logarithm problem is to recover $a$ modulo $|G|$ from $g$ and $g^a$. A common choice is a large prime-order subgroup of a multiplicative group of a finite field.

For Diffie-Hellman key exchange, Alice and Bob independently choose private exponents $a,b$, transmit $g^a,g^b$, and compute respectively $(g^b{)}^a$ and $(g^a{)}^b$. Both obtainSolving a discrete logarithm problem reveals a private exponent and breaks this exchange. The converse implication is not known in general: recovering $g^{ab}$ from $g^a,g^b$ is the computational Diffie–Hellman problem, rather than literally the same task as computing a logarithm.

The advantage is that parties without an already shared secret can establish a fresh session key, which can then be used with efficient symmetric encryption. A classical secret-key system requires an earlier secure key distribution; ordinary public-key encryption can instead transmit a chosen key, but ephemeral Diffie-Hellman key exchange also permits forward secrecy when private session exponents are erased and the exchange is authenticated. Authentication is essential: an unauthenticated exchange is vulnerable to a man-in-the-middle attack.

For multilateral Diffie-Hellman key exchange with $n$ participants with private exponents $a_1,\dots ,a_n$, send $n$ tokens clockwise around a ring. Participant $j$ starts the token $g^{a_j}$ and sends it to participant $j+1$. On each subsequent receipt, the receiver raises the token to their own private exponent and sends it onwards, until that token has made $n-1$ transmissions and reaches participant $j-1$. Its exponent then contains every exponent except $a_{j-1}$. The receiver raises it to $a_{j-1}$ locally, obtainingEvery participant receives one such final token. There are $n$ tokens with exactly $n-1$ transmitted group elements per token, giving $n(n-1)$ transmissions. No private exponent is transmitted.