1、Assignment #3 Solutions,January 24, 2006,January 24, 2006,Practical Aspects of Modern Cryptography,Problem #1,Use Fermats Little Theorem and induction on k to prove thatxk(p1)+1 mod p = x mod pfor all primes p and k 0.,January 24, 2006,Practical Aspects of Modern Cryptography,Answer #1,By induction
2、on k Base case k = 0:xk(p1)+1 mod p = x0+1 mod p = x mod p Base case k = 1:xk(p1)+1 mod p = x(p-1)+1 mod p= xp mod p = x mod p(by Fermats Little Theorem),January 24, 2006,Practical Aspects of Modern Cryptography,Answer #1 (cont.),Inductive step:Assume that xk(p1)+1 mod p = x mod p.Prove that x(k+1)(
3、p1)+1 mod p = x mod p.,January 24, 2006,Practical Aspects of Modern Cryptography,Answer #1 (cont.),x(k+1)(p1)+1 mod p= xk(p1)+(p-1)+1 mod p= xk(p1)+1+(p-1) mod p= xk(p1)+1x(p-1) mod p= x x(p-1) mod p (by inductive hypothesis)= xp mod p= xp mod p (by Fermats Little Theorem),January 24, 2006,Practical
4、 Aspects of Modern Cryptography,Problem #2,Show that for distinct primes p and q, x mod p = y mod p x mod q = y mod qtogether imply that x mod pq = y mod pq.,January 24, 2006,Practical Aspects of Modern Cryptography,Answer #2,x mod p = y mod p (x mod p) (y mod p) = 0 (x y) mod p = 0 (by first assign
5、ment) (x y) is a multiple of p.Similarly x mod q = y mod q (x y) is a multiple of q.,January 24, 2006,Practical Aspects of Modern Cryptography,Answer #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, 2006,Practical Aspects of
6、Modern Cryptography,Problem #3,Put everything together to prove that xK(p1)(q-1)+1 mod pq = x mod pq For K 0 and distinct primes p and q.,January 24, 2006,Practical Aspects of Modern Cryptography,Answer #3,Let k1=K(q1) and k2=K(p1).xK(p1)(q-1)+1 mod p = xk1(p1)+1 mod p = x mod p andxK(p1)(q-1)+1 mod
7、 q = xk1(q1)+1 mod q = x mod q By Problem #1, and then by Problem #2 xK(p1)(q-1)+1 mod pq = x mod pq.,January 24, 2006,Practical Aspects of Modern Cryptography,Problem #4,E(x) = x43 mod 143 Find the inverse function D(x) = xd mod 143.,January 24, 2006,Practical Aspects of Modern Cryptography,Answer
8、#4,143 = 1113 We need to find d such that 43d mod (111)(131) = 1.Use the Extended Euclidean Algorithm to find a solution to find x and y such that 120x + 43y = 1.,January 24, 2006,Practical Aspects of Modern Cryptography,Extended Euclidean Algorithm,Given A,B 0, set x1=1, x2=0, y1=0, y2=1, a1=A, b1=
9、B, i=1.Repeat while bi0: 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, 2006,Practical Aspects of Modern Cryptography,Answer #4 (cont.),January 24, 2006,Practical Aspects of Modern Cryptography,Ans
10、wer #4 (cont.),January 24, 2006,Practical Aspects of Modern Cryptography,Answer #4 (cont.),January 24, 2006,Practical Aspects of Modern Cryptography,Answer #4 (cont.),January 24, 2006,Practical Aspects of Modern Cryptography,Answer #4 (cont.),January 24, 2006,Practical Aspects of Modern Cryptography
11、,Answer #4 (cont.),January 24, 2006,Practical Aspects of Modern Cryptography,Answer #4 (cont.),January 24, 2006,Practical Aspects of Modern Cryptography,Problem #5,Digital Signature AlgorithmPublic parameters: q = 11, p = 67, g = 9, y = 62 Private secret: x = 4 Message to be signed: M = 8 Selected r
12、andom parameter: k = 2,January 24, 2006,Practical Aspects of Modern Cryptography,The Digital Signature Algorithm,To 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, 2006,Pract
13、ical Aspects of Modern Cryptography,Answer #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 = 10 The pair (3,10) is the signature on 8.,January 24, 2006,Practical Aspects of Modern Cryptography,The Digita
14、l Signature Algorithm,A 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, 2006,Practical Aspects of Modern Cryptography,Answer #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 validated.,
