1.Alice and Bob want to establish a common key pair using the Diffie-Hellman keyexchange protocol and then use it in to send each other messages using a symmetriccipher. They agree by email on a prime p=877 and a primitive root (generator) a=453; these are public knowledge). Then Alice chooses secret x=25 while Bob choosessecret y=13.

Alice is in Australia while Bob is in Brazil. Carl, a Canadian friend of Alice, has beentracking the email received and sent by Alice and decides that he wants to listen in onconversations between Alice and Bob. Carl therefore sets up a man-in-the-middleattack as follows.
Carl sees the set-up agreed to by Alice and Bob and he chooses secret z = 17.
Using the primitive root and her secret, Alice computes 45325 (mod 877) and sends itto Bob; however, Carl intercepts this email (which Bob never receives). Similarly,Carl intercepts Bob’s e-mail containing 45313 (mod 877) (which Alice neverreceives).
Determine what common key Carl sets up with Bob, and his common key with Alice. 4 marks
2. Tony selects the prime p = 2357 and a primitive root g = 2 (mod 2357). Tony also chooses the private key a = 1751 and computes ga mod p which is 21751 (mod 2357) ≡ 1185. Now Tony’s public key is (p = 2357; g = 2; ga = 1185).
To encrypt a message m = 2035 to send to Tony, Bai selects a random integer k = 1520 and computes u = 21520 (mod 2357) ≡ 1430 and v = 2035 * 11851520 (mod 2357) ≡ 697, and sends the pair ( 1430, 697) to Tony. Tony decrypts to retrieve the message 2035.
Bai then sends a second message m’ = 1339 to Tony, using the same value of random integer k: he computes u = 21520 (mod 2357) ≡ 1430 and v = 1339 * 11851520 (mod 2357) ≡ 2145, and send the pair (1430, 2145) to Tony.
Oscar, works with Tony and has seen the pair (1430, 697) and m= 2035. Oscar is now keen to obtain m' without Tony knowing. He sees the second pair (1430, 2145) on Tony’s laptop. Show how he derives m’. 4 marks
3. Use a Maple procedure to find all points on the elliptic curve y2 = x3 + 295x + 2891 over Z3137.
Capture from Maple and copy into your assignment answer all points with xcoordinate less than 50. 5 marks
4. This is an RSA factoring question. In order to do the question, you need to read and understand the preliminary part.
PRELIMINARY PART: If you know the modulus n, and can steal phi(n), then you can calculate the two primes p and q such that n=pq as follows:
n – phi(n) + 1 = n – (p-1)(q-1) + 1 = n – pq +p + q -1 +1 = p+q.
This tells you the sum of p and q.
Suppose p > q (one has to be larger than the other). Then p – q = √[(p-q)2] = √[p2 +q2+2pq – 4pq] = √[p2 +q2+2pq – 4pq] = √[(p +q)2 -4n].
Since we know p+q, we now obtain p-q from this last equation. This gives us the values of p and q using the following formulas:
p = ½ [(p+q) + (p-q)] and q = ½ [(p+q) - (p-q)].
(a) Verify that using these formulas p*q = n. 4 marks
(b) You bribe someone in the lab to give you the phi value for the current RSA
scheme being used. You now know that n = 7863043 and phi(n) = 7855120. Compute the values of the factors of n using the formulas above. Show your work. 3 marks