PROBLEM 1 GCD EXTENDED-EUCLID(a,b) where a b 1 if a mod b = 0 return (0,1) 2 (x,y) + EXTENDED-EUCLID(b, a mod b) 3 return (y,x y(a/b])) Use the extended Euclid algorithm presented in class to compute the multiplicative inverse of 71 in the group Z10 (i.e., find y E Z10 such that 71 .y = 1 mod 101). PROBLEM 2 Compute 1112+ mod 67 using Euler's theorem (show your work). PROBLEM 3 Textbook RSA is insecure Consider the textbook RSA signature scheme with the public key and private keys pk = e, sk = d, and d.e=1 mod (n) for an RSA modulus n = pq and: 1. Signsk(m): Compute md mod n. 2. Verifypk(m,o): Verify that o = me mod n. If an adversary knows the signature 01 of message my and the signature 02 of message m2, show how the adversary can compute the signature of m1m2. Does this scheme satisfy the notion of unforgeability given in class? PROBLEM 4 MD5 Collisions As we discussed in class, MD5 was once considered a secure collision resistant hash function. However, in 2004, a group of researchers, Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu, discovered a catastrophic flaw in the construction and published several collisions. One pair they published was: d131dd02c5e6eec4693d9a0698aff95c 2f cab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b 08823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cdao e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 08823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cdao e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 1. Using the xxd program and openssl dgst -md5, what was the collision value? 2. Suppose one uses PKCS1.5 signature padding, as discussed in class, with the MD5 hash. Explain how an attacker can break the system. 3. Extra credit: Using the fastcoll program from , find a new pair of collisions for MD5. Name the two files c1.bin and c2.bin and submit them. PROBLEM 1 GCD EXTENDED-EUCLID(a,b) where a b 1 if a mod b = 0 return (0,1) 2 (x,y) + EXTENDED-EUCLID(b, a mod b) 3 return (y,x y(a/b])) Use the extended Euclid algorithm presented in class to compute the multiplicative inverse of 71 in the group Z10 (i.e., find y E Z10 such that 71 .y = 1 mod 101). PROBLEM 2 Compute 1112+ mod 67 using Euler's theorem (show your work). PROBLEM 3 Textbook RSA is insecure Consider the textbook RSA signature scheme with the public key and private keys pk = e, sk = d, and d.e=1 mod (n) for an RSA modulus n = pq and: 1. Signsk(m): Compute md mod n. 2. Verifypk(m,o): Verify that o = me mod n. If an adversary knows the signature 01 of message my and the signature 02 of message m2, show how the adversary can compute the signature of m1m2. Does this scheme satisfy the notion of unforgeability given in class? PROBLEM 4 MD5 Collisions As we discussed in class, MD5 was once considered a secure collision resistant hash function. However, in 2004, a group of researchers, Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu, discovered a catastrophic flaw in the construction and published several collisions. One pair they published was: d131dd02c5e6eec4693d9a0698aff95c 2f cab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b 08823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cdao e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 08823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cdao e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 1. Using the xxd program and openssl dgst -md5, what was the collision value? 2. Suppose one uses PKCS1.5 signature padding, as discussed in class, with the MD5 hash. Explain how an attacker can break the system. 3. Extra credit: Using the fastcoll program from , find a new pair of collisions for MD5. Name the two files c1.bin and c2.bin and submit them
