If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

# Diffie-hellman key exchange

Walkthrough of Diffie-Hellman Key Exchange. Created by Brit Cruise.

## Want to join the conversation?

• How could a hacker break this? Is it possible? If not, then why are hackers able to get our information?
Thanks,
Matthew
• A hacker (Eve) would very likely try to breach security holes of the key holders PCs (Alice & Bob) and steal the keys. That is why it is important to not only have good encryption but also a good protection.
• Is the diffie-hellmann key exchange used in modern cryptography?
• Alice (private key a) sends Bob A = 3^a mod 17
Bob (private key b) sends Alice B = 3^b mod 17
The shared key becomes B^a mod 17 = A^b mod 17
(3^b mod 17)^a mod 17 = (3^a mod 17)^b mod 17
Is there an explanation for the next step:
3^b^a mod 17 = 3^a^b mod 17
In other words is there a proof for (3^b mod 17)^a mod 17 = 3^b^a mod 17
?
• 1st some general exponent rules background

If x and y are integers:
x^y says: take x and multiply it by itself y times
i.e. x^4=x * x * x * x
(x^y)^z says: take x and multiply it by itself y times then multiply that result by itself z times. But this is the same as multiplying x by itself y * z times, which is the same as multiplying x by itself z * y times.
i.e. (x^4)^3=(x * x * x * x) * (x * x * x * x) * (x * x * x * x)
= (x * x * x) * (x * x * x) * (x * x * x)*(x * x * x) = (x^3)^4
So (x^y)^z = x^(y * z) = (x^z)^y

Modular arithmetic rules

We can write any integer as x = k * z + r
This comes from long division. We divide x by z, we get some quotient k, and a remainder r (our modulus).
So when we look for x mod z , we get r and we don't care what the value of k is, as long as it is an integer.

So now we'll show that (x * y) mod z = (x mod z) * (y mod z) mod z

We write x as x = k1 * z + r1. We can see x mod z = r1
We write y as y= k2* z + r2. We can see y mod z= r2

The left hand side of the equation
x * y = ( k1 * z + r1 ) * ( k2* z + r2 )
= k1 * k2 * z * z + k1 * z * r2 + r1 * k2 * z + r1 * r2
Group all the terms multiplied by z
= ( k1 * k2 * z + k1 * r2 + r1 * k2 ) * z + r1 * r2
= (A bunch of integers ) * z + (r1 * r2)
So if r1 * r2 < z it should be clear that if we divide this by z our remainder (modulus) will be r1 * r2. Note that, if we take the r1 * r2 mod z in this case we still get r1 * r2.

If r1 * r2 >= z we can write r1 * r2 as:
( r1 * r2 ) = k3 * z + r3, Here if we divide r1 * r2 by z we clearly get r3.
So we can write x * y as
x * y = (A bunch of integers ) * z + (r1 * r2)
=(A bunch of integers ) * z + (k3 * z + r3)
=(A bunch of integers + k3 ) * z + (r3)
The mod of x * y is r3, but that is the same as the mod of r1 * r2 !
So in both case (x * y) mod z = (r1 * r2) mod z

(x * y) mod z = r1 * r2 mod z

Right hand side of the equation
we already showed x mod z = r1 and y mod z= r2
(x mod z) * ( y mod z) mod z = r1 * r2 mod z
So the left hand side and the right hand side of the equations agree. They are equal !

So when we have something like:
(3^b mod 17)^a mod 17 = 3^b^a mod 17
The left hand side is the same as taking (3^b mod 17) multiplied by itself a times
then taking the result modulo 17.
But we now know that (x * y) mod z = (x mod z) * (y mod z) mod z
so:
we can flip the left and right side of our equation (3^b mod 17)^a mod 17 = 3^b^a mod 17
to become 3^b^a mod 17 = (3^b mod 17)^a mod 17
(3^b^a) mod 17 = (3^b mod 17) * (3^b mod 17) * .... (3^b mod 17) mod 17
(the right hand side has (3^b mod 17) multiplied by itself a times )
So we see that we can apply the rule (x * y) mod z = (x mod z) * (y mod z) mod z here.

If it is not obvious why we can use the rule here, then imagine how we could break the problem down:
(3^b^a ) mod 17 = 3^b^a mod 17
break down the largest term on the right
(3^b^a ) mod 17 = (3^b^(a-1) * 3^b ) mod 17
apply our rule
(3^b^a ) mod 17 = (3^b^(a-1) mod 17) * (3^b mod 17) mod 17
break down the largest term on the right
(3^b^a ) mod 17 = (3^b^(a-2) * 3^b mod 17) * (3^b mod 17) mod 17
apply our rule
(3^b^a ) mod 17 = (3^b^(a-2) mod 17) * (3^b mod 17) * (3^b mod 17) mod 17
....
repeat this process until we have
(3^b^a) mod 17 = (3^b mod 17) * (3^b mod 17) * .... (3^b mod 17) mod 17

We have also proven before that 3^b^a=3^a^b
So that should just about do it.

Hope this makes sense
• Ok, I might be missing something obvious, but what prevents Eve from making her own private number, and pretending to be Bob?
Also, is 10 (the shared secret) a seed number to generate pseudo-random numbers, or something else?
• Great questions !
In the implementation explained in the video (classic Diffie Hellman) ,nothing prevents Eve from making her own private number and intercepting messages from Alice and pretending to be Bob, and intercepting message from Bob and pretending to be Alice. This is known as a "man in the middle attack". In practice one needs to add in some extra steps to incorporate authentication to prevent this type of attack.

The finer details on how the shared secret is used depends on the application. However, the essence of what occurs is, it is used to generate a key for a symmetric key cipher like AES (because symmetric key ciphers are much much faster). For something like SSH the shared secret would be passed through a hash function to generate a suitable key (very similar to using the secret as a seed for a PRNG).

Hope this makes sense
• Does it matter if it's a prime modulus?
• I think it was mentioned in the previous video that choosing a prime modulus makes chances of every possible outcome equal.Im not sure though.
• Why does the base and generator number of mod have to be a prime number ?
• For Diffie Hellman Key Exchange we choose:
-a modulus n (must be prime)
-and a generator g (does not need to be prime)

The reason we want to choose n to be prime is, this guarantees the group is cyclic. Amongst other useful properties, this means a generator exists. A generator is a number < n, that will produce all the numbers from 1 to n-1 exactly once if we calculate g^x for x values from 1 to n-1.
e.g. 5 is a generator for mod 7 since
5^1 mod 7=5,
5^2 mod 7 = 4,
5^3 mod 7=6,
5^4 mod 7= 2,
5^5 mod 7= 3
5^6 mod 7 = 1
all numbers from 1 to 6 have been generated when we find 5^x mod 7 for x=1 to 6.

Not all numbers have generators ! e.g. mod 6 has no generator.

Why do we need a generator ?
We want the number of unique y values that y=g^x mod n can produce to be as large as possible. This way when Eve is given some y value, it will be as hard as possible for her to figure out what x is. A brute force attack where Eve tries all the different x values should not be feasible i.e. it should take much > 100 years. Note that the values we use in practice for n are 1024 bits and larger.

If g wasn't a generator then y=g^x mod n might only produce a small number of different y values i.e. the y values would start to repeat long before x reached n. This would mean Eve would have to try much less different values for x before she could solve y=g^x mod n.

(It should be noted that in practice we can use "safe primes" and the generator only needs to be a generator of a sufficiently large subgroup of n to be suitable e.g. if n,q are prime and n=2q+1 then we can use a small generator like 2 and be confident that we have a subgroup of size at least q)

Hope this make sense
• Will the Discrete Logarithm Problem work for all one way functions?
• I don't understand this part:
Note: this is not suitable as a one way function since we can easily solve for x if we know the multiplicative inverse of g mod p (which we can efficiently obtain using the Extended Euclidian Algorithm).

Would you please explain what the multiplicative inverse of g mod p is, and how we can obtain it through Extended Euclidian Algorithm?

Thanks.
(1 vote)
• But how would they know to use this method? Do we just assume that they the other person knows this? Or is this just a theoretical solution?
• The method must have been established in prior, you can't just assume the other party knows it. Having been established, though, it is impracticable to find what the key is, making this method practically safe. It is NOT just a theoretical solution, as it is used in practice, for instance, in TLS/SSL.
• Did anyone notice that Eve's numbers if she were to do the final computation at about her two numbers when subtracted from each other create the number that the two other parties were transmuting to get to? Is this just a fluke or does it happen with enough consistency to leave there being just two possible solutions that a "eve"sdropper could get to?
• It was just a coincidence.
(Randomly picking any integer with mod 17 we would expect to hit the key 1/17 of the time)
Eve was not performing a meaningful calculation.
• At , does g and p have to be prime numbers?
• p should be a prime number, but g has to be a primitive root (otherwise known as a generator) mod p.

Remember that if we apply the exponents 1 to n-1 on a generator, g, it will produce the values 1 to n-1 (but not in order).
e.g. we could use p= 13 and g = 6
6^1 mod 13 = 6
6^2 mod 13 = 10
6^3 mod 13 = 8
6^4 mod 13 = 9
6^5 mod 13 = 2
6^6 mod 13 = 12
6^7 mod 13 = 7
6^8 mod 13 = 3
6^9 mod 13 = 5
6^10 mod 13 = 4
6^11 mod 13 = 11
6^12 mod 13 = 1