Assignment #3 SolutionsProblem #1Answer #1Answer #1 (cont.)Slide 5Problem #2Answer #2Answer #2 (cont.)Problem #3Answer #3Problem #4Answer #4Extended Euclidean AlgorithmAnswer #4 (cont.)Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Problem #5The Digital Signature AlgorithmAnswer #5Slide 24Answer #5 (cont.)Assignment #3SolutionsJanuary 24, 2006January 24, 2006Practical Aspects of Modern CryptographyProblem #1Use Fermat’s Little Theorem and induction on k to prove thatxk(p–1)+1 mod p = x mod pfor all primes p and k ≥ 0.January 24, 2006Practical Aspects of Modern CryptographyAnswer #1By induction on k … Base case k = 0: xk(p–1)+1 mod p = x0+1 mod p = x mod p Base case k = 1: xk(p–1)+1 mod p = x(p-1)+1 mod p = xp mod p = x mod p (by Fermat’s Little Theorem)January 24, 2006Practical Aspects of Modern CryptographyAnswer #1 (cont.)Inductive step: Assume that xk(p–1)+1 mod p = x mod p. Prove that x(k+1)(p–1)+1 mod p = x mod p.January 24, 2006Practical Aspects of Modern CryptographyAnswer #1 (cont.)x(k+1)(p–1)+1 mod p = xk(p–1)+(p-1)+1 mod p = xk(p–1)+1+(p-1) mod p = xk(p–1)+1x(p-1) mod p = x x(p-1) mod p (by inductive hypothesis) = xp mod p = xp mod p (by Fermat’s Little Theorem)January 24, 2006Practical Aspects of Modern CryptographyProblem #2Show that for distinct primes p and q,x mod p = y mod px mod q = y mod q together imply thatx mod pq = y mod pq.January 24, 2006Practical Aspects of Modern CryptographyAnswer #2x mod p = y mod p (x mod p) – (y mod p) = 0 (x – y) mod p = 0 (by first assignment) (x – y) is a multiple of p.Similarly x mod q = y mod q (x – y) is a multiple of q.January 24, 2006Practical Aspects of Modern CryptographyAnswer #2 (cont.)Therefore, (x – y) is a multiple of pq (x – y) mod pq = 0 (x mod pq) – (y mod pq) = 0 x mod pq = y mod pq.January 24, 2006Practical Aspects of Modern CryptographyProblem #3Put everything together to prove thatxK(p–1)(q-1)+1 mod pq = x mod pqFor K ≥ 0 and distinct primes p and q.January 24, 2006Practical Aspects of Modern CryptographyAnswer #3Let k1=K(q–1) and k2=K(p–1). xK(p–1)(q-1)+1 mod p = xk1(p–1)+1 mod p = x mod pand xK(p–1)(q-1)+1 mod q = xk1(q–1)+1 mod q = x mod qBy Problem #1, and then by Problem #2xK(p–1)(q-1)+1 mod pq = x mod pq.January 24, 2006Practical Aspects of Modern CryptographyProblem #4E(x) = x43 mod 143Find the inverse functionD(x) = xd mod 143.January 24, 2006Practical Aspects of Modern CryptographyAnswer #4143 = 1113We need to find d such that43d mod (11–1)(13–1) = 1.Use the Extended Euclidean Algorithm to find a solution to find x and y such that120x + 43y = 1.January 24, 2006Practical Aspects of Modern CryptographyExtended Euclidean AlgorithmGiven A,B > 0, set x1=1, x2=0, y1=0, y2=1, a1=A, b1=B, i=1.Repeat while bi>0: {i = i + 1; qi = ai-1 div bi-1; bi = ai-1-qibi-1; ai = bi-1; xi+1=xi-1-qixi; yi+1=yi-1-qiyi}.For all i: Axi + Byi = ai. Final ai = gcd(A,B).January 24, 2006Practical Aspects of Modern CryptographyAnswer #4 (cont.)i aibixiyiqi1 120 43 1 00 1January 24, 2006Practical Aspects of Modern CryptographyAnswer #4 (cont.)i aibixiyiqi1 120 43 1 02 43 34 0 1 21 -2January 24, 2006Practical Aspects of Modern CryptographyAnswer #4 (cont.)i aibixiyiqi1 120 43 1 02 43 34 0 1 23 34 9 1 -2-1 3January 24, 2006Practical Aspects of Modern CryptographyAnswer #4 (cont.)i aibixiyiqi1 120 43 1 02 43 34 0 1 23 34 9 1 -2 14 9 7 -1 3 34 -11January 24, 2006Practical Aspects of Modern CryptographyAnswer #4 (cont.)i aibixiyiqi1 120 43 1 02 43 34 0 1 23 34 9 1 -2 14 9 7 -1 3 35 7 2 4 -11 1-5 14January 24, 2006Practical Aspects of Modern CryptographyAnswer #4 (cont.)i aibixiyiqi1 120 43 1 02 43 34 0 1 23 34 9 1 -2 14 9 7 -1 3 35 7 2 4 -11 16 2 1 -5 14 319 -53January 24, 2006Practical Aspects of Modern CryptographyAnswer #4 (cont.)i aibixiyiqi1 120 43 1 02 43 34 0 1 23 34 9 1 -2 14 9 7 -1 3 35 7 2 4 -11 16 2 1 -5 14 37 1 0 19 -53 2-43 120January 24, 2006Practical Aspects of Modern CryptographyProblem #5Digital Signature AlgorithmPublic parameters: q = 11, p = 67, g = 9, y = 62Private secret: x = 4Message to be signed: M = 8Selected random parameter: k = 2January 24, 2006Practical Aspects of Modern CryptographyThe Digital Signature AlgorithmTo sign a 160-bit message M,•Generate a random integer k with 0 < k < q,•Compute r = (gk mod p) mod q,•Compute s = ((M+xr)/k) mod q.The pair (r,s) is the signature on M.January 24, 2006Practical Aspects of Modern CryptographyAnswer #5•r = (gk mod p) mod q = (92 mod 67) mod 11 = (81 mod 67) mod 11 = 14 mod 11 = 3•s = ((M+xr)/k) mod q = ((8+43)/2) mod 11 = (20/2) mod 11 = 10 mod 11 = 10The pair (3,10) is the signature on 8.January 24, 2006Practical Aspects of Modern CryptographyThe Digital Signature AlgorithmA signature (r,s) on M is verified as follows:•Compute w = 1/s mod q,•Compute a = wM mod q,•Compute b = wr mod q,•Compute v = (gayb mod p) mod q.Accept the signature only if v = r.January 24, 2006Practical Aspects of Modern CryptographyAnswer #5 (cont.)•w = 1/s mod q = 1/10 mod 11 = 10•a = wM mod q = 108 mod 11 = 3•b = wr mod q = 103 mod 11 = 8•v = (93628 mod 67) mod 11 = (5915 mod 67) mod 11 = 14 mod 11 = 3v = 3 and r = 3 so the signature is
View Full Document
Unlocking...