（基础数学专业论文）超椭圆曲线的密码学应用.pdf

s c h o o lc o d e ：1 0 2 6 9 a c a ( 1 e m i cn u m b e r ：5 1 0 8 0 6 0 1 0 4 3 e a s tc h i n an o r m a lu n i v e r s i t y s o m e c r y p t o g r a p h i ca p p i c a t i o n so f h y p e r e p t i cc u r v e s d 印征衄c n t ： m 萄叱 s u 巧e 优 s u l 椰s o c a s s 0 c i a ：t ep r o f e s s o ry a n gs i n l 觚 m 硒t e rc 锄d i d a t e ：l il e i 2 0 1 1 4 嗍6舯9 胂7m 3 删m唧y 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文超椭圆曲线的密码学应用，是在华东师范大 学攻读蚴博士( 请勾选) 学位期间，在导师的指导下进行的研究工作及取得的研 究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过 的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明 并表示谢意。 上7 作者签名：丝日期：功f s 蝥作者签名：耋魄日期：塑! ! ：酆 华东师范大学学位论文著作权使用声明 超椭圆曲线的密码学应用系本人在华东师范大学攻读学位期间在导师指导 下完成的巧往博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学所有。 本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相关 机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版：允许学位 论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全 国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出 版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文幸，于 年月日解密，解密后适用上述授权。 ， x 乃2 不保密，适用上述授权。 学位论文作者签名：导师签名： 日期：2 。f s 1 9 日 涉密学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文涉密审批表方为有效) ，未经上 述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适 用上述授权) 。 鸯庑硕士学位论文答辩委员会成员名单 姓名职称单位备注 谈1 螺、袭揖哗东帏苏鳟 主席 雅盔教寂珲畚邦屯蜉 锄；色固 爱披辞东玮勉火孚 华东师范大学 超椭圆曲线的密码学应用 摘要 近年来，椭圆曲线和超椭圆曲线密码体制已得到广泛研究和实际应用在2 0 0 9 年欧密会上，g 妇a i 也等人在大素数特征域上的一大类椭圆曲线上构造了一种快速 可计算自同态他们的研究表明，应用该自同态可以加速椭圆曲线密码体制的点乘运 算另一方面，秘密共享是信息安全领域中重要和基本的研究课题之一，描述秘密共 享方案的存取结构的特征是该领域中的一个公开问题c h 等人完全确定了椭圆秘 密共享方案的存取结构 本文将g a j l ，r a j 血等人的快速自同态构造方法推广到偶特征域亏格2 的超椭圆曲 线上，并提出了一个密钥生成算法实现基于该方法的快速除子点乘本文还将q 明 等人的方法推广到任意亏格超椭圆曲线的j 础i 趾上我们的结论覆盖了有关椭圆秘 密共享方案存取结构的结果 关键词：超椭圆曲线；快速可计算自同态：m 呱l f 矾表示；秘密共享；存取 结构 i 华东师范大学 超椭圆曲线的密码学应用 a b s t r a c t ki c o e n ty 璐e l h p t i c 粕dh y p e r e l l i 砸cc r y p t o s y s t 锄h a v eb c e x t 跚s h e l ys 似d i e d 柚d d 印1 0 y c di n 也er e a lw o r l 正he 切r o c r m 盯2 0 0 9 ，g a l b r a i 血，u n 觚ds c o nc o n s 仇l 曲甜 锄e 伍c i 踟d yc o m p u 试l cc n d 0 1 0 i p k s mf o ral a r g ef 缸l i l y0 fe l l i 皿c 伽m sd e f n e d a v c r f i n 沁f i e l d s0 fl 鹕ec h 啪c t 耐s t i c n e yd c m 伽s 觚t c d 1 a t 山c 锄d o m o 叩l l i s mc 卸b e 璐e d t 0a c c e l 嗽t es c a l 缸m l l l 邱l i c a t i i nm ee 玎i p 血c i l r v ec r y p t o s y s t 锄b 舔e do nm e s ec 盯v c s s e c r c ts h a 血gi s 衄细i p 嘣粕t 眵y p t 0 旷a p h i cp r i m i t i _ v e o n e0 ft h cm 血叩衄p m b l 黜吣i n s 嘴ts h a 血gi s 血ec h a 功曲枷0 f 也ea c c e s ss 仇l c t u 豫s0 fi d e a ls c c r c ts h a r i n gs c h 即舱s a 姗，u n g 蛆dx i n gc 伽哦耐yc h 绷l c l 谢2 e dt h ea c c 髓s 咖咖r c sf b rt h ce u i p 雠s r e t s h a 血gs c h 锄e s 舶ma l ge _ b r a i c g e o m e 缸i cc o d 髓硒s o c i a t e d 研也e m p d c c u r v 髓 h t l l i s 蛐w e t a m t h e m 枷o f g a i b r a i 也e ta 1 t oa n y g 锄璐2 h y p e 蛐血c i l r v e d c f n c do v c ra 霸i l i t c 币e l d0 fc v 锄c h a 均c t c i i s t i c w 已p p o 柚e 币c i e n ta ：k 耐也mt og 髓眦 a 瑚d o mg 衄璐2h y p 蛐d c r v e 锄di t sq l l 批铆i s te q _ i l i p p c dw i m a 缸t 即d 锄。卜 皿i i s m 血c j o b i 锄；s e c m y w e g 池t h e 础i m o d0 f c h e ta 1 t o t h e j 痢b i 趾s0 f h ) r p 鲫蛳c c u r v e so fa n yg 咖s o 叮r e s l l l ti n c l u d 豁t l l e c c s ss 仇l c 眦e s0 f 州c s 9 c r e t s h a r i n g h a 珊笛舔as p l 晒a lc 雒e 华东师范大学超椭圆曲线的密码学应用 1 1 研究背景 第一章概述弟一早僦逊 近几年来，超椭圆曲线在密码学的多个领域中得到了广泛深入的研究和应用超 椭圆曲线的j 北o b i 卸为基于离散对数问题( d 的公钥密码学提供了一种快速安全的 加群结构，基于超椭圆曲线的代数几何码也逐渐在安全多方计算中引起越来越多的 学术关注与传统的椭圆密码体制相比，超椭圆密码体制饵坼圮删砸cc 聊t o s y s t e m s ) 的密钥长度更短，可供选择的适合密码学需要的曲线类型更加丰富，因此超椭圆密 码体制具有更大的应用潜力超椭圆曲线密码体制最早于1 9 8 9 年由勖b l i 乜【1 3 】提出， 它是利用超椭圆曲线的除子类群代替椭圆曲线上的点群构造的一种公钥密码体制在 超椭圆密码体制中最基本、最耗时的运算是删趾上的点乘运算( 也称为标量乘法 运算) ，即将超椭圆曲线j 0 _ b i 蛆上的除子d 自相加七次，记作【七】d 计算点乘的最一 般的算法是倍加算法( d 伽悦e a n d a d dm 巴也0 d ) ，如果点乘系数七的二级制长度为l 那 么使用倍加算法计算点乘【七】d 平均需要对除子d 进行z 次二倍点运算和z 2 次点加 运算。目前，大量的算法已经被提出以加速椭圆曲线上的点乘运算，其中利用偶特 征数域上椭圆曲线的琦0 ：b 阻硫快速自同态加速点乘算法的思想首先被 b h t z 提出， 这类曲线因此也被称为k 曲l i 亿曲线【1 4 】g u n t l l 妇g e 和s t e i n 【9 】将这一方法推广到 超椭圆曲线上g a l l 卸t i a m b e n 和v - 趾s t e ( g 【聊【7 】的方法表明某些特殊的可计算快 速自同态驴，通过所谓的g l 分解【七】d = 】d + 【七l 】烈d ) ，其中，七l 二进制长度大 约是七的一半，可以用于加速某些特殊的椭圆曲线上的点乘p a r k 等人【2 3 】将g l v 方法推广到超椭圆的情况下，同样得到了较好的加速效果相关的结论和算法读者可 以在【1 6 】和【2 7 】中找到 尽管如此，g l v 方法适用的确切对象很有限，事实上该方法只适用于非常特殊 的几类曲线( 可参看【2 5 】的第七章) n j i m a m a t s ，c h 和t s u j i i 【1 2 】提出了一种构造 椭圆曲线的二次扭曲曲线( q i l a d 枷c 铆i s tc u r v e s ) 上的f r o b e n i u s 自同态的方法，该方 法构造的自同态称为s 蛔f 】b i u s 自同态最近，g a l b r a i 血，l j n 和s c o n ( g l s ) 【6 】将 华东师范大学超椭圆曲线的密码学应用 这一自同态应用于g l v 方法，加速点乘运算，同时也扩大了g l v 方法的适用范围 同l 【d b h t z 曲线相比，g l s 曲线是一大类定义在素域上的椭圆曲线1 ( 0 z a l d ，m a t 如。和 s h i 】m b m 【1 5 】注意到构造s 虹w f r o b 即i u s 自同态的方法可以推广到定义在素域上的 超椭圆曲线上，但是他们没有将这一方法应用于g l v 方法h 枇，i r a _ b i n a 和 m 朗e z e s 【1 1 】研究了如何在偶特征域椭圆曲线上应用g 】鉴方法，并证明通过缸v 分 解该方法可以加速偶特征域椭圆曲线上的点乘运算同时，在安全性方面，他们也证 明g l s 曲线对一般的g h sw 醯d e s c c n t 觚a c k 【8 】是安全的 另一方面，包括超椭圆曲线在内的一些代数曲线可以用于构造安全多方计算中 的秘密共享方案( s s s ) 秘密共享( s r e ts h a 咖曲是密码学中重要而基本的研究课题之 一，秘密共享方案就是在一组参与者( 或称用户p l a y 神中分配秘密( s 删的一种方 法在秘密共享方案中，根据不同的实际需要，要求只有那些授权的参与者集合( 即授 权集q u a l ie ds u b s e t ) 才能根据其中参与者掌握的秘密片段( s h a r e s ) 恢复秘密，而所有 授权集的全体就称为该秘密共享方案的存取结构( 孔c 髓ss 缸u c t i 】r ) 如何描述秘密共享 方案存取结构的特征是秘密共享研究中的主要的开放问题之一m 部s c y 首先考虑用编 码理论中的线性码理论研究线性秘密共享方案的存取结构【1 8 】【1 9 】在2 0 0 6 年的美密 会上，c h 朗和c r 锄盯【2 】提出用代数几何码构造秘密共享方案( 即代数几何秘密共享 方案) ，该方法实际上是s h 蛐l i r 方案【2 4 】的一般化尽管如此，【2 】中提出的方案是一 个所谓的呻方案，即在该方案中，任何小于n 个用户组成的用户集都不属于存取 结构，任何大于等于如个用户组成的用户集都属于存取结构而对于那些包含f 个用 户以sf f 2 的用户集，人们一般无法确定其是否属于存取结构【2 】中的结论说明， 用一般曲线构造的代数几何秘密共享方案存取结构的未知空白f 2 一f l 的大小为幻，这 里g 是构造代数几何码的代数曲线的亏格最近，由椭圆曲线构造的椭圆秘密共享方 案的存取结构被完全确定了【3 】 本文的第一个工作是将g l s 方法推广到偶特征域上的所有的亏格2 超椭圆曲线 上进一步，我们还给出了高效的算法去实现这一方法，并且进行了效率分析 本文的另一工作是将【3 】中的方法推广到任意亏格的超椭圆曲线上，部分确定了 基于超椭圆曲线的秘密共享方案的存取结构，对大小介于【万一d e g ( g ) ，万一d e g ( g ) + 朗 的用户子集完全确定了其是否为授权集合，由我们的结果可以推出【3 】的结论 1 2 概念和定义 在这一节中，我们将总结与本文有关的一些定义和结论希望了解更详细知识的 2 华东师范大学超椭圆曲线的密码学应用 读者，请查阅【2 0 】 1 2 1 超椭圆曲线 令玛是有g 个元素的有限域，羁是k 的代数闭包在本文中，我们总假设 鼋= 2 7 ，其中f 是素数 定义1 1 ( 超椭圆曲线) 如果在仿射坐标下亏格为g 的光滑曲线c 满足方程 c ：y 2 + 日y = ， ( 1 1 ) 其中日，【羽，是首一的，且d c g f = 2 9 + 1 ，d c g 日g ，则称曲 线c 为定义在如上的超椭圆曲线 定义1 2 令是玛的刀次扩域，如果p = 似y ) e 码码的坐标满足超椭圆曲线c 的方程( 1 1 ) ，则称p 为超椭圆曲线c 的码一有理点曲线c 的所有一有理点以及无 穷远点( 记为或d ) 组成的集合记为c ( ) ，特别的，c ( 瓦) 也简记为c 除去无穷 远点外的有理点称为有限点 定义1 3 ( 典范映射) 令p = 伉力是超椭圆曲线c 的有理点，则自反映射p = 瓴y ) h 尸= 瓴- y 一日) 称为超椭圆曲线c 的典范映射点p 称为点p 的逆点特别的，当 p = 时，规定p = 超椭圆曲线的j a c o b i 趾上有明确形式的加群结构，下面给出超椭圆曲线j a c 0 惋蛆 的有关定义 定义1 4 ( 除子，除子群) 曲线c 的除子是c 上点的形式和 d = 却p ，却z 其中只有有限多个点p 使却不为零整数p e c n ，称为除子d 的次数，记为d c g ( d ) 曲线c 上的所有除子形成一个a b e h 姐群，记为d c 如果对任意矿g a l 廊) ，都 3 华东师范大学 超椭圆曲线的密码学应用 有吠d ) = d ，则称除子d 定义在码上，所有定义在上的除子组成d c 的一个子 群，记为d c 吩) 定义1 5 ( 零除子，主除子) 次数为零的除子称为零除子，d c 吩) 中所有零除子组成 d c 吩) 的一个子群，记为d 2 既) 设，为曲线c 的有理函数域中的函数，则零除子 咖= p e c v p p 称为有理函数，所对应的主除子，其中v ，是，在点p 处的赋 值所有定义在码上的主除子形成d 芒吩) 的一个子群，记为p c 吩) 定义1 6 ( j 孔妇加群) 令c 是定义在f 覃上的亏格g 超椭圆曲线，商群j c 既) = d 罢西) p c 吩) 称为c 的定义在上的j 跹o b i 锄它是一个b 上的g 维a b e h 趾簇 超椭圆曲线j o b i 锄中的元素习惯上也称为j a c o b i 皿上的点，它是超椭圆曲线 的零除子类，其中的代表元是被称为约化除子的一类特殊的零除子而在密码学 上，为了计算的方便，通常将一个约化除子写成两个上多项式的组合的形式，即 m 衄怕r d 表示【2 2 】超椭圆密码体制中的点加运算所处理的点就是由m 叨1 f b r d 形式表 示的下面我们给出这些概念的具体定义 定义1 7 ( 约化除子) 令c 是定义在玛上的亏格g 超椭圆曲线，如果c 的零除子满足 d = 憾只一侄聃) ，这里呐o 慨g ，p f 是c 的有限点，且如果只s 印p ( d ) 那么只薯蹦即( d ) ，除非只= p j ，这时慨= 1 ，则称d 是c 的约化除子 根据m 舢一r 0 c h 定理，超椭圆曲线c 的每一个零除子都与唯一一个约化除子 线性等价( 见【2 6 】) 约化除子有m 咖1 f b r d 表示，定义如下： 定义1 8q 如m f 砌形式) 【2 2 】设d = 佻p l 一晓，l i ) ，其中只= 瓴，) 7 i ) 是超椭圆曲线 c 在f 孽上的约化除予，则d 可表示为唯一的一对上的多项式“和，记为 d = ，1 ，) ，其中h = 兀 。船州d ) ( x 一蕾) 魄，如g ( 窖+ 1 ) 2 ，i 舞j c ；吩) ，对任意d k ) 【r 】我们有妒( 功= 【御d ， 其中炉+ l 兰o ( m o dr ) 证明以下对每一种类型的超椭圆曲线我们分别给出证明 假设c 是第一型超椭圆曲线，令除子d k 吩) ( 即蜥，峰) ，由( 2 3 ) ，( 2 4 ) 和( 2 5 ) ，可得驴2 ：( i l o ，) h ( 1 1 0 ，+ ( 矿+ 谚嵋+ ( 扩+ 回l l o + + d ，( h 1 l o ，v l ，v o ) h m l ，l l o ，1 ，i + + 们h l + ( 矿+ 回，v o + ( 矿+ d l o + ( 鼋2 + 0 ) 由于矿+ y = t r 略肥( 呓) = l ， 1 3 乃q d + 西 + + 嵋憎_嵋蝾懈研 一 h 华东师范大学超椭圆曲线的密码学应用 矿+ 万= ( 伊+ y ) 口3 = 国以及+ = ( 扩+ d 2 + ( 扩+ 回口3 + ( 伊+ 伽5 = 口5 ，所以 扩：( 1 1 0 ，) 一( 1 o ，v o + h j + 口3 l l o + 口5 ) ( “l 呦，v l ，v o ) h 似i 脚，1 ，i + “l + 口3 ，v o + l l o + 口5 ) 另一方面，如果d = ( x + l l o ，v o ) ，则一d = + l i o ，磐+ 口3 x + 口5 + ( ，州x l o ) ) = ( x + l l o ，v o + 瑶+ 口3 1 1 0 + 口5 ) = 妒2 ( d ) 如果d = ( 妒+ l x + l l o ，1 ，l x + ) ，则 一d = 僻+ l i l x + l l o ，磐+ ( 口3 + v 1 ) x + 口5 + v o ( m d d 铲+ m l x + 1 1 0 ) ) = 俘+ “l x + l l o ，( v l + m l + 口3 ) x + + l 0 + 嬲) = 妒2 ( d ) 假设c 是第二型超椭圆曲线，用同样的方法可得扩：( 1 1 0 ，) 一( 1 1 0 ，+ 口3 l l o ) ，( 醒l l o ，1 ，l ) 一( 砧l 蜘，1 ，l + 口3 ，v 0 ) 当c 是第三型超椭圆曲线时，同样的有 妒2 ：( i o ，v 0 ) h ( 1 i o ，v o + 口5 ) ，( h l l o ，1 ，l v o ) h0 l ，l i o ，v l + 口5 ) 所以在这两种情况下 都有妒2 ( d ) = d ，这里d ej c l 吩) 最后，由h 勰s e 删定理可知国一1 ) 4s 群j c l 吩) 臼+ 1 ) 4 如果素数r 幻+ 1 ) 2 ， 那么由，2 十地) 可知j c l 吩) 有唯一的r - 阶子群因此存在整数a 【0 ，r 一1 】满足 认d ) = d ，这里d k 吩) 【r 】综上一d = 扩( d ) = 防】d ，铲+ 1 三o ( m o d ，) 推论2 4 对于定理2 3 中的a ，我们有a = ( g 一1 ) 一1 c r l ( c 2 1 一鼋2 ) ( m o dr ) 证明由定理2 2 和定理2 3 ，我们有+ c l 驴+ c 2 矛+ 卯l a + 矿三o ( m o dr ) ，矛三 一l ( m o dr ) 因此五兰臼一1 ) 一1 c f l 娩一l 一矿) ( m o d ，) 下面的命题给出了如何计算j c l 啡) 的大小 命题2 5 设c 是定义在如上的超椭圆曲线，m = 杞峨) ，捣= 杞啡) 那么 棚b 吩) = ( 1 + c 2 + 矿) 2 一( c l + c l 咖2 2 ( 2 c 2 一碍) ( 1 + 矿) ，这里c l = m l 一鼋，c 2 = ( 如一1 一矿+ 碍) 2 证明c 玛的l 多项式以乃= 1 + c l r + c 2 r + c l 留r 3 + 矿一，这里c l = m l 一1 一g ， c 2 = ( 尬一l 一鼋2 + 砰) 2 设以d 可以分解因式为( 1 一口l d ( 1 一口l d ( 1 一砚乃( 1 一眈d ，那 么舸c ) = 以1 ) = 1 + c l + c 2 + c l 垡+ 矿，舸c 啡) = 如( 1 ) = ( 1 一砰) ( 1 一砰) ( 1 一) ( 1 一暖) = 以1 ) “一1 ) = ( 1 + c 2 + 鼋2 ) 2 一( c l + c 1 种2 假设曲线c 的矿一阶f r 蛐s 映射的特征多项式为p ( d = p + 6 l r 3 + 如r + 鼋2 6 l r + 矿那么曲线g 的鼋2 - 阶f r o b c ：n i u s 映射的特征多项式为以一n = p 一6 l p + 1 4 华东师范大学 超椭圆曲线的密码学应用 输出：z ，g ，驴，t 2 托p e a t 3 随机选择口3 ，仍，口8 以及口l o 玛 用v e i r c 卸t c i 蜘的算法计算关于c 玛的( 1 3 ) 中的c l c 2 4 随机选择口i f 2 卫满足t r 瞄砚( 哎) = 1 5 由( 2 1 ) 计算m 五s 6 由( 2 2 ) 计算口；，口；o 7 令g ：l ，2 + a p + 口3 x + 口5 ) y = f + 口；掣+ 口；x + 口：o 8 由( 2 8 ) 计算f = 舸g 0 睁) 9 衄位 f = 帆这里，是大于( g + 1 ) 2 的素数 1 0 通过( 2 3 ) ，( 2 4 ) ，( 2 5 ) 定义妒 1 1 令a = ( g 一1 ) _ l c r l ( q 一矿一1 ) r ) 1 2 r e t u 珊z ，c l ，以a 6 2 丁2 一矿6 l 丁+ 矿因此c f 脚的l 多项式为1 6 l 丁+ 如严一6 l 矿p + 矿p ，并且有 厶( 乃= 1 + 6 l 丁+ 幻丁2 + 6 l 鼋2 r 3 + 矿p 于是我们有舸c ；吩) = 以c f ；1 ) = 1 一易i + 玩一6 l 鼋2 + 矿= 灯c 吩) 一2 ( 6 l + 易l 鼋2 ) ， 这里易l = 2 c 2 一砰因此有 # j c ；吩) = ( 1 + c 2 + 矿) 2 一( c l + c l 咖2 2 ( 2 c 2 一砰) ( 1