о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3611ڡVol.36No.111999



Բ

ժҪԲĿǰϢȫѧĹ㷺ע,ӰȫԼЧ,ŹӦǰ,һֿܽĳЩȡRSADSSִ˻(ǩ),炽γо뿪ȵ.ȶԲ߼֪ʶ˼򵥽,һЩ͵ԲƲΪϸƵİȫ.л൱ƪƵԲߵĹ췽ص,ʵԲƵĹؼ.Ϊһƪ,зӳԲƵʷչ״Լǰٵ,˸Ŀǰ³ɾ,ԸƵķչ˿.
ؼʣԲ,ɢ,,ʱ临Ӷ,ȫ
ͼţTP309
ELLIPTIC CURVE CRYPTOSYSTEMSXU
Qiu-Liang
(Department of Computer Science, Shandong University, Jinan 250100)
LI Da-Xing
(Institute of Network Security, Shandong University, Jinan 250100)
AbstractRecently, elliptic curve cryptosystems have become as a promising new area in public-key cryptography. The main advantage of elliptic curve cryptosystems over other public-key cryptosystems is the fact that they are base on adifferent intractable problemb and that their keys have smaller sizes for he same level of security. These roperties lead to some better performance in application. Because of their security and efficincy, this kind of cryptosystems can be used widely in the future. In fact, they have come into strong consideration not only by theory researchers but also by standards de velopers.The paper here covers the main various aspects of elliptic curve crypt osystems. The concepts of elliptic curves and their related knowledge are introd uce briefly, and a few typical schemes are given. The seurity of elliptic curve cryptosystems is given a properly detailed descriptin. Builing of an elipic curve suitable for cryptosystems, which is essential to the setup of an elliptic curve cryptosystem, is discussed in detail.
As a summarythe advance and the status quo of the elliptic curve cryptosystems are reflected, and so do the prblems the cryptosystems face now. The newest achievements in this area are covered and views on the development of the cryptosy stems are proposed.
Key wordselliptic curve, discrete logarithm, cryptosystem, time complexity, security
1
ԲǴΡ۵ȶѧ֧һ,һֱΪǴѧ.,ڹԿѧĲ뷢չ,ѧҲҵӦ.RSAƵĻ⡪ֽԼо,ԲһǿĹߣ16.ر,Բϵ()㹹ɵAbelȺΪṹ,ʵָǹԿѧһҪ80ڱ7,8,Բ𲽳Ϊһʮ˸Ȥѧ֧,1997γһоȵ.Ƶ֮ڰȫ൱ǰ,ʹý϶̵Կ.һΪ,qԪϵԲ,qĳΪ160bitʱ,䰲ȫ൱RSAʹ1024bitģ9,ԿζСĴʹ洢Ҫ,ĳЩӦпǾԵ.ԲƵ֮һͬڴֽ⼰˷Ⱥɢѧ֮.ԹԿ,ǻڸѧ˴뷽,ܹסʱ俼㷺Ϊֻܵлڴֽ⼰ɢķ,Ҳ˵ָܵ㷨в,խѧ˵Ҳܲǵĵ,ѰµѧΪԴŬһ.ͬʱ,ԲԴḻ,ͬһϴŴͬԲ,Ϊȫ˶ı֤,ҲΪӲʵִ.
ԲϵһȺջΪ䱳ϲ15γ˷,ʵ,ִٶȷ,ĿǰԶԲִ,RSA,DSA׼ȷĶȽ,Ե˵,Բƽ϶ӦɢҪ,ǩͽܷRSA,ǩ֤ͼܷRSA9.
ȫȻκƵıش,ԲƵİȫԷҲ˸ѧɺйزŵĹע,ɹȴ˶.ҲΪԲƾиǿȵһ֤,,ѧҶƵǰֹ̬.
2ԲߵĻ
ڱ,Kܱʾһ.ʵ,ѧֻθȤ:KǴZpΪ2GF(2n)(Ϊ˷ϵķ,qԪGF(q)ʱҲFqʾ).ǻԼpܱʾһ3,ʾKĴհ,KϵӰƽP2(K)K3\{(0,0,0)}ϵĵȼ۹ϵĵȼ༯,СΪ(X1,Y1,Z1)(X2,Y2,Z2)ҽuK*ʹ(X1,Y1,Z1)=(uX2,uY2,uZ2).(X,Y,Z)ĵȼΪ(X:Y:Z).ʽ3̳ΪKϵWeierstrasṣ
Y3Z+a1XYZ+a3YZ3=X3+a23-2Z+a4XZ2+a6Z3(1)
,a1,a2,,a6K.F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3F(X,Y,Z)=0ӰP=(XYZ)P2(),FP3ƫزȫΪ0,Weierstrass(1)ƽĻ.
KϵWeierstrass(1)ƽ,÷P2енɵļE

ΪKϵһԲ.һԲ,ΨһһZΪ0,õ㼴O=(010),ǳΪԶ㡱.ԲEбʽ(E)j-j(E)ԲҪ,䶨ף10.
Ϊ˷,Weierstrass(1)Էx=X/Z,y=Y/ZʽдΪ
y2+a1xy+a3y=x3+a2x2+a4x+a6(1)
ʱ,ӦԲEǷ(1)ڷƽA2()ен⼰һ㡪Զ0ɵļ.

Ϊȷ,ԺE/KʾKϵԲE.E/KKĵ㼰ԶOΪE/KK-,E/KK-ɵļϼΪE(K),

Ϊķ,ǽԲ䶨巽,ԼEE/KܱʾKϵԲ,˵.
KϵԲ

ͬ,Ϊu,r,s,tK,u0ʹñ滻(x,y)(u2x+r,u3y+u2sx+t)E1ΪE2.KChar(K)2,3ʱ,E/Kͬ»¼״
E䣺y2=x3+ax+ba,bK
ʱ,(E)=-16(4a3+27b2)0,j(E)=-1728(4a)3/(E).KChar(K)=2ʱ,j(E)ǷΪ0,ɷֱΪֻ״,μף11.
ԲE/Kпɰзӷ㡰+ʹE,+ΪһAbelȺ,EK),+Ⱥ,֮ΪE/KȺ.֤,ʱE1(K)E2(K)ΪAbelȺͬģ11.νԲ,ǽAbelȺE(K)ϵ,潫#E(K)ʾȺE(K)Ľ.ѧֱӳE(K)ΪԲȺ,#E(K)ΪԲߵĽ,ʱҲ˵.
3͵Բ
еԲƾǴȺƽƶ,δE(K),ƽҪǶԻɢ,ȻҲRSAƵƽƣ12,13,ʵüۼֵ,Ľͻɢƽ.
GһȺ,a,bG,nʹan=b,nΪȺGbaΪ׵ɢ,Ϊn=logab.a,bG,n=logabΪGеɢ,ر,P,QE(K),nʹnP=Q,ΪԲɢ.
ElGamalֱƽƵԲȺ,õƽҪȰѴܵתΪԲϵĵ,ܽм,ʵϽΪ鷳,Ϊ鷳,MenezeVanstoneԸһ΢޸ģ11.ܵEC_ElGamalƲָĽʽ.
ECElGamalƣ
(1)ѡȡKԲE/KPE(K)(Щһû).
(2)ѡȡa,Q=aP.
(3)K,E,P,QΪԿ,ܲaΪ˽Կ.
Aliceѽ,AliceϢM=(M1,M2)KK,²:
ѡȡk.
ڼkP,kQ=(,),=0=0صڢٲ,ֱ0,0.
۷C=(kP,M1,M2)Alice.
յC,Alicea(kP)=(,),õM=(M1,M2).
EC_DSSǩƣ
(1)ѡȡKԲE/KPE(K),衴PPɵqѭȺ,qһ.
(2)ѡȡx,0<x<q,Q=xP.
(3)ѡȡHashH:MZ,,MϢռ,Z,ѡȡ˫gP0,1,,q-1}.
(4)K,E,P,Q,q,gΪϢ,Ϊǩ֤Կ,xΪǩԿ.
ϢmM,ԵǩΪ
ѡȡk,0<k<q
ڼR=kP
۽sͬ෽H(m)-xg(R)+ksmodq
mǩΪ(R,s).ǩ֤Ϊ
(Hm)s1modq)P+(g(R)s1modq)Q=R
EC_Diffie-HellmanԿЭ飺
ѡȡKԲE/KPE(K).K,E,PΪϢ.AliceBobԿ,ִ²裺
Aliceѡȡm,KA=mP,KA͸Bob
Bobѡȡn,KB=nP,KB͸Alice
Aice㣺KC=mKBBob㣺KC=nKA.KCΪAliceBob̶Կ.
4ԲƵİȫ
ԲƵİȫȡԲɢѽ.һ,ȺGϵɢ㷨ɷֳָࣺ㷨ײ.ָ㷨ָʱ临Ӷ,ҪGСƽԡ,Gа㹻ƽԪ.ȺGF(2n)ĳ˷ȺZp.Ŀǰõָ㷨ɸ14ɸ15.ײһȺ,㷨дָʱ临Ӷ.ĿǰЧײPllard-16ݺPohlig-Hellman17,ҲĿǰԲӰķ.һȺʽ.¼GһnAbelȺ,H=hhGɵnhѭȺ.
4.1Pollard-
Pollard-һ㷨,޷ʱϽ,ֻܸ.
nh֪,GֳɴԼƵ3G1,G2,G3,ʹxGi(i=1,2,3)ж׵(Լ൱һλ򼸴G),yH=h,ѡȡa0,b0ʹ1<a0,b0<nh,y0ha0yb0У
(2)
,ai,biģnhԼ,ʲɿ.еĹ챣֤еʽ:

{y}ΪHHһ()ӳ,ѭΪO,,ͨȽyiy2iǿOʱkʹyk=y2k,k=O,hakybk=ha2kyb2kybk-b2k=ha2k-ak,gcd(bk-b2k,nh)=1ʱ

,gcd(bk-b2k,nh)1Ժܸߵĸʳ(,DSS,nhһ).㷨ΪO.
4.2Pohlig-Hellman
Silver֮,PohligHellan,AbelȺGĽ׵ƽԶGɢа.yH,йʣඨ,Ҫm=loghy,ֻmmodpep.Ϊmmodpe,,penh,e1,mi{0,1,,p-1}.hm=y֪

,תΪڵĶ,ΪĽΪp,pСʱ.㷨ʱ临ӶΪ
㷨nhӵĳǴָӶȵ,nhϴ(,ȡ160bit)ʱЧ,Բƹв,ԛԲɢеǸٵ.ΪܷԲߵĽ,һ౻ΪԲߡԲE/Fq(,q=pm)ڽ,,Menezes1993֤18,ڳԲE/Fq,E(Fq)ϵɢڸʶʽʱڹԼΪFqFqkϵɢ,k6,p3ʱ,k4,ӸϷ˳ԲϵͳĿԣҵ,Բ߼ʶͱ.SemaevҲҵһ಻ƵԲ,ף19ָ,ΪpKϵԲE/K,E(K)pȺеɢʱڹԼΪKļӷȺϵɢ,˵,ԴZpϵԲE/Zp,#E(Zp)=pE(Zp)еɢ⫙ʱڹԼΪZpļӷȺϵɢ,Ӷʱ(Բ߳Ϊ쳣(anomalous)).Щ˾,˾Ҳͱѧ(Ed Schaeferٶ֪ʵδ,ѧԴһ֪,1997ǰƶĸ׼δǵ.ԲƵĹ,Ӧᵽף20,ԲߵĽṹԸĽPllard-,Ӷһ.K=GF(2m)Ϊ2mԪ,KϵԲE/KϵGF(2e)֮(߳Ϊ)ף20иE(K)ɢĸĽPllard-ԭʼPllard-ʱ併ͱ,һδĽ㷨ʱ临ӶȵĽ,eСʱ,eȫԵӰҲɺ.
,ԲƵİȫԲɢѽ,Ϊ֤Ƶİȫ,ʹõĻĽӦȲС160bit,Բ߼쳣ԲĿǰ֪Ĳ˻Բߣ21.ʹӦ.
ۿԿ,ԲƵķ˶,ĽǵĿǰΪֹеӰĽ,ɴ⣺ȷʵǿ,,δܺõʶ,ܴĸ濴,Բƻһо.ʵ,1997,ԲƼ䰲ȫԷѧҼļע,γоȵ,йظ,ѧУ(RoyalHollowayColleg)ҵ֯(Certicom)(Ұȫ)ڴӸ̽Բ뼼,ҲˡƱ׼ߵļȤ.IEEE׼P136/D8(199810°)P1363/D9(19992°)Բ˽ǰΪ꾡,Ϊص֮һ.ANSI(ұ׼)ȨĽҵ׼ίԱX9ƶԲǩ׼X9.62ԿЭ̼ݱ׼X9.63,RSAʵҲ,ҲѿʼƶΪPKCS#13Բ׼,ñ׼ںϡƽ׼,PKCS׼л,ԲʵֵϸĹ涨.ѧ,199711Waerlooѧ֯һרŵ,оԲɢ,ڶѧҼѧӦ萲μ.ֱĿǰ,δȡʵԽչ,ʱԽ,ԽʹԲƵǿ.ѧҶƵǿȼӦǰԽԽֹ̬.RSAһ,ֻо˳ʱķ,ԲƲŻΪ.
5Բߵѡȡ
ҪԲ,ҪѡȡһʵıKKѡȡһʵԲE/K.ʵù۵㿴,Kѡ:ZpΪ2GF(2n).ӽʵ,ΪЧһЩ(ǵԤ벻ͬ).ԲߵѡȡҪǰȫԡʵԵ,Щ(,ElGamalǩơDSSǩ)Ҫ֪EĽ#E(K)#E(K)һ,һЩ˻(,Diffie-HellmanԿЭ顢ElGamal)䲻Ҫ֪E(K)Ľ,ΪPohlig-Hellman,豣֤#E(K)д.ԲߵѡȡֿԿǵķ.
(1)ѡȡ
ѡȡһԲE/K,#E(K)ֱΪֹ.ַ,ӰȫԽǶһķ.
Hasseһ#E(Fq):#E(Fq)=q+1-t,Ҫ#E(Fq)ȴ,Schoofⷽ˿Եĳɹ22.ϵFrobenius̬ͬ

Ϊ2-t+q=0,,lһС,ElΪl-Ť㹹ɵȺ,ͨEl,ttt modleСl_tmodlSchoof㷨Ļ뷨ǶһϵСl=3,5,7,L,,L,t mol,Ӷйʣඨõt,õ#E(Fq).
Schoof㷨ʱ临ӶOlog92q,ǸЧ㷨ʵȴʵ,ָ#E(Fq)һŬ,˼עԴԺ,ΧƼtmodlдɹ23,24,ڷʵ˽ϴչLercierMorainDEC Alpha3000/500ϼGF2300157)ԲߵĽ,ҲDEC Alpha Workstation250(266MHz)ϼF2300ԲߵĽ,ʱǴԼ40ӣĿǰ¼DEC Alpha Workstaion 2501035СʱF21301һԲߵĽ.ڽкӵԲԽ(F2196Լ2),ø÷ԲԴ,ر,к2ϵԲ,ȫ.
(2)׵Բ
AtkinMorainġElliptic Curves and Primality Proving4ʹǿ˻ҪԲߵһ;,ø˹ZpϾضԲߵ˼뼰˹㷺ע,ƪۡĽ2528ݣ׼IEEEP1363(   ݸ,1999.2)Ҳ˸òΪԲߵķ֮һ.˼,ף28ʵ׼кӵԲߵĹ췽.
-Dһбʽ,HD(X)ʾDHilbertʽ,pһ,x,y4p=x2+Dy2,HD(X)ģpĸj0,شj-Ϊj0ԲE/Zp
4#E(Zp)=(x-2)2+Dy2(3)
ȻԲ߲j-Ψһȷ,ͨj-j0ҳʽ(3)Բ׵.ʵ,j-Ϊj0Բǡ2Ƶͬ.
ף28ĹZp(p>3)ϵԲߵķļ.
(1)ȡбʽ-D,ʹС(,D=19)
(2)ʵΧ,ѡȡx,y,4q=(x2+Dy2),q,ֱqΪֹ
(3)4p=(x+2)2+Dy2,p,pص2,ֱpΪ
(4)HD(X)0modpĸj0(-DС,÷׽)
(5)j-Ϊj0ԲEy2=x3+ax+b,ȡcZ*p,E䣺y2=x3+c2ax+c3bȡһP0,жqP=0ֱ.
֤,㷨ʱE伴ΪZpqԲߣ28.
㷨нϸߵЧ,ڴZpϹԲ.
ܵMOVԼʾ,Ƕø˹ԲߵķĳЩ,p״ơ-DǷaӰƵİȫԹ`ҶԴŹ㷺ע,ĿǰΪֹ,ûκ˵ߴգ.
6ᡡ
ۿԿ,Բܵѧ硢̡š׼֯θ,Ѱճоȵ㲢ʼʵãȻǵʶӲ,,пĳЩΪִƵ,ԲƷΪ˽,밲ȫصԲɢӦܵĹע,,Բ߽׵ļ㷽ʵּнϴչ,ԾСĸ˵ԲߵҲõΪȷԵĽ.
*õҡƻĿ863-306-ZT06-01-4ɽʡȻѧĿZ94G0108.
߼飺,,19604,ʿ,ҪоΪݰȫѧ.
,,19632,,ʿʦ,ҪоΪ簲ȫѧ.
ߵλɽѧѧϵϡ250100
ˡɽѧϢȫоϡ250100
ο
1Lenstra H W. Factoring integers with elliptic curves. Annals o f Mathematics, 1987, 126: 649673
2Montgomery P. Speeding the pollard and elliptic curve methods of facto rization. Mathematics of Computation, 1987, 48: 243264
3Montgomery P. A FFT extension of the elliptic curve method of factoriz ation. Ph D dissertation, UCLA,Los Angeles, 1992
4Atkin A, Morain F. Ellipic curvs and primality proving Mathemtics of Computtion, 1993, 61(203): 2968
5Goldwasser S, Kilian J. Almost all primes can be quickly certified. In : Proc of the 18th Annual ACM Symposium on Theory of Computing, 1986. 316329
6Pomerance C. Very short primality proofs. Mathematics of Computation, 1987, 48: 315322
7Miller V. Uses of elliptic curves in cryptography. In: Williams H C ed s. Advances in Cry ptologyCRYPTO'85 Proceedings, LNCS 218. Berlin: Springer-Verlag, 1986. 417 426
8Koblitz N. Elliptic curve ryptosytems. Mthematics o Computatio, 1987, 48: 203209
9Robshaw M, Yin Y. Elliptic Curve Cryptosystems. Mathematics of Computation, 1987, 48: 203209
10Silverman J. The Arithmeic f Elipic Curvs.New York Springer-Verlag, 1986
11Menees A. Elipic urv Public Key Cryptosystems. Boston: Kluwr Acad emicPubishers, 1993
12Demytko N.A new elloptic curve based analogue of RSA. IN: Helleseth ed. Advances in CryptologyEurcocrpt'93 Proceedings, LNCS 765. Berlin: Springs-Verlag, 1994. 4049
13Koyama K, Maurer U M Okmoto T, Vantone S A. New publi-key scheme based on ellitic curves over the rin Zn. In: Feigenbaum J eds. Advances in Cry ptologyCRYPTO'91 Proceedings, LNCS 576. Berlin: Springer-Verlag, 1992. 4049
14Coppersmith D, Odlyzko A M, Schroeppel R. Disret loarithmsin GF(p). Algorithmica, 1986. 1: 115
15Lenstra A K, Lenstra H W. The Develpment of the Number Field Sieve. Be rlin: Springer-Verlag, 1993
16Pollard J M. Monte Carlo methods for index computation(mod p). Mathemat ics of Computation, 1978, 32 918924
17Pohlig S C, Hllman M E. An imprved algorithm for computing logarithms over GF(p) and its cryptographic signifcance. IEEE Trans Inform Theory, 1978, 2 4: 106110
18Menezes A, Okamoto T, Vanstone S A. Reducing elliptic curves logarithms to logarithms in a finite field. IEEETIT, 1993, 39(5): 16391646
19Semaev I A. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Mathematics of Computation, 199 8, 67(221): 353356
20Wiener M J, Zuccherato R J. Faster attacks on elliptic curve cryptosyst ems. In: Tavares S, Meijer H eds. Selected Areas in CryptographySAC'98. Berl in: Springer-Verlag, 1998
21IEEE P1363/D9 (Draft Version 9). Standard specification for public key cryptography. 1999. http://grouper.ieee.org/groups/1363
22Schoof R. Elliptic curves over finite field and the computation of squa re roots mod p. Mathematics of Computation, 1985, 44: 483494
23Lercier R, Morain F. Counting the number of points on elliptic curves o ver finite fields: strategies and performances. In: Guillou L C, Quisquater J J eds. Advances in CryptologyEUROCRYPT'95 Proceedings, LNCS 921, 1995. 7994
24Lercier R. Finding good random elliptic curves for cryptosystems define d over. In: Fumy W ed. Advances in CryptologyEUROCRYPT97 Proceedings, LNCS 1233. Berlin: Springer-Verlag, 1997. 379392
25Morain F. Building cyclic elliptic curves modulo large primes. In: Davi es D W ed. Advances in CryptologyEUROCRYPT'91 Proceedings, LNCS 547. Berlin: Springer-Verlag, 1991.328336
26Miyaji A. Elliptic curves over Fp suitable for cryptosystems. In: Seber ry J,Zheng Y eds. Advances in CryptologyAUSCRYPT'92 Proceedings, LNCS 718. B erlin: Springer-Verlag, 1993.479491
27Lay G J, Zimmer H G. Constructing elliptic curves with given group orde r overlarge finite fields. In: Adleman L M, Huang M D eds. Algorithmic Number T heory Proceedings, LNCS 877. Berlin: Springer-Verlag, 1994. 250263
28,.ڽƵԲߵĽ췽ʵ.ѧ 199821121059-1065
Xu Qiuliang,Li Daxing. Constructing elliptic curves suitable for cryp tosystemsMethods and implementation. Chinese Journal of Computers(in Chinese), 1998, 21(12): 10591065
ԭյڣ1998-12-29޸ĸյڣ1999-08-08.
