资源描述：
《GF (2m )上椭圆曲线标量乘快速算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ComputerScienceandApplication计算机科学与应用,2014,4,76-84PublishedOnlineApril2014inHans.http://www.hanspub.org/journal/csahttp://dx.doi.org/10.12677/csa.2014.44013ResearchonFastAlgorithmsforScalarMultiplicationofEllipticCurveoverGF(2m)LiSun,MengZhouSchoolofMathematicsandSystemSc
2、ience,LMIB,BeihangUniversity,BeijingEmail:sunlibuaa@126.com,zm1613@sina.comthththReceived:Mar.6,2014;revised:Apr.4,2014;accepted:Apr.18,2014Copyright©2014byauthorsandHansPublishersInc.ThisworkislicensedundertheCreativeCommonsAttributionInternationalLicense(CCBY).http://cr
3、eativecommons.org/licenses/by/4.0/AbstractEllipticcurvecryptographyfindsnumerousapplicationsbecauseofitsexcellentanduniqueproperties.ThispaperfocusedonthescalarmultiplicationofEllipticcurve.Weproposedthere-kmcursionformulatocompute3PoverGF(2)basedontheideaoftradinginversi
4、onsformul-tiplications,whichreducedtheinversiontoonlyonce.Atthesametime,thispaperalsogaveanac-celeratedalgorithmforcomputing3PQ+,whichsavedtwoinversionscomparedtocomputingitdirectly.Theresultsuggeststhattheproposedalgorithmsaremoreefficientthanthenormalal-gorithmswhenther
5、atiosaremorethan7.4and5.9respectively.KeywordsEllipticCurve,ScalarMultiplication,AcceleratedAlgorithm,InversionGF(2m)上椭圆曲线标量乘快速算法研究孙俐，周梦北京航空航天大学数学与系统科学学院LMIB，北京Email:sunlibuaa@126.com,zm1613@sina.com收稿日期：2014年3月6日；修回日期：2014年4月4日；录用日期：2014年4月18日76mGF(2)上椭圆曲线标量乘快速算法研究摘要椭圆曲线
6、密码自提出以来便因其优良的性质而得到了广泛的应用。本文针对椭圆曲线上关键的标量乘运mk算，根据将耗时较多的求逆转换为乘法的思想，推导出了GF(2)上计算3P的递推公式，将求逆次数减少到一次。同时提出了计算3PQ+的加速算法，比直接计算节省了2次求逆。分析表明，在逆乘率分别大于7.4和5.9时，改进算法的效率优于逐次计算。关键词椭圆曲线，标量乘，加速算法，求逆1.引言1985年，椭圆曲线密码(ECC)由Miller[1]和Koblitz[2]等人分别独立提出。该密码体制一经提出便得到众多密码学研究专家的关注。ECC基于有限域中的离散对数难解
7、问题(DL)，这使得在同样的安全性能下，ECC需要的密钥长度比RSA要短很多。随着椭圆曲线密码的发展，快速实现成为学着们研究的重点。椭圆曲线的运算分为上层算法和底层算法，其中，上层加速算法是针对椭圆曲线上点的运算，即群的计算；底层算法是针对底层有限域上为实现点之间的运算而做的乘法、求逆、平方等运算。很明显，为了达到更好的计算效率，需要结合上层域以及底层域计算展开改进。这也是椭圆曲线加速算法的一个研究趋势。在椭圆曲线密码体制中，核心运算就是椭圆曲线的标量乘kP的运算，它是椭圆曲线密码体制快速实现的关键。在标量乘运算中求逆的耗时是乘法的8倍[
8、3]，用适量的乘法代替求逆可以明显的提高计算的m效率。利用此思想，Guajardo等人[4]提出了GF(2)上直接计算4P、8P、16P的算法。Sakai等人[5]k在Guajardo的基础上
