SIT 281 TRIMESTER 2 2018
ASSIGNMENT 2
DUE: By 12 NOON (Australian Eastern Standard Time), Monday 1st October 2018.
Submit a single file to the unit Cloud. The cover page is in the Assignment folder on the unit Cloud and also available at
http://www.deakin.edu.au/ data/assets/word_doc/0003/954021/SEBE- Assignment-Coversheet.docx
It should be incorporated at the beginning of your submission. Marks are given for explanations.
NO EXTENSIONS allowed without medical or other certification.
LATE ASSIGNMENTS will automatically lose 10% per day up to a maximum of three days, including weekends and holidays. Assignments submitted 4 or more days late will not be marked and are given zero. NO EXTENSIONS FOR ANY REASONS, INCLUDING THOSE BASED ON DISABILITY PLANS, PAST FRIDAY OCTOBER 5
METHOD OF SUBMISSION: Complete the cover sheet with your unit code, your full name, campus enrolled at (B, G or X) and ID; please underline your family name as recorded with Deakin.
1. Alice and Bob want to establish a common key pair using the Diffie-Hellman key exchange protocol and then use it in to send each other messages using a symmetric cipher. 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 chooses secret y=13.
Alice is in Australia while Bob is in Brazil. Carl, a Canadian friend of Alice, has been tracking the email received and sent by Alice and decides that he wants to listen in on conversations between Alice and Bob. Carl therefore sets up a man-in-the-middle attack 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 it to Bob; however, Carl intercepts this email (which Bob never receives). Similarly, Carl intercepts Bob’s e-mail containing 45313 (mod 877) (which Alice never receives).
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 x- coordinate 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
TOTAL: 20 marks
