15 251 Great Theoretical Ideas in Computer Science Clarifications of some of the homework Problems Problem 1 Problem 5 Problem 6 Raising numbers to powers Cyrptography and RSA Lecture 14 February 25 2010 p 1 p 1 It s all done with splay trees QED Class Dismissed Not How do you compute 58 using few multiplications First idea 5 52 53 54 55 56 57 58 52 5 5 5 How do you compute 58 Better idea 5 5 52 5524 54 5 5 5 5 2 4 8 Used only 3 mults instead of 7 Repeated squaring calculates 2k a in k multiply operations compare with 2k 1 multiply operations used by the na ve method How do you compute 513 Use repeated squaring again 5 52 54 58 516 too high what now assume no divisions allowed How do you compute 513 Use repeated squaring again 5 52 54 58 Note that 13 8 4 1 1310 1101 2 So a13 a8 a4 a1 Two more multiplies To compute am Suppose 2k m 2k 1 a a2 a4 a8 2k a This takes k multiplies Now write m as a sum of distinct powers of 2 say m 2k 2i1 2i2 2it a a m 2k a 2i1 a 2it at most k more multiplies Hence we can compute am while performing at most 2 log2 m multiplies How do you compute 513 mod 11 First idea Compute 513 using 5 multiplies 5 52 54 58 512 513 1 220 703 125 4 12 5 58 55 then take the answer mod 11 1220703125 mod 11 4 How do you compute 513 mod 11 Better idea keep reducing the answer mod 11 5 52 25 11 3 54 11 58 512 513 11 81 11 36 11 15 9 11 4 11 3 11 4 Hence we can compute am mod n while performing at most 2 log2 m multiplies where each time we multiply together numbers with log2 n 1 bits How do you compute 5121242653 mod 11 The current best idea would still need about 54 calculations answer 4 Can we exponentiate any faster OK need a little more number theory for this one First recall Zn 0 1 2 n 1 Zn x Zn GCD x n 1 Fundamental lemmas mod n 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 i e if c in Z 4 cx n cy a n b n Euler Phi Function n n size of Zn p prime p p 1 p q distinct primes pq p 1 q 1 Fundamental lemma of powers If x n y Then ax n ay NO 2 3 5 but it is not the case that 22 3 25 Correct Fundamental lemma of powers If a Zn and x n y then ax n ay Equivalently for a Zn ax n ax mod n How do you compute 5121242653 mod 11 121242653 mod 10 3 53 mod 11 125 mod 11 4 Why did we take mod 10 for a Zn ax n ax mod n Hence we can compute am mod n while performing at most 2 log2 n multiplies where each time we multiply together numbers with log2 n 1 bits 343281327847324 mod 39 Step 1 reduce the base mod 39 Step 2 reduce the exponent mod 39 24 NB you should check that gcd 343280 39 1 to use lemma of powers Step 3 use repeated squaring to compute 34 taking mods at each step Correct Fundamental lemma of powers If a Zn and x n y then ax n ay Equivalently for a Zn ax n ax mod n How do you prove the lemma for powers Use Euler s Theorem For a Zn a n n 1 Corollary Fermat s Little Theorem For p prime a Zp ap 1 p 1 Proof of Euler s Theorem for a Zn a n n 1 Define a Zn a n x x Zn for a Zn By the cancellation property Zn aZn x n ax as x ranges over Zn x n x a size of Zn 1 n asize of Zn Commutativity Cancellation a n n 1 Please remember Euler s Theorem For a Zn a n n 1 Corollary Fermat s Little Theorem For p prime a Zp ap 1 p 1 Basic Cryptography One Time Pads One Time Pads they give perfect security But reuse is bad XOR Can do other attacks as well Agreeing on a secret One time pads rely on having a shared secret Alice and Bob have never talked before but they want to agree on a secret How can they do this A couple of small things A value g in Zn generates Zn if g g2 g3 g4 g n contains all elements of Zn Diffie Hellman Key Exchange Alice Picks prime p and a generator g in Zp Picks random a in Zp Sends over p g ga mod p Bob Picks random b in Zp and sends over gb mod p Now both can compute gab mod p What about Eve Alice Picks prime p and a value g in Zp Picks random a in Zp Sends over p g ga mod p Bob Picks random b in Zp and sends over gb mod p Now both can compute gab mod p If Eve s just listening in she sees p g ga gb It s believed that computing gab mod p from just this information is not easy also discrete logarithms seem hard Discrete Log Given p g ga mod p compute a How fast can you do this If you can do discrete logs fast you can solve the Diffie Hellman problem fast How about the other way If you can break the DH key exchange protocol do discrete logs fast Diffie Hellman requires both parties to exchange information to share a secret can we get rid of this assumption The RSA Cryptosystem Our dramatis personae Adleman Shamir Rivest Euler Fermat Pick secret random large primes p q Multiply n p q Publish n n p q p 1 q 1 Pick random e Z n Publish e Compute d inverse of e in Z n Hence e d 1 mod n Private Key d p q random primes e random Z n n p q e d 1 mod n n e is my public key Use it to send me a message p q prime e random Z n n p q e d 1 mod n n e messag em me mod n me d n m Extended gcd on ocaml egcd a b returns a triple x y g such That g is the gcd a b and g ax by let rec egcd a b if a 0 then 0 1 b else let x y g egcd b mod a a in y b a x x g How hard is cracking RSA If we can factor products of two large primes can we crack RSA If we know n and …
View Full Document
Unlocking...