Module 137

Complete Diffie-Hellman Key Exchange Numerical Example

(Exactly in exam style — step-by-step, full marks guaranteed — 10–12 marks question)

Question:
Alice and Bob want to agree on a shared secret key using Diffie-Hellman key exchange.
They publicly agree on:

• A large prime number: p = 23
• A primitive root modulo p (generator): g = 5

Alice chooses her private key: a = 6
Bob chooses his private key: b = 15

Show all steps and find the final common secret key that both Alice and Bob compute.

Step-by-Step Solution (Write exactly like this in exam)

Step 1: Publicly agreed parameters (known to everyone)
Prime modulus: p = 23
Primitive root (base): g = 5

Step 2: Alice’s computation
Private key of Alice (secret): a = 6

Alice computes her public value A:
A = g^a mod p
A = 5⁶ mod 23

Calculate using successive squaring:
5¹ = 5
5² = 25 ≡ 25 − 23 = 2
5⁴ = (5²)² = 2² = 4
5⁶ = 5⁴ × 5² = 4 × 2 = 8

∴ A = 8

Alice sends A = 8 to Bob (over public channel)

Step 3: Bob’s computation
Private key of Bob (secret): b = 15

Bob computes his public value B:
B = g^b mod p
B = 5¹⁵ mod 23

Successive squaring method:
5¹ = 5
5² = 2
5⁴ = 4
5⁸ = 4² = 16

Now 15 in binary: 1111₂ = 8 + 4 + 2 + 1
∴ 5¹⁵ = 5⁸ × 5⁴ × 5² × 5¹
= 16 × 4 × 2 × 5

16 × 4 = 64 ≡ 64 − 2×23 = 64 − 46 = 18
18 × 2 = 36 ≡ 36 − 23 = 13
13 × 5 = 65 ≡ 65 − 2×23 = 65 − 46 = 19

∴ B = 19

Bob sends B = 19 to Alice (publicly)

Step 4: Alice computes the shared secret key
Alice receives B = 19
She computes:
K = B^a mod p
K = 19⁶ mod 23

Compute 19⁶ mod 23:
First, 19 ≡ −4 mod 23 (easier) → but let’s do direct:
19² = 361 → 361 ÷ 23 = 15×23 = 345 → 361−345 = 16 → 19² ≡ 16
19⁴ = (19²)² = 16² = 256 → 256 ÷ 23 = 11×23 = 253 → 256−253 = 3 → 19⁴ ≡ 3
19⁶ = 19⁴ × 19² = 3 × 16 = 48 → 48 − 2×23 = 48 − 46 = 2

∴ Shared key computed by Alice: K = 2

Step 5: Bob computes the shared secret key
Bob receives A = 8
He computes:
K = A^b mod p
K = 8¹⁵ mod 23

8² = 64 ≡ 64 − 2×23 = 64 − 46 = 18
8⁴ = 18² = 324 → 324 ÷ 23 = 14×23 = 322 → 324−322 = 2 → 8⁴ ≡ 2
8⁸ = 2² = 4

Now 15 = 1111₂ → 8¹⁵ = 8⁸ × 8⁴ × 8² × 8¹ = 4 × 2 × 18 × 8

4 × 2 = 8
8 × 18 = 144 → 144 − 6×23 = 144 − 138 = 6
6 × 8 = 48 → 48 − 2×23 = 48 − 46 = 2

∴ Shared key computed by Bob: K = 2

Final Shared Secret Key = 2
Both Alice and Bob now have the same secret key: 2
This key can now be used for symmetric encryption (e.g., AES).

Summary Table (Always include in exam)

Parameter	Value
Prime p	23
Generator g	5
Alice private key (a)	6
Bob private key (b)	15
Alice public value (A)	8
Bob public value (B)	19
Shared secret key (K)	2 (both sides)

Why it works (1–2 lines for theory marks)

Even though A and B are public, computing g^(ab) from g^a and g^b is the Discrete Logarithm Problem → computationally infeasible for large p.

Most Common Exam Variations

• Change p=71, g=7 → still same steps
• Ask to verify g is primitive root (not needed here, but know order concept)
• Man-in-the-middle attack → mention Eve can intercept

Practice this example with p=23, g=5 → 100% question has appeared in Mumbai University, VTU, Anna University, etc.

You’re now fully ready for Diffie-Hellman numerical! 🚀