[ale] OT: Diffie-Hellman key exchange for dummies?

Jay Loden ale at jayloden.com
Mon Aug 6 14:48:32 EDT 2007


JK, thanks for taking the time to write this up. I had gathered much of this
from the descriptions in the RSA and wikipedia pages, but your last few
paragraphs really helped tie it together from the mathematical perspective, in
particular this part:

>     (g^x mod p)^y mod p == (g^y mod p)^x mod p == g^xy mod p

Thanks again for the thorough explanation, I appreciate it!

-Jay

JK wrote:
> This excerpt from the Wiki page captures the essence:
> 
>     <quote>
>     1. Alice and Bob agree to use a prime number p=23 and base g=5.
>     2. Alice chooses a secret integer a=6, then sends Bob (g^a mod p)
>            * 56 mod 23 = 8.
>     3. Bob chooses a secret integer b=15, then sends Alice (g^b mod p)
>            * 515 mod 23 = 19.
>     4. Alice computes (g^b mod p)^a mod p
>            * 196 mod 23 = 2.
>     5. Bob computes (g^a mod p)^b mod p
>            * 815 mod 23 = 2.
> 
>     Both Alice and Bob have arrived at the same value, because g^ab
>     and g^ba are equal.
>     </quote>
> 
> In this case, the agreed-upon key value is g^ab=2 (the "same value"
> mentioned above).  In other words, the basic principle is:
> 
>    (1) Pick a number, a.
>    (2) Perform some mathematical operation F on a, and call the
>        result r. (The mathematical properties of F are important!)
>    (3) Send r to the other party.
>    (4) The other party has chosen a number b, computed F(b),
>        and sent you the result (call it s).
>    (5) Now, both you and the other party have r and s, which are
>        numbers "built from" a and b using F.  You have a, she has b.
>        You can use some "reversibility" property of the operation
>        F to arrive at a common value known only to you and the
>        other party.  Anyone can see the values r and s go across
>        the wire, but without the a or b values, which are secret,
>        they cannot use the knowledge of r and s to figure out the
>        common value (the key).  The key (pardon the pun) to the whole
>        mechanism is choosing a function F that is easy to compute,
>        but whose inverse is hard to compute unless you know one of
>        the secret values. (This is kind of a magic trick: finding
>        good functions of this nature is not a trivial task.)
> 
> In the Wikipedia example, the function F is exponentiation mod p=23
> using base g=5:
> 
>     F(x) = (5^x)%23
> 
> Bob has a, g, g^b mod p (received from Alice), and p; a is secret.
> Alice has b, g, g^a mod p (received from Bob), and p; b is secret.
> Since in general:
> 
>     (g^x mod p)^y mod p == (g^y mod p)^x mod p == g^xy mod p
> 
> therefore Bob and Alice can each compute g^ab mod p using only
> the numbers the know -- that is, they don't need to know the
> other party's secret value (a or b, respectively).  So g^ab mod p
> becomes the shared key.
> 
> A third party watching this exchange *cannot* compute the shared
> key, because even though they know all of g, p, r=g^a mod p, and
> s=g^b mod p, they do not know either a or b, and computing
> g^ab mod p using only r and s is a difficult problem.  (Actually
> for tiny primes it can easily be brute-forced, but in real life DH
> is done with, like, 1000-digit primes.)
> 
> -- JK
> 



More information about the Ale mailing list