Lecture 14 Oct 12 2006 p 1 p Fall 2006 Carnegie Mellon University CS 15 251 1 Modular Arithmetic and the RSA Cryptosystem Anupam Gupta Great Theoretical Ideas In Computer Science Rivest Euler Shamir Fermat Starring Adleman RSA is one of the most used cryptographic protocols on the net Your browser uses it to establish a secure session with a site Rivest Shamir and Adelman 1978 The RSA Cryptosystem Private Key d n p q Mumbo p 1 q 1 jumbo Pick random e Z n Publish e Compute d inverse of e in Z n Mumbo jumbo Hence e d More 1 mod n Pick secret random large primes p q Publish n p q n e is my public key Use it to send me a message p q random primes e random Z n n p q e d 1 mod n me d n m me mod n n e p q prime e random Z n n p q e d 1 mod n message m To understand this we need a little number theory Why do all the steps work What is n What is Z n But how does it all work MAX a b MIN a b a b We say that n divides m n m means that m is an integer multiple of n GCD x y greatest k 1 s t k x and k y Greatest Common Divisor LCM x y smallest k 1 s t x k and y k Least Common Multiple Fact GCD x y LCM x y x y MAX a b MIN a b a b GCD x y LCM x y xy If a dn r with 0 r n Then r a mod n and d a div n a mod n means the remainder when a is divided by n Written as a n b and spoken a and b are equivalent modulo n a b mod n if a mod n b mod n n a b Defn Modular equivalence of integers a and b 31 81 mod 2 31 2 81 In other words Reflexive a n a Symmetric a n b b n a Transitive a n b and b n c a n c n is an equivalence relation a and b are said to be in the same residue class or congruence class exactly when a n b integers into n classes n induces a natural partition of the a and b are equivalent modulo n a n b n a b Define Residue class i the set of all integers that are congruent to i modulo n a and b are equivalent modulo n a n b n a b 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 Residue Classes Mod 3 Example 10 6 16 10 3 16 If x n y and k n Then x k y Fact equivalence mod n implies equivalence mod any divisor of n Proof If x n y and k n then x k y If x n y and a n b Then 1 x a n y b 2 x a n y b 3 x a n y b Fundamental lemma of plus minus and times modulo n The other two proofs are similar Proof of 3 xa yb mod 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 n Fundamental lemma of plus minus and times modulo n 2 2 4 247 when working mod 251 249 504 mod 251 Please calculate We do all our calculations using these representatives We pick exactly one representative from each residue class A Unique Representation System Modulo n 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 0 1 2 0 0 0 0 and defined on S Finite set S 0 1 2 1 0 1 2 2 0 2 1 Unique representation system modulo 3 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 and defined on S Finite set S 0 1 1 1 1 0 1 1 1 0 1 Unique representation system modulo 3 a n b a b mod n a n b a b mod n Define operations n and n Zn 0 1 2 n 1 The reduced system modulo n Perhaps the most convenient set of representatives a n b a b mod n x y Zn x n y Zn Commutative x y Zn x n y y n x x y z Zn x n y n z x n y n z Associative Closed a n b a b mod n Zn 0 1 2 n 1 a n b a b mod n x y Zn x n y Zn Commutative x y Zn x n y y n x x y z Zn x n y n z x n y n z Associative Closed a n b a b mod n Zn 0 1 2 n 1 a n b a b mod n n and n are commutative associative binary operators from Zn X Zn Zn a n b a b mod n Zn 0 1 2 n 1 0 0 1 2 3 0 1 2 0 2 1 1 1 0 2 2 0 0 0 0 3 0 1 2 2 1 0 1 1 2 0 2 Two binary associative operators on Z3 Z3 0 1 2 The reduced system modulo 3 0 0 1 2 0 1 0 1 1 1 0 2 0 0 0 1 0 1 Two binary associative operators on Z2 Z2 0 1 The reduced system modulo 2 0 1 1 0 0 XOR 2 0 1 1 1 0 AND 2 0 0 0 1 0 1 Two binary associative operators on Z2 Z2 0 1 The Boolean interpretation of Z2 0 0 1 2 3 0 1 2 3 0 3 2 1 1 1 0 3 2 2 2 1 0 3 3 0 0 0 0 0 0 1 2 3 Z4 0 1 2 3 3 2 1 0 1 The reduced system 2 0 2 0 2 1 2 3 0 3 0 0 1 2 3 4 0 1 2 3 4 0 4 3 2 1 1 1 0 4 3 2 2 2 1 0 4 3 3 3 2 1 0 4 4 4 3 2 0 0 0 0 0 0 1 0 Z5 0 1 2 3 4 4 3 2 1 0 1 3 1 4 2 0 2 The reduced system 2 4 1 3 0 3 1 2 3 4 0 4 0 0 1 2 3 4 5 0 1 2 3 4 5 0 5 4 3 2 1 1 1 0 5 4 3 …
View Full Document
Unlocking...