Main content
Computer science
Course: Computer science > Unit 2
Lesson 4: Modern cryptography- The fundamental theorem of arithmetic
- Public key cryptography: What is it?
- The discrete logarithm problem
- Diffie-hellman key exchange
- RSA encryption: Step 1
- RSA encryption: Step 2
- RSA encryption: Step 3
- Time Complexity (Exploration)
- Euler's totient function
- Euler Totient Exploration
- RSA encryption: Step 4
- What should we learn next?
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
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(56 votes)
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.(122 votes)
Is the diffie-hellmann key exchange used in modern cryptography?(50 votes)
Yes, for instance TLS/SSL uses the Diffie-Hellmann key exhange to generate the session keys used to encrypt data. see - http://en.wikipedia.org/wiki/Transport_Layer_Security(55 votes)
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
?(31 votes)- 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(57 votes)
- 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?(28 votes)- 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(21 votes)
- Does it matter if it's a prime modulus?(16 votes)
- 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.(8 votes)
- Why does the base and generator number of mod have to be a prime number ?(8 votes)
- 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(11 votes)
Will the Discrete Logarithm Problem work for all one way functions?(4 votes)- 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?(5 votes)
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.(7 votes)
- Did anyone notice that Eve's numbers if she were to do the final computation at about1:53her 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?(5 votes)
- 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.(6 votes)
At0:05, does g and p have to be prime numbers?(3 votes)- 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(6 votes)
1:53Video transcript
- [Voiceover] Now, this is our solution. First, Alice and Bob agree publicly on a prime modulus and a generator, in this case, 17 and three. Then, Alice selects a private,
random number, say 15, and calculates three to
the power 15, mod 17, and sends this result publicly to Bob. Then Bob selects his private,
random number, say 13, and calculates three
to the power 13, mod 17 and sends this result publicly to Alice. And now, the heart of the trick. Alice takes Bob's public result and raises it to the power
of her private number to obtain the shared secret,
which in this case is 10. Bob takes Alice's public result and raises it to the power
of his private number, resulting in the same shared secret. Notice they did the same calculation, though it may not look like it, at first. Consider Alice, the 12
she received from Bob was calculated as three
to the power 13, mod 17. So her calculation was the same as three to the power 13,
to the power 15, mod 17. Now consider Bob, the six
he received from Alice was calculated as three
to the power 15, mod 17. So his calculation was the same as three to the power 15, to the power 13. Notice they did the same calculation with the exponents in a different order. When you flip the exponent,
the result doesn't change. So they both calculated three raised to the power of
their private numbers. Without one of these
private numbers, 15 or 13, Eve will not be able to find the solution. And this is how it's done. While Eve is stuck grinding away at the discrete logorithm problem, and with large enough numbers, we can say it's practically
impossible for her to break the encryption in
a reasonable amount of time. This solves the key exchange problem. It can be used in conjunction
with a pseudorandom generator to encrypt messages between
people who have never met.