0

In general, I understand the principle of Diffie-Hellman key exchange. What I don't understand is what is so fundamental about primitive roots modulo p that guarantees that the shared secret is the same. I'll use the notation similar from the Wikipedia Diffie-Hellman Key Exchange article,

Alice has private key, a.

Alice generates her public key, A = g^a (mod p)

Bob has private key, b.

Bob generates his public key, B = g^b (mod p)

Alice sends her public key, A, to Bob.

Bob sends his public key, B, to Alice.

Alice generates the shared secret key, s = B^a (mod p) = [g^b (mod p)]^a (mod p)

Bob generates the shared secret key, s = A^b (mod p) = [g^a (mod p)]^b (mod p)

(I'm aware that Bob and Alice only have access to capital A, and B, respectively, just expanding out the expression to show the private key inputs)

Why is it necessarily true then that:

[g^b (mod p)]^a (mod p) = [g^a (mod p)]^b (mod p)

?

Maybe I just don't understand the "rules" of modular operations. Does the (mod p) just come outside the exponents somehow? Then you just get g^ba (mod p) = g^ab (mod p), which would make sense.

Any good references for this? Been searching around and not finding a clear cut explanation.

Thanks.

Edit: Left out some of the "mod p"'s in the expressions. I have since learned that the public keys A and B are guaranteed to be coprimes of p, so it more or less boils down to the question: "why are coprimes of p, raised to some power (a or b in this case) then divide by p and get the remainder, guaranteed to be equal?". Also if this isn't the right place for this question, please let me know. I know it leans more math side but the math resources I'm looking at don't seem specific enough to answer my question.

Edit 2: I understand the principle behind Diffie-Hellman key exchange; specifically, I'm asking if anyone intuitively (or verbosely) understands the rules of modular arithmetic enough to explain why the secret key that's generated on both sides is guaranteed to be the same.

3
  • It's a good post, but unfortunately, no. It boils down to claiming a "fancy property of modulo exponent", without explaining why it's true. My question is why that property of modulo exponents is true. To me it seems really unintuitive that they would necessarily always be equal (the shared secret). Apr 5 at 15:08
  • 1
    @MichaelBurt: "My question is why that property of modulo exponents is true" - because of mathematical properties. This is not actually a security question but a math question and understanding might require deeper knowledge of algebra. Apr 5 at 15:22
  • @SteffenUllrich Fair enough. I probably need to take my question over to math stack exchange. Thanks Apr 5 at 15:27
0

I found an answer to my own question here on math SE (so this can be deleted, or left for reference):

https://math.stackexchange.com/questions/61358/prove-equivalence-of-diffie-hellman-shared-secret

Not the answer you're looking for? Browse other questions tagged or ask your own question.