In Diffie-Hellman, why is the shared secret guaranteed to be the same?



  • 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.



  • 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


Log in to reply
 

Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2