Lab 4 — Diffie-Hellman Key Exchange

Purpose

Understand the Diffie-Hellman key exchange protocol and find values of public parameters g and p that maximize the number of unique keys K.

Theory

Diffie-Hellman allows two parties (Alice and Bob) to establish a shared secret key over an insecure channel using modular exponentiation:

Public key for Alice: A = g^a mod p
Public key for Bob:   B = g^b mod p
Shared secret:        K = B^a mod p = A^b mod p

The number of unique keys K depends on how many distinct values g^x mod p produces. This is maximized when g is a primitive root of p and p is prime.

Task — Using Excel

Download the worksheet: Diffie_Hellman_DH.xlsx

1. Column F computes g^x for x = 0, 1, 2, ... and column G computes g^x mod p using =MOD(F1,C1).
2. Try different values of g and p. Count unique values in column G — that is K.
3. Example: g=2, p=9 gives K=6 unique keys: 1, 2, 4, 8, 7, 5.
4. Find values of g and p where K is maximum (ideally K = p-1).

Example — Alice and Bob

Public params: g=7, p=2401
Alice private: a=4  =>  A = 7^4 mod 2401 = 2401  (sent to Bob)
Bob   private: b=4  =>  B = 7^4 mod 2401 = 2401  (sent to Alice)
Shared secret: K = A^b mod p = B^a mod p = 7

Report Contents

1. Screenshot of the Excel worksheet with your best g and p values.
2. The values of g, p, and K you found.
3. Description of the trend: how to choose g and p to maximize K.

Live Demo

Enter public parameters g, p and private keys a, b to compute the shared secret on the server.

Code-behind (C#)

// Lab 4 - Diffie-Hellman
protected void btnCompute_Click(object sender, EventArgs e)
{
    long g = long.Parse(txtG.Text);
    long p = long.Parse(txtP.Text);
    long a = long.Parse(txtA.Text);
    long b = long.Parse(txtB.Text);

    long ModPow(long bas, long exp, long mod)
    {
        long result = 1; bas %= mod;
        while (exp > 0) { if ((exp & 1) == 1) result = result * bas % mod; exp >>= 1; bas = bas * bas % mod; }
        return result;
    }

    long A = ModPow(g, a, p);
    long B = ModPow(g, b, p);
    long secretA = ModPow(B, a, p);
    long secretB = ModPow(A, b, p);

    bool match = secretA == secretB;
}

Conclusion

The security of Diffie-Hellman relies on the difficulty of the discrete logarithm problem. Choosing p as a large prime and g as a primitive root modulo p ensures the maximum number of possible keys, making brute-force attacks infeasible.