**Unformatted text preview:**

Solutions to Sample Exam 21. (a) Round 1: Peggy chooses r1randomly, computes h1≡ αr1(mod p) andcomputes h2≡ βh−11(mod p). She sends h1, h2to Victor. When Victor asks forr1, she sends it. Round 2: Peggy chooses r2randomly, computes h2≡ αr2(mod p)and computes h1≡ βh−12(mod p). She sends h1, h2to Victor. When Victor asksfor r2, she sends it.(b) Peggy will need to solve αr2≡ h2(mod p) for r2. This is a discrete logproblem, which is hard.2. (a) If there are n possible birthdays and two lists, each with around√nelements, then it is likely that some element from the first will match some elementfrom the second. In part (a), Eve makes two lists: one is the hashes of 104ofAlice’s checks, the other is the hashes of the 104fraudulent checks. Since there aren = 220≈ 106hash values, and 104is much larger than√n ≈ 103, there is almostcertainly a match. Eve then takes the signature of the hash of Alice’s check thatmatches the hash for a bad check, and uses Alice’s signature on this fraudulentcheck.(b) In this case, n ≈ 1060, so√n ≈ 1030, which is much larger than 104. There-fore it is unlikely that there is a match.3. (a) u2≡ βmrr≡ αamαkr≡ αs≡ u1.(b) am ≡ s − kr (mod p − 1). There are gcd(m, p − 1) solutions a to thiscongruence. Try each one until β ≡ αa(mod p) is satisfied.(c) Eve must satisfy the verification congruence αs≡ βmrr(mod p). She hasalready chosen m and r. Therefore she must solve (for s) the discrete log problemαs≡ c (mod p), where c = βmrris known to Eve. This should be hard to dobecause discrete logs are hard. (Note that no mention of a and k is made in theverification congruence.)4. The whole situation does not depend on the choice of the function f. Switchleft and right and put R3L3into the encryption machine. Usually, the keys wouldhave to be taken in reverse order, but here the key is the same for each round. Afterthree rounds, R0L0comes out. The verification is identical to the one given at thebottom of page 99 in the book. Switch left and right to get the original plaintextL0R0.5. (a) Eve knows P1and P2= bP1. Eve solves a discrete log to find b. Similarly,Eve knows P2and P3= a1P2. Eve solves a discrete log to find a1. She thencalculates a ≡ a−11(mod n) to get a.(b) Alice and Bob publicly agree on a large prime p. Alice chooses a secret integer awith gcd(a, p−1) = 1 and Bob chooses a secret integer b with gcd(b, p−1) = 1. Alicesends m1≡ ma(mod p) to Bob. Bob sends m2≡ mb1to Alice. Alice computesa1≡ a−1(mod p − 1) and sends m3≡ ma12(mod p) to Bob. Bob computesb1≡ b−1(mod p − 1) and computes m4≡ mb13(mod p). It can be shown thatm4≡ m mod

View Full Document