椭圆曲线密码技术

,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,p,*,.,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,*,橢圓曲線密碼技術,交通大學 資訊工程系,陳榮傑,http:/www.cs.nctu.edu.tw/rjchen/ECC2012S/,Outline,1 Discrete Logarithm Problem,2 Algorithms for Discrete Logarithm,3 Cryptosystems Based on DLP,4 Elliptic Curves,5 Elliptic Curve DLP,6 Signature Scheme:ECDSA,7 How to find secure ECs?,8 Hyperelliptic Curves,9 ID-based Cryptosystems,10 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-1,Given,g,and,i,it is easy to compute,g,i,by repeated squaring,Discrete logarithm problem,Given ,find,x,such that,We denote,1 Discrete Logarithm Problem,Example 1,G=Z,19,*,=1,2,18n=18,generator,g,=2,then log,2,14=7 log,2,6=14,Example 2,G=,GF,*,(2,3,)with irreducible poly.p(x)=,x,3,+,x,+1G=Z,n,*,/p(x)=1,x,x,2,1+,x,1+,x,2,x,+,x,2,1+,x,+,x,2,n=7,generator,g,=,x,then log,x,(,x,+1)=3 log,x,(,x,2,+,x,+1)=5 log,x,(,x,2,+1)=6,Example 3,Let p,NB:p,=158(2,800,+25)+1 and has 807 bits.,Find x in Z,such that,2,x,=3 mod p,2 Algorithms for Discrete Logarithm,trivial algorithm,Shanks algorithm(Baby-step giant-step),Pollard rho discrete log algorithm,Pohlig-Hellman algorithm,The index calculus method*,The index calculus method,The index calculus method(Suitable only for G=Z,p,*),Example,log,5,9451 mod 10007=?,Choose B=2,3,5,7.Of course log,5,5=1.,Use lucky exponents 4063,5136,and 9865,5,4063,mod 10007=42=2*3*7,5,5136,mod 10007=54=2*3,3,5,9865,mod 10007=189=3,3,*7,And we have three congruences:,log,5,2+log,5,3+log,5,7=4063 mod,10006,log,5,2+3 log,5,3=5136 mod,10006,3 log,5,3+log,5,7=9865 mod,10006,There happens to be a unique solution modulo 10006,log,5,2=6578,log,5,3=6190,and log,5,7=1301,Choose random exponent s=7736 and try to calculate,ag,s,=9451*5,7736,mod 10007=8400,Since 8400=2,4,*3*5,2,*7 factors over B,we obtain,log,5,9451=(4 log,5,2+log,5,3+2 log,5,5+log,5,7 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 F,q,*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 Distribution,Diffie-Hellman,1976,Encryption,Massey-Omura cryptosystem,1983,Digital Signature,ElGamal,1985,Diffie-Hellman Key Exchange Algo,Global Public Elements,q,:prime number,:,q,and is a primitive root of,q,User A Key Generation,Select private X,A,:X,A,q,Calculate public Y,A,:Y,A,=,XA,mod,q,User B Key Generation,Select private X,B,:X,B,q,Calculate public Y,B,:Y,B,=,XB,mod,q,Generation of Secret Key by User A,K=(Y,B,),XA,mod,q,Generation of Secret Key by User B,K=(Y,A,),XB,mod,q,User A,User B,Generate,random X,A,q,;,Calculate,Y,A,=,XA,mod,q,Calculate,K=(Y,B,),XA,mod,q,Generate,random X,B,q,;,Calculate,Y,B,=,XB,mod,q,Calculate,K=(Y,A,),XB,mod,q,Y,A,Y,B,Diffie-Hellman Key Exchange,Massey-Omura for message transmission,Parameters,q,:prime number,e,:a random private integer,0,e,3,Curve form,E:Y,2,=X,3,+aX+b,where a,b,F,q,q=p,n,4a,3,+27b,2,0,Group operation,given P,1,(x,1,y,1,)and P,2,(x,2,y,2,),compute P,3,(x,3,y,3,)=P,1,+P,2,P,Q,P+Q,Example:,P,-,P,Q,P+Q,Example of EC over GF(p),Addition(P,1,P,2,),Doubling(,P,1,=P,2,),Computational Cost,I+3 M,Computational Cost,I+4 M,Over Fields of Characteristic 2,Curve form,E:Y,2,+XY=X,3,+aX,2,+b,where a,b,F,q,b0,q=2,n,Group operation,given P,1,(x,1,y,1,)and P,2,(x,2,y,2,),compute P,3,(x,3,y,3,)=P,1,+P,2,Example of EC over GF(2,m,),Addition(P,1,P,2,),Doubling(,P,1,=P,2,),Computational Cost,I+2 M+S,Computational Cost,I+2 M+S,5 Elliptic Curve DLP,Basic computation of ECC,Q=kP=,where P is a curve point,k is an integer,Strength of ECC,Given curve,the point P,and kP,It is hard to recover k,-,Elliptic Curve Discrete Logarithm Problem(ECDLP),Security of ECC versus RSA/ElGamal,Elliptic 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,Z,p,.,(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,Symmetric Key Size(bits),RSA and Diffie-HellmanKey Size(bits),Elliptic Curve Key Size(bits),80,1024,160,112,2048,224,128,3072,256,192,7680,384,256,15360,521,NIST Recommended Key Sizes,ECC Benefits,ECC 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 1991,Was adopted as a standard on