资源描述：
《用替换标量加速椭圆曲线点乘的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、学术研究AcademicResearch本栏目由保密通信賣点实竣室协办用替换标量加速椭圆曲线点乘的研究王悦，邱卫东(上海交通大学信息安全工程学院，上海200240)［摘要］在优化有限域上椭圆曲线点乘的研究中.寻找标凰的等价衣示形式以减少点加和倍点运算的数址一直是关注的热点。因为点乘运算在一个n阶冇限群中•利用冇限群的性质,QMP=(—k)(-P)。对于椭圆曲线和容易计算，尸是计算点乘的标址比可以替换为—忍因此，计算点乘时可通过选取代价更小的标凰来减少计算俭。理论和实验研究表明，替换标员可在微小的开销F便通常的虫复倍加点算法的点加次数平均减少约5%0
2、［关键词］椭圆曲线密码学；加速点乘；替换标忙［中图分类号］TN918.1［文献标识码］A［文章编号］1009-8054(2012)02-078-02AcceleratingEllipticCurvePointMultiplicationUsingAlternativeScalarWANGYue,QIUWei-dong(SchoolofInformationSecurityandEngineering«ShanghaiJiaotong【JriiversitytShanghai200240>China)［Abstract］Intheaccelerati
3、onofellipticcurvepointmultiplication9significantresearchisfocusedonfindingequivalentandefficientrepresentationofthescalar.Becausepointmultiplicationoccurswithinafinitegroupofordern,andbasedonthisproperty,Q-kP-{n-k}(-P)twheren_kand-Pcouldbeeasilycomputed・Thustwoalternativescala
4、rskandn-kareleft・Bychoosingthescalarthatinvolveslesscomputation,currentmethodsofpointmultiplicationcouldbefurtheraccelerated・Thetheoryandpracticeshowsthatbyusingalternativescalar,thenumberofpointadditionsinrepeateddouble-and-addalgorithmcouldhereducedhy5%onaverage・［Keywords］el
5、lipticcurvecryptography;pointmultiplicationacceleration;alternativescalar0引言点乘是椭圆曲线密码体制中的基本运算.涉及椭圆曲线密钥交换、加密、签名等关键算法。因为其计算速度直接关系到椭圆曲线密码的性能，所以快速计算点乘一直是该领域的研究热点。点乘的优化途径有两个方面：一方面是提高大整数有限域运算的速度.另一方面是利用标量斤的等效形式减少点加和倍点运算。其中，有限域运算的快速实现不仅是椭圆曲线密码的需求山，而且也是众多密码算法的关键技术。基于标量k的算法除了基本的重复倍加点算法
6、之外,还有非相邻表示型（Non-AdjacentForm,NAF）、窗口法、ccmb算法、加法链等。替换标量的操作可补充上述基于标量的优化算法，进一步减少标量编码中非零位的个数（即汉明重虽），加速点乘的计算。收稿日期：2011-10-26作者简介：王悦，1986年生，男，硕士研究生，研究方向：应用密码学、系统安全；邱卫东，1973年生，男，教授，研究方向：密码算法、安全协议、取证技术。"基金项目：科研院所社会公益研究专项资助项目（编号：GY0905）o1点乘与替换标量设P是素数，〃是正整数.q=p”、匚是特征为g的有限域。在竹上的椭圆曲线是指满足
7、方程声2#尹+6尸xa2x2+a4x+a6,竹，x,yE.①所有的点（x,_y）与无穷远点O的并集，记为E（Fq）。定义疋（巧）上的点的加法运算⑴之后，E（FJ对于该加法运算构成一个有限交换群。在椭圆曲线密码体制中，通信双方要先协商确定曲线参数门参数集合包括有限域的特征g,曲线的各项系数①，曲线上的基点G,基点G的阶皿素数），余因子h（nh即为椭圆曲线上所有点的个数）o给定E上一点P=（x,刃，P的阶为”，点乘即计算Q=kP、0,根据有限群的性质，Q^kP^（-k）（-P）^（n-k）（-P）=kP,如果称&为原标量,k=
8、n-k为替换标fit,那么求替换标fit"和点P=（x,均只需一次整数减法（若基域为二进制扩域，则计算P=（x,x+y需一
