How can two computers agree on a secret key when anyone can listen?

Two computers agree a key by sending each other a scrambled value and never sending the private number that went into it. Each then combines the other side's scrambled value with its own private number, and both arrive at the same shared key that a listener recording every message cannot reconstruct.

The public starting values are a prime, called the modulus, and a base. Call the modulus $p$ and the base $g$. One side chooses a private exponent $a$, computes $g^a \bmod p$ and sends it. The other chooses a private exponent $b$, computes $g^b \bmod p$ and sends it. The first side raises what it received to $a$, the second raises what it received to $b$, and both get the same number because the two exponentiations commute.

The public values are $p=23$ and $g=5$. The first side picks $a=6$. It computes $5^6=15625$, and $15625=23\cdot 679+8$, so it sends $8$. The second side picks $b=15$. It computes $5^{15}=30517578125$, and $30517578125=23\cdot 1326851222+19$, so it sends $19$.

The first side receives $19$ and computes $19^6 \bmod 23$. By repeated squaring, $19^2=361=23\cdot 15+16$, $19^4=16^2=256=23\cdot 11+3$, and $19^6=19^4\cdot 19^2=3\cdot 16=48=23\cdot 2+2$. The second side receives $8$ and computes $8^{15}\bmod 23$. Here $8^2=64=23\cdot 2+18$, $8^4=18^2=324=23\cdot 14+2$, $8^8=2^2=4$, so $8^{15}=8^8\cdot 8^4\cdot 8^2\cdot 8=4\cdot 2\cdot 18\cdot 8=1152=23\cdot 50+2$. Both hold $2$.

The natural guess is that the listener, seeing $8$ and $19$, can simply combine them. It cannot. Multiplying them gives $8\cdot 19=152=23\cdot 6+14$, and $14$ is not the key. Raising $8$ to the $19$th power is not the same as raising $8$ to the $15$th power; only the second is what the second side did. To reach $2$, the listener needs either $6$ or $15$. Recovering $15$ from $5^{15}\bmod 23$ means trying exponents until one produces $19$. With $p=23$ there are only $22$ nonzero exponents to try, and the listener can do that by hand. That is exactly the weakness the real sizes are chosen to remove: the same search is still the only known route, but the number of candidates is made far too large to run.

Recovering an exponent from $g^a \bmod p$ is the discrete logarithm problem. No fast method is known at the sizes used, but nobody has proved that no fast method exists. The security is an assumption, not a theorem. If someone found a fast method, the listener could recover $a$ or $b$ from the published values and compute $g^{ab}\bmod p$ exactly as the two sides do. The method is used because it has survived sustained attack, not because it has been proved safe.

Two conditions matter. The modulus must be large enough that the search is out of reach; a modulus that is too small makes the listener's job a finite computation, as it was with $p=23$. Reusing one modulus across many conversations is also dangerous, because the expensive part of the attack depends on the modulus and not on the particular pair of private exponents, so an attacker can precompute once and reuse the result.

Separately, this exchange gives secrecy against a listener who only records. It gives nothing against an attacker who can alter messages, because that attacker can intercept both public values, substitute its own, and run two separate exchanges, one with each side. Both sides then share a key with the attacker rather than with each other, and the arithmetic is perfectly valid. Authentication, not more arithmetic, is what closes that gap.