Diffie-Hellman key exchange (sometimes Diffie-Hellman-Merkel, often abbreviated as D-H) allows two parties to derive a shared secret key over an insecure channel. This means that if Alice and Bob are strangers on the internet and they want to create a secure, encrypted channel for communication, they can do so even if an attacker, Eve, is listening to all of their communications. The complete source code for this post is available on github.
Warning: The code in this tutorial is for instructional purposes only. It’s unwise to use homebrew encryption code in sensitive or production environments. If you need real security, use an established, audited and thoroughly tested encryption package like OpenSSL or GNUTLS.
When I first learned about Diffie-Hellman, I didn’t understand how such a scheme could be possible. If all communications between two parties are being intercepted, how can they establish a shared encryption key that the attacker won’t also know? The answer lies in the discrete logarithm problem.
The Discrete Logarithm
The discrete log problem involves solving $$a^x=b \pmod p$$ where \(a, x\) and \(b\) are real numbers and \(p\) is prime.
For instance, \(3\) is a solution to \(2^x=8 \pmod {11}\) because \(2^3 \pmod {11} = 8\). However, \(3\) isn’t the only solution. \(13, 23\) and \(43\) are also solutions because they each solve the equation \(\log_2 8 = x\pmod {11}\) or \(2^x \pmod {11} = 8\). Because of the modulus operation, there are infinitely many solutions to each discrete log equation.
The discrete log problem is this: Given the values of \(a, b\) and \(p\) in the equation \(a^x=b \pmod p\), it’s difficult to determine which value of \(x\) was the original solution to the equation. The discrete log problem is computationally difficult, and no known algorithm can efficiently solve the problem using currently available computers. Schor’s algorithm can be used to solve the discrete log problem, but it requires a quantum computer that hasn’t been realized yet.
How Diffie-Hellman Works
Diffie-Hellman Key Exchange involves two parties computing exponents modulo a large prime, exchanging results, and using the combination of publicly exchanged results with private values to derive a shared secret. An eavesdropper can see both publicly exchanged values but since he or she can’t access the parties’ private values, the eavesdropper can’t compute the same shared secret. Wikipedia’s paint analogy does a good job of showing how it works:
Diffie-Hellman analogue, performed with paint.
Since Eve the eavesdropper doesn’t know Alice or Bob’s secret paint colors, she won’t be able to derive the correct common secret color.
Both parties agree on a prime \(p\) and a generator \(g\) ahead of time, or the values can be exchanged publicly over an insecure channel. In practice, \(g\) is usually \(2, 3\) or \(5\) and \(p\) is usually taken from RFC 3526 or generated dynamically.
- Alice computes \(A\) and sends it to Bob. $$g^a \pmod p = A$$
- Bob computes \(B\) and sends it to Alice. \(A\) and \(B\) are Alice and Bob’s public keys, respectively. $$g^b \pmod p = B$$
- Alice computes the shared secred, \(s\):$$B^a \pmod p = (g^b)^a \pmod p = s$$
- Bob performs an equivalent computation to arrive at the same value for \(s\): $$A^b \pmod p = (g^a)^b \pmod p = s$$
Since \(g^{ab} \pmod p = g^{ba} \pmod p\), Alice and Bob will both compute the same secret. Even if Eve captures \(A\) and \(B\), since she doesn’t know \(a\) or \(b\) (the secret paint colors in the illustration) she won’t be able to compute the same shared secret as Alice and Bob.
A variant of Diffie-Hellman can be used between more than two parties. Although the protocol protects against eavesdropping, it doesn’t protect against Man in the Middle attacks. If Eve gets between Alice and Bob and convinces each that she is the other, she can negotiate separate keys with each party and transparently intercept messages. Unless authentication is used in addition to Diffie-Hellman, neither Alice nor Bob will know that Eve is an impostor.
Simple Diffie-Hellman Example (in Python)
Python provides a handy and computationally efficient method for modular exponentiation (exponentiation by squares, in case you’re interested). Instead of using a**b % c to compute modular exponents, use pow(a, b, c). The two representations are functionally equivalent, but pow() is faster and uses less memory.
The core of Diffie-Hellman is simple to implement. Generate a secure random number for each private key (\(a\) and \(b\)), perform the modular exponentiation and pass the result (\(A\) or \(B\)) to the other party:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
from random import getrandbits g = 2 prime = 7919 bits = 32 a = getrandbits(bits) A = pow(g, a, prime) b = getrandbits(bits) B = pow(g, b, prime) s1 = pow(A, b, prime) s2 = pow(B, a, prime) if(s1 == s2): print "Shared secrets match: ", s1 |
RFC 3526 specifies safe primes that can be used in Diffie-Hellman implementations and provides some key-strength estimates for each prime. For instance, if you want to generate a 128-bit AES key, you should use the 3072-bit MODP prime with an exponent that has at least 256 bits of randomness. To generate a 256-bit AES key, use the 8192-bit MODP prime with an exponent that has at least 512 bits of randomness. The resulting shared secret can then be hashed to obtain a key of usable size.
Diffie-Hellman in Python: A more practical example
The DiffieHellman python class is a fully-functional implementation of the Diffie-Hellman protocol. It includes functions for generating private and public keys, shared secrets and a usable encryption key. It also includes a function to make sure a received public key is valid by verifying that its Legendre Symbol is equal to one.
Verifying the Legendre symbol of a public key is recommended by NIST SP800-56, but the publication doesn’t assume the use of safe primes. Checking the Legendre symbol isn’t really necessary when safe primes are used, and OpenSSL doesn’t bother to check, but I do (more background here).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#!/usr/bin/env python from binascii import hexlify import hashlib # If a secure random number generator is unavailable, exit with an error. try: import Crypto.Random.random secure_random = Crypto.Random.random.getrandbits except ImportError: import OpenSSL secure_random = lambda x: long(hexlify(OpenSSL.rand.bytes(x>>3)), 16) class DiffieHellman(object): """ An implementation of the Diffie-Hellman protocol. This class uses the 6144-bit MODP Group (Group 17) from RFC 3526. This prime is sufficient to generate an AES 256 key when used with a 540+ bit exponent. """ prime = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A92108011A723C12A787E6D788719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6287C59474E6BC05D99B2964FA090C3A2233BA186515BE7ED1F612970CEE2D7AFB81BDD762170481CD0069127D5B05AA993B4EA988D8FDDC186FFB7DC90A6C08F4DF435C93402849236C3FAB4D27C7026C1D4DCB2602646DEC9751E763DBA37BDF8FF9406AD9E530EE5DB382F413001AEB06A53ED9027D831179727B0865A8918DA3EDBEBCF9B14ED44CE6CBACED4BB1BDB7F1447E6CC254B332051512BD7AF426FB8F401378CD2BF5983CA01C64B92ECF032EA15D1721D03F482D7CE6E74FEF6D55E702F46980C82B5A84031900B1C9E59E7C97FBEC7E8F323A97A7E36CC88BE0F1D45B7FF585AC54BD407B22B4154AACC8F6D7EBF48E1D814CC5ED20F8037E0A79715EEF29BE32806A1D58BB7C5DA76F550AA3D8A1FBFF0EB19CCB1A313D55CDA56C9EC2EF29632387FE8D76E3C0468043E8F663F4860EE12BF2D5B0B7474D6E694F91E6DCC4024FFFFFFFFFFFFFFFF generator = 2 def __init__(self): """ Generate the public and private keys. """ self.privateKey = self.genPrivateKey(576) self.publicKey = self.genPublicKey() def genPrivateKey(self, bits): """ Generate a private key using a secure random number generator. """ return secure_random(bits) def genPublicKey(self): """ Generate a public key X with g**x % p. """ return pow(self.generator, self.privateKey, self.prime) def checkPublicKey(self, otherKey): """ Check the other party's public key to make sure it's valid. Since a safe prime is used, verify that the Legendre symbol is equal to one. """ if(otherKey > 2 and otherKey < self.prime - 1): if(pow(otherKey, (self.prime - 1)/2, self.prime) == 1): return True return False def genSecret(self, privateKey, otherKey): """ Check to make sure the public key is valid, then combine it with the private key to generate a shared secret. """ if(self.checkPublicKey(otherKey) == True): sharedSecret = pow(otherKey, privateKey, self.prime) return sharedSecret else: raise Exception("Invalid public key.") def genKey(self, otherKey): """ Derive the shared secret, then hash it to obtain the shared key. """ self.sharedSecret = self.genSecret(self.privateKey, otherKey) s = hashlib.sha256() s.update(str(self.sharedSecret)) self.key = s.digest() def getKey(self): """ Return the shared secret key """ return self.key def showParams(self): """ Show the parameters of the Diffie Hellman agreement. """ print "Parameters:" print print "Prime: ", self.prime print "Generator: ", self.generator print "Private key: ", self.privateKey print "Public key: ", self.publicKey print def showResults(self): """ Show the results of a Diffie-Hellman exchange. """ print "Results:" print print "Shared secret: ", self.sharedSecret print "Shared key: ", hexlify(self.key) print if __name__=="__main__": """ Run an example Diffie-Hellman exchange """ a = DiffieHellman() b = DiffieHellman() a.genKey(b.publicKey) b.genKey(a.publicKey) if(a.getKey() == b.getKey()): print "Shared keys match." print "Key:", hexlify(a.key) else: print "Shared secrets didn't match!" print "Shared secret: ", a.genSecret(b.publicKey) print "Shared secret: ", b.genSecret(a.publicKey) |
The following code will create two instances of the DiffieHellman class and perform an exchange:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
""" Perform an example Diffie-Hellman exchange """ a = DiffieHellman() b = DiffieHellman() a.genKey(b.publicKey) b.genKey(a.publicKey) if(a.getKey() == b.getKey()): print "Shared keys match." print "Key:", hexlify(a.key) else: print "Shared secrets didn't match!" print "Shared secret: ", a.genSecret(b.publicKey) print "Shared secret: ", b.genSecret(a.publicKey) |
The complete source code for this post is available in the pyDHE repository on github.
Further Reading
RFC 2631 – Diffie-Hellman Key Agreement Method
Incoming search terms:
diffie hellman python
python diffie hellman
diffie hellman key exchange algorithm code in java
java code for diffie hellman key exchange algorithm
python diffie hellman aes key
diffie hellman in python
diffie hellman python example
java program for diffie-hellman key exchange
diffie helman python
diffie—Hellman python
That’s informative. Great.
I have a little question.
In public-key crypto theory, Alice encrypt her data using Bob’s public key and send bob. Bob decrypt her data using his public key. And Bob encrypt vice versa. I am confused about D-H key exchange. Is it the same concept as the pk crypto?
Thank you for your post.
RSA is more like the kind of asymmetric encryption you’re describing. Whereas Diffie-Hellman uses public and private keys to establish a shared secret, RSA is used to encrypt data with a public key and decrypt the cyphertext with a private key.
Hey evening,
the code in “Diffie-Hellman in Python: A more practical example” is not able to run in Python 3, do you have any other ways?
what kind of error is it giving?
Hi Mark, thank you for the reply,
Error:
Traceback (most recent call last):
File “C:/Users/jo12/Desktop/Test Python/p.py”, line 105, in <module>
a.genKey(b.publicKey)
File “C:/Users/jo12/Desktop/Test Python/p.py”, line 70, in genKey
s.update(str(self.sharedSecret))
TypeError: Unicode-objects must be encoded before hashing
Hi Mark, thank you for the reply,
Error:
Traceback (most recent call last):
File “C:/Users/jo12/Desktop/Test Python/p.py”, line 105, in
a.genKey(b.publicKey)
File “C:/Users/jo12/Desktop/Test Python/p.py”, line 70, in genKey
s.update(str(self.sharedSecret))
TypeError: Unicode-objects must be encoded before hashing