Diffie Hellman calculator in Python and my first story
It was the 1980’s, probably the best decade of all time ? I was growing up and attending elementary schools in the USA and later primary schools in India. I would normally get picked up from school by my parents. This changed later on as I graduated to the school bus and then finally cycling my way to school.
So what has all of this got to do with Diffie Hellman or Python, we will come to know shortly! Getting picked up by your mom or dad from school is great till the time you realize they cannot make it because of work. You are left standing on the school grounds, its cold and windy and you are at the mercy of the class bully you have been trying to avoid all day.
To cover for this scenario, if ever they could not make it, they would have had to send someone, a friend, the neighbor or someone from office, yippie I am saved ! This arrangement should work correct ? Well not exactly, how about if they send someone who is not known to me ? A stranger coming up to me saying my parents have asked them to pick me up, was not something I could risk, not even in the good old 80s.
We had to find out a way, for me to “authenticate” this person who comes to pick me up. A crude method was invented. I agreed with a “secret word” with my parents, if the person told me the correct secret word, then it was safe to go with them.
Fast forward to the year 2018. I had dabbled around with Cryptography for a few years during the course of my career and had finally taken the plunge to pursue a Masters in Information Security from AUT in New Zealand.
Cryptography is ubiquitous with information security and is considered as both the art and science of securing data over an insecure medium. It is broadly divided into two types Symmetric and Asymmetric. I will not go into further details in this story, as I assume if you are here reading about Diffie Hellman you already know a bit or two about Cryptography.
With Symmetric Cryptography a single key is used to both encrypt and decrypt the data being exchanged between two parties. In order to do this, both parties must first have this single key. This further leads to many challenges, how is this single key exchanged securely between Alice and Bob or in my case between my parents and me or my parents and the person they send to fetch me from school? I am glad I did not have to solve this problem in the 80s!
Diffie Hellman in the late 70’s proposed an algorithm which allowed for two parties Alice and Bob to reach a shared secret in the presence of eavesdropper Eve, without Eve being able to mathematically calculate the secret from the information exchanged by Alice and Bob to reach that very shared secret. I wrote the crude Python code which follows to understand this better. There are many implementations of the Diffie Hellman calculator out there and this is my humble attempt.
Step 1: The Common prime and primitive root
Alice and Bob choose two numbers
N = a prime number
g = the primitive root such that g < N
Step 2: Alice and Bob private keys
Next Alice and Bob choose their private keys. The private keys as the name suggests are private and these are NEVER shared.
private_a = Alice’s private key
private_b = Bob’s private key
Step 3: Alice and Bob public keys
Alice and Bob calculate their public keys as
Alice’s public key = public_a = ((g)^private_a) modulus N
Bob’s public key = public_b = ((g)^private_b) modulus N
Step 4: Alice and Bob exchange the public keys
Alice and Bob exchange the public keys, Eve can see them and store them and do whatever.
Step 5: Alice and Bob calculate the shared secret
Shared secret calculated by Alice
shared_key_one = (public_b^private_a) modulus N
substituting the value of public_b
shared_key_one = [{((g)^private_b) modulus N}^private_a] modulus N
= [(g^private_b)^private_b] modulus N
= [g^(private_b)(private_a)] modulus N
Shared secret calculated by Bob
shared_key_two = (public_a^private_b) modulus N
substituting the value of public_a
shared_key_two = [{((g)^private_a) modulus N}^private_b] modulus N
= [(g^private_a)^private_b] modulus N
= [g^(private_a)(private_b)] modulus N
Since [g^(private_b)(private_a)] modulus N is the same as
[g^(private_a)(private_b)] modulus N
Bob and Alice reach their shared secret without their private keys ever being transmitted over the insecure channel.
Eve has the following pieces of information to work with N, g, public_a and public_b. To determine the private keys of Alice and Bob, Eve will need to take a discrete log i.e.
private_a = dlog N,g (public_a)
Although it is easy to calculate the exponential and modulus, it is practically infeasible to calculate the discrete logs for large prime numbers. In short choose your primes wisely as this is where the strength lies.
The below Diffie Hellman calculator was written in an attempt to understand the mathematics under the hood as part of COMP830 course at AUT.
Sample data to test with N = 23, g = 5, private_a = 15, private_b = 27
I followed this up with a GUI version of the calculator in 2019 written utilizing Python tkinter. The code is available on GitHub here, its again a bit crude but gets the job done.
This was my first story on Medium and I hope you liked it. If you are interested in Cryptography, I would highly recommend two of my favorite academics in this field, Prof Bill Buchanan OBE and Dr. Christof Paar.
Oh and by the way we never got to use the pickup password in the 80s as my parents were always there for me. This was before my shenanigans on the school bus and the bike dashes to school, we will leave this for another day eh.
