Diffie-Hellman marked a pivotal moment in the history of cryptography. With the introduction of Diffie-Hellman, public key cryptography was born, forever changing the landscape of data security. This remarkable algorithm, devised by Whitfield Diffie and Martin Hellman in the 1970s, unlocked a world of possibilities for programmers and computer scientists, enabling secure communication, authentication, and data protection on an unprecedented scale. In this post, we will dive into the magic of Diffie-Hellman and explore its profound impact from a programmer’s perspective in python programming language from scratch.
Vlog
Join this video to see the magic of Diffie-Hellman key exchange algorithm from a python programmer’s perspective.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Public configuration of the algorithm
We will need a base generator g – possibly a small number, and a large prime modulus p – most likely around 1K bits. These values are going to be public for everyone. Let’s use the following values in this experiment.
# base generator g = 17 # prime modulus p = 158 * ( pow(2, 800) + 25 ) + 1
Generating private keys
Alice and Bob will generate a large private keys. I will use 1024 bit private key values in this experiment. As understand from the name, private keys must be kept secret.
# Alice's private key a = random.getrandbits(1024) # Bob's private key b = random.getrandbits(1024)
Notice that 1024-bit Diffie-Hellman key equivalent is 160-bit elliptic curve cryptography key. You can adopt Elliptic Curve Diffie-Hellman to exchange keys faster with smaller keys!
Public keys
Alice and Bob will calculate the base generator g to to power of their private keys to find their public keys.
# Alice's public key # ga = pow(g, a) % p ga = pow(g, a, p) # Bob's public key # gb = pow(g, b) % p gb = pow(g, b, p)
Notice that I commented lines where we find the base generator g to the power of private keys first and find the final value for modulo p second. Instead of this, I used python’s built-in pow function with 3 arguments which are base, exponent and modulo respectively. Even though they will give same result, built-in pow function is much faster.
Besides, g to the power of a means multiplying g to itself a times.
ga = g * g * g * … * g
Here, if you find the result for modulo p in each multiplication, you will have the same result faster.
ga = ( ( (g * g mod p) * g mod p ) *g mod p * … )
This is the magic of Diffie-Hellman from the programmers’ perspective! Moreover, python pow function implements this with binary exponentiation technique which is much faster. This is another magic from the programmers’ perspective!
Discrete Logarithm Problem
Calculating a public key is very easy and fast if base generator g, private key a or b, and prime modulus p are known. This calculation takes just milliseconds. On the other hand, finding a is computationally hard if Q, g and p are known. This is called discrete logarithm problem and Diffie-Hellman depends on the hardness of this problem.
Q = ga mod p
An attacker should run a brute force attack to find the power a from this equation. To be honest, attacker might spend more than the age of the universe to find this value!
i = 0
while True:
i += 1
if pow(g, i, p) == ga:
print(f"a is {i}")
break
Key exchange
Once Alice and Bob calculated their public keys, they will publish these key values publicly. So, Alice will know Bob’s public key gb but she does not know Bob’s private key b. Similarly, Bob will know the public key of Alice, but he will not know the private key of Alice.
They will calculate the other side’s public key to the power of their own private key to calculate the shared key. Notice that this shared key must be kept secret.
# Alice's shared key sa = pow(gb, a, p) # Bob's shared key sb = pow(ga, b, p) assert sa == sb
Now, Alice and Bob can use this shared key as a key of a symmetric key encryption algorithm such as DES or AES to encrypt & decrypt messages.
Math behind the key exchange
Alice calculated Bob’s public key to the power of her private key. Similarly, Bob calculated Alice’s public key to the power of his private key. This must be equal to the generator g to the power of multiplication of a and b.
sa = (gb)a mod p
sb = (ga)b mod p
Bob calculated his public key as generator g to the power of his private key b, and Alice calculated her public key as generator g to the power of her private key a. Let’s replace these calculations in the shared key calculation.
sa = (gb)a mod p
sb = (ga)b mod p
These must be equal to each other according to the power rule of exponent.
sa = sb = (gb)a = (ga)b = ga*b
Let’s the see correctness of this in the implementation.
g_to_a_times_b = pow(g, a*b, p) assert g_to_a_times_b == sa assert g_to_a_times_b == sb
Man in the middle attack
Carol knows ga and gb values because these are published publicly. If she multiplies these values then she will get generator g to the power of sum of a and b according to the product rule of exponents. This is not equal to the shared key Alice and Bob calculated. It was generator g to the power of multiplication of a and b.
ga x gb = (ga) x (gb) = ga+b
Let’s the see correctness of this in the implementation.
g_to_a_plus_b = ( ga * gb ) % p # this must be different than the shared key assert g_to_a_plus_b != g_to_a_times_b assert g_to_a_plus_b == pow(g, a+b, p)
Conclusion
In conclusion, the Diffie-Hellman key exchange stands as a testament to the power of innovative thinking and the transformative potential of cryptography. From its humble beginnings, this algorithm has evolved into a cornerstone of modern cybersecurity, enabling secure transactions, encrypted communications, and secure data storage across countless applications and platforms. As programmers, we have the privilege of harnessing the magic of Diffie-Hellman to create robust and secure systems that safeguard the sensitive information of users around the globe. By understanding the principles and inner workings of Diffie-Hellman, we can continue to push the boundaries of secure communication, protect against cyber threats, and contribute to the ever-evolving landscape of digital security. As we bid farewell to this exploration of Diffie-Hellman, let us carry its spirit of innovation, collaboration, and resilience forward as we embark on the next chapter of securing the digital world.
I pushed the source code of this study into GitHub. You can support this work if you star⭐ its repo.
Like this blog? Support me on Patreon
