Slide 1Raising numbers to powers, Cyrptography and RSA,Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Agreeing on a secretA couple of small thingsDiffie-Hellman Key ExchangeWhat about Eve?also, discrete logarithms seem hardSlide 36The RSA CryptosystemOur dramatis personaeSlide 39Slide 40Slide 41Slide 43How hard is cracking RSA?Slide 4515-251Great Theoretical Ideas in Computer ScienceLecture 14 (February 26, 2009)Raising numbers to powers,Cyrptography and RSA,p-1p1How do you compute…58First idea:552535455565758= 5*5= 52*5using few multiplications?How do you compute…58Better idea:5525458= 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?5525458How 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 * … * a2it a2k. . .say, m = 2k + 2i1 + 2i2 … + 2itat most k more multipliesHence, we can compute am while performing at most 2 log2 m multipliesHow do you compute…513 (mod 11)First idea: Compute 513 using 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´11 3´11 9´11 81´11 36´11 15´11 4´11 3´11 4 25Hence, we can compute am (mod n)while performing at most 2 log2 m multiplieswhere each time we multiplytogether numbers with log2 n + 1 bitsHow 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 n y) and (a n b). Then1) x + a n y + b2) x * a n y * b3) x - a n y – b4) cx n cy a n bi.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 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.Equivalently,for a Zn*, ax n ax mod Á(n)If a Zn* and x ´Á(n) y then ax n ayHow 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 log2 n + 1 bitsfor a Zn*, ax n ax mod Á(n)343281327847324 mod 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 n ax mod Á(n)If a Zn* and x ´Á(n) y then ax n ayUse Euler’s TheoremFor a Zn*, a Á(n) n 1Corollary: Fermat’s Little TheoremFor p prime, a Zp* ap-1 p 1How do you prove the lemma for powers?Proof of Euler’s Theorem: for a Zn*, a Á(n) n 1Define a Zn* = {a *n x | 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 =n asize of Zn* [Cancellation]a Á(n) =n 1Euler’s TheoremFor a Zn*, a Á(n) n 1Corollary: Fermat’s Little TheoremFor p prime, a Zp* ap-1 p 1Please rememberBasic CryptographyOne Time PadsOne Time Padsthey give perfect security!But reuse is badXOR=Can do other attacks as wellAgreeing 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*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 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)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?The 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 n mHow 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 powers Euler phi function (n) = |Zn*| Euler’s theorem Fermat’s little theoremDiffie-Hellman Key ExchangeRSA algorithmHere’s What You Need to
View Full Document