Modular Arithmetic and the RSA CryptosystemSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 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 58Slide 59Zn* = {x 2 Zn | GCD(x,n) =1}Slide 61Z15*Slide 63Slide 64Slide 65Slide 66Slide 67f(pq) = (p-1)(q-1) if p,q distinct primesSlide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85The RSA CryptosystemSlide 87Slide 88Slide 89Slide 90Slide 91Modular Arithmetic and the RSA CryptosystemGreat Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2004Lecture 8 Feb 5, 2004 Carnegie Mellon Universityp-1´p1n|m means that m is a an integer multiple of n.We say that “n divides m”.True: 5|25 2|-66 7|35,False: 4|5 8|2(a mod n) means the remainder when a is divided by n. If ad + r = n, 0· r < nThen r = (a mod n)and d = (a div n)Modular equivalence of integers a and b:a ´ b [mod n]a ´n b“a and b are equivalent modulo n”iff (a mod n) = (b mod n)iff n|(a-b)31 equals 81 modulo 231 ´ 81 [mod 2]31 ´2 81(31 mod 2) = 1 = (81 mod 2)2|(31- 81)´n 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 the residue class [i] to be 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, ..}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: Recall, x´ny , n|(x-y) k|n and n|(x-y)Hence, k|(x-y) Of course, k|(x-y) ) x´kyFundamental lemma of plus, minus, and times modulo n:If (x ´n y) and (a ´n b)Then: 1) x+a ´n y+b 2) x-a ´n y-b 3) xa ´n ybEquivalently,If n|(x-y) and n|(a-b) Then: 1) n|(x-y + a-b)2) n | (x-y – [a-b]) 3) n|(xa-yb)Proof of 3: xa-yb = a(x-y) – y(b-a)n|a(x-y) and n|y(b-a)Fundamental lemma of plus minus, and times modulo n:When doing plus, minus, and time modulo n, I can at any time in the calculation replace a number with a number in the same residue class modulo nPlease calculate in your head: 329 * 666 mod 331-2 * 4 = -8 = 323A Unique Representation System Modulo n:We pick exactly one representative from each residue class. We do all our calculations using the 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 -11The reduced system modulo n:Zn = {0, 1, 2, …, n-1}Define +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 associative binary operators from Zn X Zn ! Zn:When ~ = +n or *n :[Closure] x,y2 Zn ) x ~ y 2 Zn[Associativity] x,y,z2 Zn ) ( x ~ y ) ~ z = x ~ ( y ~ z )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, associative binary operators from Zn X Zn ! Zn:[Commutativity]x,y2 Zn ) x ~ y = y ~ xThe 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 ofZ2 = {0, 1} 0 means FALSE 1 means TRUE +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 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 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 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.There are exactly 8 distinct multiples of 3 modulo 8. 75 310624There are exactly 8 distinct multiples of 3 modulo 8.75 310624There are exactly 8 distinct multiples of 3 modulo 8.75 310624There are exactly 8 distinct multiples of 3 modulo 8.75 310624There are …
View Full Document