Diffie-Hellman Protocol
The Diffie-Hellman protocol enables two parties to establish a shared secret key over a public channel without transmitting it directly.
Rather than being a method for directly encrypting messages, it is a protocol for securely generating a shared private key remotely. This key can then be used with symmetric encryption algorithms, such as AES, to encrypt and decrypt messages.
Its security relies on the discrete logarithm problem, which is computationally challenging to solve.
How Does It Work?
Imagine two users, \( A \) and \( B \), located far apart—one in Italy and the other in Australia.
They want to communicate securely by encrypting their messages using a shared secret key. However, they can’t send this key directly over the communication channel, as it could be intercepted.
The Diffie-Hellman protocol solves this problem.
First, \( A \) and \( B \) agree on two publicly known values:
- A prime number \( p \),
- A base \( g \), which serves as a generator for the multiplicative group modulo \( p \).
Each party then selects a private key that remains confidential:
- \( A \) chooses \( a \) as their private key,
- \( B \) chooses \( b \) as their private key.
They compute and exchange their public keys as follows:
- \( A \) computes \( A_{\text{pub}} = g^a \mod p \) and sends it to \( B \),
- \( B \) computes \( B_{\text{pub}} = g^b \mod p \) and sends it to \( A \).
Using the received public key and their own private key, both users calculate the shared secret key:
- \( A \) computes \( K = (B_{\text{pub}})^a \mod p = g^{ab} \mod p \),
- \( B \) computes \( K = (A_{\text{pub}})^b \mod p = g^{ab} \mod p \).
The resulting shared secret key \( K \) is identical for both parties.
This allows \( A \) and \( B \) to establish a private key without ever transmitting it directly.
They can now use this key to encrypt and decrypt messages using a symmetric encryption algorithm.
A Practical Example
Let’s walk through an example of generating a shared secret key using the Diffie-Hellman protocol between two users, \( A \) and \( B \).
After generating the key, I’ll use it to encrypt the message "ciao" with newly assigned public and private key values.
For simplicity, I’ll demonstrate this using the Caesar cipher as the encryption method.
The two users, \( A \) and \( B \), first agree on the following publicly known values:
- \( p = 23 \) (a shared prime number),
- \( g = 5 \) (a shared base).
Next, each user selects a private key, which they keep confidential:
- \( A \) selects \( e_A = 6 \),
- \( B \) selects \( e_B = 15 \).
They then calculate and share their respective public keys:
- \( A \) computes and shares \( X_A = g^{e_A} \mod p = 5^6 \mod 23 = 8 \),
- \( B \) computes and shares \( X_B = g^{e_B} \mod p = 5^{15} \mod 23 = 19 \).
Verification. To confirm these calculations, we apply the properties of exponents as follows:
- \( 5^1 \mod 23 = 5 \),
- \( 5^2 \mod 23 = 2 \),
- \( 5^4 \mod 23 = (5^2 \cdot 5^2) \mod 23 = 4 \),
- \( 5^6 \mod 23 = (5^4 \cdot 5^2) \mod 23 = 4 \cdot 2 = 8 \),
- \( 5^{15} \mod 23 = (5^8 \cdot 5^6 \cdot 5^1) \mod 23 = (16 \cdot 8 \cdot 5) \mod 23 = 19 \).
After exchanging their public keys, the users proceed to compute the shared secret key:
- \( A \) calculates \( X_{AB} = X_B^{e_A} \mod p = 19^6 \mod 23 = 2 \),
- \( B \) calculates \( X_{AB} = X_A^{e_B} \mod p = 8^{15} \mod 23 = 2 \).
In this example, the shared secret key is \( X_{AB} = 2 \).
Verification. These calculations can be verified using the following steps:
- \( 19^1 \mod 23 = 19 \),
- \( 19^2 \mod 23 = 16 \),
- \( 19^4 \mod 23 = (19^2 \cdot 19^2) \mod 23 = 3 \),
- \( 19^6 \mod 23 = (19^4 \cdot 19^2) \mod 23 = 3 \cdot 16 = 2 \),
- \( 8^1 \mod 23 = 8 \),
- \( 8^2 \mod 23 = 18 \),
- \( 8^4 \mod 23 = (8^2 \cdot 8^2) \mod 23 = 2 \),
- \( 8^{15} \mod 23 = (8^8 \cdot 8^4 \cdot 8^2 \cdot 8^1) \mod 23 = (4 \cdot 2 \cdot 18 \cdot 8) \mod 23 = 2 \).
Both users now share the same secret key, which can be used for secure communication.
Encrypting the Message
To illustrate encryption, I’ll use the Caesar cipher to encode the message "ciao" with the shared key \( X_{AB} = 2 \), shifting each letter by two positions in the alphabet:
The word "ciao" is made up of the letters "c", "i", "a", and "o", which correspond to the following numerical values in a 26-letter alphabet: \( c = 2, i = 8, a = 0, o = 14 \).
| Letter | Code | Letter | Code | Letter | Code |
|---|---|---|---|---|---|
| a | 0 | b | 1 | c | 2 |
| d | 3 | e | 4 | f | 5 |
| g | 6 | h | 7 | i | 8 |
| j | 9 | k | 10 | l | 11 |
| m | 12 | n | 13 | o | 14 |
| p | 15 | q | 16 | r | 17 |
| s | 18 | t | 19 | u | 20 |
| v | 21 | w | 22 | x | 23 |
| y | 24 | z | 25 |
Applying the shared key \( X_{AB} = 2 \) (modulo 26), the encrypted message becomes:
- \( c = (2 + 2) \mod 26 = 4 \) → "e",
- \( i = (8 + 2) \mod 26 = 10 \) → "k",
- \( a = (0 + 2) \mod 26 = 2 \) → "c",
- \( o = (14 + 2) \mod 26 = 16 \) → "q".
The encrypted message is "ekcq", which is then sent to \( B \).
Decrypting the Message
The recipient \( B \) receives the encrypted message "ekcq."
Using the shared key \( X_{AB} = 2 \), \( B \) decrypts the message as follows:
- \( e = (4 - 2) \mod 26 = 2 \) → "c",
- \( k = (10 - 2) \mod 26 = 8 \) → "i",
- \( c = (2 - 2) \mod 26 = 0 \) → "a",
- \( q = (16 - 2) \mod 26 = 14 \) → "o".
Thus, the original message, "ciao," is successfully recovered.
Is the Protocol Secure? Even if a third party intercepts the public values (\( p \), \( g \), \( X_A \), \( X_B \)), they would be unable to derive the shared secret key \( X_{AB} \) without solving the computationally difficult discrete logarithm problem. This ensures that two parties can establish a secure communication channel, even over an untrusted public network.
Security of the Protocol
The protocol's security relies on the difficulty of solving discrete logarithms. For example, given \( g^e \mod p \), it is computationally hard to deduce \( e \).
Note. Compared to RSA, Diffie-Hellman is faster because modular multiplication and exponentiation are more efficient. Additionally, it requires shorter keys to achieve the same level of security.
However, if the discrete logarithm problem becomes solvable, the protocol would be compromised.
Both RSA and Diffie-Hellman are currently secure, but Diffie-Hellman is generally more efficient for key exchange, while RSA offers greater flexibility for direct message encryption.
In practice, a hybrid approach that combines the strengths of both systems is often recommended for enhanced security.
Future Risks. With the advent of quantum computers, both RSA and Diffie-Hellman could become vulnerable, as Shor’s algorithm efficiently solves the mathematical problems they rely on. This underscores the importance of developing post-quantum cryptographic methods.
Advantages and Disadvantages of Diffie-Hellman
The protocol allows for the secure creation of a shared key over an unprotected channel. It is computationally efficient and eliminates the need for private key exchange.
However, on its own, Diffie-Hellman does not provide authentication, leaving it susceptible to Man-in-the-Middle (MitM) attacks.
Example. An attacker could intercept communications and impersonate \( A \) to \( B \), or vice versa. To prevent this, authentication via certificates is required.
Another limitation is that Diffie-Hellman does not directly encrypt messages; a symmetric cipher, such as AES, is necessary for encryption and decryption.
And so on.
