Diffie-Hellman Algorithm

Diffie-HellmanIn the previous article, I provided an overview of asymmetric encryption. Today, we begin our look at asymmetric algorithms, starting with Diffie-Hellman.

The biggest problem in symmetric cryptography is the security of the secret key. Obviously, you cannot transmit transmit the key over the same medium as the ciphertext, since any unauthorized parties observing the communications could use the key to decode the messages. Prior to the development of asymmetric cryptography and the Diffie-Hellman key exchange, secret keys were exchanged using trusted private couriers and other out-of-band methods.

In the mid-1970s, Whitfield Diffie and Martin Hellman published the Diffie-Hellman algorithm for key exchange, which allowed a secret key to be transmitted securely over an insecure line. This was the first published use of public-key cryptography, and one of the cryptography field’s biggest advances. With the Diffie-Hellman algorithm, the DES secret key – sent with a DES-encrypted payload message – could be encrypted via Diffie-Hellman by one party, and decrypted only by the intended recipient.

Because of the inherent slowness of asymmetric cryptography, the Diffie-Hellman algorithm was not intended for use as a general encryption scheme. Rather, its purpose was to transmit a private key for DES (or a similar symmetric algorithm) across an insecure medium. In most cases, Diffie-Hellman is not used for encrypting a complete message, because it is much slower than DES, depending on implementation.

The Diffie-Hellman Key Exchange in Practice

In practice, this is how a key exchange using Diffie-Hellman works:

  1. Two parties agree on two numbers; one is a large prime number, the other is a small integer number. This can be done in the open, as it does not affect security.
  2. Each of the two parties separately generate another number, which is kept secret. This number is equivalent to a private key. A calculation is made involving the private key and the previous two public numbers. The result is sent to the other party. THe result is effectively a public key.
  3. The two parties exchange their public keys. They then perform a calculation involving their own private key and the other party’s public key. The resulting number is the session key. Each party should arrive at the same number.
  4. The session key can be used as a secret key for another cipher, such as DES. No third party monitoring the exchange can arrive at the same session key without knowing one of the private keys.

The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime and g is primitive root mod p. Actual implementations require using large numbers to achieve security. The protocol is considered secure if the initial numbers are chosen properly. The eavesdropper would have to solve the Diffie-Hellman problem to obtain the secret keys. This is currently considered difficult. An efficient algorithm to solve the discrete logarithm problem would make it easy to compute a or b and solve the Diffie-Hellman problem, making this and many other public key cryptosystems insecure.

Diffie-Hellman’s greatest strength is that anyone can know either or both of the sender’s and recipient’s public keys without compromising the security of the message. Both the public and private keys are actually very large integers. The Diffie-Hellman algorithm takes advantage of complex mathematical functions known as discrete logarithms, which are easy to perform forward, but extremely difficult to inverse. Secure Internet Protocol (IPSec) uses the Diffie-Hellman algorithm in conjunction with the Rivest, Shamir, & Adleman (RSA) authentication to exchange a session key used for encrypting all traffic that crosses the IPsec tunnel.

External Links:

Diffie-Hellman key exchange at Wikipedia

Be Sociable, Share!

Speak Your Mind


© 2013 David Zientara. All rights reserved. Privacy Policy