Edwards曲线安全快速标量乘法运算算法——EDSM

《Edwards曲线安全快速标量乘法运算算法——EDSM》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第10期张宝华等：Edwards曲线安全快速标量乘法运算算法——EDSM·81·Edwards曲线安全快速标量乘法运算算法——EDSM张宝华1，殷新春2，张海灵2（1.复旦大学计算机科学技术学院，上海200433；2.扬州大学信息工程学院，江苏扬州225009）摘要：对Edwards曲线上标量乘法的安全及快速算法进行研究，首先提出新的倍点及点加公式，分析表明，其运算效率优于Edwards曲线上的已有公式；其次给出一种新的安全快速的标量乘法运算算法——EDSM算法；最后将EDSM算法与改进的Montgomery算法以及已有的安全快速算

2、法在安全性和效率上进行比较，结果表明，EDSM算法在运算效率方面和安全性方面均有显著的提高。关键词：椭圆曲线；Edwards曲线；标量乘法；旁门攻击；Montgomery方法中图分类号：TP309.7文献标识码：A文章编号：1000-436X(2008)10-0076-06EDSM:secureandefficientscalarmultiplicationalgorithmonEdwardscurvesZHANGBao-hua1,YINXin-chun2,ZHANGHai-ling2(1.SchoolofComputerScien

3、ce,FudanUniversity,Shanghai200433,China;2.InstituteofInformationTechnology,YangzhouUniversity,Yangzhou225009,China)Abstract:InvestigatethesecureandefficientalgorithmforscalarmultiplicationonEdwardscurves.First,severalnewadditionanddoublingformulaswereproposed.Analysiss

4、howsthatournewformulasaremoreefficientthanexistedformulas.Thenanewscalarmultiplicationalgorithmwasforwarded,calledEDSMalgorithm.Finally,ourEDSMalgorithmwiththeimprovedMontgomerymethodandotherexistedsecureandefficientalgorithmswerecompared.Experimentalresultsshowthatour

5、EDSM(scalarmultiplicationonEdwardscurve)algorithmmakegreatimprovementsinaspectsofefficiencyandsecurity.Keywords:ellipticcurve;Edwardscurve;scalarmultiplication;side-channelattacks;Montgomerymethod第10期张宝华等：Edwards曲线安全快速标量乘法运算算法——EDSM·81·1引言收稿日期：2008-06-02；修回日期：2008-10-0

6、6基金项目：国家自然科学基金资助项目（90607005）；国家高技术研究发展计划（“863”计划）基金资助项目（2007AA012448）；江苏省六大人才高峰项目（06-E-025）FoundationItems:TheNationalNaturalScienceFoundationofChina(90607005);TheNationalHighTechnologyResearchandDevelopmentofChina(863Program)(2007AA012448);TheSixScientificFieldsSummit

7、ofJiangsuProvince(06-E-025)标量乘法运算是椭圆曲线密码体制的关键运算，其速度及安全性直接影响到椭圆曲线密码体制的有效实现。许多年来，人们致力于研究椭圆曲线的各种形式，寻求具有快速、安全特点的标量乘法运算。1985年，Miller[1]给出了椭圆曲线的Jacobian形式：Y2=X3+a4XZ2+a6Z6，其上的点(X:Y:Z)对应于椭圆曲线一般形式y2=x3+ax+b上的点(x/z2,y/z3)，该曲线上的标量乘法运算若采用NAF[2]算法，平均每比特需要的计算量是3.33M+9.33S+1D，其中，M表示

8、乘法运算，S表示平方运算，D表示乘以a4的运算。考虑安全性，假设在能够抵抗简单能量分析(SPA,simplepower第10期张宝华等：Edwards曲线安全快速标量乘法运算算法——EDSM·81·analysis)攻击的前提下，若采