Diffie–Hellman key exchange

From Wikipedia, the free encyclopedia

Diffie–Hellman key exchange is a method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as originally conceptualized by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography.

Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical channel, such as paper key lists transported by a trusted courier. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

Diffie–Hellman is used to secure a variety of Internet services. However, research published in October 2015 suggests that the parameters in use for many DH Internet applications at that time are not strong enough to prevent compromise by very well-funded attackers, such as the security services of large governments.

General overview

Diffie–Hellman key exchange establishes a shared secret between two parties that can be used for secret communication for exchanging data over a public network. The conceptual diagram at the right side of the page illustrates the general idea of the key exchange by using colors instead of very large numbers.

The process begins by having the two parties, Alice and Bob, agree on an arbitrary starting color that does not need to be kept secret (but should be different every time); in this example, the color is yellow. Each of them also selects a secret color that they keep to themselves – in this case, red and blue-green. The crucial part of the process is that Alice and Bob each mix their own secret color together with their mutually shared color, resulting in orange-tan and light-blue mixtures respectively, and then publicly exchange the two mixed colors. Finally, each of the two mixes the color they received from the partner with their own private color. The result is a final color mixture (yellow-brown in this case) that is identical to the partner's final color mixture.

If a third party listened to the exchange, it would only know the common color (yellow) and the first mixed colors (orange-tan and light-blue), but it would be computationally difficult for this party to determine the final secret color (yellow-brown). In fact, when using large numbers rather than colors, this action is computationally expensive: It is impossible to do in a reasonable amount of time even for modern supercomputers.

Continue reading

Cryptographic explanation

The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p–1. Here is an example of the protocol, with non-secret values in blue, and secret values in red.

  1. Alice and Bob publicly agree to use a modulus p = 32717 and base g = 7 (primitive root modulo of 32717)
  2. Alice chooses a secret integer a = 244890, then sends Bob A = ga mod p
    • A = 7244890 mod 32717 = 23559
  3. Bob chooses a secret integer b = 100005, then sends Alice B = gb mod p
    • B = 7100005 mod 32717 = 16367
  4. Alice computes s = Ba mod p
    • s = 16367244890 mod 32717 = 887
  5. Bob computes s = Ab mod p
    • s = 23559100005 mod 32717 = 887
  6. Alice and Bob now share a secret (the number 887).
Simplfied example

Visualization

Alice
desktop-icon

Server
server-icon


Bob
desktop-icon