Cryptography: Diffie-Hellman Key Exchange

 

•The first published public-key algorithm that defined public-key cryptography

•A number of commercial products employ this key exchange technique.

•The purpose of the algorithm is to enable two users to securely exchange a key that can then be used for subsequent encryption of messages.

•The algorithm itself is limited to the exchange of secret values.

•Diffie-Hellman is a way of generating a shared secret between two people in such a way that the secret can't be seen by observing the communication.

•That's an important distinction: You're not sharing information during the key exchange, you're creating a key together.

•This is particularly useful because you can use this technique to create an encryption key with someone, and then start encrypting your traffic with that key.

•And even if the traffic is recorded and later analyzed, there's absolutely no way to figure out what the key was, even though the exchanges that created it may have been visible.

•This is where perfect forward secrecy comes from.

–Nobody analyzing the traffic at a later date can break in because the key was never saved, never transmitted, and never made visible anywhere.

•The way it works is reasonably simple. A lot of the math is the same as you see in public key crypto in that a trapdoor function is used.

–A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".

•But even though it uses the same underlying principles as public key cryptography, this is not asymmetric cryptography because nothing is ever encrypted or decrypted during the exchange.

•It is, however, an essential building-block, and was in fact the base upon which asymmetric crypto was later built.

The basic idea works like this:

1.I come up with two prime numbers g and p and tell you what they are.

2.You then pick a secret number a, but you don't tell anyone. Instead you compute ga mod p and send that result back to me. i.e. A = ga mod p

3.I do the same thing, but will call my secret number b and the compute number B. So I compute gb mod p and send you the result (called "B")

4.Now, you take the number I sent you and do the exact same operation with it. So that's Ba mod p.

5.I do the same operation with the result you sent me, so: Ab mod p.

•

•

•The "magic" here is that the answer I get at step 5 is the same number you got at step 4. Now it's not really magic, it's just math:

(ga mod p)b mod p = gab mod p

(gb mod p)a mod p = gba mod p

•

•A primitive root of a prime number p is one whose powers modulo p generate all the integers from 1 to p - 1. That is, if a is a primitive root of the prime number p, then the numbers

a mod p , a2 mod p, … , ap-1 mod p

are distinct and consist of the integers from 1 through p - 1 in some permutation.

•For any integer b and a primitive root a of prime number p, we can find a unique exponent i such that

b º ai (mod p) where 0 ≤ i ≤ (p - 1)

•The exponent i is referred to as the discrete logarithm of b for the base a, mod p.

•We express this value as dloga,p(b).

 



 

•The result is that the two sides have exchanged a secret value.

•Furthermore, because XA and XB are private, an adversary only has the following ingredients to work with: q, a , YA, and YB.

•Thus, the adversary is forced to take a discrete logarithm to determine the key.

•For example, to determine the private key of user B, an adversary must compute

XB = dloga,q(YB)


•The adversary can then calculate the key K in the same manner as user B calculates it.

Security of Algorithm

•The security of the Diffie-Hellman key exchange lies in the fact that, while it is relatively easy to calculate exponentials modulo a prime, it is very difficult to calculate discrete logarithms.

•For large primes, the latter task is considered infeasible.