**Unformatted text preview:**

MATH/CMSC 456 (Washington) Sample Exam 21. Suppose p is a large prime, α is a primitive root, and β ≡ αa(mod p). Thenumbers p, α, β are public. Peggy wants to prove to Victor that she knows a withoutrevealing it. They do the following:(1) Peggy chooses a random number r (mod p − 1).(2) Peggy computes h1≡ αr(mod p) and h2≡ xαa−r(mod p) and sendsh1, h2to Victor.(3) Victor chooses i = 1 or i = 2 asks Peggy to send either r1= r or r2= a − r(mod p − 1).(4) Victor checks that h1h2≡ β (mod p) and that hi≡ αri(mod p).(5) They repeat steps (1) through (4) one more time.(a) Suppose Peggy does not know a but she correctly guesses that Victor will askfor r1in the first round and r2in the second round. What strategy should Peggyuse to be able to answer both of Victor’s questions correctly?(b) Suppose Peggy does not know a. She knows the value of r1such that αr1≡ h2(mod p), but Victor asks for r2in the first round. Why will it be difficult for Peggyto compute the value of r2quickly?2. (a) Suppose Alice uses a budget hash function h to sign her checks, so shesigns a check m by signing h(m) where h(m) is a string of 20 binary bits. Thisyields pairs (m, sig(h(m)), which she stores on her computer. Suppose Eve has aset of 104fraudulent checks and she wants to put Alice’s signature on at least oneof them. Eve breaks into Alice’s computer and obtains a list of 104signed checks(m, sig(h(m)). Describe how Eve can (with very high probability) put Alice’ssignature on some fraudulent check? (Note: 220≈ 106)(b) Suppose Alice upgrades to a better hash function h1such that h1(m) is a stringof around 200 bits. Why is it unlikely that Eve will be able to use a birthday attackto put Alice’s signature on a fraudulent check.3. Consider the following signature algorithm. Alice wants to sign a message m.She chooses a large prime p and a primitive root α. She chooses a secret integera and calculates β ≡ αa(mod p). She publishes (p, α, β) but keeps the number asecret. To sign the message, she does the following:(1) Chooses a random integer k with gcd(k, p − 1) = 1.(2) Computes r ≡ αk(mod p).(3) Computes s ≡ am + kr (mod p − 1).(4) The signed message is (m, r, s).Bob verifies the signature as follows:(1) Computes u1≡ αs(mod p).(2) Computes u2≡ βmrr(mod p).(3) Declares the signature valid if u1≡ u2(mod p).(a) Show that if Alice signs the document correctly then the verification congruenceholds.12(b) Suppose Eve finds out the value of k that Alice used. Describe how Eve canfigure out the value of a. (Note: she might at first have more than one possibility(but probably not very many possibilities) for a; you should include a descriptionof how she determines which is the correct one.)(c) If Eve chooses a value of r for her own message m, why will she have a hardtime finding a value of s that makes the verification congruence hold?4. Consider the following Feistel cryptosystem consisting of three rounds. Thekey K is the same for each round and has 64 bits. The input for the ith roundconsists of 64 bits, divided into a left half and a right half: Li−1Ri−1, where Lian Rieach have 32 bits. The output is LiRi, where Li= Ri−1and Ri= Li−1⊕f(K, Ri−1). The function f is given by f (K, R) ≡ RK(mod 264), written as a64-bit string.If you receive the ciphertext L3R3, describe how you would decrypt it to obtainL0R0. Show that this decryption works. (You may not simply quote results aboutthis type of decryption.)5. Consider the following elliptic curve protocol: Alice wants to send a messagem to Bob. Alice and Bob publicly determine an elliptic curve E mod a large primep and an integer n such that nP = ∞ for all points P on E. Alice represents m asa point P0on E by some publicly known procedure (the procedure is known, butnot P0or m). They perform the following steps:(1) Alice chooses a secret integer a with gcd(a, n) = 1 and Bob chooses a secretinteger b with gcd(b, n) = 1.(2) Alice computes P1= aP0and sends P1to Bob.(3) Bob computes P2= bP1and sends P2to Alice.(4) Alice computes a1≡ a−1(mod n) and computes P3= a1P2. She sends P3to Bob.(5) Bob computes b1≡ b−1(mod n) and computes P4= b1P3. It can be shownthat P4= P0, so Bob has received the message m (that is, he can extractm from P0).(a) Suppose Eve knows how to compute discrete logs for elliptic curves and shelistens to the communications between Alice and Bob. How can she determine thesecret integers a and b? (This also allows Eve to determine P0, and therefore m,but don’t show this.)(b) Describe a classical version (that is, a non-elliptic curve version related to theclassical discrete log problem) of the above protocol in which the message is nowan integer m mod a large prime

View Full Document