This Web

All Webs

brayden.org

Books RSS

Random RSS

Software RSS

Other

Diffie-Hellman Key Exchange

This protocol allows two or more participants to agree on a secret key without ever requiring access to a private channel. Even if Eve is able to see every message passed between the principles, it is mathematically infeasible for her to deduce the secret key.

The basic protocol is as follows:

Using a clear channel, Alice and Bob agree on two prime numbers, G and N. G has to be primitive modulo N, but there is no need for these numbers to be secret. N has to be a large number (1024 bits is fine as of 2001 AD, but this may change depending on what happens in quantum computing) such that (N-1)/2 is also prime. G doesn't necessarily have to be primitive modulo N, but if G is not primitive, N has to be larger so that G generates just as big a subgroup.

Alice chooses a large integer A at random, and using A, she computes B = (G A) mod N. She transmits B to Bob.

Bob chooses a large integer C at random, and using C, he computes D = (G C) mod N. He transmits D to Alice.

Now Alice can compute K = (DA) mod N and Bob can compute K = (CB) mod N. K is actually equal to (GAC)mod N in both cases.

Eve, because she doesn't know Alice's value A, can't use Alice's method of getting at K. Because she doesn't know Bob's value C, she can't use Bob's method of getting at K. So It's safe for Bob and Alice to use K as a key.

What makes this secure is that it's easy to exponentiate under a modulus (that's the operation that Alice and Bob are using), but hard to take roots under a modulus (which is the operation Eve would have to do to recover A or C).