**Unformatted text preview:**

MATH/CMSC 456 EXAM 2 ANSWERS May 7, 20031. (a) 11 ≡ 44 · 2−2≡ 36· 3−20≡ 3−14. Since 3136≡ 1, we have 11 ≡ 3−14+136≡3122. Therefore, x = 122.(b) The line through (0,1) and (3,0) has slope −1/3 ≡ 2 (mod 7). The line isy ≡ 2x+1. Intersecting with E yields (2x + 1)2≡ x3+1, so x3−4x2+··· ≡ 0. Thesum of the roots is 4 (= negative the coefficient of x2), so 4 = 0 + 3 + x. Therefore,x = 1. The y-coordinate of the intersection is y = 2x + 1 = 3. Reflect across thex-axis to get the answer (1, −3), or (1, 4) (since −3 ≡ 4 (mod 7)).(c) Since H(x + 10100) = H(x), it is easy to find collisions.2. (a) If βα−i≡ αj, then β ≡ αi+j, so x ≡ i + j (mod p − 1).(b) If there are N birthdays, the birthday attack needs approximately√N on eachlist to get a 50% chance of a match. Therefore, M should be approximately 1015.(c) Make two lists. One is B − iA for√N random values of i. The other is jA for√N random values of j. Look for a match. A match yields B = (i + j)A.3. (a)v1≡ α(mα−k)s(αa)−f (r)≡ msα1−ks−af (r)≡ msα0≡ v2.(b) One way: Eve follows steps (1) through (4). Since a is multiplied by f(r) = 0,she never needs a, which is the only secret Alice has.Another way: Choose s = 1 and r ≡ α−1m.4. (a) Peggy chooses random integers r1and r3and computes m1≡ αr1andm3≡ αr3. She lets m3≡ βm−11m−13. Since Victor does not ask for r2, Peggy doesnot need to know it.(b) If Peggy does not know x, then she cannot know all of r1, r2, r3, since r1+ r2+r3≡ x (mod p − 1). Therefore, there is at least one of the ri’s that Peggy doesnot know. The probability is 2/3 that Victor will ask for that value in any givenround. Therefore, after several rounds, it is very likely that he will discover thatPeggy does not know x.5. Note that L2= R1and R2= L1⊕ f(K, R1). Switch L2and R2to get R2L2.Now put these into the encryption machine. After one round, we obtain:On the left: L2= R1.On the right: R2⊕ f(K, L2) = (L1⊕ f(K, R1)) ⊕ f(K, R1) = L1.Therefore, one round yields R1L1.The same reasoning shows that the second round yields R0L0. Now switch leftand right to obtain

View Full Document