Discrete Logarithms and Diffie-Hellman

The second classical hard problem looks nothing like factoring. It is about exponents rather than products, and the trapdoor is placed differently. Underneath, it satisfies the same three-clause contract, and it falls to the same quantum algorithm.

01.The forward direction

Fix a prime $p$ and a base $g$, and raise $g$ to a power modulo $p$. Take $p = 17$ and $g = 3$, and list the powers as they come:

$$3^1 \equiv 3, \quad 3^2 \equiv 9, \quad 3^3 \equiv 10, \quad 3^4 \equiv 13, \quad 3^5 \equiv 5, \quad 3^6 \equiv 15, \quad 3^7 \equiv 11, \quad 3^8 \equiv 16 \pmod{17}.$$

Each step is one multiplication by $3$ followed by one reduction modulo $17$, which is the arithmetic from Modular Arithmetic. Check the fourth one by hand: $3^3 \equiv 10$, so $3^4 \equiv 30 \equiv 30 - 17 = 13$.

Continuing to the end of the cycle:

$$3^9 \equiv 14, \; 3^{10} \equiv 8, \; 3^{11} \equiv 7, \; 3^{12} \equiv 4, \; 3^{13} \equiv 12, \; 3^{14} \equiv 2, \; 3^{15} \equiv 6, \; 3^{16} \equiv 1 \pmod{17}.$$

Something worth noticing: the sixteen powers produce all sixteen non-zero values modulo $17$, each exactly once, before returning to $1$. A base that does this is called a generator, and it is the right kind of base to build a cryptosystem on, because it means the output could be anything.

02.Making the forward direction fast

Computing $3^{16}$ by sixteen separate multiplications is fine. Computing $3^{1000000}$ that way is not, and real exponents are astronomically larger than a million.

The trick is repeated squaring, and it is the same trick that made RSA encryption fast in the previous note. Instead of stepping up one power at a time, square repeatedly to leap:

$$3^2, \quad 3^4 = (3^2)^2, \quad 3^8 = (3^4)^2, \quad 3^{16} = (3^8)^2, \; \ldots$$

Each squaring doubles the exponent for the price of one multiplication. To reach an arbitrary exponent, write it in binary and multiply together the squarings whose positions carry a $1$.

Work an example modulo $17$. To compute $3^{11}$, write $11 = 8 + 2 + 1$, so

$$3^{11} \;=\; 3^8 \cdot 3^2 \cdot 3^1 \;\equiv\; 16 \cdot 9 \cdot 3 \pmod{17}.$$

Then $16 \cdot 9 = 144 = 8 \cdot 17 + 8$, so that is $8$, and $8 \cdot 3 = 24 \equiv 7$. The table above gives $3^{11} \equiv 7$, which matches.

The cost is about $\log_2 x$ multiplications rather than $x$ of them. Reaching an exponent of a million takes about twenty multiplications. At cryptographic sizes, with $p$ several hundred digits long, the forward direction stays well under a millisecond.

03.The backward direction

Now reverse the question. You are told $g = 3$, $p = 17$, and that $3^x \equiv 5 \pmod{17}$. Find $x$.

With $p = 17$ there are only sixteen candidates, so read the table: $3^5 \equiv 5$, giving $x = 5$. Trivial, and trivial for the same reason factoring $143$ was trivial. The modulus is tiny.

This backward problem is called the discrete logarithm problem. The name is an analogy with ordinary logarithms, where $\log_3 243 = 5$ because $3^5 = 243$. Over the real numbers that is easy, because the powers of $3$ increase steadily and you can home in on the answer by bisection. Modulo $17$ they do not increase at all. The sequence $3, 9, 10, 13, 5, 15, 11, 16, 14, 8, \ldots$ jumps around with no usable order. Knowing that $3^x \equiv 5$ and that $3^4 \equiv 13$ tells you nothing about whether $x$ is above or below $4$. Every bisection strategy is dead on arrival.

At cryptographic sizes the candidate space has around $p$ elements, and no classical algorithm does substantially better than subexponential time. Pollard's rho, baby-step giant-step, index calculus and the number field sieve for discrete logarithms are all far better than checking every candidate, and all far too slow at deployed sizes.

There is a variant worth naming because it is what your browser actually uses. The same exponentiation can be performed on the points of an elliptic curve rather than on integers modulo a prime. The best known classical attack there runs in about $\sqrt{p}$ time, which is worse for the attacker than in the integer setting, so the keys can be much smaller. A $256$-bit elliptic-curve key gives roughly the same security as a $3072$-bit RSA key. That size advantage is why elliptic curves displaced RSA across most of the modern web.

04.Where the trapdoor lives: Diffie-Hellman key exchange

The trapdoor sits in a different place from RSA, and the scheme it produces solves the key-distribution problem from the first note directly.

Alice and Bob agree publicly on $p$ and $g$. Eve knows both. Then:

Alice picks a secret $a$ and sends $A = g^a \bmod p$.

Bob picks a secret $b$ and sends $B = g^b \bmod p$.

Alice computes $B^a \bmod p$. Bob computes $A^b \bmod p$.

Both arrive at the same value, because

$$B^a \;=\; (g^b)^a \;=\; g^{ab} \;=\; (g^a)^b \;=\; A^b \pmod p .$$

That shared value is their key, and neither of them ever transmitted it.

Work it fully with $p = 17$, $g = 3$. Alice picks $a = 5$ and sends $A = 3^5 \equiv 5$. Bob picks $b = 7$ and sends $B = 3^7 \equiv 11$.

Alice computes $B^a = 11^5 \bmod 17$. By repeated squaring: $11^2 = 121 \equiv 2$, then $11^4 \equiv 2^2 = 4$, then $11^5 \equiv 4 \cdot 11 = 44 \equiv 10$.

Bob computes $A^b = 5^7 \bmod 17$. Again: $5^2 = 25 \equiv 8$, $5^4 \equiv 8^2 = 64 \equiv 13$, and $5^7 = 5^4 \cdot 5^2 \cdot 5 \equiv 13 \cdot 8 \cdot 5$. Now $13 \cdot 8 = 104 \equiv 2$, and $2 \cdot 5 = 10$.

Both get $10$. The shared secret is $10$, and it was never sent.

Eve has heard $p$, $g$, $A = 5$ and $B = 11$. To compute $g^{ab}$ she needs $a$ or $b$, and getting either from $A$ or $B$ is exactly the discrete logarithm problem. At $p = 17$ she reads it off a table in seconds. At a few hundred digits she does not.

The signature version puts the same hardness to a different use. In ECDSA the signer knows a secret exponent $x$, publishes $g^x$, and produces signatures only someone knowing $x$ could produce. Forging one means recovering $x$ from $g^x$, once again the discrete logarithm problem.

05.Two problems, one shared fate

Factoring and discrete logarithms look unrelated. One is about pulling a product apart, the other about undoing an exponentiation. They were discovered separately, they have different best-known attacks, and for decades the fact that deployed cryptography rested on two independent problems felt like healthy insurance. If one fell, the world could migrate to the other.

HTTPS, VPNs, secure email, software update signatures, payment networks and interbank settlement all rest on one or both of them.

That insurance turned out to be worth nothing, and the next note explains why. Both problems have a hidden structural property in common, and one algorithm published in 1994 exploits it in both.