[Math] Why/How does the Diffie-Hellman Key Exchange work

algebra-precalculuscryptography

I have always been interested in cryptology, but struggled with Algebra as a kid. As a result I know the basics of how the Diffie-Hellman Key Exchange (DH from here on) works, but I don't know why it does. I know that by two similar algorithms with two private numbers, both parties come to the same conclusion.

Why?

(I have used the wikipedia article to gain my understanding of the formulae and reproduce them in a Ruby script for my own learning.)

My primary curiosity is over the two primary steps of deriving the public keys (which are exchanged) and then deriving the same, final encryption key. How do Alice and Bob actually get the same key without the sharing of their two private keys? I'm probably missing an obvious "solve for …" or a simple rule, somewhere.

Given:

  • G: a small prime
  • P: a very large prime (EG, 1024 bits)

Secret Keys (just a random number):

  • $X_a$ Alice's secret key
  • $X_b$ Bob's secret key

Temporary (shared) Keys:

  • Alice: $Y_a = G^{X_a} \mod P$
  • Bob: $Y_b = G^{X_b} \mod P$

Final Key:

  • Alice: ${Y_b}^{X_a} \mod P$
  • Bob: ${Y_a}^{X_b} \mod P$

Edit:

Assume:

$G = 7$

$P = 11$

$X_a = 6$

$X_b = 9$

Should be:

$Y_a = 4$

$Y_b = 8$

By lhf's answer and a proper application of simplifying exponents, $G^{a \centerdot b} \mod P = 3$ should be correct. However, it is nowhere close. Manipulating it to $G^{a + b} \mod P = 3$ is still incorrect, but closer.

Why is $(G^{a + b} \mod P) \mod P = 3$ correct?

Edit 2:

The calculator that I use on my computer incorrectly handles % as modulo, and therefore does not emit the correct answer. If you have a Mac, you can use Spotlight (cmd+space) and (7^(6*9)) % 11 (even if you use "modulo") becomes 8—and no, I have no idea why.

So… chalk one problem up to trusting calculators. I understood exponents and their rules to begin with, but with a faulty calculator in the way it even made me question what I practically aced as a kid. Sheesh.

Best Answer

The wikipedia article says it plainly: "Both Alice and Bob have arrived at the same value, because $(g^a)^b$ and $(g^b)^a$ are equal mod $p$." Note that they're both equal to $g^{ab}$ mod $p$.

Related Question