**Unformatted text preview:**

MATH/CMSC 456 (Washington) Exam 2 May 7, 2003Do each problem on a separate piece of paper. That is, do problem 1 onpage 1, problem 2 on page 2, etc.1. (20 points=6+7+7) (a) Suppose you know that36≡ 44 (mod 137), 310≡ 2 (mod 137).Find a value of x with 0 ≤ x ≤ 135 such that 3x≡ 11 (mod 137).(b) Let E be the elliptic curve y2≡ x3+1 (mod 7). Evaluate the sum (0, 1)+(3, 0)on E.(c) Let H be the function that takes as input a large integer and reduces it mod10100. That is, H(x) = x (mod 10100). Why is H not a good cryptographic hashfunction?2. (20 points = 4+8+8) An attack on discrete logarithms goes as follows. Let p bea prime and let α be a primitive root mod p. Given β, we want to find x such thatβ ≡ αx(mod p). Make two lists of length M (for the value of M , see part (a)).The first list is βα−i(mod p) for M random values of i. The second list is αjforM random values of j.(a) Suppose there is a match between an element of the first list and one on thesecond list. Show that this yields a value of x that solves the discrete log problem.(b) Suppose p is approximately 1030. Approximately how large should M be sothat there is a 50% chance of a match? (Your answer should be something like 1010or 1019. You don’t need to be more accurate than a power of 10.)(c) Describe the analog of this procedure for elliptic curves. Namely, let E bean elliptic curve with N points and suppose A and B are points on E. SupposeB = xA for some integer x. Give the procedure for finding x.3. (20 points: 10+10) Let p be a large prime and let α be a primitive root modp. Let f be a function that maps integers to integers (so f(x) is an integer when xis an integer). Alice wants to sign a message m, which is represented as an integermod p. Alice chooses a secret integer a and computes β ≡ αa(mod p). She makesp, f, α, β public and keeps a secret. To sign m, Alice does the following:(1) She chooses a secret random integer k with gcd(k, p − 1) = 1.(2) She computes r ≡ mα−k(mod p).(3) She computes s ≡ k−1(1 − f (r)a) (mod p − 1).(4) The signed message is (m, r, s).Bob verifies the signature as follows:(1) He computes v1≡ αrsβ−f (r)(mod p).(2) He computes v2≡ ms(mod p).(3) He declares the signature valid if v1≡ v2(mod p).(a) Show that if Alice performs the required steps correctly, then v1≡ v2(mod p).12(b) Suppose Alice uses the constant function satisfying f(x) = 0 for all x. Let m beEve’s message. Show how Eve can forge Alice’s signature on m (that is, describehow Eve can produce a signed message (m, r, s) that Bob will declare to be valid).4. (20 points=10+10) Suppose p is a large prime and α is a primitive root modp. Suppose β ≡ αx(mod p) for some x. Peggy wants to prove to Victor that sheknows x without telling Victor the value of x. (Victor knows p, α, β.) They do thefollowing:(1) Peggy chooses three random integers r1, r2, r3such that r1+ r2+ r3≡ x(mod p − 1).(2) Peggy computes mi≡ αri(mod p) for i = 1, 2, 3.(3) Peggy sends m1, m2, m3to Victor.(4) Victor checks that m1m2m3≡ β (mod p).(5) Victor chooses two integers j, k ∈ {1, 2, 3} and sends them to Peggy.(6) Peggy sends rjand rkto Victor.(7) Victor checks that vj≡ αrj(mod p) and that vk≡ αrk(mod p).(a) Suppose Peggy does not know x but guesses correctly that Victor will ask forj = 1 and k = 3. Describe what Peggy should do so that Victor does not find outthat she doesn’t know x.(b) Suppose that Peggy does not know x. Why is it likely, after several repetitionsof the above procedure, that Victor will discover that Peggy does not know x?5. (20 points) Consider the following Feistel cryptosystem consisting of two rounds.The key K is the same for each round and has 64 bits. The input for the ithround consists of 64 bits, divided into a left half and a right half: Li−1Ri−1, whereLi−1and Ri−1each have 32 bits. The output is LiRi, where Li= Ri−1andRi= Li−1⊕ f(K, Ri−1). The function f is given by f(K, R) ≡ R ⊕ RK(mod 264),written as a 64-bit string.If you receive the ciphertext L2R2, describe how you can use the encryptionalgorithm to decrypt it and obtain L0R0. Show that this decryption works. (Youmay not simply quote results about this type of

View Full Document