PROBLEM 3 Textbook RSA is insecure Consider the textbook RSA signature scheme with the public key and private keys pk = e, sk = d, and die = 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 my .m2. 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 2fcab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf 280373c5b 08823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cdao e99f33420f577ee8ce54b67080a80dle c69821bcb6a8839396f9652b6ff72a70 d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 08823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cdao 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 3 Textbook RSA is insecure Consider the textbook RSA signature scheme with the public key and private keys pk = e, sk = d, and die = 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 my .m2. 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 2fcab58712467eab4004583eb8fb7f89 55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf 280373c5b 08823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cdao e99f33420f577ee8ce54b67080a80dle c69821bcb6a8839396f9652b6ff72a70 d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 08823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cdao 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
