115-251Great Theoretical Ideas in Computer ScienceLecture 14 (February 26, 2009)Raising numbers to powers,Cyrptography and RSA,p-1≡p1How do you compute…58First idea:5 52535455565758= 5*5= 52*5using few multiplications?How do you compute…58Better idea:5 525458= 5*5= 52*52= 54*54Used only 3 multsinstead of 7 !!!Repeated squaring calculatesa2kin k multiply operationscompare with(2k– 1) multiply operationsused by the naïve methodHow do you compute…513516too high! what now?assume no divisions allowed…Use repeated squaring again?55254582How do you compute…513Use repeated squaring again?5525458Note that 13 = 8+4+1So a13= a8* a4* a1Two more multiplies!1310= (1101)2To compute amSuppose 2k≤ m < 2k+1aa2a4a8This takes k multipliesNow write m as a sum of distinct powers of 2am= a2k* a2i1* … * a2ita2k. . .say, m = 2k+ 2i1+ 2i2… + 2itat most k more multipliesHence, we can compute amwhile performing at most 2 log2m multipliesHow do you compute…513 (mod 11)First idea: Compute 513using 5 multiplies5525458512513= 58*54= 512*5then take the answer mod 11= 1 220 703 1251220703125 (mod 11) = 4How do you compute…513 (mod 11)Better idea: keep reducing the answer mod 115525458512513≡113≡119≡1181≡1136≡1115≡114≡113≡11425Hence, we can compute am(mod n)while performing at most 2 log2m multiplieswhere each time we multiplytogether numbers with log2n + 1 bits3How do you compute…5121242653 (mod 11)The current best idea would stillneed about 54 calculationsanswer = 4Can we exponentiate any faster?OK, need a little more number theory for this one…Zn= {0, 1, 2, …, n-1}Zn*= {x ∈ Zn| GCD(x,n) =1}First, recall…Fundamental lemmas mod n:If (x ≡ny) and (a ≡nb). Then1) x + a ≡ny + b2) x * a ≡ny * b3) x - a ≡ny – b4) cx ≡ncy ⇒ a ≡nbi.e., if c in Zn*Euler Phi Function φ(n) φ(n) = size of Zn* p prime ⇒ φ(p) = p-1p, q distinct primes ⇒φ(pq) = (p-1)(q-1)Fundamental lemma of powers?If (x ≡ny)Then ax≡nay?NO! (2 ≡35) , but it is not the case that: 22≡3254(Correct) Fundamental lemma of powers.Equivalently,for a ∈ Zn*, ax≡nax mod φ(n)If a ∈ Zn* and x ≡φ(n)y then ax≡nayHow do you compute…5121242653 (mod 11)121242653 (mod 10) = 353(mod 11) = 125 mod 11 = 4Why did wetake mod 10?Hence, we can compute am(mod n)while performing at most 2 log2φ(n) multiplieswhere each time we multiplytogether numbers with log2n + 1 bitsfor a ∈ Zn*, ax≡nax mod φ(n)343281327847324mod 39Step 1: reduce the base mod 39Step 2: reduce the exponent mod φ(39) = 24Step 3: use repeated squaring to compute 34, taking mods at each stepNB: you should check that gcd(343280,39)=1 to use lemma of powers(Correct) Fundamental lemma of powers.Equivalently,for a ∈ Zn*, ax≡nax mod φ(n)If a ∈ Zn* and x ≡φ(n)y then ax≡nayUse Euler’s TheoremFor a ∈ Zn*, aφ(n)≡n1Corollary: Fermat’s Little TheoremFor p prime, a ∈ Zp*⇒ ap-1≡p1How do you prove the lemma for powers?5Proof of Euler’s Theorem: for a ∈ Zn*, aφ(n)≡n1Define a Zn*= {a *nx | x ∈ Zn*} for a ∈ Zn*By the permutation property, Zn* = aZn*∏ x ≡nΠ ax [as x ranges over Zn* ] ∏x ≡n∏ x (a size of Zn*) [Commutativity]1 =nasize of Zn*[Cancellation]aφ(n)=n1 Euler’s TheoremFor a ∈ Zn*, aφ(n)≡n1Corollary: Fermat’s Little TheoremFor p prime, a ∈ Zp*⇒ ap-1≡p1Please rememberBasic CryptographyOne Time PadsOne Time Padsthey give perfect security!But reuse is badXOR=Can do other attacks as well6Agreeing on a secretOne time pads rely on having a shared secret!Alice and Bob have never talked beforebut they want to agree on a secret…How can they do this?A couple of small thingsA value g in Zn*“generates” Zn*ifg, g2, g3, g4, …, gφ(n)contains all elements of Zn*But for prime p,Zp*alwayshas a generatorMight not exist for composite n.Diffie-Hellman Key ExchangeAlice: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?If Eve’s just listening in,she sees p, g, ga, gbIt’s believed that computing gab(mod p) from justthis information is not easy…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)also, discrete logarithms seem hardDiscrete-Log:Given p, g, ga(mod p), compute aHow 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 DHkey exchange protocol, do discrete logs fast?Diffie Hellman requires both parties to exchange information to share a secretcan we get rid of this assumption?7The RSA CryptosystemOur dramatis personaeRivestShamirAdlemanEulerFermatPick 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”: eCompute d = inverse of e in Z*φφφφ(n)Hence, e*d = 1 [ mod φ(n) ]“Private Key”: dn,e is my public key. Use it to send me a message.p,q random primese 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≡nm8How 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 exponentiationFundamental lemma of powersEuler phi function φ(n) = |Zn*|Euler’s theoremFermat’s little theoremDiffie-Hellman Key ExchangeRSA algorithmHere’s What You Need to
View Full Document