Overview

This article will cover a simple implementation of the Diffie–Hellman Key Exchange(D-H) method using Python as a way to explain the simplicity and elegance of the method. The basic implementation of the D-H method is actually quite simple, as the below code shows. The D-H method allows two people to agree on a shared secret number (a symmetric key) over a communications medium that is not secure. The benefit of a symmetric key verses a public key is that a symmetric key can encrypt and decrypt much faster, and is easier to implement.

Important note: Never try to create your own encryption system for use on production software. An excellent breakdown of this can be found in Bruce Schneier’s article: Cryptography: The Importance of Not Being Different.

The Code

# use Python 3 print function
# this allows this code to run on python 2.x and 3.x
from __future__ import print_function

# Variables Used
sharedPrime = 23	# p
sharedBase = 5		# g

aliceSecret = 6		# a
bobSecret = 15		# b

# Begin
print( "Publicly Shared Variables:")
print( "	Publicly Shared Prime: " , sharedPrime )
print( "	Publicly Shared Base:  " , sharedBase )

# Alice Sends Bob A = g^a mod p
A = (sharedBase**aliceSecret) % sharedPrime
print( "\n	Alice Sends Over Public Chanel: " , A )

# Bob Sends Alice B = g^b mod p
B = (sharedBase ** bobSecret) % sharedPrime
print( "	Bob Sends Over Public Chanel: ", B )

print( "\n------------\n" )
print( "Privately Calculated Shared Secret:" )
# Alice Computes Shared Secret: s = B^a mod p
aliceSharedSecret = (B ** aliceSecret) % sharedPrime
print( "	Alice Shared Secret: ", aliceSharedSecret )

# Bob Computes Shared Secret: s = A^b mod p
bobSharedSecret = (A**bobSecret) % sharedPrime
print( "	Bob Shared Secret: ", bobSharedSecret )

The Output:

When run under python 2.x or 3.x, the output should be:

Publicly Shared Variables:
    Publicly Shared Prime:  23
    Publicly Shared Base:   5

  Alice Sends Over Public Chanel:  8
    Bob Sends Over Public Chanel:  19

------------

Privately Calculated Shared Secret:
    Alice Shared Secret:  2
    Bob Shared Secret:  2

Basics of the Diffie-Hellman Method

The basic purpose of the Diffie-Hellman (D-H) method is for two parties (Alice and Bob) to agree on a shared secret (the symetric key) over an insecure medium where an attacker (Eve) is listening (these names are all common cryptography placeholder names, used to help clarify discussions of cryptography by using common names for various actors in a cryptographic exchange. A listing of these actors can be found here). A good explination of the D-H method can be found on Wikipedia.

The Code Line-by-line

Line 3: This code ensures that the print function works the same in Python 2.x and 3.x.

Line 6 & 7: First Alice and Bob agree on a Prime number: P, and a Base: G. These numbers are not secret, and can be known by Eve.
P must be a prime number, and G is a Primitive root modulo.

Line 9 & 10: Alice and Bob then each randomly select their own private integer that they keep secret (even from each other), a and b.

Line 18: Alice calculates A = g^a mod p. Alice sends A to Bob over the insecure channel (Eve can see this number).
Line 22: Bob calculates B = g^b mod p. Bob sends B to Eve over the insecure channel.

Line 28: Alice computes the shared secret, s = B^a mod p.
Line 32: Bob computes the shared secret, s = A^b mod p.

Now Alice and Bob have a shared secret key, s, that Eve does not know, even though Eve knows p, b, A, and B.

Where to go From Here

Applied Cryptography: Protocols, Algorithms, and Source Code in C: If you have any interest in cryptography, this book is incredible. The author is Bruce Schneier, well known in the cryptography and computer security field. The book covers the theory of cryptography, as well as how to properly add cryptography to your project. This is one of the best technical books I have ever read. It is a well written, authoritative, and comprehensive books on Cryptography.

Take a look at the Python bindings for OpenSSL: pyOpenSSL.

See how Diffie-Hellman is used in Perfect Forward Secrecy.

The OpenSSL Cookbook is a free eBook on OpenSSL. This is a good read.

An easy to understand article on the theory Forward Security: SSL Labs: Deploying Forward Secrecy, mentioning SSL and Diffie-Hellman.

A good article on implementing Forward Security: Configuring Apache, Nginx, and OpenSSL for Forward Secrecy.

Mozilla’s configuration guide for server-side TLS: Security/Server Side TLS. This is a fairly dense article, but is excellent and worth looking over.

Efficient methods for calculating prime numbers in Python from O’Reily: Recipe 18.10: Computing Prime Numbers.