超椭圆曲线上快速标量乘算法分析

《超椭圆曲线上快速标量乘算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、杭州电子科技大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。申请学位论文与资料若有不实之处，本人承担一切相关责任。论文作者签名：日期：年月日学位论文使用授权说明本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大

2、学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。（保密论文在解密后遵守此规定）论文作者签名：日期：年月日指导教师签名：日期：年月日杭州电子科技大学硕士学位论文摘要超椭圆曲线是一类特殊的代数曲线，一般可以看成是椭圆曲线的推广。超椭圆曲线应用于公钥密码体制中，相比于其它公钥密码体制，具有诸多优势。例如，与椭圆曲线密码体制相比，在相同的安全水平下，它所用的基域更小，操作数更短；在相同的定义域上，亏格越大，可供选择的曲线越多等。因此，超椭圆曲线密码体制的提出，为构建安全的密码系统提供了一种很好的选择，因而也得到

3、许多关注和研究。但是，超椭圆曲线密码体制所基于的离散对数问题，是建立在一个称为Jacobian群的交换群上的。超椭圆曲线Jacobian群的结构比椭圆曲线有理点群的结构更为复杂，致使超椭圆曲线密码体制的实现速度比较慢，目前该体制亦尚未得到广泛应用。Jacobian群上的除子标量乘，是超椭圆曲线密码体制实现中最重要同时也最耗时的一环。因此，加快除子标量乘运算以提高超椭圆曲线密码体制的实现速度，对于该密码体制的实用化具有重要意义。本文主要对偶特征域上的超椭圆曲线进行了研究。主要研究的内容及成果包括以下几个方面：（1）第1章首先介绍了超椭圆曲线密码体制的研究现状以及亟待解决的相关问题，然后重点

4、归纳总结了现有的、加速除子标量乘的方法，主要包括：优化Jacobian群基本运算公式；用除子二分算法代替倍加算法；使用退化除子的加法与倍加公式；利用除子加法和倍加公式的并行算法；通过对标量进行适当编码来加速标量乘；研究特殊超椭圆曲线上的快速标量乘。（2）第3章推导出了偶特征域上，亏格为3的一般超椭圆曲线上，最常见情况下除子二分算法的操作过程。由一般曲线上的算法可以看出，该算法的运算量与曲线方程的参数密切273相关。于是，我们针对一类特殊的超椭圆曲线C:yhyxfxfxf，其中h0，e_003100给出了该曲线上除子二分算法的完整流程，以及各种除子情况下的确定性公式，并分析证明

5、了我们的二分算法公式确实比现有最优的倍加公式有效，在最常见除子情况下，二分算法公式比倍加公式节省了1次域上的乘法和2次域上的平方运算。（3）第4章给出了两个快速计算偶特征域上亏格为2的一类超椭圆曲线25rC:yyxaxb上除子标量乘的算法。利用单除子思想，我们找到了直接得到4D（rab为任意正整数，D为C曲线的Jacobian群上的任意除子）计算结果的公式化表示。然后通ab过把标量表示成四进制形式，得到两个计算该类曲线上除子标量乘的高效算法。与符号二元法相比，在不采用预计算技术的情况下，这两个算法分别节省了45.5%和53.1%的域运算量；若结合预计算技术，则分别可节省约56.1

6、%和53.2%的运算量。（4）第5章讨论了域2n上曲线Cab的特征多项式，其中a,b2n，n为任意正整数。我们首先介绍了C曲线的同构类，然后分别讨论各个同构类的特征多项式。最终得到了当n为abI杭州电子科技大学硕士学位论文奇数、n2mod4和n0mod4且Tra()0时，曲线C的特征多项式，并给出了n0mod44ab且Tra()0时，曲线的4种所有可能的特征多项式。利用所得到的特征多项式，我们也给出4了一种加速C曲线上除子标量乘的算法，它的效率比（符号）二进制算法大有提高。ab关键词：超椭圆曲线，Jacobian群，标量乘，二分算法，单除子，特征多项式II杭州电子科技大学

7、硕士学位论文ABSTRACTHyperellipticcurvesareaspecialclassofalgebraiccurves,andgenerallyregardedasgeneralizationsofellipticcurves.Public-keycryptographyapplyinghyperellipticcurveshasmanyadvantagescomparedtoothers.Forexample,com