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

第28卷第6期 杭 州 电子 科 技 大 学 学 报 V0】．28．N0．6 2008年 l2月 J0umal 0f }Iar咖 D uIliv∞时 Dec．008 HECC中几个经典除子标量乘算法及实现 陈小娥 ，游 林2 (1．海南师范大学数学系，海南海口571158； 2．杭州电子科技大学通信工程学院，浙江杭州310ol8) 摘要：给出了超椭圆曲线除子标量乘运算常用的除子加法和除子倍加算法并用Maplle实现。在实 现超椭圆曲线密码体制中起关键作用的运算是除子标量乘，利用 M印le实现超椭圆曲线中几个经 典的除子标量乘算法，并比较、分析他们的计算复杂度。最后，用MapIe实现超椭圆曲线密码体制 中加解密。 关键词：超椭圆曲线密码体制；除子；标量乘 中图分类号：rN393．o8 文献标识码：A 文章编号：10o1—9146(20o8)06—0o56一o3 O 引 言 提出了基于椭圆曲线上的公钥密码体制后，提出超椭圆曲线密码体制是椭圆曲线密码体制的自然 推广，但不仅仅是一种简单的推广 -3j。超椭圆曲线密码体制所基于的除子类群，又称Jacobian群，其 结构与运算比有理点群复杂得多。但 由于超椭圆曲线密码体制相对其他公钥密码体制拥有 自己的优 点：在相同的安全强度下，HECC的密钥可以更短，降低了系统的存储和运行的开销；在相同的基域下， 超椭圆曲线随着亏格的增大，可选择的安全加密曲线就越多；安全性更高，目前对低亏格的HECC的攻 击是指数时间的；能够在一个很小的基域上构造具有较大素数因子的阶的Jac0bian群。这些优点使超 椭圆曲线密码体制逐渐受到人们的重视。但在Jac0bia11群上计算的困难性，使得对超椭圆曲线密码体 制的研究主要还处于理论阶段，他仍然存在着许多公开性问题值得去解决。本文主要介绍超椭圆曲线 基础知识，除子标量乘的算法的分析、比较和改进以及超椭圆曲线密码体制中的加密和解密实现。 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是不可行的。 算法 1 Cantor提出的除子复合与约化 输入 约化除子D1=[al(u)，bl(u)]，D2=[a2(u)，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期 陈小娥等：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)]。输出 除子2D。 (1)计算d：sa+t(2b+h)，w：a2／d2，： 生