07-02: Exercises¶

Question¶

Alice and Bob want to establish a shared secret using Diffie-Hellman key exchange over a public channel. They agree on the following public parameters:

Prime modulus: p = 23
Generator: g = 5

Their private values (chosen secretly, never transmitted) are:

Alice's private value: a = 6
Bob's private value: b = 15
Compute Alice's public value A that she sends to Bob.
Compute Bob's public value B that he sends to Alice.
Compute the shared secret as calculated by Alice (using Bob's public value and her own private value).
Compute the shared secret as calculated by Bob (using Alice's public value and his own private value).
Confirm both sides arrive at the same shared secret.

Solution¶

Step 0: Recall the Diffie-Hellman formulas¶

Alice computes: A = g^a mod p
Bob computes: B = g^b mod p
Alice sends A to Bob (in the open); Bob sends B to Alice (in the open).
Alice then computes the shared secret: s = B^a mod p
Bob then computes the shared secret: s = A^b mod p
Because of modular exponentiation's properties, both sides land on the same value:
(g^b)a mod p = (g^a)b mod p = g^(ab) mod p

An eavesdropper who only sees p, g, A, and B cannot feasibly recover a, b, or the shared secret without solving the discrete logarithm problem.

Step 1: Alice computes her public value A = 5^6 mod 23¶

Compute 5^6 step by step, reducing mod 23 as we go:

5^1 = 5
5^2 = 25 → 25 mod 23 = 2
5^3 = 5^2 × 5 = 2 × 5 = 10
5^4 = 5^3 × 5 = 10 × 5 = 50 → 50 mod 23 = 4
5^5 = 5^4 × 5 = 4 × 5 = 20
5^6 = 5^5 × 5 = 20 × 5 = 100 → 100 mod 23: 23 × 4 = 92, 100 − 92 = 8

A = 8

Alice sends A = 8 to Bob over the public channel.

Step 2: Bob computes his public value B = 5^15 mod 23¶

Use repeated squaring. First build up powers of 2:

5^1 = 5
5^2 = 25 mod 23 = 2
5^4 = (5²⁾2 = 2^2 = 4
5^8 = (5⁴⁾2 = 4^2 = 16

Now write 15 in binary: 15 = 8 + 4 + 2 + 1

So:

5^15 = 5^8 × 5^4 × 5^2 × 5^1 = 16 × 4 × 2 × 5

Multiply step by step, reducing mod 23:

16 × 4 = 64 → 64 mod 23: 23 × 2 = 46, 64 − 46 = 18
18 × 2 = 36 → 36 mod 23 = 13
13 × 5 = 65 → 65 mod 23: 23 × 2 = 46, 65 − 46 = 19

B = 19

Bob sends B = 19 to Alice over the public channel.

Step 3: Alice computes the shared secret s = B^a mod p = 19^6 mod 23¶

Compute 19^6 mod 23 step by step:

19^1 = 19
19^2 = 361 → 361 mod 23: 23 × 15 = 345, 361 − 345 = 16
19^3 = 19^2 × 19 = 16 × 19 = 304 → 304 mod 23: 23 × 13 = 299, 304 − 299 = 5
19^4 = 19^3 × 19 = 5 × 19 = 95 → 95 mod 23: 23 × 4 = 92, 95 − 92 = 3
19^5 = 19^4 × 19 = 3 × 19 = 57 → 57 mod 23: 23 × 2 = 46, 57 − 46 = 11
19^6 = 19^5 × 19 = 11 × 19 = 209 → 209 mod 23: 23 × 9 = 207, 209 − 207 = 2

Alice's shared secret = 2

Step 4: Bob computes the shared secret s = A^b mod p = 8^15 mod 23¶

Use repeated squaring. First build up powers of 2:

8^1 = 8
8^2 = 64 → 64 mod 23 = 18
8^4 = (8²⁾2 = 18^2 = 324 → 324 mod 23: 23 × 14 = 322, 324 − 322 = 2
8^8 = (8⁴⁾2 = 2^2 = 4

Again, 15 = 8 + 4 + 2 + 1, so:

8^15 = 8^8 × 8^4 × 8^2 × 8^1 = 4 × 2 × 18 × 8

Multiply step by step, reducing mod 23:

4 × 2 = 8
8 × 18 = 144 → 144 mod 23: 23 × 6 = 138, 144 − 138 = 6
6 × 8 = 48 → 48 mod 23 = 2

Bob's shared secret = 2

Step 5: Confirm both sides match¶

Alice computed: 2
Bob computed: 2

Both sides independently arrive at the same shared secret without ever transmitting a, b, or the secret itself directly — only p, g, A, and B ever crossed the public channel.

Final Answer¶

Public parameters: p = 23, g = 5
Alice's public value: A = 8
Bob's public value: B = 19
Shared secret (computed by both Alice and Bob): 2