In modern cryptography, secure key exchange is essential for private communication over public channels. One of the earliest practical implementations of public key exchange is the Diffie-Hellman Key Exchange. This post will guide you through the concept and a simple Java implementation to illustrate how two parties can securely generate a shared secret key.

What is Diffie-Hellman Key Exchange?

The Diffie-Hellman Key Exchange (developed in 1976) is a method that allows two users to exchange cryptographic keys over a public channel securely. The beauty of this method is that both parties can compute the same secret key independently, which can then be used for encrypting future messages.

Here’s how it works conceptually:

1. Two parties (say, Alice and Bob) agree on a large prime number p and a primitive root g of that number.
2. Alice chooses a private key x, computes R1 = g^x mod p and sends R1 to Bob.
3. Bob chooses a private key y, computes R2 = g^y mod p and sends R2 to Alice.
4. Alice computes the secret key as k1 = R2^x mod p.
5. Bob computes the secret key as k2 = R1^y mod p.
6. Both k1 and k2 will be the same due to properties of modular arithmetic:
   g^(xy) mod p = g^(yx) mod p.

Java Implementation

Here’s a basic Java program that demonstrates the concept:

package diffie;

import java.io.*;
import java.math.BigInteger;

class Diffie {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // Step 1: Accept a prime number 'p'
        System.out.println("Enter prime number:");
        BigInteger p = new BigInteger(br.readLine());

        // Step 2: Accept a primitive root 'g' of p
        System.out.print("Enter primitive root of " + p + ": ");
        BigInteger g = new BigInteger(br.readLine());

        // Step 3: Alice chooses her private key 'x'
        System.out.println("Enter value for x less than " + p + ":");
        BigInteger x = new BigInteger(br.readLine());
        BigInteger R1 = g.modPow(x, p);  // R1 = g^x mod p
        System.out.println("R1 = " + R1); // Alice's public value

        // Step 4: Bob chooses his private key 'y'
        System.out.print("Enter value for y less than " + p + ":");
        BigInteger y = new BigInteger(br.readLine());
        BigInteger R2 = g.modPow(y, p);  // R2 = g^y mod p
        System.out.println("R2 = " + R2); // Bob's public value

        // Step 5: Both compute the shared secret key
        BigInteger k1 = R2.modPow(x, p); // Alice's computation
        System.out.println("Key calculated at Alice's side: " + k1);

        BigInteger k2 = R1.modPow(y, p); // Bob's computation
        System.out.println("Key calculated at Bob's side: " + k2);

        System.out.println("Diffie-Hellman secret key encryption has taken place.");
    }
}

Sample Output

Below is a sample run of the program:

Enter prime number:
11
Enter primitive root of 11: 7
Enter value for x less than 11:
3
R1 = 2
Enter value for y less than 11:
6
R2 = 4
Key calculated at Alice's side: 9
Key calculated at Bob's side: 9
Diffie-Hellman secret key encryption has taken place.

Explanation of Output

• We chose p = 11 and g = 7.
• Alice selects private key x = 3:
  R1 = 7^3 mod 11 = 343 mod 11 = 2
• Bob selects private key y = 6:
  R2 = 7^6 mod 11 = 117649 mod 11 = 4
• Alice computes:
  k1 = R2^x mod p = 4^3 mod 11 = 64 mod 11 = 9
• Bob computes:
  k2 = R1^y mod p = 2^6 mod 11 = 64 mod 11 = 9

Both parties independently calculated the same secret key: 9. This key can now be used for symmetric encryption between Alice and Bob.

The Diffie-Hellman algorithm lays the foundation for secure communication. While real-world systems use larger keys and more advanced implementations, this simple Java program helps you understand the core concept.