Slide 1Number Theory, Cryptography and RSASlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15If p,q distinct primes then f(pq) = (p-1)(q-1)What are the properties of Zn*Slide 18Slide 19Slide 20new stuff starts here…Fundamental Lemmas until nowSlide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29A note about exponentiationHow do you calculateTime to computeFaster exponentiationSlide 34How much time did this take?Ok, back to number theoryAgreeing on a secretDiffie-Hellman Key ExchangeWhat about Eve?btw, discrete logarithms seem hardThe RSA CryptosystemOur dramatis personaeSlide 43Slide 44Slide 45Slide 46How hard is cracking RSA?Slide 4815-251Great Theoretical Ideas in Computer ScienceLecture 14 (October 08, 2008)Number Theory, Cryptography and RSAp-1p1The reduced system modulo n:Zn = {0, 1, 2, …, n-1}Define operations +n and *n:a +n b = (a+b mod n)a *n b = (a*b mod n)Zn = {0, 1, 2, …, n-1}a +n b = (a+b mod n) a *n b = (a*b mod n)+n and *n are commutative and associativebinary operators from Zn * Zn ZnThe reduced systemZ6 = {0,1,2,3,4,5}+ 0 1 2 3 4 50 0 1 2 3 4 51 1 2 3 4 5 02 2 3 4 5 0 13 3 4 5 0 1 24 4 5 0 1 2 35 5 0 1 2 3 4An operator has the permutation property if each row and each column has a permutation of the elements.For every n, +n on Zn has the permutation property+ 0 1 2 3 4 50 0 1 2 3 4 51 1 2 3 4 5 02 2 3 4 5 0 13 3 4 5 0 1 24 4 5 0 1 2 35 5 0 1 2 3 4An operator has the permutation property if each row and each column has a permutation of the elements.What about multiplication?Does *6 on Z6 have the permutation property?An operator has the permutation property if each row and each column has a permutation of the elements.* 0 1 2 3 4 50 0 0 0 0 0 01 0 1 2 3 4 52 0 2 4 0 2 43 0 3 0 3 0 34 0 4 2 0 4 25 0 5 4 3 2 1NoFundamental lemma of plus, minus, and times modulo n:If (x n y) and (a n b). Then1) x + a n y + b2) x - a n y - b3) x * a n y * bIs there a fundamental lemma of division modulo n? cx n cy x n y ? No!When can’t I divide by c?If GCD(c,n) > 1 then you can’t always divide by c.Fundamental lemma of division modulo n. If GCD(c,n)=1, then ca n cb a n b SoConsider the setZn* = {x Zn | GCD(x,n) =1}Multiplication over this set Zn* will have the cancellation property.Euler Phi Function (n) Define (n) = size of Zn* = number of 1 ≤ k < n that are relatively prime to n.Z6 = {0, 1,2,3,4,5}Z6* = {1,5}+ 0 1 2 3 4 50 0 1 2 3 4 51 1 2 3 4 5 02 2 3 4 5 0 13 3 4 5 0 1 24 4 5 0 1 2 35 5 0 1 2 3 4* 0 1 2 3 4 50 0 0 0 0 0 01 0 1 2 3 4 52 0 2 4 0 2 43 0 3 0 3 0 34 0 4 2 0 4 25 0 5 4 3 2 1Z12* = {0 ≤ x < 12 | gcd(x,12) = 1} = {1,5,7,11} *121 5 7 111 1 5 7 115 5 1 11 77 7 11 1 511 11 7 5 1(12) = 4Z5* = {1,2,3,4}*51 2 3 41 1 2 3 42 2 4 1 33 3 1 4 24 4 3 2 1= Z5 \ {0}For all primes p, Zp* = Zp \ {0}, since all 0 < x < p satisfy gcd(x,p) = 1If p,q distinct primes then (pq) = (p-1)(q-1) If p prime then (p) = (p-1)If p prime then (p2) = ?What are the properties of Zn*For *n on Zn* the following properties hold[Closure]x, y Zn x *n y Zn[Associativity] x, y, z Zn ( x *n y ) *n z = x *n ( y *n z )[Commutativity]x, y Zn x *n y = y *n xThe additive inverse of a Zn is the unique b Zn such that a +n b n 0. We denote this inverse by “–a”. It is trivial to calculate: “-a” = (n-a).Efficient algorithm to find multiplicative inverse a-1 from a and n.Extended Euclidean Algorithm(a, n) Get r,s such that ra + sn = gcd(a,n) = 1So ra n 1Output: r is the multiplicative inverse of aZn = {0, 1, 2, …, n-1}Zn* = {x Zn | GCD(x,n) =1}Define +n and *n: a +n b = (a+b mod n) a *n b = (a*b mod n)<Zn, +n>1. Closed2. Associative3. 0 is identity4. Additive Inverses5. Cancellation6. Commutative<Zn*, *n>1. Closed2. Associative3. 1 is identity4. Multiplicative Inverses5. Cancellation6. Commutativec *n ( a +n b) n (c *n a) +n (c*n b)new stuff starts here…Fundamental Lemmas until nowFor x, y, a, b in Zn, (x n y) and (a n b). Then1) x + a n y + b2) x - a n y - b3) x * a n y * bFor a,b,c in Zn*then ca n cb a n bFundamental lemma of powers?If (a n b)Then xa n xb ?NO! (2 3 5) , but it is not the case that: 22 3 25By the permutation property, two names for the same set:Zn* = aZn*whereaZn* = {a *n x | x Zn*}, a Zn** 1 2 3 41 1 2 3 42 2 4 1 3a 3 1 4 24 4 3 2 1Example:Z5*Two products on the same set:Zn* = aZn*aZn* = {a *n x | x Zn*}, a Zn* x n ax [as x ranges over Zn* ] x n x (asize of Zn*) [Commutativity]1 =n asize of Zn* [Cancellation]a(n) =n 1Euler’s Theorema Zn*, a(n) n 1Fermat’s Little Theoremp prime, a Zp* ap-1 p 1(Correct) Fundamental lemma of powers.Suppose x Zn*, and a,b,n are naturals.If a (n) b Then xa n xb Equivalently,xa n xa mod (n)Defining negative powersSuppose x Zn*, and a,n are naturals.x-a is defined to be the multiplicative inverse of xax-a = (xa)-1Rule of integer exponentsSuppose x,y Zn*, and a,b are integers.(xy)-1 n x-1 y-1Xa Xb n Xa+bCan use Lecture 13 to do fast exponentiation!A note about exponentiationHow do you calculate26666666666661 mod 7Fundamental lemma of powers.Suppose x Zn*, and a,n are naturals.xa n xa mod (n)For x 2 Zx*, xa (mod n) = xa mod (n) (mod n)Time to compute To compute ax (mod n) for a 2 Zn*first, get x’ = x mod Φ(n)By Euler’s theorem: ax = ax’ (mod n)Hence, we can calculate ax’ where x’ · n.But still that might take x’-1 ¼ n stepsif we calculate a, a2, a3, a4, …, ax’Faster exponentiationHow do you compute ax’ fast?Suppose x’ = 2ka ! a2 (mod n) ! a4 (mod n)…! a2k-1 (mod n) ! a2k (mod n)Suppose …
View Full Document