椭圆曲线密码系统的硬件实现和安全性分析

上海交通大学硕士学位论文椭圆曲线密码系统的硬件实现和安全性分析姓名：陶靛生申请学位级别：硕士专业：通信与信息系统指导教师：陈恭亮;方龙森2005091012005091823,,FPGAROM/CAMVerilogHDLModelSim4TheHardwareImplementationandSecurityAnalysisinEllipticCurveCryptosystemAbstractManyindustriesinourcountryhaverealizednetworkingandinformationalizationwiththecontinuousdevelopingofinternetandelectronictransaction.Thenetworkandinformationsystemareplayingmoreandmoreimportantroleindailyoperationingovernment,enterprisesandorganizations.Theimprovementininformationalizationbringsgreatopportunitytothedevelopmentofsociety,itisalsoaflintychallenge.Thesecurityofinformationcommunicationisdrawingmoreandmorepublicconcerns.Itisbecomingtheurgentdemandtorealizesecurecommunicationininsecurecommunicationchannels.Tomeetthisdemand,manyencryptionalgorithmsandcommunicationprotocolshavebeendesigned.Fromtheviewpointoftechnology,thesesystemshavemoreorlessholeinsecurity,becausemostofthesealgorithmsandprotocolsaresymmetriccryptosystem.Withtheincrementoftheportfolioload,higherdemandinsecurityisrequired.Therefore,theellipticcurvecryptosystem,basedonpublic-keycryptography,appearsnow.ThispaperintroducesanimplementationofasmallellipticcurvecryptosysteminFPGA,basedadetailedanalysisonthetechnologyinpublic-keycryptography.Itgivesadetailedpresentationontheprincipleofencryption,decryptioninECC,andanalysistoitsarchitectureinhardwaresystemanditsimplementationprocedure.Thepaperalsoevaluatesthesimulationresultandsecurity.ItprovidesasimpleandpracticalmethodinROM/CAMtoimplementfunction,thusprovidesaneffectivesolutionfortheextensiveapplicationofECC.WiththedevelopmentofLargeScaleIntegratedCircuit,ProgrammableLogicDevices’havelargerandlagercapacity.And,thecontinuousdevelopmentofsoftwaretechnologyinPLDprovidesnecessarycondition5fortheimplementationofcryptosystem.TheimplementationforalgorithmsinthispaperisdescribedinVerilogHDL,andsimulatedinModelSimforfunctionality.Theresultisshowntheimplementationisveryflexibleanduniversal.Keyword:Internet,EncryptionAlgorithmECC,PLD8-–91.11918•1949•1967•2070NBSDataEncryptionStandard1975317NBSFederalRegister19761123DESDES1998197611DiffeHellman(Newdirectionsincryptography)1977Rivest,ShamirAdlemanRSA1985KoblitzMiller101.21.2.11-11-1Fig.1-1Encryptionanddecryption11RSANZN26C≡P+3(mod26)PCX→AY→BM→P1970OneTimePadVernamVernam19197221,310,719Vernam2612ONETIMEPADTBFRGFARFMIPKLPSFHGQO+Tmod26=IN+Bmod26=PE+Fmod26=KVernam(DES)IBM197746-25613DES••nn(n-1)/2•1.2.21976DiffieHellman1977RSA14.,,.NPNPNP•RSARabin-William•Merkle-HellmanKnapsack•ElGamal•EllipticCurvesCryptosystemECC2.115•IFP•DLP•ECDLPRSARSA2.321985MillerKoblitz1.3(ECC)PCFFEECC2GF(p)p•16•••ECCIEEEANSIISOIETFATMECCECC1.4ECCwizPLDPLDECCwiz172.1Z={…-3-2-10123…}a,b∈Za≠0c∈Zb=acababbaa|bc∈Zb=acaba³ba|aa|bb|ca|ca|ba|cx,y∈Za|(bx+cy)a|b,b|aa=±b(Euclid)2.12.1()a,b∈Zb≥1qra=bq+r,0≤rb2-12.1(2-1)qabrab2.2xxx[x]18[x]≤x[x]+1[3.14]=3[-3.14]=-4[3]=3[-3]=-32.1q=[ba]r=a–b[ba]2.3p≠0±1±1±ppp()pp≠0±1p-p2.2a1,a2,…,ana1,a2,…,an(a1,a2,…,an)gcd(a1,a2,…,an)(a1,a2,…,an)=1a1,a2,…,an2.3b(0,b)=b2.4a,b,ca=bq+cq(a,b)=(b,c)2.5gcd(a1,a2,…,an)=gcd(gcd(a1,a2,…,an-1),an)2.6pp|abp|ap|b2-1Algorithm2-1ExtensiveEuclidDivision19Input:TwopositiveintegersabOutput:Apositiveintegerrn=(a,b)r0=a,r1=br0=r1q1+r2,0≤r2r1r1=r2q2+r3,0≤r3r2……rn-2=rn-1qn-1+rn,0≤rnrn-1rn-1=rnqn+rn+1,rn+1=0returnrnnrn+1=00=rn+1rnrn-1…r2r1=bb2-12.72.7a,bgcd(a,b)=rnrn2.1[2-1]a=-1859b=1573(a,b)(-18591573)=(18591573)1859=1*1573+2861573=5*286+143286=2*1432.7(-18591573)=1432.4()a1,a2,…,annmnmna1,a2,…,an[a1,a2,…,an]lcm(a1,a2,…,an)2.8a,b[a,b]=ab202.9a,b(1)a|mb|m[a,b]|m(2)[a,b]*(a,b)=ab2.10a1,a2,…,anna1|m,a2|m,…,an|m[a1,a2,…,an]|m2.11()n1n=p1…psp1≤…≤pspin=q1…qtq1≤…≤qtqis=tqi=pi1≤i≤s2.22.5()mabmm|(a–b)a≡b(modm)m29≡1(mod7)7|(29–1)abm2.12abm2.12aba≡b(modm)ka=b+kma≡b(modm)m|(a–b)ka–b=kma=b+km21ka=b+kma–b=kmm|(a–b)a≡b(modm)2.132.13m(1)()aa≡a(modm)(2)()a≡b(modm)b≡a(modm)(3)()a≡b(modm)b≡c(modm)a≡c(modm)aKa={c|c∈Za≡c(modm)}Kamr0,r1,…,rn-1mr0,r1,…,rn-1mm2.6()mm01…m-1m)(mj(Euler)m=100910101379)10(j=42.7()mm2.8()mmmmm)(mj137910)10(j=4m=p12…p-1p)(pj=p-1222.14mn)(mnj=)(mj)(nj)77(j=)7(j)11(j=6*10=602.15ma(a,m)=1a’aa’≡1(modm)mama’a’ama’=a-1(modm)2.3[2-2]m=7a=2(2,7)=1,)7(j=671234562•1≡22•2≡42•3≡62•4≡12•5≡32•6≡5(mod7)(2•1)(2•2)(2•3)(2•4)(2•5)(2•6)≡1•2•3•4•5•6(mod7)26•1•2•3•4•5•6≡1•2•3•4•5•6(mod7)26≡1(mod7)2.152.15(Euler)m1a(a,m)=1)(mod1)(mam≡j[2-3]m=11a=2(2,11)=1,)11(j=10210≡1(mod11)232.16(Fermat)pa)(modpaap≡2.4x=a1modm1…x=akmodmkaimi∈Z1≤i≤rgcd(mi,mj)=1i≠j2.17()m1,…,mkkb1,…,bk,x=b1modm1…x=bkmodmkxi=xi-1+Ni-1(N’i-1(bi-xi-1)(modmi))(modm1…mi)i=2,…,k242.5y2≡a(modp)2.9mx2≡a(modm)(a,m)=1am()am()14-141247-1357-11248913151735671011121417mp(a,p)=12.18()p(a,p)=1x2≡a(modp)(a,p)=1(2-2)(1)apap21-≡1(modp)(2)apap21-≡-1(modp)ap(2-2)2.19p(p-1)/22.10p(Legendre)1ap)(pa=-1ap0p|a252.182.202.20()p(a,p)=121)(-=papa(modp)2.20(1)1)(1=p(2)21)1()(1--=-pp2.212.21(1))()(pappa=+(2)))(()(pbpapab=(3)(a,p)=11)(2=papaap(Gauss)2.1(Gauss)p(a,p)=1akk=1,…,(p-1)/2pp/2mmpa)1()(-=(Gauss)2.22(Gauss)pq)()1()(2121qppqqp---=26[2-4]x2≡137(mod227)13727))(()()(2275*3*22271227902271372--==))((22