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.

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.

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.

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

**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) \).

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.

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 :)

D Chandrajith

Technical Lead

Series: Cryptography and Encryption Series

01

read in 2 min

27 May 2024

02

read in 4 min

03 June 2024

03

read in 4 min

10 June 2024

04

read in 3 min

18 June 2024

05

read in 4 min

26 June 2024

06

read in 4 min

28 June 2024

07

read in 4 min

01 July 2024

08

read in 6 min

08 July 2024

09

read in 5 min

09 July 2024

10

read in 3 min

15 July 2024