（通信与信息系统专业论文）基于超椭圆曲线密码体系的数字签名技术.pdf

武汉理工大学硕士学位论文 摘要 近几年来椭圆曲线密码体制被广泛地应用在实际之中，超椭圆曲线密码体 制是椭圆曲线密码体制的一种推广。在同等安全水平下，h e c c 比e c c 所用的 基域小，并且在同样的定义域上，髓c c 可以提供更多的曲线，这样可以用于密 码学中的安全的曲线的选项便增多了，由于这些优点使得h e c c 在近几年来， 在密码界中受到越来越多的重视。但是由于在j a g o b i a n 商群上计算的困难性， 使得对于超椭圆曲线密码体制的研究主要还处于理论研究阶段，虽然近几年来， 已经有了些比较简单的关于核心计算的成果，但是它仍然存在着大量的问题值 得去解决，如：如何加快除子标量乘的速度、如何使得超椭圆曲线密码体制标 准化等等。本文主要是针对h e c c 存在的一些问题作了些研究，包括对超椭圆 曲线的数学背景的介绍以及除子标量乘的算法的探讨，并且在最后提出了一种 基于超椭圆曲线密码体系的普通数字签名方案。 相对于r s a 和e c c 来说，h e c c 在安全性上更胜一筹，而超椭圆曲线密码 体制的安全性是基于求解超椭圆曲线的j a e o b i a n 商群上的离散对数的困难性。 为了确保这一系统的稳定性与安全性，h e c c 的几个主要参数的选取问题就起了 很大的作用，本文对这几个参数选取作了详细介绍，并且归纳了求基点和求阶 的方法。这对于h e c c 的标准化有着重要的作用。选取了特定的有限域和亏格 以及超椭圆曲线来讨论h e c c 的除子标量乘问题。除子的标量乘对于实现超椭 圆曲线来说是十分重要的，加快除子标量乘可以更快地使超椭圆曲线密码体制 早日地走向实用之路。 在对基于超椭圆曲线密码体系的数字签名的研究过程中，根据椭圆曲线密 码体制中的数字签名方案，提出了一种基于超椭圆曲线密码体系的普通数字签 名方案，该方案具有普遍性，而且可以将髓c - e i o a m a l 签名方案和h e c d s a 签名方案等属于基于离散对数问题的e 1 c r a m a l 类数字签名方案都规约到这一种 方案上，使其使用更加地方便。 关键词：超椭圆曲线密码体制；j a c o b i a n ；除子；标量乘；数字签名 武汉理工大学硕士学位论文 a b s t r a c t d u r i n gt h ep a s tf e wy e a r s ，e l l i p s ec l l r v ec r y p t o g r a p h yi sb r o a & ye x t e n d e di n a p p l i c a t i o n h y p e r e l l i p t i c “l r v e sc r y p t o g r a p h y ( h e c c ) i so n ek i n ds u r p a s s i n go f e l l i p s ec u r v ec r y p t o g r a p h y ( e c c ) 1 1 舱b a s e df i e l do nw h i c hh e c c i sc o n s t r u c t e di s l e s st h a nt h a to fe c cw i t ht h es a n l es e c u r i t yl e v e l , a n di ng a m ef i e l d , h e c cc o u l d s u p p l ym o r e c t l l - v e s8 0t h a tt h e r ea 船m o l ec h o i c ef o rb u i l d i n gt h es a f ec r y p t o g r a p h y b e c a u s eo ft h e s ev i r t u e sh e c ci sm o l ea n dm o l ei m p o r t a n tf o rs c h o l a ro f c r y p t o g r a p h y b u tn o wt h er e s e a r c ho fh e c ci sm a i n l yi nt h e o r yb e c a u s eo ft h e d i f f i c u l t yo fc o m p u t i n gi nt h ej a c o b i a ng r o u p t h o u g ht h e r ea i e $ o m es i m p l e a c h i e v e m e n t sa b o u tk e r n e lc o m p u t i n gi nr e c e n t l y , t h e r ea r em a n yg r e a to fp r o b l e mt o s o l v e s u c ha s ：h o wt os p e e dt h ed i v i s o rs c a l a rm u l t i p l i c a t i o na n dh o wt on 幽t h e s t a n d a r d i z a t i o no fd i v i s o rs c a l a rm u l t i p l i c a t i o nh y p e r e l l i p t i ce u l v e sc r y p t o g r a p h y i n t h i sa r t i c l e , w em a l 【e5 0 m er e s e a r c hd u et os o m ep r o b l e m so fh e c c i n c l u d i n gt h e m a t hb a c k g r o u n do f h y p e r e l l i p t i cc u r v e sc r y p t o g r a p h y , t h ea l g o r i t h mo f d i v i s o rs c a l a r m u l t i p l i c a t i o n , a n dp r o v i d i n ga k i n do f g e n e r a ld i g i t a ls i g n a t u r eb a s e do nh y p e r e t l i p t i c g u i v e sc r y p t o g r a p h y c o m p a r e dt or s a a n de c c t h es e c u r i t yo f h e c ci sb e t t e r t h u st h es e c u r i t yo f h e c ci sb a s e do nt h ed i f f i c u l t yo fc o m p u t i n gt h ed i s c r e t el o g a r i t h mo nj a c o b i a n g r o u p h o wt oc h o o s et h ep a r a m e t e r so fh e c cp l a y sa ni m p o r t a n tr o l et om a k es u 糟 t h es y s t e ms t a b i l i z a t i o na n ds e c u r i t y t h e r ei si n t r o d u c t i o na b o u th o wt oc h o o s et h e p a r a m e t e r so fh e c ci nt h i sa r t i c l e i m p l e m e n tt h ea l g o r i t h mo fd i v i s o rs c a l a r m u l t i p l i c a t i o nf o r t h ec e r t a i nc x u v c s ，w h i c hi sg o o df o rt h eh y p e r e l l i p t i cc u r q e s c r y p t o g r a p h yi nr e a l i t y t h r o u g ht h ed i g i t a ls i g n a t o ms c h e m eb a s e d0 1 1e l l i p t i cc u r v e $ c r y p t o g r a p h y , i n t r o d u c ean e wk i n do fd i g i t a ls i g n a t u r es c h e m eb a s e do nh y p e r e l l i p t i co 1 r v e $ c r y p t o g r a p h y t h i ss c h e m em a k e st h et y p eo fd i g i t a ls i g n a t u r es c h e m eb a s e do n d i s c r e t e1 0 9 a r i t h mp r o b l e mt o g e t h e r k e yw o r d s ：i - i e c c ，j a c o b i a n , d i v i s o r , s c a l a rm u l t i p l i c a t i o n , d i g i t a ls i g n a t u r e 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：煎缝e t 期：翊。工 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：盘毽导师签名：舀丛座日期：选啦 武汉理工大学硕士学位论文 1 1 课题研究背景 第1 章绪论 安全在通信中扮演着重要的角色，为了确保信息在传送中不被篡改和窃取， 通常对重要的信息进行加密。美国数学家香农( s h a n n o n ) 于1 9 4 9 年在“保密系统 的通信理论”一文中建立了保密通信的数学理论，将密码学的研究纳入了科学 的轨道。随着通信事业的进步，密码学也在不断地发展，从经典密码学到现代 密码学，不断地有新的加密、解密方法被提出来取代旧的加密、解密标准。 1 9 7 6 年加密体制发生了重大的变革，d i t i i e 和h e l l m a n 在“密码学的新方向l 【l ， 中提出了公钥密码思想，开始了公钥密码体制的发展。公钥密码体制不仅可以 解决传统密码技术的密钥分配问题和大量密钥的保存问题，而且还可以解决数 字签名和身份认证问题。主要的密码交换协议是基于有限域上解决离散对数问 题( d l p ) ，在其基础上提出了许多密码体制。1 9 7 7 年m i t 的三名研究人员r i v e s t 、 s h a m i r 、a d l e m a n 就在此基础上提出了一种实用的密码体制r s a 2 1 。r s a 是 公钥密码体制的典型代表，它是基于大整数因子分解的公钥密码系统，r s a 的安 全性便是建立在此基础之上的。但是随着分解大整数因子方法的进步和计算机 技术的发展，为了确保使用r s a 的安全性，其密钥的位数一直在增加，但这使其 的实现变得复杂，所以有必要发展新的体制来慢慢代替r s a 。椭圆曲线密码体制 e c c ( e u i p t i c c u r v e s c r y p t o s y s t e m s ) ，即基于椭圆曲线离散对数问题的公钥密码体 制，最早于1 9 8 5 年由m i l l e r 秉l k o b l i t z 分别提出，它是利用有限域上的椭圆曲线有 限群代替基于离散对数问题密码体制中的有限循环群后所得到的一类密码体 制。与r s a 相比，椭圆曲线密码体制有非常大的优越性，r s a 数字签名算法及加 密算法，由于计算量大、签名速度慢，限制了它在某些领域的应用( 如i c 卡中用 r s a 算法实现是比较困难的) ，而e c c 签名算法在一定程度上避免了这些弱点。 其密钥长度短、计算数据量小、运算速度快、灵活性好，在没有协处理器的情 况下，容易在i c 卡中实现，这使得身份识别系统的安全性及易操作性大大提高； 另外，椭圆曲线密码体制有取之不尽的椭圆曲线可用于构造椭圆曲线有理点群， 且不存在计算椭圆曲线有理点群的离散对数问题的亚指数算法。因此，e c c 被认 武汉理工大学硕士学位论文 为是最具有发展潜力的公钥密码体制，而且也可能代替r s a 。超椭圆曲线密码体 制就是在e c c 基础上推广来的。它是r h n e i lk o b l i t z 于1 9 8 9 年提出的【4 】，虽然它是 e c c 的一种自然推广，但是并不是一种简单的推广，超椭圆曲线密码系统是基于 有限域上超椭圆曲线上一种称为j a c ：o b i a n 商群上的离散对数问题，要比有理点群 复杂得多，而与e c c 相比，h e c c 又有着明显的优势。 1 2 选题意义 对于企业或是个人一种好的密码体制可以更安全有效地确保他们的利益， 各种密码体制不断地被提出，目前e c c 被认为是最具有发展潜力的公钥密码体 制，而与e c c 相比来说，h e c c 具有非常明显的优势： ( 1 ) 与传统的公钥密码系统相比，在相同的安全强度下，h e c c 可以使用 长度更短的操作数。亏格为2 的h e c c ，其所基于的有限域可为9 0 - b i t ，由此所 建立的密码体制的安全性与1 6 0 b i t 的e c c 等同，远远大于1 0 2 4 位的r s a ， ( 2 ) 在同等安全水平条件下，超椭圆曲线密码要比椭圆曲线密码用的基域 小。e c c 要获得具有较大阶的有理点群，必须选取一个相应大的基域，而h e c c 可以在一个很小的基域上构造具有较大素数因子的阶的j a c o b i a n 群； ( 3 ) 可以模拟基于一般乘法群上如r s a 、e l g a m a l 等几乎所有的协议； ( 4 ) 目前对于低亏格的超椭圆曲线的攻击是指数时间的，x q g l o g q 时，i n d e x 算法的复杂度就成了亚指数时间的了 m a r kl b a u e r 将a d l e m a n - d e m a r r a i s - h u a n g 的思想推广到了任意有限域上， 当亏格较小时，i n d e x 算法的复杂度就就不再是亚指数时间的了，通过与 p o h l l a r d - r h o 方法的比较可以看出：在亏格g 4 时，还是p o h l l a r d r h o 方法比较 好。 ( 3 ) 超奇异超椭圆曲线。f r 归约攻击是对超奇异超椭圆曲线离散对数的一 种快速攻击方法。这种攻击方法是将定义在有限域g f ( g ) 的超奇异超椭圆曲线离 散对数问题转换为有限域g f ( n 上的离散对数问题，其中扩张次数蚴是只与 5 武汉理工大学硕士学位论文 超椭圆曲线亏格有关的一个整数。因此，建立密码体制时，大素数域g f ( q ) 上的 超椭圆曲线的j a c o b i a n 中不可以有口阶子群。 h e c c 在国内外都是密码学者的研究热点之一，但是它也存在着许多的问 题，例如：如何提高超椭圆曲线j a c o b i a n 上的标量乘运算，从而提高整个超椭 圆曲线密码体制的实现速度；寻找计算超椭圆曲线j a c o b i a n 的点的个数的有效 算法；超椭圆曲线密码体制的标准化。目前关键的问题便是如何减少j a c o b i a n 上 的除子加和标量乘。 1 4 论文的主要研究工作 目前来说，超椭圆曲线密码体制还是处于研究阶段，因此不论是对于除子 的标量乘运算的研究，还是超椭圆曲线密码体制的研究。都在一点一点地进步 之中。而本文主要是针对加快除子标量乘的运算以及基于超椭圆曲线密码体系 的数字签名方案的研究。现将所研究的内容及所取得的成果概括为以下几点； ( 1 ) 分析了利用有效自同态加速除子标量乘的运算，基于由l a n g e 和p a r k 提出的算法，给出了计算k = e ：。矿的方法，并且结合他们算法的优点给出了 对于特定的超椭圆曲线上的除予标量快速算法。 ( 2 ) 分析了建立超椭圆曲线密码体系所用的几个主要参数；一个有限域l ； 在l 上一条适合建立密码体制的超椭圆曲线c ；在j a c o b i a n 上的一个基点d ； j a c o b i a n 商群的阶拌j ( c ，r ) 。 ( 3 ) 提出了一种基于超椭圆曲线的数字签名方案。 ( 4 ) 实现了本文提出的基于超椭圆曲线密码体系的数字签名x h e c d s 。 1 5 论文的组织结构 在第二章中主要介绍了超椭圆曲线密码的数学背景知识，如有限域上超椭 圆曲线的定义，除子的定义及性质，超椭圆曲线的j a c o b i a n 群和除子加法运算 等等，对超椭圆曲线密码体制有了大致的了解。 在第三章中，作者利用了g t i n t e r ，l a n g e 和s t e i n 与p a r k 、l e e 和p a r k 的算 法思想1 1 2 ，1 4 1 ，得出了计算k = y 7 的方法，从而给出了一般超椭圆曲线上的 除子标量乘的快速算法，并且将这一算法与l a n g e 所提出的算法【1 2 】进行了比较。 6 武汉理工大学硕士学位论文 在第四章中论述了有关数字签名的相关内容，并且阐述了两种基于超椭圆 曲线密码体系的数字签名方案既c - e l g 锄a l 签名方案和h e c d s a 签名方 案。而且通过文献 1 4 1 q b 的普通数字签名方案，提出了一种基于超椭圆曲线的数 字签名方案。并且分析归纳了在建立系统时所用到的主要参数的选取问题。 在第五章中，主要讨论在第四章所提出的基于超椭圆曲线密码体制的数字 签名的实现。 最后作者总结了全文，并提出了未来工作的一些研究方向。 7 武汉理工大学硕士学位论文 第2 章超椭圆曲线密码体制的数学背景 超椭圆曲线是椭圆曲线的一种推广，n e a l k o b l i t z 于1 9 8 9 年首次提出的。本 章介绍了超椭圆曲线的基本数学知识，主要对是超椭圆曲线在密码学中应用的 相关内容进行了介绍，定理的证明细节可以参考文献【4 】【1 5 】。 2 1 超椭圆曲线 本节介绍了超椭圆曲线的基本定义和性质。 定义2 1 若域的元素为有限个，则称这个域为有限域或g a l o i s 域，记做b 或g f 国) 。 在文中有限域的记号b 和g f ( q ) 是不加以区分的。而最常见的有限域一般 可以分为两种类型：特征为2 的有限域里少和素数域b 。 代数闭域的概念是超椭圆曲线定义的基础之一，下面介绍它的定义。 定义2 2 令f 为一个域，f m 上的任一个多项式都可以彻底地分解为一次线 性因式的乘积。等价地，f m 上的每一个次方程都有且只有个根。那么f 便是一个代数闭域。 定义2 3f 的最小代数封闭扩域称作f 的代数闭包，记为f 。 可以证明f 的代数闭包是唯一的，例如：复数域就是一个代数闭域，它是 实数域的代数闭包。 定义2 4 1 1 6 】设f 是域，f 是其代数闭域，则f 上亏格为g ( 兰1 ) 的超椭圆 曲线c 是指具有方程形式 c v 24 - h ( u ) v = 厂( ”) ( 2 1 ) 的曲线。这里知( f m 是次数不大于g 的多项式，j ( - ) e f u 是一个次数为2 9 + l 的首一多项式，并且不存在( “，v ) i f 同时满足曲线方程( 2 1 ) 以及两个 偏导数方程2 v + 坝的= 0 和( ) ，一，( “) = 0 。如果g = l ，则称c 为椭圆曲线。 与椭圆曲线一样，在超椭圆曲线上的任何一点都是非奇异的，奇异点是指 同时满足曲线方程( 2 1 ) 以及两个偏导数方程2 v + ( 田= 0 和 ) v 一厂 ) = 0 的 点。 公理2 1 e 1 6 l 设c 是域f 上的超椭圆曲线，由( 2 1 ) 式所定义的，则： 8 武汉理工大学硕士学位论文 ( 1 ) 如果缓功= 0 ，那么c h a r ( 1 7 ) 2 。 ( 2 ) 如果c h a r ( f ) 2 ，那么变化u 一”及1 ，一v h ( u ) 2 将c 变成形式1 ，2 = 苁功，这里a e g 。 = 2 9 + l 。 ( 3 ) 设c 的方程形式为( 2 - 1 ) 且坂功= 0 及c h a r ( f ) 2 ，那么c 是一条超椭 圆曲线当且仅当，( 在域f 上无重根。 由上面的公理可以得知，经过变化甜一甜及1 ，一v h ( u y 2 ，在大素数域上， 可以得到曲线c 的简化形式v 2 = 贝妨，在后面的章节里会用到曲线c 的这种形式。 定义2 5 【l q 设k 是f 上的一个扩域，那么曲线c 上的一个k - 有理点的集 合定义为所有满足方程( 2 - 1 ) 的解( ，v ) e k k 以及符号o o ( 一个特殊的在c 上的 无穷远点) 所构成的集合。c 上所有的k 点记为集合c ( 1 ( ) ，简记为c ，在c 中 除了m 以外的点均称为有限点。 定义2 6 1 6 1 设p = ( 材，v ) 是一个超椭圆曲线c 上的一个有限点，那么它的相 反点定义为户= ( 打，- y 联v ) ) ，而将无穷远点的相反点定义为它自身，即p = m ， j 5 = o o 。如果，是一个有限点且满足p = 声，则称p 是一个特殊点，否则称p 是 一个普通点。 2 2 除子和j a c o b i a n 群 定义2 7 1 1 研一个除子d 是c 上若干点的一种形式和 d 2 w p ，怖z ( 2 2 ) 这里只有有限个整数肇非零，整数。开_ 称为d 的度数，记为a e g d ，d 在， 点的阶是怖，表示为o r d ，( d ) = 怖。 定义2 8 一个除子中点的数目称为除子的重量。 设d 表示所有除予的集合，它构成了一个加法群，其加法规则如下： m 0 + 哆只= ( + 珥) 只( 2 3 ) 露e ce , e - c 昂c 例如，设在域b 上，一条超椭圆曲线c ： 矿+ z n ，= u s + 3 矿+ 2 矿+ 6 铲4 - 甜+ 4 佗- 4 ) 一个除子为： d 2 2 ( 2 - 3 ) + 4 ( 3 ，6 ) + ( 1 ，o ) + ( 5 ，2 ) 那么除子d 的次数就可以记为： d e g ( d ) = 叻2 24 - 4 4 - 14 - 1 = 6 9 武汉理工大学硕士学位论文 记次数为0 的除子集合为d o ，即d o = d did e g d = o ) ，可以得出d o 是 d 的一个子群。 定义2 9 t 埔1 设d i 。脚，和h 2 脚，是两个除子，则d i 和d 2 的最大 公因子定义为： g c d ( d i ，蚴= p e cn l i n ( ，) ，一( 脚n l i l l ( ，) ) ( 2 - 5 ) 符号g o d ( “，1 。用来表示甜与1 ，的最大公因子，定义为： g c du ，1 ，) = m a x k ：七i 且七l 吩 定义2 1 0 【1 5 1 给定一个多项式c - ( u ，v ) - 【”，川，g ( u ，v ) 可被视为曲线上的 一个函数，在实际中，通过代入曲线的方程降低g 似，v ) 中1 ，的次数直到将g ( u ， v ) 表示为如下的形式：g ( u ，v ) = 口( 功一b ( u ) v 。设 0 ，只是一个有限点且满足以下条件：当p f e s u p p ( d ) 时，霉 不属于s u p p ( d ) 。除非只= 霉且m j _ l 。 半约化除子在其等价类中并不是唯一的，因此在超椭圆曲线中并不是用半 约化除子来表示的，而是用约化除子来表示，它可以唯一的表示j a c o b i a n 商群 中的每一个元素。 定义2 1 6 峋d 是一个形式为( 2 9 ) 的半约化除子，如果m j g ，那么d 就称 为一个约化除子或称d 是约化的。 因此，如果以下条件成立，则半约化除子d e d o 是一个约化除子： ( 1 ) 所有的m ，是非负的，并且当p j 是一个特殊点时m ，sl ； ( 2 ) 当只是一个普通点时，则只和它的相反点不同时出现在d 中； ( 3 ) 肼f 茎g 虽然j a c o b i a n 商群中的每一个元素可以用约化除子唯一的表示出来，但是 上面提出的约化除子的形式在运算中并不是很方便，因此，m u m f o r d 提出了用 多项式来表示除子的方法。 定理2 1 f 1 6 1 设d 是一个半归约除子，其中p f - ( x l ，如，珊sg ，则d 可以 由f q 中满足下列条件的两个多项式甙，6 ( 唯一地确定： ( 1 ) “是一个首一多项式，烈田= 1 1 - x i ) m l ； ( 2 ) d e 驴 g ，则置口- a ，6 pb 并返回上一步； ( 5 ) 输出d i v ( 口，6 ) 为d 。 这是两个除子的加法，其实多个除子的加和倍加也分别有两种算法，应用 得还是上面的算法，只不过是除子复合和除子约化的顺序不同而已，一种是先 将所有的除子合成，之后在将所得到的半归约化除子约化；另一种是将除子在 合成的同时也约化，之后再合成约化。文献【1 8 】中有相关的详细介绍，在此仅对 结果进行分析，由 1 8 】可知第一种算法要比第二种需多耗2 5 m ( 这里忽略了加减 所耗的时间，因为和乘除相比较加减所耗很小了，m 代表乘运算一次所耗的时 问，代表除运算所花的时间，即取逆。) 。 在超椭圆曲线上的乘运算是标量乘运算，它的形式是： m d = d + d + + d 、- - - - - - - - - 、，- - - - - - - ， m 武汉理工大学硕士学位论文 为了安全设想一般情况下取辨接近于d 或j a c o b i a n 商群的阶的整数。 对于研究超椭圆曲线密码体制除子的标量乘是很重要的，加快实现标量乘 运算对于超椭圆曲线密码体制的实用化有很大的促进。 2 5f r o b e n i u s 自同态 应用f m b e n i u s 自同态可以加快标量乘的计算速度，在此简单介绍f r o b e n i u s 自同态的定义，在第三章中会用于实现除子闻的标量乘运算。 定义2 1 7 令k 为一有限域，k ( x ) k ( x ) 是非奇异曲线x k 的函数域，那么 k ( 固，k ( x ) 定义了一个完全映射矿： 妒：x x 令k = f q ，g = ，那么x k 是一个完全的非奇异曲线，( f r o b k ) ：k ( 矽一 k ( 工) ，。这一f r o b e n i u s 映射包含了曲线的自同态、i ，：x ( ， 呻z 。矿和、l ，的串 联就导致了x 的另一种自同态o 。 定义2 1 8 令浒；是一条非奇异曲线，那么在有限域r 上x 的f r o b c n i u s 自同态定义为： o：xx 盯= j c ，矿 。可以扩展为6 ：承x ) 专- ( 工) ，：，虬耐啊寸三d q q ，其中撕r ，a , e f 0 ( x ) 。 if r o b e n i u s 映射。 设c 是定义在有限域k 上亏格为g 的方程形式为伊+ j j l ( “) v = 的超椭圆 曲线，且j ( c ，b ) 是该曲线在乓上的j a c o b i a n 群，那么在有限域岛上的f r o b e n i u s 自同构所诱导的j ( c ，f q ) 上的自同态定义如下； o ：j ( c f q ) 一j ( c f q ) d = 弓一( m , x o o ) - - , d 4 = 帆甲一( m , x o o ) 根据c 上的一个点p = ，v ) ，可以定义，= ( u o ，竹这样一个点；如果p 一- - - 0 0 ， 那么尸= m 。从而可以得到如果除子d = 咖( 口 ，那么= ( 一b o ) 。o ，l 是k 上的单位映射，因此在j ( cf g ) 上诱导的映射矿也是单位映射，在j ( c k ) 上诱 导的f r o b e n i u s 映射。的特征多项式p ( 乃如下所示： p ( t ) - - t 2 + a l t 2 s - i + a 2 t 2 。- 2 + + 吒p + q i t g 一+ + 矿- 1 a l t + q 8 ( 2 - l o ) 这一多项式是对于曲线x f q 的，而对于y l 的。的特征多项式p ( d 如下所示： p ( 丁) = r 2 。一q r 2 霉q + a 2 t 2 。一2 咚r 2 q a g i t 譬q 一q s - 1 a t t + q 。( 2 - 1 0 1 4 武汉理工大学硕士学位论文 其中= l ，嘶= 矿1 a 2 s - i ，( o s i g 例如：对于亏格为2 ，坂田= l 的超椭圆曲线c l ：伊+ v = u s + 矿，它的f m b e n i u s 自同态的特征多项式为：，( d = r + 2 t 3 + 2 t 2 + 4 t + 4 目i l 坂田= 的曲线c 2 ：1 2 + w = 矿+ l ，它的自同态的特征多项式为：p ( 乃= ，+ t 3 + 2 t + 4 i i 有效自同态妒 例1 i 爱p - - - l ( r o o d 4 ) 是一个素数，定义在有限域易上亏格为g 的超椭圆曲 线形如c l ：v 2 = 拼2 9 + + 呸j q 甜2 | - 1 + + a 3 u 3 + q 。在c l 上的映射矿可以定义为：似 谚一( “，它诱导了一个j a c o b i a n 中的有效自同态矿的特征多项式为：p ( 0 2 产+ l 。矿在j a c o b i a n 中的作用可以定义如下： 口： u 2 + a l u + a o , b l u + b o - “2 - - a l u + 4 6 l “+ i ；c 1 6 0 】 印+ a o ，b o l _ m a o , r - o l _ a o 例2 设p ；1 ( r o o d 5 ) 是一个素数，定义在有限域昂上亏格为2 的超椭圆曲 线形如c ：1 ，2 = 矿+ 口。在c 2 上的映射矿可以定义为：( ，一晒甜，d ，它诱导了 一个j a c o b i a n 中的有效自同态。妒的特征多项式为：p = ，+ ，+ t 2 + f + l 。矿在 j a c o b i a n 中的作用可以定义如下： 矿：i n 2 + 口l 甜+ a o , b l + 6 0 1 【铲+ 5 口l 甜+ 5 2 a o , f 1 扣l 甜+ b o 阻+ a o ，b o _ + 瞳嗨6 0 】 例3 设p ；l ( r o o d8 ) 是一个素数，定义在有限域昂上亏格为2 的超椭圆曲 线形如g ：v 2 = 矿+ a n 。在c 3 上的映射伊可以定义为：似v ) 一簖材，8 v ) ，它诱 导了一个j a c o b i a n 中的有效自同态。妒的特征多项式为：p ( f ) = ，+ l 。矿在j a c o b i a n 中的作用可以定义如下： 矿： u 2 + 口l + a o ，b t u + b d 【矿+ p 8 口l 甜+ 白4 a o , 白- 1 6 l 甜+ r ，8 b o 【甜+ a o ，b o 】【u + r 8 印，白1 6 0 】 2 6 小结 本章详细介绍了有关超椭圆曲线及其上的j a c o b i a n 群的基本数学知识和除 子类加的c a n t o r 算法，如有限域上超椭圆曲线的定义及性质，除子的定义及性 质等。还简单的介绍了除子的标量乘以及利用f r o b e l l i l l s 自同态加速除子标量乘 武汉理工大学硕士学位论文 第3 章f r o b e n i u s 有效自同态加快除子标量乘算法 k o b l i t z 建议将超椭圆曲线的j a c o b i a n s 商群应用到密码学之中，相对于椭圆 曲线来说，它所需较小的域，而且在建立密码体制时有更多的曲线可供选择。 而在超椭圆曲线密码体系中最费时的运算便是标量乘的运算惫d ，其中d 是 在j a c o b i a n 群上的除子。为了加快标量乘的运算速度，人们引用了f r o b e n i u s 自 同态来加快算法的实现。而对于在j ( c f q ) 上的f r o b e n i u s 自同态的特征多项式 p ( d 应该是不可约的，因为根据w e i l 定理【1 9 】可得，若特征多项式可约，那么j ( c k ) 的阶将至少是由两个以上的大素数的积构成的，或是由若干个小素数的积组 成，在这样的有限域上是不适合建立密码体系的。因此，在本文中所引用的特 征多项式都是不可约的。 k o b l i t z 提出了定义在二进制域上的曲线 2 0 j ，但是该曲线的坐标可以适合更 大的扩展域，称为k o b l i t z 曲线。g i i n t e r ，l a n g e 和s t e i n 将这一k o b l i t z 曲线推 广到了超椭圆曲线上口。他们提出了对于特殊的一条曲线1 ，2 + w = 矿+ a f + l 的关于f r o b e n i u s 自同态算法。而l a n g e 和c h o i e 与l e e 也提出了关于f r o b e n i u s 自同态的有效加快标量乘算法【1 2 捌，而且还将其推广到了任何特征的有限域上。 g a l l a n t , l a m b e r t 和v a n s t o n e 提出一种利用具有有效自同态的特殊椭圆曲线 来加速椭圆曲线上的有理点乘的算法田】。而p a r k 、j e o n g 和l i m 将这一思想推广 到了超椭圆曲线上【2 4 】，利用有效自同态加快了标量乘运算速度。p a r kt - j ，l e e m k 和p a r kk 利用同种思想提出另一种有效的加速除子标量乘的算法【1 4 1 ，计算 除子d 和整数k 的乘积加l ，其中_ | 的展开式为k = 罗：，系数r j 满足如下的 式子：+ p + r j 2 矿+ r , 3 p 3 或是o + l y + 2 f + 3 t 3 ( r e z ) ，p 、丫是在文献【1 3 】中 用到的有效自同态。 本章利用了g - t i n t e r ，l a n g e 和s t e i n 与p a r kt - j ，l e em - k 和p a r kk 的算法 思想，得出了计算式k = y ：。矿的方法，从而给出了一般超椭圆曲线上的除子 标量乘的快速算法。 1 6 武汉理工大学硕士学位论文 3 1 格子 设c 是有限域f 叮上，亏格为g 的超椭圆曲线，那么在有限域k 上的f r o b e n i u s 映射所诱导的j ( c ，f q ) 上的映射。的特征多项式p ( d 为： ，( d = 严+ q r 2 l 卅+ 啦r 。_ 2 + + a s t 譬+ q a s _ f s - z + + 9 一q ，+ 9 5 ( 3 - 1 ) 其中伽= 1 ，通过牛顿公式可得：蛔；踊+ & l a l + + $ 1 a i - i ，s = ，一仃+ 1 ) ，l s i g 且川- l 五( 乃m 。 令。是多项式p 0 3 的一个根，那么p ( 力= 0 ，可得： g 譬d = 庐( d ) - a l o 2 。一1 ( d ) - - - - a g c r s ( d ) - _ a l q ( s - 1 ) o ( d ) = o c o ( o ( d ( d ) + q d ) + 毋d ) + + a l q s - i d ) 这样就可以得到一个m 展开式o j ( d ) ，推广一下，这一思想不止可以表示矿也可 以表示任意的整数。令f 也是多项式p ( 乃的一个根，那么就可以将m d 中的m 表示成关于t 的一个线性展开式酞d ) 。对于在z 【f 】中的元素可以用如下方式表 示：c = c o + c l t + + 乞。1 t 2 9 - i ，o z 引理3 1 【切c = c o + c l f + + 色。1 f 2 纠整除b 有且只有碉c 。 证明：令矿陋 如果存在任意的i z ，自j l i a c = q 。；+ 叩+ + c 2 。- l f 2 一 从而可得： f = ( f g q t 2 9 - i 一二一f 窖一一q q s - l t ) ；i + c l t + + c 2 s _ 1 f s - i = “( q a a q s - 1 一c , ) + + ( 勺一口| _ ) t 1 4 + + ( c 州一q i h 缸4 一豕2 一) 那么便可以证得咖。 在分析亏格g = 2 的情况之前，先分析一个2 9 维格子，所有的元素均属于 z 有一组蔬a 净 ( 羔i - o 佛，蓦“卜z ) ，可以得出在这一个碟l l o j 组中任何两个元素的和或是向量之间的整数乘都在元素组a 中，因而这些元素 在q 就形成了一个格子这就可以推出2 维和4 维的格子，如果 w l ，w 2 ) 是一 个2 维格子l 在z 上的基量，那么可以令l = p l ，w 2 。同样的，如果 w i ，w 2 ， w 3 ，w 4 是一个4 维格子l 在z 上的基量，记为l = l ，w 2 ，坳，w 4 。对于l = 【w l ，w 2 可以令t l w i + t 2 w 2 ，其中0 s sl ；而对于l = w l ，w 2 ，w 3 ，州可以构 1 7 武汉理工大学硕士学位论文 成一组t l w l + t 2 w 2 + t 3 w 3 + t 4 w 4 中所有的点，