LOGBOOK

HELP

Quiz Entry - updated: 2026.07.10

Why can't Eve compute the DH shared secret $K = g^{ab} \mod p$ by simply multiplying the intercepted values $g^a \mod p$ and $g^b \mod p$?

Because $g^a \cdot g^b = g^{a+b} \neq g^{ab}$. Multiplication of the intercepted values gives the wrong exponent — addition instead of multiplication. Computing $g^{ab}$ from $g^a$ and $g^b$ requires solving the discrete logarithm.

Why multiplying g^a and g^b yields the wrong exponent

* Multiplying the intercepts adds exponents; reaching g^(ab) would require a discrete log. *

It's worth sitting with why this gap exists, because the entire security of DH rests on it. Combining the two intercepts the obvious way adds the exponents; getting them to multiply would mean first pulling an exponent back out of a power — the discrete logarithm — and that single step is the one nobody knows how to do efficiently.

What Eve knows: $g$, $p$, $g^a \mod p$, $g^b \mod p$

What Eve can compute:

  • $g^a \cdot g^b = g^{a+b} \mod p$ — but this is useless (wrong exponent)
  • She needs $g^{ab} \mod p$, which requires knowing either $a$ or $b$

Why this is hard:

  • To find $a$ from $g^a \mod p$: she must solve $a \equiv \log_g(g^a) \mod p$ — the discrete logarithm problem
  • This is a one-way function without trapdoor — nobody can compute it efficiently, not even the key owner
  • Unlike RSA (where the factorization is a trapdoor), there is no secret shortcut for the discrete log

The key mathematical insight: Exponentiation mod p "scrambles" the relationship between $a$, $b$, and $ab$. Even though $a \cdot b$ is trivial to compute from $a$ and $b$, computing $g^{ab}$ from $g^a$ and $g^b$ without knowing the exponents is (believed to be) computationally infeasible.

Tip: This is the Computational Diffie-Hellman (CDH) assumption — the foundation of DH security.

Go deeper:

From Quiz: KRYPTOG / Diffie-Hellman and ElGamal | Updated: Jul 10, 2026