Diffie-Hellman Key Exchange explained (Python)

Diffie–Hellman (DH) key exchange is a method of securely exchanging cryptographic keys over a public channel and was one of the first public-key protocols as originally conceptualized by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Today, DH is used for all sorts of applications like Proton Mail and SSH. A free file encryption software that uses DH is GPG (for more information, read Michael Galarnyk’s Public-key (asymmetric) Cryptography using GPG).

The Problem in End-to-End Encryption

Let’s think of a super simple situation. Imagine Michael and I decide to exchange information. Now, let’s say a hacker named Mr. Robot, is trying to intercept our message.

A logical way to stop Mr. Robot from reading our message is by encryption. In encryption, it is assumed that even if the encryption system is known, the message cannot be decrypted without the encryption key. Therefore, as long as Michael and I use the same encryption method and have the same key, we are good to go! However, just one problem…

For me to decrypt Michael’s encrypted message, I need to him to send me the key over the network. Trouble is, Mr. Robot is on a lookout for the key. If he gains access to the key, he can easily decrypt all our messages! This key exchange problem is addressed by the Diffie-Hellman algorithm.

How Diffie-Hellman solves the problem?

Diffie-Hellman works on the principle of not sharing the encryption key over the wire completely. Instead, each party consists of a public key (which everyone, including Mr. Robot, can see) and a private key (only the endpoint user can see). I do not have access to Michael’s private key. Nor does Michael have access to my private key.

Now, let’s assume we both are using a common encryption algorithm and we need to somehow reconstruct a common encryption key, without sharing too much information over the wire.

Creating the Base Class

Here is the preliminary base class below of an endpoint using DH encryption. For now, don’t worry too much about the details as I will go through each function in depth throughout the process!

class DH_Endpoint(object):
    def __init__(self, public_key1, public_key2, private_key):
        self.public_key1 = public_key1
        self.public_key2 = public_key2
        self.private_key = private_key
        self.full_key = None
        
    def generate_partial_key(self):
        partial_key = self.public_key1**self.private_key
        partial_key = partial_key%self.public_key2
        return partial_key
    
    def generate_full_key(self, partial_key_r):
        full_key = partial_key_r**self.private_key
        full_key = full_key%self.public_key2
        self.full_key = full_key
        return full_key
    
    def encrypt_message(self, message):
        encrypted_message = ""
        key = self.full_key
        for c in message:
            encrypted_message += chr(ord(c)+key)
        return encrypted_message
    
    def decrypt_message(self, encrypted_message):
        decrypted_message = ""
        key = self.full_key
        for c in encrypted_message:
            decrypted_message += chr(ord(c)-key)
        return decrypted_message

Next, let’s define the secret message Michael is planning to send me as well as our respective private and public keys set at our endpoints. Realize in real life, we would be using large prime numbers. Here, we will use small values for showing the math part easily.

message="This is a very secret message!!!"
s_public=197
s_private=199
m_public=151
m_private=157
Sadat = DH_Endpoint(s_public, m_public, s_private)
Michael = DH_Endpoint(s_public, m_public, m_private)

Partial Key Exchange

Let’s assume we cannot see anything inside Michael’s server (including his private key).

Now, I need to create a partial encryption key using 3 available information: my private and public keys.. and Micahel’s public key. Algorithmically, we have agreed to use my public key as the base and his public key as the modulo.

If we look at our function for generating the partial key, this is exactly what we are doing:

def generate_partial_key(self):
        partial_key = self.public_key1**self.private_key
        partial_key = partial_key%self.public_key2
        return partial_key

Now let’s generate this partial key and send it to Michael over the wire.

s_partial=Sadat.generate_partial_key()
print(s_partial) #147

In the same manner, Michael sends me his partial keys and sends it over to me via the wire.

m_partial=Michael.generate_partial_key()
print(m_partial)

Comparing both partial key calculations side by side:

Over the wire, Mr. Robot naturally got a glimpse of the partial key exchange. He can clearly see both public keys. Now he needs to crack our respective private keys.

All Mr. Robot knows are the partial keys and the respective public keys, including the formula used to derive the partial keys. The thing about modulo is that is the function causes the value to cycle. If you have modulo 151, the value will be between 0 and 151–1.

There is an infinite number of possible values whose modulo can either be 66 or 147. As a result, there is not enough information to derive the end users’ private keys (except brute forcing an insanely large number of possibilities). Also, realize that I am using small numbers for private and public keys. In real life, these would be massive!

Generating the Full Key

Now that we have successfully exchanged out partial keys, let’s apply the power and modulo operator again on the other person’s partial key using our own private keys as follows:

Implementing this in Python:

def generate_full_key(self, partial_key_r):
        full_key = partial_key_r**self.private_key
        full_key = full_key%self.public_key2
        self.full_key = full_key
        return full_key

Here is the code from my side:

s_full=Sadat.generate_full_key(m_partial)
print(s_full) #75

And here is the same for Michael’s side using my partial key:

m_full=Michael.generate_full_key(s_partial)
print(m_full) #75

Comparing them both side by side:

Noticed something interesting? We both ended up with the same full keys of 75! The reason this happened is due to the following mathematical relation:

Here, a and b are private keys while g and p are public keys. The important part is that we managed to exchange enough information with each other over the wire to generate a common encryption key without compromising our respective private keys.

Encryption Time!!!

Now that we have a common encryption key, it’s time to start exchange messages! As explained at the begin of this section, Michael wishes to send me an encrypted message. Here is a simple encryption algorithm I have written to encrypt Michael’s message:

def encrypt_message(self, message):
        encrypted_message = ""
        key = self.full_key
        for c in message:
            encrypted_message += chr(ord(c)+key)
        return encrypted_message

Nothing too fancy. Each character is being encoded into an integer, the key value being added and then the integer being converted back into a character. This process is repeated for each character in the message. The original message Michael wanted to share was “This is a very secret message!!!”. Let’s throw this into the algorithm with our new encryption key.

m_encrypted=Michael.encrypt_message(message)
print(m_encrypted) #'\x9f³´¾k´¾k¬kÁ°½Äk¾°®½°¿k¸°¾¾¬²°lll'

The encrypted message is “\x9f³´¾k´¾k¬kÁ°½Äk¾°®½°¿k¸°¾¾¬²°lll”, which is complete garbage to read. Mr. Robot has no clue what Michael is sharing with me over the wire.

I gained the garbage text over the wire. Now it’s time to decrypt the message on my end.

def decrypt_message(self, encrypted_message):
        decrypted_message = ""
        key = self.full_key
        for c in encrypted_message:
            decrypted_message += chr(ord(c)-key)
        return decrypted_message

This function does the reverse. While the encryption step added the key value, the decryption step will subtract the same key value.

message = Sadat.decrypt_message(m_encrypted)
print(message) #'This is a very secret message!!!'

Got the message! Nice try Mr. Robot. We managed to exchange encrypted messages without compromising our encryption keys.

Better luck with Evil Corp!

Limitations

As with all algorithms, there are drawbacks which may be needed to take into consideration in terms of End-to-End Encryption.

• Depending on your view of government surveillance, this may or may not be a great solution. Usually, when data is stored on a database (owned by the data center for example), it is possible to gain a warrant to uncover the data. While this might be taken as a factor for law enforcement and security, privacy advocates can argue that a hacker or totalitarian government can easily compromise valuable information at this data center. The idea of DH encryption is that the data at the data center is complete garbage until deciphered at the end user’s respective servers. This is the idea behind Proton Mail. If law enforcement is a concern, the data can simply be extracted from the end user’s device (e.g. searching a smartphone with a warrant).
• Another assumption we have made is that the endpoint is secure. By definition, proper user interfacing requires the hiding of all the encryption that takes place behind the scene. For example, when you are sending an email over WhatsApp or Proton Mail, the data eventually needs to be decrypted for you to view the message. Hence, if the end system is compromised, the data can still be gained unencrypted.