NTRU公钥密码体制及安全性分析

NTRU公钥密码体制及安全性分析卓泽朋a,魏仕民b(a.,b.,235000):NTRU,p,q,NTRUNTRU,NTRU:NTRU;;;:TP309.7:A:1009-7961(2006)05-0065-03NTRUPublicKeyCryptosystemandItsAnalysisofSecurityZHUOZe-penga,WEIShi-minb(a.DepartmentofMathematics;b.DepartmentofComputerScience&Technique,HuaibeiCoalIndustryTeachersCollege,HuaibeiAnhui235000,China)Abstract:NTRUisanewpublickeycryptosystem.Theencryptionprocedureusesamixingsystembasedonpolynomialalgebraandreductionmodulotwopandq.Thedecryptionprocedureusesanun-mixingsystemwhosevaliditydependsonelementaryprobabilitytheory.ThesecurityoftheNTRUpublickeycryptosystemcomesfromtheinteractionofthepolynomialmixingsystemwiththeindependenceofreductionmodulopandqandthedifficultyinfindingextremelyshortvectors.Inthispaper,thebasicNTRU,sencryptionalgorithmisdescribedandthesecurityofNTRUisspeciallyanalyzed.Keywords:NTRU;encryption;decryption;polynomialring:2006-06-09;:2006-09-15:(60573026):(1978-),,,,,:0NTRU(NumberTheoryResearchUnit),1996BrownJeffreyHoffstein,JillPipherJosephH.Silverman,,,,,,NTRUIEEEP1363,WorkingGroupforStandardsinPublicKeyCryptographyNTRU,LLL(Lenstra-Lenstra-Lovasz),LLL,,,,1NTRU1.1NTRU,(N,p,q)N-1Lf,Lg,L,Lm,N,p,q,,gcd(p,q)=1,qpNTRUR=Z[x]/(xN-1),FR,F,F=155Vo.l15No.5200610JournalofHuaiyinInstituteofTechnologyOct.2006N-1i=0Fixi=[F0,F1,,FN-1]+,*,XN1,XN+1X,XN+1X2,F=[F0,F1,,FN-1]R,G=[G0,G1,,GN-1]R,F+G=N-1i=0(Fi+Gi),F*G=H=[H0,H1,,HN-1],Hk=ki=0FiGk-i+N-1i=k+1FiGN+k-i=i+j=k(modN)FiGjL(d1,d2)={FR:Fd11,d2-1,0},df,dg,dLf=L(df,df-1),Lg=L(dg,dg),L=L(d,d),Lm={mR:m[-(p-1)/2,(p-1)/2],p}1NTRU1NTRUNpqdfdgd107364151251673128612018503325621672551.2Bobfg,fLf,gLg,fpqFp,Fq,Fq*f1(modq)Fp*f1(modp),FpFq,fgcd(f(1),pq)=1,,f,BobhpFq*g(modq),h,f,,BobFp,(f,Fp)1.3AlicemLmBob,dL,,Bobhe*h+m(modq),AliceeBob1.4Bobe,faf*e(modq),a[-q/2,q/2],ba(modp),cFp*b(modp),cm1.5af*e(modq)f*(*h+m)(modq)(e*h+m(modq))f*(p*Fq*g+m)(modq)(hpFq*g(modq))p*f*Fq*g+f*m(modq)p*g+f*m(modq)(Fq*f1(modq))ap*g+f*m(modq)f,g,m,*g,f*mq,pq,(p*g+f*m)[-q/2,q/2],q,ba(modp)p*g+f*m(modp)f*m(modp)(p*g0(modp))cFp*b(modp)Fp*f*m(modp)m(modp)(Fp*f1(modp)),m[-(p-1)/2,(p-1)/2],c=m2NTRUN=11,p=3,q=32,df=4,dg=3,d=3,(1.1)df,dgf,g:f=(-1,1,1,0,-1,0,1,0,0,1,-1),g=(-1,0,1,1,0,1,0,0,-1,0,1)(1.2)Fp,h:Fp=(1,2,0,2,2,1,0,2,1,2,0),h=(24,7,10,12,20,8,17,13,20,13,16)Bobh,(f,Fp)AliceBob,d=(-1,0,1,1,0,1,0,-1,0,0,-1),Alicem=(1,0,1,1,-1,0,0,1,-1,0,-1),Alice(1.3)Bobhme=(0,17,22,0,16,8,25,14,28,11,20)BobAlicee,(1.4)f,Fpe:a=(-2,10,14,7,2,0,-9,-13,-6,3,-5),b=(1,1,-1,1,-1,0,0,-1,0,0,1),c=(1,0,1,1,-1,0,0,1,-1,0,-1)cAliceBobm3NTRUNTRU:,hf,g,hf1,g1f1*h662006g1(modq)NTRU:+*,,RSAECC,,,NTRURSAECC,2()2NTRURSAECCRSANTRUECC51216711310242631602048503282NTRU,,,NTRU,NTRUNO(N2),RSAO(N3),NTRURSA100NTRU,RSA300NTRU,,NTRU,,DC,,510-53NTRU,4NTRURSA3NTRU()()340642250226.55301169282.9277.51595402422852170,,NTRURSA4NTRURSA(/)(/)()NTRU1666622730.007947627240.0184730790.1528RSA512()10201250.26768()588420.591024()385231.28:4NTRU200MHzPentiumPro,runningLinux,RSA255MHzDigitalAlphaStation4NTRU4.1NTRUNSSNTRU,,,4.2,,,NTRU,NTRU:4.3NTRU,USIM5NTRU,NTRU,,,,RSA(下转第78页)5:NTRU67[2]C.K.Chen,M.H.Hon.ThemorphologyandmechanicalpropertiesofTi/Ni-P-SiChybridcoatings[J].SurfaceandCoatingsTechnology,2002,(155):214-220.[3],,,.Al2O3Ni-P[J].,2005,(2):265-269.[4]Q.Zhao,Y.Liu,H.Muller-Steinhagen,G.Liu.GradedNi-P-PTFEcoatingsandtheirpotentialapplications[J].SurfaceandCoatingsTechnology,2002,(155):279-284.[5],,,.(Ni-P)-PTFE[J].,2004,24(4):4-7.[6],.Ni-P-(RE)-SiO2[J].,2002,11(3):7-9.[7],,.ZrO2Ni-P[J].,1996,25(5):7-8.[8],.[J].,1999,28(6):7-9.[9],,,.TiO2[J].,2006,(2):3-6.[10],,,.[J].,2003,(6):68-74.[11],,,.[J].:,2006,(4):415-420.[12],,,.[J].:,2000,(6):75-78.[13],,,.TiO2[J].,1999,5(27):5-7.[14],,,.[J].,1995,(6):29-34.[15].Ni-P-TiO2[J].,2004,(10):61-63.(责任编辑:吴延东)(上接第67页):[1]JeffreyHoffstein,JillPigher,JosephHSilverman.NTRU:ARing-BasedPublicKeyCryptosystem[J].In:ProcofANTS,1423:267-288.[2]LenstraAK,LenstraHW,LovaszL.FactoringPolynomialswithIntegercoefficients[J].MathematischeAnnalen,1982,261:515-534.[3],.NTRU[J].,2004,30():308-309.[4],.NTRUJavaCard[J].,2005,(1):1-3.[5].[J].,2004,24(2):1-4.[6],.NTRU[J].,2003,140(8):99-100.[7].NTRU[J].,2002,11(1):67-68.[8].NTRUUSIM[J].,2005,35(10):54-56.[9],.NTRU[J].,2006,(1):111-113.(责任编辑:吴延东)782006