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.

Main content

Diffie-hellman key exchange

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

Want to join the conversation?

  • male robot hal style avatar for user Wayming
    How could a hacker break this? Is it possible? If not, then why are hackers able to get our information?
    Thanks,
    Matthew
    (53 votes)
    Default Khan Academy avatar avatar for user
  • purple pi purple style avatar for user TheFourthDimension
    Is the diffie-hellmann key exchange used in modern cryptography?
    (50 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user middlecope
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • blobby green style avatar for user canthavemyphonenumber
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • leaf green style avatar for user L
    Does it matter if it's a prime modulus?
    (16 votes)
    Default Khan Academy avatar avatar for user
  • male robot hal style avatar for user Enn
    Why does the base and generator number of mod have to be a prime number ?
    (8 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • old spice man green style avatar for user ♦Patrick Z.♦
    Will the Discrete Logarithm Problem work for all one way functions?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user TL
      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)
  • blobby green style avatar for user danielumby
    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)
    Default Khan Academy avatar avatar for user
    • leaf red style avatar for user agxxvi
      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)
  • blobby green style avatar for user Jacob Edward Barney
    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?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • spunky sam blue style avatar for user Kyle H
    At , does g and p have to be prime numbers?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)

Video 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.