HECC中几个经典除子标量乘算法及实现

《HECC中几个经典除子标量乘算法及实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第28卷第6期杭州电子科技大学学报V0】．28．N0．62008年l2月J0umal0f}Iar咖DuIliv∞时Dec．008HECC中几个经典除子标量乘算法及实现陈小娥，游林2(1．海南师范大学数学系，海南海口571158；2．杭州电子科技大学通信工程学院，浙江杭州310ol8)摘要：给出了超椭圆曲线除子标量乘运算常用的除子加法和除子倍加算法并用Malple实现。在实现超椭圆曲线密码体制中起关键作用的运算是除子标量乘，利用M印le实现超椭圆曲线中几个经典的除子标量乘算法，并比较、分析他们的计算复杂

2、度。最后，用MapIe实现超椭圆曲线密码体制中加解密。关键词：超椭圆曲线密码体制；除子；标量乘中图分类号：rN393．o8文献标识码：A文章编号：10o1—9146(20o8)06—0o56一o3O引言提出了基于椭圆曲线上的公钥密码体制后，提出超椭圆曲线密码体制是椭圆曲线密码体制的自然推广，但不仅仅是一种简单的推广-3j。超椭圆曲线密码体制所基于的除子类群，又称Jacobian群，其结构与运算比有理点群复杂得多。但由于超椭圆曲线密码体制相对其他公钥密码体制拥有自己的优点：在相同的安全强度下，HECC的

3、密钥可以更短，降低了系统的存储和运行的开销；在相同的基域下，超椭圆曲线随着亏格的增大，可选择的安全加密曲线就越多；安全性更高，目前对低亏格的HECC的攻击是指数时间的；能够在一个很小的基域上构造具有较大素数因子的阶的Jac0bian群。这些优点使超椭圆曲线密码体制逐渐受到人们的重视。但在Jac0bia11群上计算的困难性，使得对超椭圆曲线密码体制的研究主要还处于理论阶段，他仍然存在着许多公开性问题值得去解决。本文主要介绍超椭圆曲线基础知识，除子标量乘的算法的分析、比较和改进以及超椭圆曲线密码体制中的加

4、密和解密实现。1基础知识及常用函数Maple实现设c：y+^())，=厂()是Fq上亏格为g的超椭圆曲线，其中deg(h)≤g，deg(f)=2g+l。Jc(Fq)是超椭圆曲线c上的Jac0bian群，#Jc(Fq)=llIl，n是大素数，h=1或是较小的余因子，c∈Jc(Fq)是具有大素数阶的约化除子。对Vk∈z，计算P=k×G是可行的，但根据P、G得k是求解超椭圆曲线上离散对数问题L3J是不可行的。算法1Cantor提出的除子复合与约化输入约化除子D1=[al(u)，bl(u)]，D2=[a2(u

5、)，b2(u)]。输出约化除子[a3(u)，b3(u)]=D1+D2。(1)利用扩展的欧几里德算法计算最大公因式d=sla1+s2a2+s3(bl+b2+h)；计算a3+-ala2／d2；b3．--收稿日期：2008—08—31基金项目：教育部重点科研资助项目(20r7089)；海南省自然科学基金资助项目(8Q528)；海南省教育厅高校科研基金资助项目(2oo6o16)；2008年海南省高校硕士研究生创新科研资助项目(H)cwsy2008—21)作者简介：陈小娥(1983一)，女，湖北随州人，在读研究

6、生，密码学．第6期陈小娥等：HEcc中几个经典除子标量乘算法及实现57(s1a1b2+s2a2bl+s3(blb2+f))／d(In0da3)。(2)当deg(a3)>g时，计算a3一(f一一b3)／a3，b3一一h—b3(moda3)。(3)返回[a3(u)，b3(u)]。程序用saveDivAdd，”f：＼cti0n＼DivAdd．m”存，鼢d”f：＼tion＼DivAdd．m”调用[引，输入Di—vAdd(p，g，h，f，D1，D2)计算。算法2除子的倍点运算输入除子D=[a(u)，b(u)]。

7、输出除子2D。(1)计算d：sa+t(2b+h)，w：a2／d2，：生(modw)。(2)将除子[w，z]约化，w的系数化为一，即得到2D=[w，z]。程序用saveDivD0ubl，”f：＼mcti0n＼DivDoub1．m”存，”f：＼鼬lcti0n＼DivDoub1．m”调用[4。，再输入DivD0ubl(p，g，h，f，D)计算。2标量乘算法的实现及比较2．1算法及实现二进制展开法即将m表示成m=￡Ln2“+A+ai2+A+a12+ao2o，其中ai∈{0，l}。则除子标量乘可以表示为：mD=

8、∑a；(2D)，其中a∈{0，l}。算法3二进制展开法标量乘算法输入除子D和正整数m。输出R=Ⅱl【)。(1)将m转化为二进制数：m=convert(m，base，2。(2)B—D，R一0。(3)f0rifmmOt0n一1doifai=l山enR=R+B；B=2·B。(4)retumR。例如，若m=7，则n=8D—D这就是NAF法(带符号的二元向量)。这里主要实现二进制算法。程序用saveMDivBase2，”f：＼function＼MDivBase2．