Carnegie Mellon UniversityOct 12, 2006Lecture 14CS 15-251 Fall 2006Anupam GuptaGreat Theoretical Ideas In Computer ScienceModular Arithmetic and the RSA Cryptosystemp-1≡p1StarringRivestShamirAdlemanEulerFermatThe 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≡nmBut 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 ≡nb, and spoken“a and b are equivalent modulo n”31 ≡ 81 [mod 2]31 ≡281≡nis an equivalence relationIn other words,Reflexive:a ≡naSymmetric:(a ≡nb) ⇒ (b ≡na)Transitive:(a ≡nb and b ≡nc) ⇒ (a ≡nc)a ≡nb ↔ 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 ≡nb ↔ 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 ≡ny) and (k|n)Then: x ≡kyExample: 10 ≡616 ⇒ 10 ≡316If (x ≡ny) and (k|n)then x ≡kyProof:Fundamental lemma of plus, minus, and times modulo n:If (x ≡ny) and (a ≡nb). Then1) x + a ≡ny + b2) x - a ≡ny – b3) x * a ≡ny * 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:021101112220020+210120110200020*Unique representation system modulo 3Finite set S = {0, 1, -1}+ and * defined on S:0-1110111-1-1-100-10+-1101-10110-1000-10*Perhaps the most convenient set of representatives:The reduced system modulo n:Zn= {0, 1, 2, …, n-1}Define operations +nand *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 +ny ∈ Zn[Associative]x, y, z∈ Zn⇒ ( x +ny ) +nz = x +n( y +nz )[Commutative]x, y∈ Zn⇒ x +ny = y +nxZn= {0, 1, 2, …, n-1}a +n b = (a+b mod n) a *n b = (a*b mod n)[Closed]x, y ∈ Zn⇒ x *ny ∈ Zn[Associative]x, y, z∈ Zn⇒ ( x *ny ) *nz = x *n( y *nz )[Commutative]x, y∈ Zn⇒ x *ny = y *nxZn= {0, 1, 2, …, n-1}a +n b = (a+b mod n) a *n b = (a*b mod n)+nand *nare commutative, associativebinary operators from Zn X Zn→ Zn:The reduced system modulo 3Z3= {0, 1, 2}Two binary, associative operators on Z3:021101112220020+3210120110200020*3The reduced system modulo 2Z2= {0, 1}Two binary, associative operators on Z2:`01110010+210100010*2The Boolean interpretation of Z2Z2= {0, 1}Two binary, associative operators on Z2:`01110010+2XOR10100010*2ANDThe reduced systemZ4= {0, 1,2,3}103221322021101123330030+202022202310130110300030*The reduced systemZ5= {0,1,2,3,4}21043320433143221322021101134440040+24130321303342023202410140110400040*The reduced systemZ6= {0,1,2,3,4,5}543210+054321154321005432543243210321052105410543543210*43210100000054320000234540242042The reduced systemZ6= {0,1,2,3,4,5}543210+054321154321005432543243210321052105410543An operator has the permutation property if each row and each column has a permutation of the elements.For every n, +non Zn has the permutation property543210+054321154321005432543243210321052105410543An operator has the permutation property if each row and each column has a permutation of the elements.What about multiplication?Does *6on Z6have the permutation property?An operator has the permutation property if each row and each column has a permutation of the elements.543210*5432101000000054320000123452402430303420427654321076543210*What about *8on Z8?Which rows have the permutation property?There are exactly 8 distinct multiples of 3 modulo 8.75 310624hit all numbers ⇔ row 3 has the “permutation property”There are exactly 2 distinct multiples of 4 modulo 875 310624row 4 does not have “permutation property” for *8on Z8There is exactly 1 distinct multiple of 8 modulo 875 310624There are exactly 4 distinct multiples of 6 modulo 875 310624There are exactly LCM(n,c)/c = n/GCD(c,n)distinct multiples of c modulo nand hencevalues of c with GCD(c,n) = 1have the permutation propertyfor *non ZnThe multiples of c modulo n is the set:{0, c, c +nc, c +nc +nc, ….}= {kc mod n | 0 ≤ k ≤ n-1}75 310624Multiples of 6Theorem: There are exactly k = n/GCD(c,n) = LCM(c,n)/cdistinct multiples of c modulo n: { c*i mod n | 0 ≤ i < k }Clearly, c/GCD(c,n) ≥ 1 is a whole numberck = n [c/GCD(c,n)] ≡n0⇒ There are ≤ k distinct multiples of c mod n: c*0, c*1, c*2, …, c*(k-1) Also, k = all the factors of n missing from c⇒ cx ≡ncy ↔ n|c(x-y) ⇒ k|(x-y) ⇒ x-y ≥ kThere are ≥ k multiples of c. Hence exactly k.Fundamental lemma of plus, minus, and
View Full Document