The basic problem of cryptography is the following: Alice and Bob want to communicate over a public channel such that an eavesdropper cannot understand their communication. For that reason, they encrypt their messages before sending and decrypt their messages after receiving. This encryption and decryption depends on an cryptography method that is publicly known and a secret cryptographic key (which is just a number), that is only known to Alice and Bob. Without knowing the secret, an eavesdropper cannot efficiently decipher the encrypted communication. This requires, however, that Alice and Bob agree on a shared secret in the first place. In many situations, they can only do so via public communication. Paradoxically, even through a public communication channel they can still agree on a shared secret number that is difficult to guess for any eavesdropper. An algorithm for that purpose is known as the Diffie-Hellman-Merkle Key Exchange. It involves computation over finite fields Fp, for which we first review some facts. Let p N be a prime number and let g Fp be an element of the finite field Fp. When k N, then the k-th power of g is written g k and defined in the usual manner: g 1 = g, g 2 = g g, g 3 = g g g, and so on, where all multiplications are computed within Fp. Of course, the typical laws of arithmetics hold: when k, l N, then g k g l = g kl and (g k ) l = g kl. Since Fp has only p elements, the values g, g2 , . . . , gp Fp already give all possible powers of g. The Diffie-Hellman-Merkle Key Exchange between Alice and Bob works as follows. (i) Public: Alice and Bob agree publicly on prime number p and on g Fp. (ii) Private: Alice picks a {1, . . . , p} and computes A = g a in Fp. (iii) Private: Bob picks b {1, . . . , p} and computes B = g b in Fp. (iv) Public: Alice sends her result A to Bob, and Bob send his result B to Alice. (v) Private: Alice computes A0 = Ba in Fp. (vi) Private: Bob computes B0 = Ab in Fp. One can show (as you do in this exercise) that A0 = B0 , which is the secret number that Alice and Bob agree upon. The secret values a and b are only know to Alice and Bob, respectively, and are never shared directly. The motivation for the Diffie-Hellman-Merkle Key Exchange is the following: given g Fp and k N, it is quite easy to compute c = g k , as you have seen in Exercise 3 above. However, when p is a very large prime number, then it is very difficult to compute the exponent k from the base g and the power c. Essentially, one cannot do much better than simply computing g, g2 , g3 , . . . until we hit c. This is known as discrete logarithm problem. When p is a very large prime number, then the discrete logarithm problem is considered infeasible for practical purposes. Alice and Bobs public communication involves the prime number p, the base g, and the two intermediate values A and B. But it is difficult to compute the shared secret number C from A and B alone. An eavesdropper would like to compute the exponents a and b used by Alice and Bob, but as mentioned above, this is practically very difficult. Hence, by all practical means, the shared secret number is only known to Alice and Bob. For practical purposes, p is typically chosen as a very large prime number, and g is a so-called primitive root modulo p, which means that the powers g, g2 , g3 , . . . cover all of Fp. For example, 5 is a primitive root modulo 23, and 20 is a primitive root module 37. But 2 is not a primitive root modulo 7. Complete the following exercises: (1) Explain why the number A0 computed by Alice and the number B0 computed by Bob are the same, i.e., A0 = B0 . (2) Suppose that Alice and Bob have agreed on p = 23 and g = 5 (which is a primitive root modulo 23). Compute the Diffie-Hellman-Merkle Key Exchange with these parameters, assuming that Alice picks her secret number a = 4 and Bob picks his secret number b = 3. Verify that their shared secret is 18 F23. Show the computations. (3) Pick a friend and share a secret! Perform the Diffie-Hellman-Merkle Key Exchange with the prime number p = 37 and g = 20