This preview shows page 1-2-3-4-5-6-7-8-9-10-11-79-80-81-82-83-84-85-86-87-88-89-90-159-160-161-162-163-164-165-166-167-168-169 out of 169 pages.
Practical Aspects of Modern CryptographyJosh BenalohBrian LaMacchiaJohn ManferdelliJanuary 17, 2006Practical Aspects of Modern CryptographyPublic-Key History• 1976 New Directions in CryptographyWhit Diffie and Marty Hellman• One-Way functions• Diffie-Hellman Key Exchange• 1978 RSA paperRon Rivest, Adi Shamir, and Len Adleman• RSA Encryption System• RSA Digital Signature MechanismJanuary 17, 2006Practical Aspects of Modern CryptographyThe Fundamental EquationZ=YZ=YXXmod Nmod NJanuary 17, 2006Practical Aspects of Modern CryptographyDiffie-HellmanZ=YZ=YXXmod Nmod NWhen X is unknown, the problem is known as the discrete logarithm and is generally believed to be hard to solve.January 17, 2006Practical Aspects of Modern CryptographyDiffie-Hellman Key ExchangeAlice• Randomly select a large integer a and send A= Yamod N.• Compute the key K = Bamod N.Bob• Randomly select a large integer b and send B= Ybmod N.• Compute the key K = Abmod N.Ba= Yba= Yab= AbJanuary 17, 2006Practical Aspects of Modern CryptographyOne-Way Trap-Door FunctionsZ=Z=YYXXmod Nmod NRecall that this equation is solvable for Y if the factorization of N is known, but is believed to be hard otherwise.January 17, 2006Practical Aspects of Modern CryptographyRSA Public-Key CryptosystemAlice• Select two large random primes P & Q.• Publish the product N=PQ.• Use knowledge of P & Q to compute Y.Anyone• To send message Y to Alice, compute Z=YXmod N.• Send Z and X to Alice.January 17, 2006Practical Aspects of Modern CryptographySome RSA DetailsWhen N=PQ is the product of distinct primes,YXmod N = YwheneverX mod (P-1)(Q-1) = 1 and 0 ≤Y<N.Alice can easily select integers E and D such that E•D mod (P-1)(Q-1) = 1.January 17, 2006Practical Aspects of Modern CryptographyRemaining RSA Basics• Why is YXmod PQ = Y wheneverX mod (P-1)(Q-1) = 1, 0 ≤Y<PQ,and P and Q are distinct primes?• How can Alice can select integers E and Dsuch that E•D mod (P-1)(Q-1) = 1?January 17, 2006Practical Aspects of Modern CryptographyFermat’s Little TheoremIf p is prime,then xp-1mod p = 1 for all 0 < x < p.Equivalently …If p is prime,then xpmod p = x mod p for all integers x.January 17, 2006Practical Aspects of Modern CryptographyThe Binomial Theorem(x + y)p= xp+ ( )xp-1y + … + ( )xyp-1+ ypwhere ( ) =p1Proof of Fermat’s Little Theorempp–1pip!i!(p–i)!January 17, 2006Practical Aspects of Modern CryptographyThe Binomial Theorem(x + y)p= xp+ ( )xp-1y + … + ( )xyp-1+ ypwhere ( ) =If p is prime, then ( ) mod p = 0 for 0 < i < p.p1Proof of Fermat’s Little Theorempp–1pipip!i!(p–i)!January 17, 2006Practical Aspects of Modern CryptographyThe Binomial Theorem(x + y)p= xp+ ( )xp-1y + … + ( )xyp-1+ ypwhere ( ) =If p is prime, then ( ) mod p = 0 for 0 < i < p.Thus, (x + y)pmod p = (xp+ yp) mod p.p1Proof of Fermat’s Little Theorempp–1pipip!i!(p–i)!January 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremJanuary 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremBy induction on x…January 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremBy induction on x…BasisJanuary 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremBy induction on x…BasisIf x = 0, then xpmod p = 0 = x mod p.January 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremBy induction on x…BasisIf x = 0, then xpmod p = 0 = x mod p.If x = 1, then xpmod p = 1 = x mod p.January 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremJanuary 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremInductive StepJanuary 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremInductive StepAssume that xpmod p = x mod p.January 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremInductive StepAssume that xpmod p = x mod p.Then (x + 1)pmod p = (xp+ 1p) mod pJanuary 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremInductive StepAssume that xpmod p = x mod p.Then (x + 1)pmod p = (xp+ 1p) mod p= (x + 1) mod p.January 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremInductive StepAssume that xpmod p = x mod p.Then (x + 1)pmod p = (xp+ 1p) mod p= (x + 1) mod p.Hence, xpmod p = x mod p for integers x ≥ 0.January 17, 2006Practical Aspects of Modern CryptographyProof of Fermat’s Little TheoremInductive StepAssume that xpmod p = x mod p.Then (x + 1)pmod p = (xp+ 1p) mod p= (x + 1) mod p.Hence, xpmod p = x mod p for integers x ≥ 0.Also true for negative x, since (-x)p= (-1)pxp.January 17, 2006Practical Aspects of Modern CryptographyProof of RSAJanuary 17, 2006Practical Aspects of Modern CryptographyProof of RSAWe have shown …January 17, 2006Practical Aspects of Modern CryptographyProof of RSAWe have shown …YPmod P = Y whenever 0 ≤ Y < PJanuary 17, 2006Practical Aspects of Modern CryptographyProof of RSAWe have shown …YPmod P = Y whenever 0 ≤ Y < Pand P is prime!January 17, 2006Practical Aspects of Modern CryptographyProof of RSAWe have shown …YPmod P = Y whenever 0 ≤ Y < Pand P is prime!You will show …January 17, 2006Practical Aspects of Modern CryptographyProof of RSAWe have shown …YPmod P = Y whenever 0 ≤ Y < Pand P is prime!You will show …YK(P-1)(Q-1)+1mod PQ = Y when 0 ≤ Y < PQJanuary 17, 2006Practical Aspects of Modern CryptographyProof of RSAWe have shown …YPmod P = Y whenever 0 ≤ Y < Pand P is prime!You will show …YK(P-1)(Q-1)+1mod PQ = Y when 0 ≤ Y < PQP and Q are distinct primes and K ≥ 0.January 17, 2006Practical Aspects of Modern CryptographyFinding PrimesJanuary 17, 2006Practical Aspects of Modern CryptographyFinding PrimesEuclid’s proof of the infinity of primesJanuary 17, 2006Practical Aspects of Modern CryptographyFinding PrimesEuclid’s proof of the infinity of primes• Suppose that the set of all primes were finite.January 17, 2006Practical Aspects of Modern CryptographyFinding PrimesEuclid’s proof of the infinity of primes• Suppose that the set of all primes were finite.•Let N be the product of all of the primes.January 17, 2006Practical Aspects of Modern CryptographyFinding PrimesEuclid’s proof of the infinity of primes• Suppose that the set of all primes were finite.•Let N be the product of all of the primes.• Consider
View Full Document
Unlocking...