15-853_Algorithms.ppt

《15-853_Algorithms.ppt》由会员分享，可在线阅读，更多相关《15-853_Algorithms.ppt（43页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、15-853:Algorithms in the Real WorldCryptography 3 and 4115-853Cryptography OutlineIntroduction:terminology,cryptanalysis,security Primitives:one-way functions,trapdoors,Protocols:digital signatures,key exchange,.Private-Key Algorithms:Rijndael,DESPublic-Key Algorithms:Diffie-Hellman Key ExchangeRSA,

2、El-Gamal,Blum-GoldwasserQuantum CryptographyCase Studies:Kerberos,Digital Cash 215-853Public Key CryptosystemsIntroduced by Diffie and Hellman in 1976.EncryptionDecryptionK1K2CyphertextEk(M)=CDk(C)=MOriginal PlaintextPlaintextPublic Key systemsK1=public keyK2=private keyDigital signaturesK1=private

3、keyK2=public keyTypically used as part of a more complicated protocol.315-853One-way trapdoor functionsBoth Public-Key and Digital signatures make use of one-way trapdoor functions.Public Key:Encode:c=f(m)Decode:m=f-1(c)using trapdoorDigital Signatures:Sign:c=f-1(m)using trapdoorVerify:m=f(c)415-853

4、Example of SSL(3.0)SSL(Secure Socket Layer)is the standard for the web(https).Protocol(somewhat simplified):Bob- B-A:client hello:protocol version,acceptable ciphers A-B:server hello:cipher,session ID,|verisign B-A:key exchange,masterkeyamazons public key A-B:server finish:(amazon,prev-messages,mast

5、erkey)key1 B-A:client finish:(bob,prev-messages,masterkey)key2 A-B:server message:(message1,message1)key1 B-A:client message:(message2,message2)key2|h|issuer =Certificate =Issuer,issuers private key private key=Digital signature public key=Public-key encryption.=Secure Hash ()key =Private-key encryp

6、tionkey1 and key2 are derived from masterkey and session ID hand-shakedata515-853Public Key HistorySome algorithmsDiffie-Hellman,1976,key-exchange based on discrete logsMerkle-Hellman,1978,based on“knapsack problem”McEliece,1978,based on algebraic coding theoryRSA,1978,based on factoringRabin,1979,s

7、ecurity can be reduced to factoringElGamal,1985,based on discrete logsBlum-Goldwasser,1985,based on quadratic residuesElliptic curves,1985,discrete logs over Elliptic curvesChor-Rivest,1988,based on knapsack problemNTRU,1996,based on LatticesXTR,2000,based on discrete logs of a particular field615-8

8、53Diffie-Hellman Key ExchangeA group(G,*)and a primitive element(generator)g is made public.Alice picks a,and sends ga to BobBob picks b and sends gb to AliceThe shared key is gabNote this is easy for Alice or Bob to compute,but assuming discrete logs are hard is hard for anyone else to compute.Can

9、someone see a problem with this protocol?715-853Person-in-the-middle attackAliceBobMallorygagbgdgcKey1=gadKey1=gcbMallory gets to listen to everything.815-853Merkle-HellmanGets“security”from the Subset Sum(also called knapsack)which is NP-hard to solve in general.Subset Sum(Knapsack):Given a sequenc

10、e W=w0,w1,wn-1,wi Z of weights and a sum S,calculate a boolean vector B,such that:Even deciding if there is a solution is NP-hard.915-853Merkle-HellmanW is superincreasing if:It is easy to solve the subset-sum problem for superincreasing W in O(n)time.Main idea of Merkle-Hellman:Hide the easy case b

11、y multiplying each wi by a constant a modulo a prime pKnowing a and p allows you to retrieve the superincreasing sequence1015-853Merkle-HellmanWhat we needw1,L,wn superincreasing integersp i=1n wi and primea,1 a pwi=a wi mod pPublic Key:wiPrivate Key:wi,p,a,Encode:y=E(m)=i=1n mi wiDecode:z=a-1 y mod

12、 p =a-1 i=1n mi wi mod p =a-1 i=1n miaiwi mod p =i=1n mi wi Solve subset sum prob:(w1,L,wn,z)obtaining m1,L mn1115-853Merkle Hellman:ProblemWas broken by Shamir in 1984.Shamir showed how to use integer programming to solve the particular class of Subset Sum problems in polynomial time.Lesson:dont le

13、ave your trapdoor loose.1215-853Groups based on modular arithmeticThe group of positive integers modulo a prime pZp*1,2,3,p-1*p multiplication modulo pDenoted as:(Zp*,*p)Required properties1.Closure.Yes.2.Associativity.Yes.3.Identity.1.4.Inverse.Yes.Example:Z7*=1,2,3,4,5,6 1-1=1,2-1=4,3-1=5,6-1=6131

14、5-853Other properties|Zp*|=(p-1)By Fermats little theorem:a(p-1)=1(mod p)Example of Z7*xx2x3x4x5x6111111241241326451421421546231616161For all p the group is cyclic.Generators1415-853What if n is not a prime?The group of positive integers modulo a non-prime nZn 1,2,3,n-1,n not prime*p multiplication

15、modulo nRequired properties?1.Closure.?2.Associativity.?3.Identity.?4.Inverse.?How do we fix this?1515-853Groups based on modular arithmeticThe multiplicative group modulo nZn*m:1 m n,gcd(n,m)=1*multiplication modulo nDenoted as(Zn*,*n)Required properties:Closure.Yes.Associativity.Yes.Identity.1.Inv

16、erse.Yes.Example:Z15*=1,2,4,7,8,11,13,14 1-1=1,2-1=8,4-1=4,7-1=13,11-1=11,14-1=141615-853The Euler Phi FunctionIf n is a product of two primes p and q,thenEulers Theorem:Or for n=pqThis will be very important in RSA!Law of exponentiation:1715-853GeneratorsExample of Z10*:1,3,7,9xx2x3x411113971793191

17、91Generators1815-853Operations we will needMultiplication:a*b(mod n)Can be done in O(log2 n)bit operations,or betterPower:ak(mod n)The power method O(log n)steps,O(log3 n)bit ops fun pow(a,k)=if(k=0)then 1 else if(k mod 2=1)then a*(pow(a,k/2)2 else(pow(a,k/2)2Inverse:a-1(mod n)Euclids algorithm O(lo

18、g n)steps,O(log3 n)bit ops1915-853Euclids AlgorithmEuclids Algorithm:gcd(a,b)=gcd(b,a mod b)gcd(a,0)=a“Extended”Euclids algorithm:Find x and y such that ax+by=gcd(a,b)Can be calculated as a side-effect of Euclids algorithm.Note that x and y can be zero or negative.This allows us to find a-1 mod n,fo

19、r a Zn*In particular return x in ax+ny=1.2015-853Euclids Algorithmfun euclid(a,b)=if(b=0)then a else euclid(b,a mod b)fun ext_euclid(a,b)=if(b=0)then(a,1,0)else let(d,x,y)=ext_euclid(b,a mod b)in(d,y,x (a/b)y)endThe code is in the form of an inductive proof.Exercise:prove the inductive stepgcdxyinte

20、ger quotient2115-853RSAInvented by Rivest,Shamir and Adleman in 1978Based on difficulty of factoring.Used to hide the size of a group Zn*since:.Factoring has not been reduced to RSAan algorithm that generates m from c does not give an efficient algorithm for factoringOn the other hand,factoring has

21、been reduced to finding the private-key.there is an efficient algorithm for factoring given one that can find the private key.2215-853RSA Public-key CryptosystemWhat we need:p and q,primes of approximately the same sizen=pq(n)=(p-1)(q-1)e Z(n)*d=e-1 mod(n)Public Key:(e,n)Private Key:dEncode:m ZnE(m)

22、=me mod nDecode:D(c)=cd mod n2315-853RSA continuedWhy it works:D(c)=cd mod n =med mod n =m1+k(p-1)(q-1)mod n =m1+k(n)mod n =m(m(n)k mod n =mWhy is this argument not quite sound?What if m Zn*then m(n)1 mod n Answer 1:Still works prove mk(n)+1=m mod n via Chinese Remainder Theorem Answer 2:jackpot if

23、you find an m Zn*then GCD(m,n)is a factor of n2415-853Proof for m Zn*CaseAssume w.l.o.g.that q divides m but p does not:Let x=m1+k(p-1)(q-1)=m*(m(p-1)k(q-1)(1)x p m (by Eulers Theorem)(2)x q 0 (since q|m)The Chinese Remainder Theorem states that for any two solutions x1 and x2 to equations(1)and(2),

24、x1 n x2.Notice that for both x1=m1+k(p-1)(q-1)and x2=m the equations are satisfied.Hence x1 n x2 n m.2515-853RSA computationsTo generate the keys,we need to Find two primes p and q.Generate candidates and use primality testing to filter them.Find e-1 mod(p-1)(q-1).Use Euclids algorithm.Takes time lo

25、g2(n)To encode and decodeTake me or cd.Use the power method.Takes time log(e)log2(n)and log(d)log2(n).In practice e is selected to be small so that encoding is fast.2615-853Security of RSAWarning:Do not use this or any other algorithm naively!Possible security holes:Need to use“safe”primes p and q.I

26、n particular p-1 and q-1 should have large prime factors.p and q should not have the same number of digits.Can use a middle attack starting at sqrt(n).e cannot be too smallDont use same n for different es.You should always“pad”2715-853Algorithm to factor n given d and eGiven(n),easy to factor n(two

27、equations,two unknowns):(p-1)(q-1)=(n)pq=nGiven d and e,dont have(n),but sinceed =1 mod(n),haveed-1=k(n),for some unknown k.Almost as good.2815-853Algorithm to factor n given d and eSuggested by Millers primality testing paper(1976):Function TryFactor(e,d,n)1.write ed 1 as 2sr,r odd2.choose w at ran

28、dom .5.Will return p or q if it passes.Try until you pass.Let(n)=LCM(p-1,q-1)Let m=#2(k(n)/(n)/2)(#2 is largest power of 2)w(n)/2-1 shares a factor with nw(n)/2=w k(n)/2m mod n2915-853RSA PerformancePerformance:(600Mhz PIII)(from:ssh toolkit):AlgorithmBits/keyMbits/secRSA Keygen1024.35sec/key20482.8

29、3sec/keyRSA Encrypt10241786/sec3.52048672/sec1.2RSA Decrypt102474/sec.074204812/sec.024ElGamal Enc.102431/sec.031ElGamal Dec.102461/sec.061DES-cbc5695twofish-cbc128140Rijndael1281803015-853RSA in the“Real World”Part of many standards:PKCS,ITU X.509,ANSI X9.31,IEEE P1363Used by:SSL,PEM,PGP,Entrust,Th

30、e standards specify many details on the implementation,e.g.e should be selected to be small,but not too small“multi prime”versions make use of n=pqrthis makes it cheaper to decode especially in parallel(uses Chinese remainder theorem).3115-853Factoring in the Real WorldQuadratic Sieve(QS):log n bits

31、 in input,superpolynomial timeUsed in 1994 to factor a 129 digit(428-bit)number.1600 Machines,8 months.Number field Sieve(NFS):Used in 1999 to factor 155 digit(512-bit)number.35 CPU years.At least 4x faster than QSUsed in 2003-2005 to factor 200 digits(663 bits)75 CPU years($20K prize)3215-853Discre

32、te LogarithmsIf g is a generator of Zn*,then for all y there is a unique x(mod(n)such thaty=gx mod nThis is called the discrete logarithm of y and we use the notationx=logg(y)In general finding the discrete logarithm is conjectured to be hardas hard as factoring.3315-853ElGamalBased on the difficult

33、y of the discrete log problem.Invented in 1985Digital signature and Key-exchange variants Digital signature is AES standard Public Key used by TRW(avoided RSA patent)Works over various groupsZp,Multiplicative group GF(pn),Elliptic Curves3415-853ElGamal Public-key Cryptosystem(G,*)is a group a genera

34、tor for Ga Z|G|=aG is selected so that it is hard to solve the discrete log problem.Public Key:(,)and some description of GPrivate Key:aEncode:Pick random k Z|G|E(m)=(y1,y2)=(k,m*k)Decode:D(y)=y2*(y1a)-1 =(m*k)*(ka)-1 =m*k*(k)-1 =mYou need to know a to easily decode y!3515-853ElGamal:ExampleG=Z11*=2

35、a =8=28(mod 11)=3Public Key:(2,3),Z11*Private Key:a=8Encode:7Pick random k=4E(m)=(24,7*34)=(5,6)Decode:(5,6)D(y)=6*(58)-1 =6*4-1 =6*3(mod 11)=73615-853Probabilistic EncryptionFor RSA one message goes to one cipher word.This means we might gain information by running Epublic(M).Probabilistic encrypti

36、on maps every M to many C randomly.Cryptanalysists cant tell whether C=Epublic(M).ElGamal is an example(based on the random k),but it doubles the size of message.3715-853BBS“secure”random bitsBBS(Blum,Blum and Shub,1984)Based on difficulty of factoring,or finding square roots modulo n=pq.Fixedp and

37、q are primes such that p=q=3(mod 4)n=pq(is called a Blum integer)For a particular bit seq.Seed:random x relatively prime to n.Initial state:x0=x2ith state:xi=(xi-1)2ith bit:lsb of xiNote that:Therefore knowing p and q allows us to find x0 from xi3815-853Decrypt:Using p and q,find Use this to regener

38、ate the bi and hence miBlum-Goldwasser:A stream cypherPublic key:n(=pq)Private key:p or qxixormi(0 i l)ci(0 i l)biRandom xx2 mod nBBSlsbci(l i l+log n)=xlEncrypt:3915-853Quantum CryptographyIn quantum mechanics,there is no way to take a measurement without potentially changing the state.E.g.Measurin

39、g position,spreads out the momentumMeasuring spin horizontally,“spreads out”the spin probability verticallyRelated to Heisenbergs uncertainty principal 4015-853Using photon polarization=?(equal probability)or=or?(equal probability)measurediagonalmeasuresquaredestroys state4115-853Quantum Key Exchang

40、e1.Alice sends bob photon stream randomly polarized in one of 4 polarizations:2.Bob measures photons in random orientationse.g.:x+x x x+x(orientations used)|-/-(measured polarizations)and tells Alice in the open what orientations he used,but not what he measured.3.Alice tells Bob in the open which are correct4.Bob and Alice keep the correct valuesSusceptible to a man-in-the-middle attack4215-853In the“real world”Not yet used in practice,but experiments have verified that it works.IBM has working system over 30cm at 10bits/sec.More recently,up to 10km of fiber.4315-853