15 251 Raising numbers to powers Cyrptography and RSA Lecture 14 February 26 2009 Great Theoretical Ideas in Computer Science p 1 p 1 How do you compute 58 using few multiplications First idea How do you compute 58 Better idea 5 52 53 54 55 56 57 58 52 5 5 5 5 52 54 58 52 4 54 52 5 5 5 Used only 3 mults instead of 7 How do you compute Repeated squaring calculates k a2 in k multiply operations compare with 2k 1 multiply operations used by the na ve method 513 Use repeated squaring again 5 52 54 58 516 too high what now assume no divisions allowed 1 How do you compute To compute am Suppose 2k m 2k 1 513 a a2 a4 a8 Use repeated squaring again 5 k This takes k multiplies 58 54 52 a2 Now write m as a sum of distinct powers of 2 Note that 13 8 4 1 1310 1101 2 So a13 a8 a4 a1 say m 2k 2i1 2i2 2it k i1 am a2 a2 a2 it at most k more multiplies Two more multiplies How do you compute Hence we can compute am while performing at most 2 log2 m multiplies 513 mod 11 First idea Compute 513 using 5 multiplies 1 220 703 125 5 52 54 58 512 513 4 12 5 5 58 5 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 9 58 512 Hence we can compute am mod n while performing at most 2 log2 m multiplies 513 11 81 11 36 11 15 11 4 11 3 11 4 where each time we multiply together numbers with log2 n 1 bits 2 How do you compute 5121242653 mod 11 The current best idea would still need about 54 calculations OK need a little more number theory for this one answer 4 Can we exponentiate any faster 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 4 cx n cy a n b i e if c in Zn Euler Phi Function n Fundamental lemma of powers n size of Zn If x n y Then ax n ay p prime p p 1 NO p q distinct primes pq p 1 q 1 2 3 5 but it is not the case that 22 3 25 3 Correct Fundamental lemma of powers How do you compute 5121242653 mod 11 If a Zn and x n y then ax n ay 121242653 mod 10 3 Equivalently 53 mod 11 125 mod 11 4 for a Zn ax n ax mod n 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 Correct Fundamental lemma of powers If a Zn and x n y then ax n ay 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 How do you prove the lemma for powers Use Euler s Theorem For a Zn a n n 1 Equivalently Corollary Fermat s Little Theorem for a Zn ax n ax mod n For p prime a Zp ap 1 p 1 4 Proof of Euler s Theorem for a Zn a n n 1 Please remember Define a Zn a n x x Zn for a Zn Euler s Theorem By the permutation property Zn aZn For a Zn a n n 1 x n ax as x ranges over Zn x n x a size of Zn 1 n asize of Zn Commutativity Corollary Fermat s Little Theorem Cancellation a n n 1 For p prime a Zp ap 1 p 1 One Time Pads Basic Cryptography One Time Pads But reuse is bad XOR they give perfect security Can do other attacks as well 5 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 A couple of small things A value g in Zn generates Zn if g g2 g3 g4 g n contains all elements of Zn But for prime p Zp always has a generator How can they do this Might not exist for composite n 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 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 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 Diffie Hellman requires both parties to exchange information to share a secret How fast can you do this If you can do discrete logs fast you can solve the Diffie Hellman problem fast can we get rid of this assumption How about the other way If you can break the DH key exchange protocol do discrete logs fast 6 Our dramatis personae The RSA Cryptosystem Euler Pick secret random large primes p q Multiply n p q Publish n Adleman Shamir Rivest Fermat p q random primes e random Z n n p q e d 1 mod 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 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 message m me mod n me d n m 7 How hard is cracking RSA If we can factor products of two large primes can we crack RSA If we know n and n can we crack RSA How about the other way Does cracking RSA mean we must do one of these two We don t know yet Fast exponentiation Fundamental lemma of powers Euler phi function n Zn Euler s theorem Fermat s little theorem Diffie Hellman Key Exchange Here s What You Need to Know RSA algorithm 8
View Full Document
Unlocking...