椭圆曲线密码技术.ppt

橢圓曲線密碼技術,交通大學 資訊工程系陳榮傑 http:/www.cs.nctu.edu.tw/rjchen/ECC2012S/,Outline,1 Discrete Logarithm Problem2 Algorithms for Discrete Logarithm3 Cryptosystems Based on DLP4 Elliptic Curves5 Elliptic Curve DLP6 Signature Scheme:ECDSA7 How to find secure ECs?8 Hyperelliptic Curves9 ID-based Cryptosystems10 Pairing-based Cryptography,Let G is a finite cyclic group of size n generated by generator g,i.e.G=g i|i=1,2,n or g i|i=0,1,n-1Given g and i,it is easy to compute gi by repeated squaringDiscrete logarithm problem Given,find x such that We denote,1 Discrete Logarithm Problem,Example 1G=Z19*=1,2,18n=18,generator g=2 then log214=7 log26=14,Example 2G=GF*(23)with irreducible poly.p(x)=x3+x+1G=Zn*/p(x)=1,x,x2,1+x,1+x2,x+x2,1+x+x2 n=7,generator g=xthen logx(x+1)=3 logx(x2+x+1)=5 logx(x2+1)=6,Example 3Let p NB:p=158(2800+25)+1 and has 807 bits.Find x in Z,such that 2x=3 mod p,2 Algorithms for Discrete Logarithm,trivial algorithmShanks algorithm(Baby-step giant-step)Pollard rho discrete log algorithmPohlig-Hellman algorithmThe index calculus method*,The index calculus method,The index calculus method(Suitable only for G=Zp*),Example log59451 mod 10007=?Choose B=2,3,5,7.Of course log55=1.Use lucky exponents 4063,5136,and 9865 54063 mod 10007=42=2*3*7 55136 mod 10007=54=2*33 59865 mod 10007=189=33*7 And we have three congruences:log52+log53+log57=4063 mod 10006 log52+3 log53=5136 mod 10006 3 log53+log57=9865 mod 10006,There happens to be a unique solution modulo 10006 log52=6578,log53=6190,and log57=1301Choose random exponent s=7736 and try to calculate ags=9451*57736 mod 10007=8400 Since 8400=24*3*52*7 factors over B,we obtain log59451=(4 log52+log53+2 log55+log57 s)mod 10006=(4*6578+6190+2*1+1301 7736)mod 10006=6057 mod 10006,Complexity of Index Calculus,For factoring and the discrete logarithm problem in finite fields Fq*there are index calculus algorithm(implemented with Number Field Sieve technique)These have subexponential complexity O(exp(c(lnN)1/3(lnlnN)2/3),3 Cryptosystems based on DL,Key DistributionDiffie-Hellman,1976EncryptionMassey-Omura cryptosystem,1983 Digital SignatureElGamal,1985,Diffie-Hellman Key Exchange Algo,Global Public Elementsq:prime number:q and is a primitive root of qUser A Key GenerationSelect private XA:XA qCalculate public YA:YA=XA mod qUser B Key GenerationSelect private XB:XB qCalculate public YB:YB=XB mod qGeneration of Secret Key by User AK=(YB)XA mod qGeneration of Secret Key by User BK=(YA)XB mod q,User A,User B,Generate random XA q;Calculate YA=XA mod qCalculate K=(YB)XA mod q,Generate random XB q;Calculate YB=XB mod qCalculate K=(YA)XB mod q,YA,YB,Diffie-Hellman Key Exchange,Massey-Omura for message transmission,Parametersq:prime numbere:a random private integer 0 e q and gcd(e,q-1)=1d:an inverse of ed=e-1 mod q-1,i.e.,de1 mod q-1M:a message to be encrypted and decryptedUser A wants to send a message M to User BUser A:eA and dA are both privateUser B:eB and dB are both private,User A,User B,1.Encryption(1)C1=M eA mod q3.Encryption(3)C3=C2dA=(M eAeB)dA=M eB mod q,2.Encryption(2)C2=C1eB=M eAeB mod q4.Decryption M=C3dB=M eBdB mod q,Massey-Omura for message transmission,C1,C2,C3,ElGamal signature scheme,1985 ElGamalParameters p:a large prime:a primitive number in GF(p)x:a private key,x 1,p-1 y:a public key,y=x(mod p)m:a message to be signed,m 1,p-1 k:a random integer that is privately selected,k 0,p-2Signature r=k mod pm=ks+rx mod(p),where GCD(k,(p)=1(m,(r,s)is sent to the verifierVerificationm=rs yr mod pThe signature(r,s)is accepted when the equality holds true.,ElGamal encryption scheme,Parameters p:a large prime:a primitive number in GF(p)a:a private key,a 1,p-1:a public key,=a(mod p)m:a message to be signed,m 1,p-1 k:a random integer that is privately selected,k 0,p-2K=(p,a,):public key+private keyEncryption eK(m,k)=(y1,y2)where y1=k mod p and y2=mk mod pDecryption m=dK(y1,y2)=y2(y1a)-1 mod p,(xP+Q,yP+Q),(xP+Q,yP+Q),4 Elliptic Curves,Over Fields of Characteristic p3Curve formE:Y2=X3+aX+b where a,b Fq,q=pn 4a3+27b20Group operationgiven P1(x1,y1)and P2(x2,y2)compute P3(x3,y3)=P1+P2,Example:,P,-P,Q,P+Q,Example of EC over GF(p),Addition(P1P2)Doubling(P1=P2),Computational CostI+3 M,Computational CostI+4 M,Over Fields of Characteristic 2Curve formE:Y2+XY=X3+aX2+b where a,b Fq,b0,q=2nGroup operationgiven P1(x1,y1)and P2(x2,y2)compute P3(x3,y3)=P1+P2,Example of EC over GF(2m),Addition(P1P2)Doubling(P1=P2),Computational CostI+2 M+S,Computational CostI+2 M+S,5 Elliptic Curve DLP,Basic computation of ECCQ=kP=where P is a curve point,k is an integerStrength of ECCGiven curve,the point P,and kPIt is hard to recover k-Elliptic Curve Discrete Logarithm Problem(ECDLP),Security of ECC versus RSA/ElGamalElliptic curve cryptosystems give the most security per bit of any known public-key scheme.The ECDLP problem appears to be much more difficult than the integer factorisation problem and the discrete logarithm problem of Zp.(no index calculus algo!)The strength of elliptic curve cryptosystems grows much faster with the key size increases than does the strength of RSA.,Elliptic Curve Security,NIST Recommended Key Sizes,ECC BenefitsECC is particularly beneficial for application where:computational power is limited(wireless devices,PC cards)integrated circuit space is limited(wireless devices,PC cards)high speed is required.intensive use of signing,verifying or authenticating is required.signed messages are required to be stored or transmitted(especially for short messages).bandwidth is limited(wireless communications and some computer networks).,6 Signature Scheme:ECDSA,Digital Signature Algorithm(DSA)Proposed in 1991Was adopted as a standard on December 1,1994Elliptic Curve DSA(ECDSA)FIPS 186-2 in 2000,Digital Signature Algorithm(DSA),Let p be a L-bit prime such that the DL problem in Zp*is intractable,and let q be a 160-bit prime that divides p-1.Let be a qth root of 1 modulo p.Define K=(p,q,a,):=a mod p p,q,are the public key,a is private,L=0 mod 64,512L1024,For a(secret)random number k,definesig(x,k)=(,),where=(k mod p)mod q and=(SHA-1(x)+a)k-1 mod qFor a message(x,(,),verification is done by performing the following computations:e1=SHA-1(x)*-1 mod qe2=*-1 mod qver(x,(,)=true iff.(e1e2 mod p)mod q=,Elliptic Curve DSA,Let p be a prime,and let E be an elliptic curve defined over Fp.Let A be a point on E having prime order q,such that DL problem in is infeasible.Define K=(p,q,E,A,m,B):B=mA p,q,E,A,B are the public key,m is private,For a(secret)random number k,define sigk(x,k)=(r,s),where kA=(u,v),r=u mod q ands=k-1(SHA-1(x)+mr)mod qFor a message(x,(r,s),verification is done by performing the following computations:i=SHA-1(x)*s-1 mod qj=r*s-1 mod q(u,v)=iA+jBver(x,(r,s)=true if and only if u mod q=r,7 How to find secure elliptic curves?,(1)Randomly choose a,b,p and calculate#Elliptic curve(y2=x3+ax+b)until#E=a prime q,where#E is calculate by using Schoof-Elkies-Atkin algorithm(2)(Complex multiplication method)Given a big prime q,find p,a,b such that#Elliptic curve(y2=x3+ax+b)=q,8 Hyperelliptic Curves,1.Definition of HC 2.Example of HC(rational points of HC do not form a group)3.Divisor 4.Jacobian(Jacobian is a group)5.HCDLP,Definitions of hyperelliptic curves,A hyperelliptic curve C of genus g over a finite field K(g1)C:y2+h(x)y=f(x)whereh(x)Kx is a polynomial of degree at most g,f(x)Kx is a monic polynomial of degree 2g+1.Elliptic curves are hyperelliptic curves of genus 1.,Group law in an elliptic curve,y2=x3-x over R,？,-R,P+Q=,Example:Hyperelliptic curve,A genus 2 hyperelliptic curve over R:C:y2=x5-5x3+4x=x(x+1)(x-1)(x+2)(x-2)The rational points on C do not form a group.,Divisors,Definition:(divisor,degree)A divisor D is a formal sum of points in C:The degree of D,The set of all divisors,denoted D,forms an additive group under the addition rule:D0(K)is the subgroup of all divisors defined over K and of degree 0.,D1=2P1+P2-3D2=P1+P3,deg(D1)=2+1-3=0deg(D2)=1+1=2,D1+D2=3P1+P2+P3-3,Principal divisor,Definition:(principal divisors)Let R K(C)be a rational function.The divisor of R is called a principal divisor:In fact,degree of a principal divisor is 0.The set of all principal divisors,denoted P(K),is a subgroup of D0(K).,C:y2=x5-5x3+4x x-1,Q1=(1,0)on Cdiv(x-1)=2Q1-2,Jacobian,Definition:(Jacobian)The quotient group JC(K)=D0/P is called the Jacobian of the curve C.If D1,D2 D0 and D1-D2 P,then D1 and D2 are said to be equivalent divisors;we write D1D2.,Group law in HC,A genus 2 hyperelliptic curve over R:C:y2=x5-5x3+4xy=a3x3+a2x2+a1x+a0,P1,P2,P4,？,P3,HCDLP,HCDLP:(hyperelliptic curve discrete logarithm problem)Let a divisor D1 in JC(Fq)with known order N,and D2 in To find an integer s.t.D2=D1 is hard.,9 ID-based Cryptosystem,Private Key Generator(PKG),Bob,Alice,Authentication(IDBob),KRIDBob,(params,IDBob),KRIDBob,IDBob is arbitrary and meaningfulex:or 0912345678,Setup generate params and master key,Extract generate KRIDBob by IDBob and master key,Encrypt,Verify,or,Decrypt,Sign,or,Certificate-based Cryptosystem,Certificate Authority(CA),Bob,Alice,Authentication(KUBob),Certificate(Bob,KUBob),Certificate(Bob,KUBob),Encrypt,KUBob,Decrypt,KRBob,KUBob is random,Verify,Sign,or,or,ID-based Encryption Scheme,Proposed by Boneh and Franklin(Crypto 2001)First complete and efficient schemeBilinear PairingG1:additive group generated by P,ord(P)=qG2:multiplicative group with same order qAssume that DLP in G1 and G2 are hardLet e:G1xG1 G2 satisfies:1.Bilinear:e(P1+P2,Q)=e(P1,Q)e(P2,Q)e(P,Q1+Q2)=e(P,Q1)e(P,Q2)2.Non-degenerate:P,Q G1,s.t e(P,Q)13.ComputabilityBilinear Diffie-Hellman(BDH)AssumptionGiven P,aP,bP,cP G1,compute e(P,P)abc is HARD!,ID-based Encryption Scheme,ID-based EncryptionSetup:(1)Choose P E/Fp of order q(2)Pick a random s Zq*and set Ppub=sP(3)Two hash functions:H1:0,1*G*1(MapToPoint)H2:G2 0,1n for some nExtract:Given a ID 0,1*,build private key SID as follows:QID=H1(ID)Set dID=sQID,where s is the master key,System:k-bit prime p p=2 mod 3,p=6q-1 E:y2=x3+1 over Fp,Params:Master-key:s,Encrypt:Use MapToPoint to map ID to QIDchoose a random r Zq*C=Decrypt:Let C=,if U is not a point of order q then rejectM=V H2(e(dID,U),e(dID,U)=e(sQID,rP)=e(QID,P)sr=e(QID,sP)r=e(QID,Ppub)r,dID=sQID,Ppub=sP,ID-based Encryption Scheme,(Def)Weil pairing where is called the m-torsion group,Um is the group of the mth roots of unityGiven P,QE m,DP,DQDiv 0 such thatDP(P)(O)and DQ(Q)(O).Also,fP,fQ such that div(fP)=m DP and div(fQ)=m DQ.Suppose supp(DP)supp(DQ)=Then,Weil Pairing,End-to-end security for SMS(short message service),RSA Mechanism,ID-based Mechanism,End-to-end security for SMS,10 Pairing-based Cryptography,1.Implementation of Pairings Bilinear paring e:G1 x G2 GT G1,G2:prime-order subgroups of an elliptic curve E over GF(qk)GT:prime-order subgroup of GF(qk)*k is the embedding degree of E(w.r.t.r=#E(GF(q)k is the smallest positive integer s.t.r|qk-1,Various pairings:Weil pairing Tate pairing Eta pairing Ate pairing Generalized Ate pairing,2.Use of parings in cryptography Attack on ECDLP(MOV attack)One-round 3-way key exchange(Joux)IDE(Boneh-Franklin)Short digital signature(Boneh-Lynn-Shacham)Other applications:Group signatures,Bach signatures,aggregate signatures,threshold cryptography,authenticated encryption,broadcast encryption,etc.,3.Constructing pairing-friendly curves Want k large enough so that DLP in GF(qk)*is computational infeasible,but small enough so that pairing is easy to compute.Cock-Pinch strategy MNT strategy Dupon-Enge-Morain strategy*Brezing-Weng strategy Scott-Barreto strategy,