Diffie-Hellman Key Exchange (DHKE) Algorithm

(This Blog post is part of a collaborative work between Me and Mustapha El Idrissi, Consult his devTo page for more information: https://dev.to/appsbymuss)

Introduction & History

The Diffie-Hellman Key Exchange algorithm is a fascinating method that allows two parties to securely share a secret key over an insecure communication channel (for example: over the internet). Introduced by Whitfield Diffie and Martin Hellman in 1976 and it marked a significant advancement in the field of cryptography because, prior to its development, securely exchanging keys was a major challenge, particularly in the realm of symmetric encryption.

What is the "DHKE" Algorithm?

The Diffie-Hellman Key Exchange algorithm is a type of public key cryptography that enables two parties, who may have never communicated before and are connected over an unsecured network, to establish a shared secret. This shared secret can then be used to encrypt subsequent communications using symmetric encryption algorithms (such as AES-256).

Phase I: Initialization

Two parties, typically called Alice and Bob, agree on a common set of public parameters:
- 𝑝: A large prime number, which will be used as the "modulus".
- g: a primitive root (also known as the generator) of 𝑝, which is a number that, when raised to various powers, generates all the numbers from 1 to 𝑝−1 under modulo 𝑝.

Phase II: Key Exchange

Private Key Selection:

• Alice selects a private key X, which is a random integer that she keeps secret.
• Bob selects a private key Y, which is also a random integer that he keeps secret.

Public Key Computation and Exchange:

• Both Alice and Bob calculate their public keys respectively using the equations in the graph shown below.

• Then Alice and Bob exchange their public keys (A and B over the insecure channel)

Phase III: Shared Secret Computation

Shared Secret Derivation:

The Last step is to derive the Shared Secret using the equations below

Both calculations result in the same shared secret K, which can now be used as a key for symmetric encryption to securely communicate.

Disadvantages...

Diffie-Hellman is a great algorithm but when used alone there are vulnerabilities such as, Man-in-The-Middle attack (MiTM).
It goes like the following:

• In the exact moment that "Alice" and "Bob" have generated their Public Keys (A and B) and when one of them tries to share their public key with the other over an insecure network, an Attacker ("Aku" for example) intercepts that public key, only to replace it with his own calculated Public key.
• The process then happens the same way for both parties (Bob and Alice).
• Aku Sends his Public Key C to Bob and receives Bob's public key B.
• Aku Sends his Public Key C to Alice and receives Alice's public key A.

• Shared Secret Derivation gets calculated by Bob, Alice, and as for Aku, he does that calculation 2 times (one for Aku-Bob shared secret, and another for Aku-Alice shared secret)

• In the end, Aku ends up seeing what both Alice and Bob send each other over the network.

• Digital Certificates help against this type of Attack because it confirms that "Bob" is Bob and that "Alice" is Alice.