（通信与信息系统专业论文）超椭圆曲线密码体制快速算法研究.pdf

内容提要本文对超椭圆曲线密码体制快速算法进行了比较深入的研究，内容包括：从有限域算术、群运算的明确公式、标量乘算法的角度对影响超椭圆曲线密码体制性能的诸多因素进行的研究以及在不同的应用环境下椭圆曲线密码体制( e c c ) 与超撩圆曲线密码体制( h e c c ) 的优化实现问题，我们主要的成果有：l 、给出了最优塔域6 f ( p 2 2 ) 与g f ( p 2 3 ) 的构造方法并推导了上述两个有限域中快速求逆公式。2 、在最优塔域g f ( ( 2 ”一3 ) 一) 上构造了1 6 0 比特的二次孪生椭圆曲线密码体制并结合最优塔域上的快速求逆公式以及孪生曲线上f r o b e n i u s 映射给出了该密码体制的快速实现。3 、实现了最优扩域g f ( ( 2 ”一3 ) 7 ) 上1 7 5 比特的椭圆曲线密码体制以及最优塔域g f ( ( 2 ”一3 ) 2 2 ) 上1 7 6 l 特亏格为2 的超椭圆曲线密码体制，对两个密码体制的性能作了详尽的比较与分析。4 、首次在射影坐标系下对亏格为3 的超椭圆曲线密码体制推导了无需求逆的明确公式。选取了4 个有代表性的有限域( 包括1 个素数域及3 个二元域) 对新公式的性能进行了测试。对新公式与已有明确公式的实现速度进行了详尽的比较与分析。5 、利用查表法对基于特殊超椭圆曲线上有效自同态的标量乘算法进行了改进，分析了改进算法的时间与空间复杂度。6 、提出了同时除子类加一减算法，在仿射坐标系以及射影坐标系下给出了该算法的明确公式并利用该技巧提高了两种标量乘算法预计算部分的速度。关键词：公钥密码体制椭圆曲线密码体制超椭圆曲线密码体制最优塔域明确公式标量乘a b s t r a c tad e t a i l e di n v e s t i g a t i o no ff a s ta l g o r i t h m sf o rh y p e r e l l i p t i cc u r v ec r y p t o s y s t e m( h e c c ) i sg i v e ni nt h i st h e s i s w eh a v ef o c u s e do nm a n yf a c t o r sw h i c hi n f l u e n c eo nt h ep e r f o r m a n c eo fh e c cf r o mt h ev i e w p o i n to ff i n i t ef i e l da r i t h m e t i c ，e x p l i c i tf o r m u l a ef o rg r o u pa r i t h m e t i ca n ds c a l a rm u l t i p l i c a t i o na l g o r i t h m ，a n do nt h eo p t i m i z e di m p l e m e 。n t a t i o n so f e c ca n dh e c c t h ek e yc o n t r i b u t i o n sf o l l o wb e l o w 1 c o n s t r u c t i o nm e t h o d so ft w oo p t i m a lt o w e rf i e l d s ( o t f s ) g f ( p 27 ) a n dg f ( p 2 ) a r eg i v e n f a s ti n v e r s i o nf o r m u l a eo v e rt w oo t f sa b o v ea r ed e r i v e d 2 16 0 一b i t sq u a d r a t i ct w i s te c ci sc o n s t r u c t e do v e ro t fg f ( ( 2 ”一3 ) 2 1 b a s e do nac o m b i n a t i o no f f a s ti n v e r s i o nf o r m u l a eo f o t fa n df r o b e n i u sm a po f t w i s tc u r v e s ，t h ec r y p t o s y s t e ma b o v ei si m p l e m e n t e d 3 1 7 5 - b i t se c cd e f i n e do v e ro p t i m a le x t e n s i o nf i e l d ( o e f ) g f ( ( 2 ”一3 ) 7 1a n d17 6 - b i t sg e n u st w oh e c cd e f i n e do v e ro t fg f ( ( 2 ”一3 ) 2 ) a r ei m p l e m e n t e d t h ep e r f o r m a n c eo f t w oc r y p t o s y s t e m si sc o m p a r e da n da n a l y z e di nd e t a i l 4 f o rt h ef i r s tt i m e ，t h ei n v e r s i o n f r e ee x p l i c i tf o r m u l a ea r ed e r i v e df o rg e n u s3h e c ci np r o j e c t i v ec o o r d i n a t es y s t e m f o u rr e p r e s e n t a t i v ef i n i t ef i e l d si n c l u d i n go n ep r i m ef i e l da n dt h r e eb i n a r yf i e l d sa r es e l e c t e dt ot e s tt h ep e r f o r m a n c eo fn e we x p l i c i tf o r m u l a e t h ei m p l e m e n t a t i o ns p e e do ft h en e wa n do r i g i n a le x p l i c i tf o r m u l a ei sc o m p a r e da n da n a l y z e di nd e t a i l 5 u s i n gt h el o o k - u pt a b l e s ，t h es c a l a rm u l t i p l i c a t i o na l g o r i t h mb a s e do ne f f i c i e n tc o m p u t a b l ee n d o m o r p h i s m so ns p e c i a lh y p e r e l l i p t i cc n r v e si si m p r o v e d t i m ea n ds p a c ec o m p l e x i t yo fi m p r o v e da l g o r i t h m sa r ea n a l y z e d 6 s i m u l t a n e o u sd i v i s o rc l a s sa d d i t i o n s u b t r a c t i o na l g o r i t h mi sp r o p o s e d e x p l i c i tf o r m u l a eo ft h ea l g o r i t h ma r eg i v e ni na f f i n ea n dp r o j e c t i v ec o o r d i n a t es y s t e m u s i n gt h i ss k i l l ，t h ep r e c o m p u t a t i o np a r to ft w os c a l a rm u l t i p l i c a t i o na l g o r i t h m sf o rh e c ci sa c c e l e r a t e d k e yw o r d s ：p u b l i c - k e yc r y p t o s y s t e me l l i p t i cc u r v ec r y p t o s y s t e mh y p e r e l l i p t i cc u r v ec r y p t o s y s t e mo p t i m a lt o w e rf i e l de x p l i c i tf o r m u l as c a l a rm u l t i p l i c a t i o n创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，涂了本文中特别加以标注和致谢中所罗列的内容外，论文中不包含其他人已经发表或撰写过的研究成果；也不包舍为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。本人签名：楚叠虫日期i 监。f 。惶关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期阎论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表的论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阏论文；学校可以公布论文的全部或部分内容；可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本人签名：踅竖邀导师签墨：堡：叠彬e l 期：塑堕。f ! 嚏日期：、二耵o i 6致谢木文的1 f 究成果是对我在信息安全与保密教研寮一年多来研究工作的总结，由于对超椭圆曲线密码体制的研究在我国才刚刚起步希望我的研究成果对于那些正在研究并准备应用超椭圆曲线密码体制的大学以及工业界能有所帮助。一年多来，如果没有很多人的支持与帮助我不可能完成本文中的研究工作。首先，对我的导m j 信息安伞专家毫育蠢教授表选深深的敬意，感谢王老师将我引入了信息安全这引人入胜的领域，加入王老师的研究团队是我正确无悔的选择，成为王老师的学生是我莫火的荣幸，在王老师的指导下顺利完成研究工作是我极大的成功。我所取得的每一点成绩和进步都离不开王老师的谆谆教诲和悉心点拨。早在研究的初期王老师就根据我的特点与兴趣为我指出了超椭圆曲线密码体制的研究方向以及理论与应用相结合的研究方法，在研究过程中王老师给了我多次将密码理论与工程实践相结合的机会，充分发挥了我各方面的能力，也使我学会了如何在工程实践中认识数学、如何在工程实践中理解数学、如何在工程实践中体会数学的美。更重要的，王老师教会了我如何做学问、如何做人，这将对我今后的人生道路以及科研工作产生深远的影响。我和王老师在科研工作中所结下的深厚的师生之谊将令我终生难忘。感谢师母置老师对我生活的关心。特别感谢德国b o c h u m 大学的幡_ 口俐嗡咿博士，半年多来与他深入的交流与讨论使我受益匪浅，他在超椭圆曲线密码体制软件与硬件设计方面的丰富经验给了我很大的帮助，在研究过程中他对我完成的每篇论文都提出了很多建设性的意见并进行了认真细致地修改，极大地提高了我的论文质量，他对我精神上的支持与鼓励使我在研究工作中克服了很多困难，我们讨论闫题以及合作撰写论文的那些日日夜夜至今依然历历在目。感谢美国b r o w n 大学的捌钿- - 教授详细地解答了我提出的关于如何在二次孪生超椭圆曲线上构造f m b e n i u s 映射的问题。感谢日本h i 协c h i 有限公司系统开发实验室的琢棚垆田a 咖博士以及奥地利c - r a z 技术大学的卿蝴a 盯博士，他们在边信道攻击研究方面出色的工作以及独到的见解给了我根多启发。瘟谢澳大利亚q u n s l a n d 大学蝻_ - 瑚翻b 吒博士，她对于如何在智能卡上有效地实现椭圆曲线密码系统给了我不少建议和帮助。深深地感谢赐予我生命和智慧的爸爸、妈妈，感谢你们多年来为儿子营造的温馨和睦的家庭氛固，感谢你们多年来对儿子生活上无微不至的照顾感谢你们多年来对儿子的理解与支持，你1 门是儿子事业发展的精神支柱和坚强后盾。儿子对于数年求学的过程中未能你们身边尽孝感到深深的内疚和自责，希望儿子的顺利毕业能够给你们送去一丝欣慰。儿子一定会成为你们的骄傲，将沿着所选择的人生道路脚踏实地地实现自己的理想，r 一步一步地走向辉煌i感谢肖国镶教授、王靳捧教授、寇卫东教授、马建唪教授、胡予漠教授、柘藏教授、曹建华教授、享晖副教授的指点和教诲。他们与王老师共同创造的西电密码学严谨、求实以及创新的学术氛围为掘们年轻的科研工作者提供了充分展现自身能力的平台，这种浓厚的学术氛围为我今后的研究工作奠定了庭好的基础。感谢那些曾经和正在信息安全与保密教研室学习和工作的师兄弟、师姐妹们，他们分别是 张方国博士、毛剑博士、睐晓峰博士、赢虎明博士、王艇林博士、陈丹博士、伍前扛博士、张犍虹博士、柙艳华博士、 i l l 蠢博士、向明森博士、王萱博士、善正涛博士、庞n 军博士、束硗妍博士、拿恕海博士、谭示豢博士、柳藏博士、日浑博博士、彝渡博士、孙t 博士、詹阳博士、石鹏硕士、王平硕士、倪菲硕士、鄙先供硕士、高明硕士、耿航硕士、田伟硕士、裹一沫硕士等。感谢多年来一直陪伴在我身边关心我、鼓励我、支持我的亲友们，你们减轻了我的工作压力，让我感受到了生括的美丽与快乐，你们为我所做的一切都令我深深地感动。科学研究的道路是漫长而艰辛的，每取得一点成绩都需要付出巨大的努力，但我相信追逐梦想的路上有你们相伴我会飞得更高、走得更远!最后，谨以王瞳雏先生人间词话中做学问的三个境界自勉：昨夜西风凋碧树，特上高楼，望尽天涯路。表带渐竟终不悔，为伊消得人幢悴。众里寻他千百度。萎然回首。那人却在灯火阚珊处。一一垂珠摊，它花柳束 1 ) 的超椭圆曲线c 定义为如下方程在有限域f 上的解( 甜，v ) f x f 的集合：c ：v 2 + ( “) v = f ( u ) i n 研“，v 】( 2 ，1 )其中h ( u ) f i u 】是一个次数至多为g 的多项式，厂 ) f u 】是一个次数为2 9 + 1 的多项式，并且不存在( “， i y ) f x f 同时满足盐线方程v 2 + ( ) v = f ( u ) 以及两个偏导数方程2 v + 矗( “) = 0 和矗。( u ) v - f 。( “) = 0 。同时满足曲线方程v 2 + ( “) v = f ( u ) 以及两个偏导数方程2 v + 矗( “) = 0 和矗( “) v f ( “) = 0 的点( 虬v ) e f x f 称为c 上的奇异点。由定义2 2 2 可知超椭圆曲线并没有任何奇异点。引理2 1 3 m w 删1 设c 是由方程( 2 1 ) 定义的有限域f 上的一条超椭圆曲线，则：综合业务网理论及关键技术国家重点实验室信息安全与保密教研室1 如果h ( u ) = 0 贝0 c h a r ( y ) 2 ；2 若c h a r ( f ) 2 ，则变量代换“寸1 4 , v 斗v ( ”) 2 将曲线c 变为形如v 2 = 厂( “) ，其中d e g 。( 门= 2 9 + l ；3 设c 由方程( 2 1 ) 定义，且而( 甜) = 0 ，c 矗卯( 叼2 。则c 是一条超椭圆曲线当且仅当厂( “) 在蟊中没有重根。定义2 1 4 m w z 9 8 1 设k 是f 的个扩域，超椭圆曲线c 上k 有理点的集合c ( k ) 定义为所有满足方程 1图2 3 零点的重数f c “定义2 , 2 2 一个除子中点的数目称为除子的重量。所有除子的集合( 记为皿) 在如下定义的加法规则下构成一个加法群：牡坼霉+ 恻蛸= 氍( 碍+ 埤 牟用舻表示次数为零的除子所构成的子群。定义2 2 3 设日= ，。m e p 和d 2 = 。饰p 是两个除子，则q 与皿的最大公因子定义为：g c d ( d 一，d 2 ) = 。m i n ( m e ，n e ) p ( 。m i n ( m 。，脚) 扣综合业务网理论及关键技术国家重点实验室信息安全与保密教研室!堑塞皇耋型堇蠢耄壅圭丝塞；壑鬓奥塑丝童堡笪型堡建墼l i 堕一：一：= ：= ：2 3 主除子在引入j a c i b i a n 之前，我们必须定义主除子，本节中我们仅给出最本质的定义，对于更多的细节请读者参考 k o b 9 8 或 f u l 6 9 。定义2 3 1 1 m w 翘卅给定个多项式a ( u ，v ) e 研v 】，g ( u ，v ) 可被视为曲线上的一个函数c 等价地，g ( u ，可被视为商环研“，v ( v 2 + ( “) v 一厂( “) ) 中的一个元素) 。在实际中，通过代入曲线豹穷程降低g ( u ，v ) 中v 的次数直到将g ( u ，v ) 表示为如下的形式：g ，v ) = a ( u ) - b ( u ) v 。设r、( g ( ) ) = 执( g ，v ) ) = 耻d 峨( g ) = i 朋，只i 一帆冲皿。表示多项式函数g ( u ，v y 的除子( 其中系数巩1 的选取使得除子的次数为o ) 。系数碍是函数g ( u ，v ) 在p 点的阶。定义2 3 2 m w z 9 8 1 形姗( g ( # ，v ) ) 一( h ( ” 呦联滁子称为主除子。换句话说，有理函数g ( u ，v ) h ( u ，v ) 的除子称为主除子。主除予( g ( 甜，v ) ) 一( 捞( 甜，v ) ) 曲有理函数g 似，v ) h ( u ，v ) 的零点和极点所支撑，其中零点被指定为正系数面极点被指定为负系数。所有主除子的集合记为妒，由于任一主除子的次数为0 ，可以证明p 是扩的一个子群。例2 【g 。棚1 设，是一个谪数，除子硪坝力晌够被分解为两个除子的差：d i v ( f ) = d i v o ( f ) - d i v 。( f ) ，其中d i v o ( f ) 对应于曲线c 与瑚线f = o 钓交点，d i v 。( f ) 对应于曲线c 与曲线一1 ：0 的交点。在图2 4 中，我们给出个例子，其中a i v ( f ) = 片4 - 昱+ 与+ 只一( 2 蜴+ 2 q 2 ) 。图2 4 一个主除子的例予1 6 8 “i2 4j a c o b i a n1 一般丽言，次数为0 的除子不一定是主除子。正如定义2 3 2 所述，p 是皿。的一个子群。定义2 4 1 m w z 9 研设( 更准确地j ( k ) ，其中k 是f 的扩域) 表示由主除子( 来自于有理函数g ，v ) l h ( u ，v ) ，其中g ，h k u ，v 】) 构成的子群p 对定义在k 上的次数为0 的除子构成的群助。进行陪集划分后得到的商群，即( k ) = 皿。p 。我们称j ( )为曲线的j a e o b i a n 。任取d l ，d 2ed o ，如果d l 一破e p ( 此时d l ，d 2 在同个陪集中) ，则记为q 皿，称d l ，砬是等价除子。因此，j a c o b i a n 是由一个无限群对另一个无限群进行陪集划分后得到的有限商群。j a c o b i a n 中的每一个元素是一个除子的等价类。图2 5 显示了定义在一条曲线上的两个有理函数( 为了可视化，我们在实数域r 上画出该图1 。钮醌| |”丁、孓li心地、后。、_ - _ _ _ 一x + z t = 0图2 5 定义在曲线上的有理函数的例子f g l “7为了在中进行运算，我们需要找到一种唯一的并且“容易7 的方式描述舻p中的每一个等价类，即选取一个便于计算的陪集代表元的集合。在超椭圆曲线的情形下，中的元素能够被唯一的表示。在2 6 节，我们将引入j a c o b i a n 群中元素的唯一表示形式。在2 7 节和2 8 节，我们给出j a c o b i a n 群中的加法规则。在介绍这些内容之前我们首先在2 5 节引入约化除子的概念。2 5 约化除子为了得到j 中等价类的一种唯一的并且“容易7 的表示，在本节中我们介绍约化除子的概念。考虑一个次数为0 的除子d ，该除子可写为：d = 。；。强# 一( 。他) o 。，综合业务网理论及关键技术国家重点实验室信患安全与保密教研室其中只= ( ，y ，) 并且当j - ，时只p 。定义2 5 1 m w z 9 8 1 设d = 砚0 是一个除子，则d 的支撑集定义为：s u p p ( d ) = 只c i m ，o 定义2 5 。2 l m w z 赔i 一个半约纯除子具有如下的形式：d = b 。m r , 一( 日。m 1 ) o 。其中每个d ，霉是有限点并且满足当只j u p p ( d ) 时，只( 鼻的反点掘s u p p ( d ) ，除非有异= 卑，在这种情形下m = 1 。下面的引理表明对于每个元素d d o 存在一个与d 等价的半约化除子d l ：引理2 5 3 1 狲v z g s l 对于每一个除子d d o 存在一个半约化除子n 妒满足d d l 。( 注】半约化除子在其等价类申并不是唯一的在超椭圆曲线豹情形我们能够证明一个更强韵结果( 利朔r i e m a n n - r u c h 定理【f “6 9 j ) ：j 中的每个元素能够被所谓的约化除子难一表示。约化豫子可如下定义：定义2 5 4 唧。堋设d = 艺卑一( 如是一个半约化除子，如果柳，g ( g 是曲线c 竹亏格) ，则。称为一个约亿除子。因此，如果以下三令条件成立贝口除子d = 帆只一( m , ) o o e d 。就是约化的：1 所有的是非负的并且当鼻等于它的反点卑时m is 1 ；2 若只f ，则# 和鼻不同时出现在形式和中；3 g 。1 和2 保证该除子是半约化的，加上条件3 后就成为约化除子。我m n - i 以证明商群j = 舻，p 的每一个陪集中仅有一个约化除子：定理2 5 5 l m w z 9 剐对于每一个除子d 扩存在唯一的约化除子皿妒满足d d 。2 6 除子的表示在2 。5 节中，利用除子的概念，我们得到了j j a c o b i a n 群中所有元素的唯一的表示形式，但是从实用的角度来看和用除子进行运算并不方便。m u m f o r d 提出了除子的另一种表示形式呻m 8 4 1 ，这种表示对于实际应用来说更为有效。下面的定理表明半约化滁子可以用一对多项式来描述：综合业务网理论及关键技术国家重点实验室信息安全与保密教研室引理2 6 i i m w z s s j 设尸= ( x ，y ) 是超椭圆曲线c 土盼一个普通点，则对于每一个k 1 ，存在唯一的多项式b a u ) f 阻l 满足：1 d e g 。( 吼) k ；2 以( ) = y ；3 酲( “) + 6 ( “) ( “) 厂( “) q n o d ( “一x r ) 。定理2 6 2 m w 功8 1 设d = 舰异一( p 是一个半约化除子，其中p = ( 葺，只) 。设口( “) = n m 一玉) 鸭，捌存在唯一的多项式6 m ) 满足：1 d e g 。b d e g 。口；2 对于所有使得码0 的i ，有6 ( 而) = m 成立；3 a ( u ) 整徐于b ( u ) 2 + b ( u ) h ( u ) 一f ( u ) 。并且有d = g c d ( d i v ( a ( u ) ) ，d i v ( b ( u ) 一v ) ) 。【注 通常g e d ( d i v ( a ( u ) ) ，d i v ( b ( u ) 一v ) ) 简记为d i v ( a ( u ) ，b ( u ) 一v ) ，或者更简单地记为d i v ( a ，b ) 。引理2 6 3 i m w 功剐设口0 ) ，吞( “) 冠h 】满足堍。b gd o6 k = k + 1 ：7 域= 厂一吒一。h 一( 吒一。) 2 以一。；8 吨z ( - h t 1 ) m o d u t ；9 e n d w h i l e1 0 返回毪= 哦，v 3 = 畦图2 6 亏格为2 的超椭圆曲线上两个约化除子相加示例综合业务网理论及关键技术国家霞点实验室信息安全与保密教研室! !堑塞皇王型墼堂堡圭婆塞；垫塑塑丝童塑垡磐垄叁鎏丝兰坠；! 下面的定理2 8 1 与定理2 8 2 分别证明了算法2 中复合步骤与归约步骤的正确性，定理的证明参见 m w z 9 8 1 。定理2 8 1o m w z 9 8 1 设d l = d i v “，v 1 ) 和d 2 = d i v ( u 2 ，叱) 是半约化除子，“和v 由算法2 的第2 步与第3 步给出，则d = d i v , ( u ，节) 是一个半约化除予并i i d 一日+ d 2 。定理2 s 2 i m w 军9 8 设d = d i v ( u ，v ) 是一个半约化除子，则算法2 返回的除予d 3 = d i v ( u 3 ，v 3 ) 是约化韵并且皿d 。倍徐子运算与除子加运算相比较为简单，因此算法2 的第l ，2 ，3 步可简化如下：1 d = g c d ( u ，2 v + ) = 屯材+ s 3 ( 2 v + h ) ；2 “。= d 2 ：3 v 。= i s l l i p + s 3 ( v 2 + ，) 一1 ( r o o d “)2 9j a c o h i a n 中元素韵运算h a r l e y 算法在2 8 节中，利用c a n t o r 算法能够完成超椭圆抽线却c o b i a n 中豹除予洳与倍除子运算。我们注意到c a n t o r “算法是在多项式环中进行的，即算法的每一步都需要对定义在有限域上韵多项式进行运算。h a r l e y 在【g h o o | 中提出了另一种计算除予加与倍除子的算法，作者注意到如澡根据输入除子的牲质( 即除子的重量) 来区分几种不同的情形，则我们能够减少运算的次数。h a r l e y 算法最大的特点就是通过上述的分类将多项式环中韵运算转他为在有狠域中避行。作者利用了诸如k a r a t s u b a 乘法、中匿剩余定理以及牛顿迭代等多种计算代数方面的技巧，这些技巧的运用显著地降低了j a c o b i a n 中运算的全局复杂性。为了得到明确公式饵p 仅利用有限域算术完成除子加与倍除子运算的公式) 最重要的问题就是知道输入除子的重量。一个除予d 的重量被定义为d 的支撑集中点的个数。例如，对于一条亏格为2 的超搪圊曲线，输入除子的重景可能为0 ，i或2 ，对于每一种情形我 i ，都需要给出相应的明确公式并调用不同的函数，图2 7给出了在亏格为2 的曲线上进行倍除予运算的流程图：圈2 7 亏格为2 的超椭圆曲线倍除子算法( h a r l e y 算法) 流程图综合业务网理论及关键技术国家重点实验室信息安全与保密教研室在有限域g f ( 9 ) 上，两个多项式有一个一次公园式的概率约为1 q f e “拶j 。对于亏格为2 e 或3 ) 的超椭圆曲线的情形，两个多项式没有次公因式的概率约为i 一2 。f 或l 一2 - 6 0 ) 。因此在大多数情况下两个多项式是互素的，在本文的其余章节中我们将它称为常见情形( f r e q u e n tc a s e ) 。在 i a n 0 1 】以及 l a n 0 2 a q b ，l a n g e 将i a r l e y 的算法推广到任意特征的有限域，对各种可能出现的情形进行了详细的讨论并给出了相应的明确公式。由于非常见的情形以极低的概率出现，在利用明确公式实现超椭圆曲线密码体制的过程中，我们能够设计密码协议避免非常见情形的出现( 如果非常见情形出现则我们的协议重新开始) 。在本文的其它章节中，当考虑用h a r l e y 算法完成除子加与倍除子运算时，我们仅讨论常见情形。下面我们对于亏格为2 的超椭圆睦线介绍h a l e y 算法。1 9 1 常见情形下的除子加算法在常见情形下需要复合的两个除子类包含4 个点，这4 个点彼此不同并且也不同于它们的反点。算法2 对这两个约化除子类复合后得到n ：= “。“：以及一个次数蔓3 的多项式吒满足材：i 馆+ v o h - f 。由于两个输入的约化除子类分别满足l j l 谚+ 蚋f ( i = 1 ，2 ) ，因此我们能够利用中国剩余定理得到k ：v 0 。gv ir o o d u l( 2 2 )k3 也m o d “2( 2 3 )然后通过将( 一吨 一培) ，( m 甜：) 化为首一多项式坞并取v 3 = ( - h - 吨m o d 吩) 得到归豹后的最终结果。为了优化计算过程，h a r l e y 算法并不按照上面的两步直接进行酊是利用了一些技巧。算法3 描述了整个除子加算法的计算过程：算法3 亏格为2 的超椭圆曲线上除子加( h a r l e y 算法一f r e q u e n tc a s e ) 输入：定义在f 上的两个约化除子日= d i v ( u , ，q ) 和砬= d i v ( u 2 ，吐)输出：约化除子d 3 = d i v ( u ，v 3 ) = 日+ 3 21 七= ( f - v 2 h 一呓) 毪；( e x a c t d i v i s i o n )zs ；【( v l v 2 ) u 2 】m o du l ；王，= s l , 1 2 ：t “。= k s q + h + 2 v 2 ) u l ；( e x a c t d i v i s i o n )量均= d m a d e m o n t e ； p 3 三一( 矗+ f 十v 2 ) r o o d “3 鞋 对于亏格为3 的超椭圆曲线我们需要再进行一次归约步骤才能得到最终的约化除子现= d i v ( u 4 ，v 4 ) = d l + 见，即在算法3 后增加如下的第7 步和第8 步：7 ：u 4 = ( 厂一v 3 h 一嵋) 坞；( e x a c td i v i s i o n )8 ：v i ；一( v 3 + ) m o d 综合业务网理论及关键技术嚣家重点实验室信息安全与保密教研室我们首先证明吨= i + v ：= s ：十v 2 满足( 2 2 ) 式和( 2 1 3 ) 式。v ：满足( 2 1 3 ) 式是显然的，对于( 2 2 ) 式，我们有吨ss “2 + v 2 = 【( h v 2 ) u 2 】“2 + v 2 ；v i m o d 1 我们也注意到m “2 “= “2 【女一s ( 1 + h + 2 v 2 ) = f v 2 h 吒2 一，( ，+ ) 一2 1 v 2 = 厂一v ；h 一培因此。= ( 厂一“ 一悖) “也) 是成立的。2 9 2 常见情形下的倍除子算法在常见情形下需要复合的除子类包含2 个点，这2 个点彼此不同并且也不同于它们的反点。算法2 对这个约化除子类q = d i v ( u 。，v 1 ) 复合后得到一个新的除子类味。= d i v ( 。，。) ，其中：n 。= “?心，! v z r o o d ( 2 ，4 )n ，| ? 0 + q 。 一f( 2 5 )然后通过将一力一) 7 化为首一多项式2 并取v 2 = ( - h 一。m o d u ：) 得到归约后的最终结果。为了优化计算过程，h a r l e y 算法并不按照上面的两步直接进行而是利用了一些技巧。算法4 描述了整个倍除子算法的计算过程：算法4 亏格为2 的超椭圆曲线上倍除子( h a d e y 算法一f r e q u e n tc a s e )输入：定义在f 上的一个约化除子q = d i v ( u 。，h )输出：约化除子d 2 = d i v ( u 2 ，v 2 ) = 2 0 ,1 k = ( ，一v , h - v i ) 1 ；( e x a c t d i v i s i o n )2 ，s g 【k ( + 2v 1 ) m o du l ；3 ，= s u l ；4 = s 2 + ( + 2 v ) s - k l u , ；( e x a c t d i v i s i o n )5 “2 = “m a d e m o n i c ；6 v 2e 一( + ，+ v i ) m o d 甜2 f 注 对于亏格为3 的超椭圆曲线我们需要再进行一次归约步骤才能得到最终的约化除子b = d i v ( ，吩) = 2 d j ，即在算法4 后增加如下的第7 步和第8 步：7 ：“3 = ( ，一心 一嵋) “2 ；( e x a c t d i v i s i o n )8 ：鸭2 一( v 2 + ，砼r o o d l l 3我们首先注意到，= ，+ v l = 蹦+ v l 显然满足( 2 4 ) 式。为t 证n ( 2 4 ) 式成立，我们考虑如下两个式子；0 + 删h - f = 1 2 + 2 l v l + 砰+ h l + h v f = s 2 “? + 坼 ( 而+ 2v 1 ) s j i 】以及( + 2 h 弘一是三( 晟+ 西i ) 七“矗+ 2 k ) 一k = - o m o d u l最终我们得到：o 乞+ v 。 一门。= i s 2 砰+ ( ( + 2 u 弦一七心】“? = “综合业务网理论及关键技术国家重点实验室信息安全与保密教研室基于算法3 和算法4 ，我们可以推导出各种用于亏格为2 和3 的超椭圆曲线群运算的明确公式，由于篇幅限制我们不再给出这些明确公式，对于亏格为2 的情形，请读者参考 h a t 0 0 ，l a n 0 1 ，m c t 0 1 ，m d m + 0 2 ，t a k 0 2 ，s m c t 0 2 ，l a n 0 2 a ，p w p 0 4 ；对于亏格为3 的情形，请读者参考 k g m + 0 2 ，p w g p 0 3 ，g m a + 0 4 。2 1 0 超椭圆曲线密码体制及其安全性现状我们能够利用定义在有限域上的超椭圆曲线的j a c o b i a n 所形成的有限阿贝尔群构造基于超椭圆曲线离散对数问题( h e c d l p ) 的公钥密码体制。h e c d l p 可如下描述：任意给定两个除子d l ，d 2 ，确定使得d 2 = m q 成立的最小整数m ( 如果这样的整数m 存在1 。超椭圆曲线密码体制中最核心的问题是在给定大整数m 以及除子d 后有效地计算出m d ，即d + 上) + d = m dj 广该运算称为除子乘或标量乘。标量乘运算的执行时间决定了超椭圆曲线密码体制的效率。 m v o v 9 7 ，g o r 9 8 总结了各种常用的并且有效的计算标量乘的算法，例如二元法及其各种变体。标量乘运算需要调用除子加与倍除子运算。对于大多数基于椭圆曲线或超椭圆曲线的密码学协议，一般要求群的阶至少“2 ”o 。如果超椭圆曲线密码系统( h e c c ) 定义在有限域g f ( q ) 上，则曲线的j a c o b a i n是一个阶约为9 2 的有限阿贝尔群，其中g 是曲线的亏格。h a s s e w e i l 定理给出了j a c o b i a n 阶的上界与下界，即( g 1 ) 2 5 撑，( c ) 兰( g + 1 ) “。因此对于h e c c 我们至少要求g l 0 9 2 9 “1 6 0 。对于亏格为2 的曲线，我们要求基域l g f ( g ) l “2 ”；对于亏格为3 的曲线，我们要求基域i g f ( g ) l * 2 ”。p o l l a r dr h o 算法及其并行版本 o l v 9 8 ，p 0 1 7 8 ，w e i 8 6 是最好的解决离散对数问题的算法，其核心思想是将群g 上的离散对数问题规约为其素数阶子群上的离散对数问题。对于一个阶为聆的群g ，p o l l a r dr h o 算法的时间复杂度为o ( 如) ，这是一个指数时间的算法。在 f r 9 4 ，r u e 9 9 ，作者发现了一些特殊的超椭圆曲线其攻击的时间复杂度低于d ( 聆) 。对于足够大亏格的超椭圆曲线，【a d h 9 4 q b 给出了第一个计算离散对数问题的亚指数时间的算法， f s 9 7 ，e n 9 9 9 a , g a u 0 0 ，g a u 0 0 a ，e g 0 2 】对该算法进行了改进和实现，当曲线的亏格g 4 时，该算法的时间复杂度低于p o l l a r dr h o 算法。在 f r 9 4 ，作者描述了如何利用t a t e 对将除子类群( g f ( q ) ) 中的离散对数问题规约为扩域g f ( q ) 的乘法群中的离散对数问题，当k 较小时可以利用亚指数综合业务网理论及关键技术国家重点实验室信息安全与保密教研室时间的指标法在g f ( q ) 中计算离散对数。【g 抛0 0 a 】中证明了当曲线钓亏格大于4时在超椭圆曲线的j a c o b i a n 中使用指标法计算离散对数的时间复杂度低于p o l l a r dr h o 算法，作者也进一步研究了一些特殊情形孝产得出算法的全局复杂度为。 斋 。因此攻击亏格为4 的曲线的复杂度低于p o l l a r dt h o ：算法。然而，他们在两种算法之间并没有给出任何实际的比较结果。最近，t h 6 r i a u l t 在 t h 6 0 3 j 中优化了计算低亏格超椭圆曲线j a e o b i a n 中离散对数| 可题的亚指数时间算法。t t i 6 r i m i l t 的结果表明t 对于亏格大于2 的超椭圆曲线，为了达至4 特定的安全级黜，基域必须扩大。表2 1 给出了基域的修正因子：表2 1 对i - i e c c 攻击算法复杂性的比较gl234i n d e xc a l c u l u s冒2q 2q 2q 2r h o g a u 0 0 a tq l ，2gq 3 7 2q 2r e d u c e df a c t o rb a s e 【t h a 0 3 】q 3 7 2q 8 7 5w i t hl a r g ep r i 搬e s t h e 0 3 】9 1 0 ，7q 。4 7 9c o r r e c t i o nf a c t o r ：f o r l 0 9 2i g f ( q ) i1 0 51 2 8 6【t h a 0 3 中算法是目前为止攻击超椭圆曲线密码体镥4 最有效的方法，然而该算法需要非常大的存储空间，因此在实际中并不实用。在本文的相关工作中我们考虑了t h 6 r i a u l t 的攻击并相应地扩大了基域的大小。为了避免f r e y - r u c k 攻击f f 9 9 4 1 。我们需要保证所选取的超椭圆曲线不是超奇异的曲线。在 g a l 0 1 中，s l e v e ng a l k m i t h 解释了如何避免选取超奇异超椭圆曲线并证明了在特征为2 的有限域上任何形如y 2 + y = ，( z ) ( 其中1 d e g ( h ( x ) ) g 十1 )的亏格为2 的超椭圆曲线不可能是超奇异的。g a l b r a i t h 也证明了当亏格为2 的超椭圆曲线密码体制定义在g f 昭”，时，形如y 2 + 纠= ，( x ) 的曲线是超奇异的。因此在特征为2 的有限域上构造零格，为2 豹h e c c 时，我们不能选取形如y 2 平y = ，( 功的曲线( 它们是超奇异的) 在图a 0 2 中，作者证明了对于任何整数玎2 ，在特征为2 的有限城上不存在超奇异的亏貉为2 ”一l 的超椭嘲曲线。因此在特征为2 的有限域上构造亏格为3 的h e c c 时，j 我们能够选取特殊的超椭圆曲线：步2 + y = ，( 受) ，其中厂( 工) 是次数为7 的首一多项式。除此以外，我们也需要考维w 嘲d e s e e m 攻击。f r e y 首先提出将w d l d e s c e n t攻击用于椭圆曲线密码体制【姻8 1 。在 g h s 0 2 6 p ，c r a u d r y 、h e s s 以及：s m a r t 给出了实现f r e y 思想的g h s 攻击算法。特别地，定义在g f ( 2 ”) ( 聆是合数) 上的一条椭圆综合业务网理论及关键技术国家重点实验室信息安全与保密教研室曲线能够被映射为g f f 2 ”) 的某个特定子域上的一条超椭圆曲线。因此可以将定义在g f ( 2 “) ( 是合数) 上的椭圆曲线离散对数问题归约为g f ( 2 ”) 的一个子域上的超椭圆曲线的j a c o b i a n 中的离散对数问题，然后我们可以利用a d l e m a n - d e m a r r e sh u a n g 算法 a d t t 9 4 l 实现攻击。随后，o a l b r a i t h 在 g a l 0 1 a q b 讨论将w e i i d e s c e n t 攻击用于特征为2 的有限域上超椭圆曲线的可能性。a r i t a 在 m i 0 2 伸对定义在偶扩张次数的有限域上亏格为2 的超椭圆曲线密码体制给出了一种新的攻击算法。最近，d i e m 在 d i e 0 3 中将g h s 攻击推广到任意特征的有限域。目前对于w e i l d e s c e n t攻击的研究大多还处于理论阶段，其实用性仍需要进一步的验证。上述对超椭圆曲线密码体制的攻击方式都是从数学角度讨论的，然而对h e c c的物理攻击正在逐步成为研究的热点。各种用于抵抗椭圆曲线密码体制边信道攻击( s c a ) 的措施已经被推广到超椭圆曲线密码体制。在 a v a 0 3 q b ，a v a n z i 详细地讨论了超椭圆曲线密码体制的安全实现，将两种用于椭圆曲线密码体制安全实现的措施推广到超椭圆曲线密码体制，使得h e c c 能够抵抗差分能量分析( d p a ) 。本文研究工作中对超椭圆曲线的选取是在充分考虑到现有的对超椭圆曲线密码体制攻击方法的基础上进行的，我们选取的超椭圆曲线兼顾了安全性与效率的因素。到目前为止，我们在软件实现过程中所使用的曲线都是安全的。2 1 1 小结本章详细介绍了超椭圆曲线密码的一些基本的数学背景知识，如有限域上超椭圆曲线的定义及性质，除子的定义及性质，超椭圆曲线的j a c o b i a n ，j a e o b i a n 中元素运算的两种算法等等。最后我们总结了对超椭圆曲线离散对数问题的攻击算法以