2013 椭圆曲线密码中标量乘算法的改进

《2013 椭圆曲线密码中标量乘算法的改进》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、页码计算机应用研究第28卷椭圆曲线密码中标量乘算法的改进王媛，霍李，杭小初，刘春慧中国白城兵器试验中心,吉林省白城市137001摘要:椭圆曲线密码体制的快速实现依赖于标量乘的有效计算。对使用1/2和3的幂的双重基链的表示方法进行了改进，并对算法进行了简单的分析。改进以后的算法运算量减少，举例说明，效率分别提高了5.3%和40.4%。关键词:椭圆曲线密码体制；双重基链；标量乘；半点；中图分类号:TP309.7　　　文献标志码:A文章编号：（作者可不填）doi:10.3969/j.issn.1001-3695(作者可不填)Improvemen

2、tofscalarmultiplicationalgorithminellipticcurvecryptographyWANGYuan,HUOLi,HANGXiao-chu,LIUChun-huiBaiChengOrdnanceTestCenterofChina,BaichengJinlin137001,ChinaAbstract:Thefastimplementationofellipticcurvecryptosystemreliesontheefficientcomputationofscalarmultiplication.The

3、representationmethodofdouble-basechainofscalarusingpowersof1/2and3wasimprovedandanalysed.Theresultsshowthatthemethodleadstolowercomplexityandillustrateswithexamplesthattheefficiencyareincreasedby5.3%and40.4%respectively.Keywords:ellipticcurvecryptosystem;double-basechain;

4、scalarmultiplication;pointhalving;页码计算机应用研究第28卷0引言1985年，Koblitz和Miller分别独立地提出了椭圆曲线密码体制（EllipticCurveCryptosystem,ECC），在椭圆曲线密码体制中，核心运算就是椭圆曲线的标量乘(nP)运算。本文对n的1/2和3的幂的双重基链的表示方法进行了改进，给出了一些算例，以实现新的算法，并比较了两种算法的运算量。1预备知识1.1定义[1]1.1.1有限域GF(2m)上的椭圆曲线有限域GF(2m)上的椭圆曲线是对于固定的a、b值，满足形如方程

5、的所有点(x,y)的集合，外加一个无穷远点O。其中a、b、x和y均在有限域GF(2m)上取值，这类椭圆曲线通常可用E2m(a,b)来表示。该椭圆曲线只有有限个点。域GF(2m)上的元素是m位的二进制串。1.1.2标量乘(k个P相加)P是椭圆曲线上一点，k是大于零的整数。1.2椭圆曲线的加法规则[1]满足等式的点和无穷远点O组成的一个加法交换群G。G的加法定义如下：(1)；(2)对所有的，；(3)如果，则，且，如果，则；(4)对所有的、，；(5)对所有的、和，；(6)如果；那么定义如下：若，那么若，那么1.3半点运算[2]半点运算分别由Kn

6、udsen[3]和Schroeppel[4]独立提出。它是二倍点的逆运算。令是定义在二进制数域上的椭圆曲线上的点，则（1）页码计算机应用研究第28卷（2）（3）半点运算恰恰相反，已知，求使得。它是这样计算的：由（1）式解出，由（2）式解出，最后由（3）式解出。即由解出，由解出，最后获得。1.1不同运算的运算量表1不同运算的运算量[2]运算运算量(1/2)P2M(1/2)P+Q1I+5M=11M3P1I+4S+7M=16.2M不同运算的运算量如表1所示，其中，[5]，用I表示求逆，用S表示平方，用M表示乘法。(1/2)P用H表示，(1/2)

7、P+Q用HA表示，3P用T表示。2已有算法计算kP，k是大于零的整数，P是椭圆曲线上一点。(1)k乘以2q，2q是接近数域p的一个值；(2)模数域p得到余数，即；(3)，其中，且，；(4)，其中，且，，，；例如：计算（数域）。当时，(1)；(2)；(3)；总的运算的运算量为。当时，(1)；(2)；(3)；总的运算的运算量为。3改进以后的算法计算kP，k是大于零的整数，P是椭圆曲线上一点。(1)k乘以2q，2q是接近数域p的一个值；(2)模数域p得到余数，即；(3)，其中，且；(4)，其中，且，当时，；当时,(1)；(2)；(3)；总的运算

8、的计算量为。当时，(1)；(2)；(3)；总的运算的计算量为。4运算量的比较比较两种算法的运算效率。通过文中描述，可以看到利用两种算法求314159P所需的运算量，具体数据如表2所示。表2不同