Modular Arithmetic and the RSA CryptosystemStarringThe RSA CryptosystemSlide 4Slide 5Slide 6But how does it all work?Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58What are the properties of Zn*Slide 60Slide 61Slide 62Slide 63Z15*Slide 65Slide 66Slide 67Theorem: if p,q distinct primes then f(pq) = (p-1)(q-1)Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Fundamental Lemmas until nowSlide 76Slide 77Slide 78Slide 79Slide 80How do you calculateSlide 82Slide 83Slide 84Slide 85Slide 86Slide 87Back to our dramatis personaeSlide 89Slide 90Slide 91Slide 92Great Theoretical Ideas In Computer ScienceSteven RudichCOMPSCI 102 Fall 2007Lecture 17 October 29, 2007 Duke UniversityModular Arithmetic and the RSA Cryptosystemp-1p1StarringRivestShamirAdlemanEulerFermatThe RSA CryptosystemRivest, Shamir, and Adelman (1978)RSA is one of the most used cryptographic protocols on the net. Your browser uses it to establish a secure session with a site.Pick secret, random large primes: p,q “Publish”: n = p*q (n) = (p) (q) = (p-1)*(q-1)Pick random e Z*(n)“Publish”: eCompute d = inverse of e in Z*(n)Hence, e*d = 1 [ mod (n) ]“Private Key”: dMumbo jumbo…More Mumbo jumbo…n,e is my public key. Use it to send me a message.p,q random primes, e random Z*(n)n = p*qe*d = 1 [ mod (n) ]n, ep,q prime, e random Z*(n)n = p*qe*d = 1 [ mod (n) ]message mme [mod n](me)d n mBut how does it all work?What is φ(n)? What is Zφ(n)*?…Why do all the steps work?To understand this, we need a littlenumber theory...MAX(a,b) + MIN(a,b) = a+bn|m means that m is an integer multiple of n.We say that “n divides m”.Greatest Common Divisor:GCD(x,y) = greatest k ≥ 1 s.t. k|x and k|y.Least Common Multiple:LCM(x,y) = smallest k ≥ 1 s.t. x|k and y|k.Fact:GCD(x,y) × LCM(x,y) = x × yGCD(x,y) × LCM(x,y) = xyMAX(a,b) + MIN(a,b) = a+b(a mod n) means the remainder when a is divided by n. If a = dn + r with 0 ≤ r < nThen r = (a mod n)and d = (a div n)Defn: Modular equivalenceof integers a and ba b [mod n]if (a mod n) = (b mod n) n|(a-b)Written as a n b, and spoken“a and b are equivalent modulo n”31 81 [mod 2]31 2 81n is an equivalence relationIn other words,Reflexive: a n aSymmetric: (a n b) (b n a)Transitive: (a n b and b n c) (a n c)a n b n|(a-b)“a and b are equivalent modulo n”n induces a natural partition of the integers into n classes. a and b are said to be in the same “residue class” or “congruence class” exactly when a n b.a n b n|(a-b)“a and b are equivalent modulo n”Define Residue class [i] = the set of all integers that are congruent to i modulo n.Residue Classes Mod 3:[0] = { …, -6, -3, 0, 3, 6, ..}[1] = { …, -5, -2, 1, 4, 7, ..}[2] = { …, -4, -1, 2, 5, 8, ..}[-6] = { …, -6, -3, 0, 3, 6, ..}[7] = { …, -5, -2, 1, 4, 7, ..}[-1] = { …, -4, -1, 2, 5, 8, ..}Fact: equivalence mod n implies equivalence mod any divisor of n.If (x n y) and (k|n)Then: x k yExample: 10 6 16 10 3 16If (x n y) and (k|n)then x k yProof:Fundamental 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 * bProof of 3: xa = yb (mod n)(The other two proofs are similar…)Fundamental lemma of plus minus, and times modulo n:When doing plus, minus, and times modulo n, I can at any time in the calculation replace a number with a number in the same residue class modulo nPlease calculate: 249 * 504 mod 251when working mod 251-2 * 2 = -4 = 247A Unique Representation System Modulo n:We pick exactly one representative from each residue class. We do all our calculations using these representatives.Unique representation system modulo 3Finite set S = {0, 1, 2}+ and * defined on S:+ 0 1 20 0 1 21 1 2 02 2 0 1* 0 1 20 0 0 01 0 1 22 0 2 1Unique representation system modulo 3Finite set S = {0, 1, -1}+ and * defined on S:+ 0 1 -10 0 1 -11 1 -10-1-10 1* 0 1 -10 0 0 01 0 1 -1-10 -11Perhaps the most convenient set of representatives:The 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)[Closed] x, y Zn x +n y Zn[Associative] x, y, z Zn ( x +n y ) +n z = x +n ( y +n z )[Commutative]x, y Zn x +n y = y +n xZn = {0, 1, 2, …, n-1}a +n b = (a+b mod n) a *n b = (a*b mod n)[Closed] x, y Zn x *n y Zn[Associative] x, y, z Zn ( x *n y ) *n z = x *n ( y *n z )[Commutative]x, y Zn x *n y = y *n xZn = {0, 1, 2, …, n-1}a +n b = (a+b mod n) a *n b = (a*b mod n)+n and *n are commutative, associative binary operators from Zn X Zn Zn:The reduced system modulo 3Z3 = {0, 1, 2}Two binary, associative operators on Z3:+30 1 20 0 1 21 1 2 02 2 0 1*30 1 20 0 0 01 0 1 22 0 2 1The reduced system modulo 2Z2 = {0, 1}Two binary, associative operators on Z2:`+20 10 0 11 1 0*20 10 0 01 0 1The Boolean interpretation of Z2Z2 = {0, 1}Two binary, associative operators on Z2:`+2XOR0 10 0 11 1 0*2AND0 10 0 01 0 1The reduced systemZ4 = {0, 1,2,3}+ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2* 0 1 2 30 0 0 0 01 0 1 2 32 0 2 0 23 0 3 2 1The reduced systemZ5 = {0,1,2,3,4}+ 0 1 2 3 40 0 1 2 3 41 1 2 3 4 02 2 3 4 0 13 3 4 0 1 24 4 0 1 2 3* 0 1 2 3 40 0 0 0 0 01 0 1 2 3 42 0 2 4 1 33 0 3 1 4 24 0 4 3 2 1The 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 4* 0 1 2 3 4 50 0 …
View Full Document
Unlocking...