Introduction to Key Sharing: Understanding the Diffie-Hellman

This is the 6th article of the article series on Cryptology. So far, we discussed encryption, symmetric and asymmetric encryption approaches, and also how to utilize both symmetric and asymmetric approaches at the same time with hybrid approaches.

People use hybrid approaches to overcome the key exchanging issues of symmetric encryption. In brief, when using symmetric encryption, both parties should have the same secret key to encrypt and decrypt the messages. So that they can securely communicate through insecure networks.

But the main issue is, how two parties can exchange the same key without exposing it to a third party, especially when they have only an insecure network. That was the main issue with the symmetric encryption.

What is Key Sharing?

Key sharing is mandatory for establishing secure communication channels, especially when using symmetric encryption. It involves distributing the cryptographic keys between parties involved in the communication without exposing the key to the attackers or third-party, to enable secure communication.

Diffie-Hellman Key Exchange

So far you have learned why you need a key exchange mechanism, and what is key exchanging. Now it’s time to discuss one of the well-known, and widely used methods for securely exchanging cryptographic keys over unsecured public channels, called Diffie-Hellman.

This method was developed by Whitfield Diffie and Martin Hellman in 1976, and named after their names. The Diffie-Hellman method allows two parties to generate a shared secret key without directly transmitting it between them.

Math Behind Diffie-Hellman

The Diffie-Hallman key exchange idea is relayed on the difficulty of solving discreet logarithm problems. There are a few easy-to-follow steps in the Diffie-Hellman process. To understand the steps, let’s consider a scenario where Alice and Bob need to generate a shared secret key.

Step 01: Selection of Public Parameters

The first step of this process is to select the parameters that are required for the mathematical calculations. So both parties have to agree on a large prime number $ p $ and a base $ g $ (also known as the generator), which is a primitive root modulo $ p $.

Special Note: If you already noticed, it says large prime number $ p $, the reason for that statement is, that when the $ p $ is relatively big. It's hard to solve the discrete logarithm problem. This means ultimately, it’s hard to break the math behind the Diffie-Hellman algorithm.

Step 02: Decide Private Keys

Once they agree on $ p $ and $ b $, it’s time to choose their private keys. Each party has to decide their private key:

Alice selects her private key $ a $, which is a random integer where $ 1 \leq a \leq p - 2 $.
Bob selects his private key $ b $, which is a random integer where $ 1 \leq b \leq p - 2 $.

As usual, they have to keep their private keys securely, without exposing them.

Step 03: Compute Public Keys

Once private keys are decided, they have to calculate their public keys.

Alice can compute her public key $ A $, where $ A = g^a \ (\text{mod} \ p) $.
Bob can compute his public key $ B $, where $ B = g^b \ (\text{mod} \ p) $.

Step 04: Compute Shared Secret

So far, all of them decided on their public keys and computed their private keys. Now Alice sends her public key $ A $ to Bob, and Bob sends his public key $ B $ to Alice.

They can compute the shared secret using their private key and the public key of the other party as below:

Alice computes the shared secret $ S $ as $ S = B^a \ (\text{mod} \ p) $.
Bob computes the shared secret $ S $ as $ S = A^b \ (\text{mod} \ p) $.

How do Both Get the Same Shared Secret?

Now you know the process. Let’s dive into the beauty it has. As we already know, $ A = g^a \ (\text{mod} \ p) $ and $ B = g^b \ (\text{mod} \ p) $.

So from Alice’s side, this shared secret $ S $ can be computed as:

So from Alice’s side,

\begin{align} S &= B^a \pmod{p} \tag{1} \\ &= (g^b)^a \pmod{p} \tag{2} \\ &= g^{ba} \pmod{p} \tag{3} \end{align}

And also from Bob’s side,

\begin{align} S &= A^b \pmod{p} \tag{4} \\ &= (g^a)^b \pmod{p} \tag{5} \\ &= g^{ab} \pmod{p} \tag{6} \end{align}

As we all know, $$g^{ba} \equiv g^{ab} \:(mod \: p)$$

So, finally, the shared secret both parties compute is the same.

How Diffie-Hellman is Secured?

As you already know, the only piece of information going over the insecure network is the public key $ A $and $ B $, also an attacker can gain access to the public parameters such as $ p $ and $ g $.

So, the unknown puzzle for the attacker is the private keys $ a $ and $ b $. If the attacker can find any method of calculating it through the known parameters, he can calculate the shared secret $ s $, which means he breaks the security of Diffie-Hellman.

Let’s try to understand, how an attacker attempts to reveal the private key $ a $ of Alice. He already knows the public key $ A $, generator $ g $, as well as the prime number $ p $ they agreed. And also he knows that,

$$A = g^a \:(mod \: p)$$

As you see, the attacker has only one unknown parameter which is $ a $. This is where the beauty of mathematics comes into the picture.

Even though there is only one unknown parameter in the equation, you can’t solve it because of the difficulty of solving discrete logarithm problems. This problem is way hard to solve especially when the prime number $ p $ is getting larger.

Happy Reading :)