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

[JK]

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

Jay Loden wrote:
> This is somewhat off topic for a Linux enthusiast group, but this a group of smart folks with lots of knowledge, so I figured it might be a good place to ask anyway:
> 
> I've heard the term "Diffie-Hellman Key Exchange" used before, and in basic terms I know that it's a secure way of agreeing on a secret key. However, when I tried to read a couple of articles to understand how it works under the hood, I found myself out of my depth. I have programming experience, but I'm not formally trained, and I never went beyond Algebra 2. Even though I was able to implement a simplistic version of the exchange by following the Linux Journal article below I don't really understand why it works on a mathematical level.
> 
> Anyone who likes a challenge feel like trying to explain in laymen's terms to a mathematically challenged individual? :-)
> 
> References:
> http://en.wikipedia.org/wiki/Diffie-Hellman
> http://www.rsa.com/rsalabs/node.asp?id=2248
> http://www.linuxjournal.com/article/6131
> http://en.wikipedia.org/wiki/Discrete_logarithm
> 
> -Jay
> _______________________________________________
> Ale mailing list
> Ale at ale.org
> http://www.ale.org/mailman/listinfo/ale
> 
> 


-- 
"What can be asserted without evidence can also be
dismissed without evidence." -- Christopher Hitchens