Diffie-Hellman

 Diffie-Hellman The algorithm of Diffie-Hellman Breaking of Diffie-Hellman Defeating the man-in-then-middle attack The development of Diffie-Hellman

 Diffie-Hellman The Diffie-Hellman key agreement protocol (also called exponential key agreement) was developed by Diffie and Hellman in 1976 and published in the ground-breaking paper "New Directions in Cryptography''. The protocol allows two users to exchange a secret key over an insecure medium without any prior secrets.

 The algorithm of Diffie-Hellman The protocol has two system parameters p and g. They are both public and may be used by all the users in a system. Parameter p is a prime number and parameter g (usually called a generator) is an integer less than p, with the following property: for every number n between 1 and p-1 inclusive, there is a power k of g such that n = gk mod p. Using the Diffie-Hellman key agreement protocol In this case, Alice and Bob want to agree on a shared secret key using the Diffie-Hellman key agreement protocol. Alice generates a random private value a and Bob generates a random private value b. Both a and b are drawn from the set of integers {1, ¼, p-2}. They derive their public values using parameters p and g and their private values. Alice's public value is ga mod p and Bob's public value is gb mod p. They exchange their public values. Alice computes gab = (gb)a mod p, and Bob computes gba = (ga)b mod p. Since gab = gba = k, Alice and Bob now have a shared secret key k. The protocol depends on the discrete logarithm problem for its security. It assumes that it is computationally infeasible to calculate the shared secret key k = gab mod p given the two public values ga mod p and gb mod p when the prime p is sufficiently large. Maurer has shown that breaking the Diffie-Hellman protocol is equivalent to computing discrete logarithms under certain assumptions.

 Breaking of Diffie-Hellman The Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. In this attack, an opponent Carol intercepts Alice's public value and sends her own public value to Bob. When Bob transmits his public value, Carol substitutes it with her own and sends it to Alice. Carol and Alice thus agree on one shared key and Carol and Bob agree on another shared key. After this exchange, Carol simply decrypts any messages sent out by Alice or Bob, and then reads and possibly modifies them before re-encrypting with the appropriate key and transmitting them to the other party. This vulnerability is present because Diffie-Hellman key exchange does not authenticate the participants. Possible solutions include the use of digital signatures and other protocol variants. The authenticated Diffie-Hellman key agreement protocol, or Station-to-Station (STS) protocol, was developed by Diffie, van Oorschot, and Wiener in 1992 to defeat the man-in-the-middle attack on the Diffie-Hellman key agreement protocol. The immunity is achieved by allowing the two parties to authenticate themselves to each other by the use of digital signatures and public-key certificates which are digital documents attesting to the binding of a public key to an individual or other entity.

 Defeating the man-in-the-middle attack Prior to execution of the protocol, the two parties Alice and Bob each obtain a public/private key pair and a certificate for the public key. During the protocol, Alice computes a signature on certain messages, covering the public value ga mod p. Bob proceeds in a similar way. Even though Carol is still able to intercept messages between Alice and Bob, she cannot forge signatures without Alice's private key and Bob's private key. Hence, the enhanced protocol defeats the man-in-the-middle attack.

 The development of Diffie-Hellman In recent years, the original Diffie-Hellman protocol has been understood to be an example of a much more general cryptographic technique, the common element being the derivation of a shared secret value from one party's public key and another party's private key. The parties' key pairs may be generated anew at each run of the protocol, as in the original Diffie-Hellman protocol. The public keys may be certified, so that the parties can be authenticated and there may be a combination of these attributes.