二进制域上快速平方运算算法的设计与实现.pdf

《二进制域上快速平方运算算法的设计与实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第28卷第2期青岛大学学报(自然科学版)Vo1．28NO．22015年5月JOURNALOFQINGDAOUNIVERSITY(NaturalScienceEdition)May2015文章编号：1006—1037(2015)02—0039一O5doi：10．3969／j．issn．1006—1037．2O15．05．09二进制域上快速平方运算算法的设计与实现段绍霞，高龙飞，程相国，于佳(青岛大学信息工程学院，青岛266071)摘要：研究了二进制域中的快速平方运算，针对字长为64bit的要求，基于查表思想提出了计算二进制域中平方运算的快速实现算法。该算

2、法运算效率高，在隔项插零算法基础上提高了80％，使定义在该域上的椭圆曲线相关运算算法的效率得到显著提高。关键词：有限域；二进制域；平方运算；隔项插零算法中图分类号：TP309文献标志码：ADiffie和HellmanE提出公钥密码思想后，公钥密码体制因其良好的性质得到广泛的应用和发展。目前最为常用的公钥密码是RSA(Rivest—Shamir-AdlemanPublicKeyCryptography)]，但RSA的安全性基于的数学困难问题是大整数分解。随着计算机运算能力不断增强，迫使不断增加RSA的密钥长度以保证其达到所需的安全强度。随着安全性要求的提

3、高，椭圆曲线密码系统(EllipticCurveCryptographySystem，ECC)[33得到广泛应用。ECC的快速实现取决于椭圆曲线上点的算术运算的实现效率，然而椭圆曲线上点的运算基于有限域上的算术运算，因此，提高ECC底层有限域上的运算效率是关键所在。在ECC中，有限域上的平方运算是极其重要的算术运算。椭圆曲线上的点加运算和倍点运算都用到了有限域上的平方运算。而在ECC的标量乘运算中，只使用曲线上的点加运算和倍点运算。因此，提高二进制域上的平方运算效率是研究的重点。wu_4研究了标准基下的平方运算和Montgomeryl_5平方运算，但其

4、所研究的既约多项式为不可约三项式，当既约多项式为更为复杂的多项式时，该方法不再适用。OPENSSLl_6]对二进制扩域上的平方运算进行了优化和实现，但频繁使用了大幅度的“移位”和“或”运算。AtharMahboob¨7提出了求二进制扩域上的平方运算多项式隔项插零的方法，但该方法每次只能处理一个bit位。文献E8]中讨论了使用预计算的方法计算二进制扩域上的平方运算，但只针对机器字长为32位的情况，并没有对机器字长为64位的情况进行讨论和研究。为此，针对机器字长为64位的情况，本文提出了使用预计算的方法计算二进制域上的平方运算，并对该平方运算进行了实现和分

5、析，结果表明该方法在效率上高于以往算法。通过设计实现的算法，能大幅提高定义在该域上的椭圆曲线的实现效率。1基础知识1．1有限域定义I设rF，+，·]是一个代数系统，其中+和·是F上的两个二元运算，如果满足：1)是一个加法交换群，单位元用0表示；2)是一个域。若域F中的元素的个数(称为域F的阶)是有限的，则称域F为有限域。收稿日期：2015—03—02基金项目：华为科技基金(批准号

6、：YB2013120027，YBCB2012071)资助；山东省自然科学基金(批准号：ZR2010FQ019)资助。通讯作者：于佳，男，博士，硕士研究生导师，研究方向：信息安全。E—mail：qduyujia@163．corn40青岛大学学报(自然科学版)第28卷1．2二进制域定义2阶为2的有限域被称为二进制域或特征为2的有限域。设厂(z)是一个m次的既约多项式，对于任意一个二进制多项式a(z)，a(z)modf(x)表示具有唯一的次数低于的余式r(．z)，r()利用口(z)和厂(z)的长除法获得，称为．厂(z)的模化约。构造二进制域GF(2)的一种有

7、效方法是使用多项式基表示法，即所有的多项式模m次既约多项式厂()后的余式所组成的集合便可构成有限域GF(2)。因此，GF(2)中的元素都是次数不超过一1的二进制多项式GF(2)一{n一1z一+口一2z一+⋯+2z+1-z+no：盘∈{0，1})域中元素的加法是普通的多项式的加法，系数使用的是模2加法；域中元素的乘法需模既约多项式()。2二进制域上的平方运算令f(x)是次数为的二进制既约多项式，并将其写成．厂(z)一+r()的形式。二进制域GF(2)中的元素都可以表示成最高次数不超过m—l的二进制多项式，域中的元素a用多项式形式表示为n()：==n一1一

8、+a一z一。+⋯+a。。-4-口+a。，口∈(0，1)，元素n也可用长度为的二进制向量表示成n