1、橢圓曲線密碼技術橢圓曲線密碼技術交通大學交通大學 資訊工程系資訊工程系陳榮傑陳榮傑 http:/www.cs.nctu.edu.tw/rjchen/ECCS/1/55Outlinen1 Discrete Logarithm Problemn2 Algorithms for Discrete Logarithmn3 Cryptosystems Based on DLPn4 Elliptic Curvesn5 Elliptic Curve DLPn6 Signature Scheme:ECDSAn7 How to find secure ECs?n8 Hyperelliptic Curvesn9
2、ID-based Cryptosystemsn10 Pairing-based Cryptography2/55nLet 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-1nGiven g and i,it is easy to compute gi by repeated squaringnDiscrete logarithm problem Given ,find x such that We denote 1 Discrete Logarithm
3、Problem3/55nExample 1G=Z19*=1,2,18n=18,generator g=2 then log214=7 log26=144/55nExample 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)=65/55nExample 3Let p=1053546280395016975304616582933958731948871814925
4、913489342608734258717883575185867300386287737705577937382925873762451990450430661350859682697410256268271147283034897563214300237166369174066615907176472549470083113107138189921280884003892629359 NB:p=158(2800+25)+1 and has 807 bits.nFind x in Z,such that 2x=3 mod pn 6/552 Algorithms for Discrete Lo
5、garithmntrivial algorithmnShanks algorithm(Baby-step giant-step)nPollard rho discrete log algorithmnPohlig-Hellman algorithmnThe index calculus method*7/55The index calculus methodnThe index calculus method(Suitable only for G=Zp*)8/55nExample log59451 mod 10007=?Choose B=2,3,5,7.Of course log55=1.U
6、se 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 9/55There happens to be a unique solution modulo 10006 log52=6578,l
7、og53=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 1000610/55Complexity of Index CalculusnFor factorin
8、g and the discrete logarithm problem in finite fields Fq*there are index calculus algorithm (implemented with Number Field Sieve technique)nThese have subexponential complexity O(exp(c(lnN)1/3(lnlnN)2/3)11/553 Cryptosystems based on DLnKey DistributionnDiffie-Hellman,1976nEncryptionnMassey-Omura cry
9、ptosystem,1983 nDigital SignaturenElGamal,198512/55Diffie-Hellman Key Exchange AlgonGlobal Public Elementsnq :prime numbern:q and is a primitive root of qnUser A Key GenerationnSelect private XA:XA qnCalculate public YA:YA=XA mod qnUser B Key GenerationnSelect private XB:XB qnCalculate public YB:YB=
10、XB mod qnGeneration of Secret Key by User AnK=(YB)XA mod qnGeneration of Secret Key by User BnK=(YA)XB mod q13/55User AUser BGenerate 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 YAYBDiffie-Hellman Key Exchange14/55Masse
11、y-Omura for message transmissionnParametersnq :prime numberne :a random private integer 0 e 3nCurve formE:Y2=X3+aX+b where a,b Fq,q=pn 4a3+27b20nGroup operationgiven P1(x1,y1)and P2(x2,y2)compute P3(x3,y3)=P1+P2PQP+Q19/55nExample:P -P QP+QExample of EC over GF(p)20/55nAddition(P1P2)nDoubling(P1=P2)C
12、omputational CostI+3 MComputational CostI+4 M21/55nOver Fields of Characteristic 2nCurve formE:Y2+XY=X3+aX2+b where a,b Fq,b0,q=2nnGroup operationgiven P1(x1,y1)and P2(x2,y2)compute P3(x3,y3)=P1+P222/55Example of EC over GF(2m)23/55Addition(P1P2)Doubling(P1=P2)Computational CostI+2 M+SComputational
13、CostI+2 M+S24/555 Elliptic Curve DLPnBasic computation of ECCnQ=kP=where P is a curve point,k is an integernStrength of ECCnGiven curve,the point P,and kPIt is hard to recover k-Elliptic Curve Discrete Logarithm Problem(ECDLP)25/55Security of ECC versus RSA/ElGamalnElliptic curve cryptosystems give
14、the most security per bit of any known public-key scheme.nThe ECDLP problem appears to be much more difficult than the integer factorisation problem and the discrete logarithm problem of Zp.(no index calculus algo!)nThe strength of elliptic curve cryptosystems grows much faster with the key size inc
15、reases than does the strength of RSA.26/55Elliptic Curve SecuritySymmetric Key Size(bits)RSA and Diffie-HellmanKey Size(bits)Elliptic Curve Key Size(bits)80102416011220482241283072256192768038425615360521NIST Recommended Key Sizes 27/55 ECC BenefitsECC is particularly beneficial for application wher
16、e:ncomputational power is limited(wireless devices,PC cards)nintegrated circuit space is limited(wireless devices,PC cards)nhigh speed is required.nintensive use of signing,verifying or authenticating is required.nsigned messages are required to be stored or transmitted(especially for short messages
17、).nbandwidth is limited(wireless communications and some computer networks).28/556 Signature Scheme:ECDSAnDigital Signature Algorithm(DSA)nProposed in 1991nWas adopted as a standard on December 1,1994nElliptic Curve DSA(ECDSA)nFIPS 186-2 in 29/55Digital Signature Algorithm(DSA)nLet p be a L-bit prim
18、e 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 privateL=0 mod 64,512L102430/55nFor a(secret)random number k,definesig(x,k)=(,),where=(k mod p)mod q and=(SHA-1(x)+a)k-
19、1 mod qnFor 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=31/55Elliptic Curve DSAnLet 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
20、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 private32/55nFor 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 qnFor a message(x,(r,s),verification is done by performing the following computations:i=SHA-1(x
21、)*s-1 mod qj=r*s-1 mod q(u,v)=iA+jBver(x,(r,s)=true if and only if u mod q=r33/557 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
22、a big prime q,find p,a,b such that#Elliptic curve(y2=x3+ax+b)=q34/558 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.HCDLP35/55Definitions of hyperelliptic curvesnA hyperelliptic curve C of genus g over a
23、finite field K(g 1)C:y2+h(x)y=f(x)wherenh(x)Kx is a polynomial of degree at most g,nf(x)Kx is a monic polynomial of degree 2g+1.nElliptic curves are hyperelliptic curves of genus 1.36/55Group law in an elliptic curveny2=x3-x over R？-RP+Q=PQRPQR-R37/55Example:Hyperelliptic curvenA genus 2 hyperellipt
24、ic curve over R:C:y2=x5-5x3+4x=x(x+1)(x-1)(x+2)(x-2)nThe rational points on C do not form a group.38/55DivisorsnDefinition:(divisor,degree)nA divisor D is a formal sum of points in C:nThe degree of D,nThe set of all divisors,denoted D,forms an additive group under the addition rule:nD0(K)is the subg
25、roup of all divisors defined over K and of degree 0.D1=2P1+P2-3D2=P1+P3deg(D1)=2+1-3=0deg(D2)=1+1=2D1+D2=3P1+P2+P3-339/55Principal divisornDefinition:(principal divisors)nLet R K(C)be a rational function.The divisor of R is called a principal divisor:nIn fact,degree of a principal divisor is 0.nThe
26、set of all principal divisors,denoted P(K),is a subgroup of D0(K).C:y2=x5-5x3+4x x-1Q1=(1,0)on Cdiv(x-1)=2Q1-240/55JacobiannDefinition:(Jacobian)nThe quotient group JC(K)=D0/P is called the Jacobian of the curve C.nIf D1,D2 D0 and D1-D2 P,then D1 and D2 are said to be equivalent divisors;we write D1
27、D2.41/55Group law in HCnA genus 2 hyperelliptic curve over R:C:y2=x5-5x3+4xny=a3x3+a2x2+a1x+a0P1P2P4？P3P5P6P6P5x-x5=0 x-x6=042/55HCDLPnHCDLP:(hyperelliptic curve discrete logarithm problem)nLet a divisor D1 in JC(Fq)with known order N,and D2 in nTo find an integer s.t.D2=D1 is hard.43/559 ID-based C
28、ryptosystemPrivate Key Generator(PKG)BobAliceAuthentication(IDBob)KRIDBob(params,IDBob)KRIDBobIDBob is arbitrary and meaningfulex:B or 0912345678Setup generate params and master keyExtract generate KRIDBob by IDBob and master keyEncryptVerifyorDecryptSignor44/55Certificate-based CryptosystemCertific
29、ate Authority(CA)BobAliceAuthentication(KUBob)Certificate(Bob,KUBob)Certificate(Bob,KUBob)EncryptKUBobDecryptKRBobKUBob is randomVerifySignoror45/55ID-based Encryption SchemenProposed by Boneh and Franklin(Crypto)nFirst complete and efficient schemenBilinear PairingG1:additive group generated by P,o
30、rd(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.ComputabilitynBilinear Diffie-Hellman(BDH)AssumptionGiven P,aP,bP,cP G1 ,compute e(P,P)abc i
31、s HARD!46/55ID-based Encryption Scheme nID-based EncryptionnSetup:(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 nnExtract:Given a ID 0,1*,build private key SID as follows:QID=H1(ID)Set dID=sQID,where s is the master ke
32、ySystem:k-bit prime p p=2 mod 3,p=6q-1 E:y2=x3+1 over FpParams:Master-key:s47/55nEncrypt:Use MapToPoint to map ID to QIDchoose a random r Zq*C=nDecrypt: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)rdID=sQIDPpub=sPID-based Encryp
33、tion Scheme 48/55n(Def)Weil pairing where is called the m-torsion group,Um is the group of the mth roots of unitynGiven 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 Pairing49/55End-to-end security for SMS(shor
34、t message service)nRSA Mechanism50/55nID-based MechanismEnd-to-end security for SMS 51/5510 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 o
35、f E(w.r.t.r=#E(GF(q)k is the smallest positive integer s.t.r|qk-1 52/55 Various pairings:Weil pairing Tate pairing Eta pairing Ate pairing Generalized Ate pairing 53/55 2.Use of parings in cryptography Attack on ECDLP(MOV attack)One-round 3-way key exchange(Joux)IDE(Boneh-Franklin)Short digital sign
36、ature(Boneh-Lynn-Shacham)Other applications:Group signatures,Bach signatures,aggregate signatures,threshold cryptography,authenticated encryption,broadcast encryption,etc.54/55 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 strategy55/55
