Skip to content

Key Exchange Algorithms

Symmetric encryption algorithms solve the problem of data encryption. Taking AES encryption as an example, in the real world, if Xiao Ming wants to send an encrypted file to a passerby (Person A), he can first generate an AES key, encrypt the file, and then send the encrypted file to the recipient. Since the recipient needs to decrypt it, the AES key generated by Xiao Ming must be available to them.

The Problem: How to Transmit the Key?

The issue arises: How do you transmit the key securely over an insecure channel?

Transmitting an encrypted file over an insecure channel is not a problem because even if a hacker intercepts the encrypted file, it remains useless without the key. However, how can you securely transmit the key over an insecure channel?

To solve this problem, the Diffie-Hellman (DH) algorithm, a key exchange algorithm, comes into play.

What is the Diffie-Hellman (DH) Algorithm?

The DH algorithm addresses the challenge of exchanging keys without directly transmitting the keys between parties. This remarkable exchange mechanism is entirely supported by mathematical theories.

Let’s examine the steps involved in the DH algorithm for exchanging keys. Suppose both Party A and Party B need to exchange a key; they can proceed as follows:

  1. Party A selects a prime number p, for example, 97. The base g is a primitive root of p, for example, 5. Party A chooses a random number a, for example, 123, and computes A = g^a mod p, resulting in 34. Party A then sends p = 97, g = 5, and A = 34 to Party B.
  2. Party B, upon receiving these values, selects a random number b, for example, 456, and computes B = g^b mod p, resulting in 75. Party B also computes s = A^b mod p, resulting in 22.
  3. Party B sends B = 75 back to Party A. Party A then computes s = B^a mod p, which results in 22, the same as Party B's computation.

Thus, both parties have collaboratively agreed upon the secret key s = 22. It is important to note that this secret key s was never transmitted over the network. The values p, g, A, and B transmitted over the network are insufficient to deduce s because the chosen prime number is very large in practical implementations.

More precisely, the DH algorithm is a key agreement protocol where both parties negotiate a common key without transmitting the key itself over the network.

Understanding the DH Algorithm

If we consider a as Party A's private key and A as Party A's public key, and similarly b as Party B's private key and B as Party B's public key, the essence of the DH algorithm is that both parties generate their own private and public keys, keep their private keys secret, exchange public keys, and then generate the final secret key secretKey using their private key and the other party's public key. The mathematical principles of the DH algorithm ensure that the secretKey computed by both parties is identical.

Implementing the DH Algorithm in Java

Here is how to implement the DH algorithm in Java:

java
import java.security.*;
import java.security.spec.*;
import javax.crypto.KeyAgreement;
import java.util.HexFormat;

public class Main {
    public static void main(String[] args) {
        // Bob and Alice:
        Person bob = new Person("Bob");
        Person alice = new Person("Alice");

        // Each generates their own KeyPair:
        bob.generateKeyPair();
        alice.generateKeyPair();

        // Both parties exchange their PublicKeys:
        // Bob generates his local secret key using Alice's PublicKey:
        bob.generateSecretKey(alice.publicKey.getEncoded());
        // Alice generates her local secret key using Bob's PublicKey:
        alice.generateSecretKey(bob.publicKey.getEncoded());

        // Check if both parties have the same SecretKey:
        bob.printKeys();
        alice.printKeys();
        // Both parties have the same SecretKey, which can be used for AES encryption and decryption in subsequent communications...
    }
}

class Person {
    public final String name;

    public PublicKey publicKey;
    private PrivateKey privateKey;
    private byte[] secretKey;

    public Person(String name) {
        this.name = name;
    }

    // Generate a local KeyPair:
    public void generateKeyPair() {
        try {
            KeyPairGenerator kpGen = KeyPairGenerator.getInstance("DH");
            kpGen.initialize(512);
            KeyPair kp = kpGen.generateKeyPair();
            this.privateKey = kp.getPrivate();
            this.publicKey = kp.getPublic();
        } catch (GeneralSecurityException e) {
            throw new RuntimeException(e);
        }
    }

    public void generateSecretKey(byte[] receivedPubKeyBytes) {
        try {
            // Recover PublicKey from byte[]:
            X509EncodedKeySpec keySpec = new X509EncodedKeySpec(receivedPubKeyBytes);
            KeyFactory kf = KeyFactory.getInstance("DH");
            PublicKey receivedPublicKey = kf.generatePublic(keySpec);
            // Generate local SecretKey:
            KeyAgreement keyAgreement = KeyAgreement.getInstance("DH");
            keyAgreement.init(this.privateKey); // Own PrivateKey
            keyAgreement.doPhase(receivedPublicKey, true); // Other party's PublicKey
            // Generate SecretKey:
            this.secretKey = keyAgreement.generateSecret();
        } catch (GeneralSecurityException e) {
            throw new RuntimeException(e);
        }
    }

    public void printKeys() {
        System.out.println("Name: " + this.name);
        System.out.println("Private key: " + HexFormat.of().formatHex(this.privateKey.getEncoded()));
        System.out.println("Public key: " + HexFormat.of().formatHex(this.publicKey.getEncoded()));
        System.out.println("Secret key: " + HexFormat.of().formatHex(this.secretKey));
    }
}

However, the DH algorithm does not solve the man-in-the-middle attack, meaning Party A and Party B cannot ensure they are communicating directly with each other without an intermediary. Eliminating man-in-the-middle attacks requires additional methods.

Exercise

Use the DH algorithm to generate a secret key.

Summary

  • The DH algorithm is a key exchange protocol that allows two parties to negotiate a secret key over an insecure channel without directly transmitting the key.
  • The DH algorithm ensures that both parties derive the same secret key through their private keys and the exchanged public keys.
  • While the DH algorithm effectively facilitates secure key exchange, it does not inherently protect against man-in-the-middle attacks.
Key Exchange Algorithms has loaded