CMSC 414: HW 2   (Due Tuesday March 28 in class)

___________________________________________________________

1.     (text 3.8)  Why is a DES weak key its own inverse?  (Hint: DES encryption and decryption are the same once the per-round keys are generated.

___________________________________________________________

2.     (text 5.1)  Would it be reasonable to compute an RSA signature on a long message m by signing m mod-n  (i.e., using (m mod-n)d mod-n as the signature).

___________________________________________________________

3.     (text 5.6)  Why do MD4, MD5, and SHA-1 require padding of messages that are already a multiple of 512-bits?

___________________________________________________________

4.      (text 6.3)  In RSA, is it possible for more than one d to work with a given e, p, and q?

___________________________________________________________

5.     (text 6.8)  Given your RSA signature on m1 and m2, how can one compute your signature on m1j×m2k for any positive integers j and k.

___________________________________________________________

6.     Using the efficient algorithm, compute 13125 mod-15.

___________________________________________________________

7.     (text 7.1)  If m and n are two positive integers, show that m/gcd(m,n) and n/gcd(m,n) are relatively prime.

___________________________________________________________

8.     (text 7.10)  If n = p1a1 × p2a2 × × × pkak where pi is prime, what is f(n).

___________________________________________________________

9.     Find all the square roots mod-15 of 1, i.e., every x in Z15 such that x×x mod-15 = 1.

___________________________________________________________

10.   Find all the square roots mod-24 of 1.

___________________________________________________________

11.  Given positive integers z1, z2, z3, x1, x2, x3, such that z1, z2, z3 are relatively prime, obtain a formula that yields a number x in Zz1×z2×z3 such that 

x mod-z1 = x1

x mod-z2 = x2

x mod-z3 = x3

___________________________________________________________