（基础数学专业论文）椭圆曲线密码中标量乘与双线性对的快速算法研究.pdf

摘要 椭圆曲线密码中标量乘与双线性对的快速算法研究 专 业：基础数学 博士生：林惜斌 指导老师：王燕鸣教授 s t e v e ng a l b r a i t h 教授 摘要 近年来，椭圆曲线密码成为公钥密码研究的重要领域之一椭圆曲线密码系统也在实 践中得到广泛应用而应用中的关键问题就是在保证安全的前提下如何提高系统效率目 前应用中的椭圆曲线密码，有两大类基本运算：点的标量乘运算和基于椭圆曲线的双线性 对计算本文从密码系统的快速实现出发，研究了这两类运算的快速算法，取得如下结果： 利用定义在扩域上的椭圆曲线，构造了可高效计算的椭圆曲线上有理点群的自同 态矽：( p ) 一( 尸) 利用该自同态结合g l v 方法实现对标量尼的分解，从而减少了运算 时所需的循环次数，较大地提高了计算速度 利用复乘方法，提出了一类嵌入次数为k = 3 i 椭圆曲线的构造方法在a e s1 2 8 的安全 度之下，在该类曲线上计算双线性a t e 对所要求的m i l l e r 循环长度在目前已有的文献 中是最短的在此类椭圆曲线上，本文提出了有针对性的优化算法这些优化算法使 得这类曲线能有效地应用于a e s1 2 8 安全度下的双线性对计算 提出计算双线性对的一种全新方法该方法适用于嵌入次数为偶数的一类椭圆曲线 新算法在计算双线性对时只需要椭圆曲线上点的x 坐标这与椭圆曲线标量乘只需要 点的x 轴坐标的蒙哥马利算法相对应理论分析和实验数据表明，在同样考虑点压缩 的情况下，新算法在一类嵌入次数k = 2 的椭圆曲线上计算双线性对的速度要快于传 统的m i l l e r 算法 本文考虑了实模型下超椭圆曲线上双线性的实现本文采用嵌入次数k = 6 的超奇异 超椭圆曲线，对在其上的双线对实现提出了一些优化算法作为比较，该研究同时给出 嵌入次数k = 3 的超奇异椭圆曲线上双线性对的优化方法本文给出了在同一平台上 实现这两种双线性对计算的效率对比 关键词：椭圆曲线密码，标量乘，双线性对，超椭圆曲线 标量乘与双线性对的快速算法研究第i 页，共1 1 8 页中山大学博士学位论文 英文摘要 r e s e a r c ho nf a s ta l g o r i t h m sf o rs c a l a rm u l t i p l i c a t i o n a n dp a i r i n gi ne l l i p t i cc u r v ec r y p t o g r a p h y m a j o r ： n a m e ： s u p e r v i s o r ： m a t h e m a t i c s x i b i nl i n p r o f y a n m i n gw a n g p r o f s t e v e ng a l b r a i t h a b s tr a c t d u r i n gt h el a s tt h r e ed e c a d e s ，e l l i p t i cc u r v ec r y p t o g r a p h yh a sb e c o m eo n eh o tt o p i ci n t h er e s e a r c ho np u b l i ck e yc r y p t o g r a p h y e l l i p t i cc u r v ec r y p t o g r a p h yh a sa l r e a d yb e e nu s e d i np r a c t i c a la p p l i c a t i o n s a sf o ra p p l i c a t i o n so n ei m p o r t a n ti s s u ei sh o wt oi m p r o v et h e e f f i c i e n c yw h i l em a i n t a i n i n gt h es e c u r i t y e l l i p t i cc u r v ec r y p t o g r a p h yh a st w of u n d a m e n t a l o p e r a t i o n s ，n a m e l yp o i n ts c a l a rm u l t i p l i c a t i o na n dc o m p u t a t i o no fb i l i n e a rp a i r i n g s t h i s w o r kf o c u s e so nf a s ta l g o r i t h m sf o re f f i c i e n ts c a l a rm u l t i p l i c a t i o na n dp a i r i n gc o m p u t a t i o n t h ef o l l o w i n ga r et h em a i nr e s u l t s ： u s i n ge l l i p t i cc u r v e sd e f i n e do v e re x t e n s i o nf i e l d ，w ec o n s t r u c te f f i c i e n th o m o m o r p h i s m o nt h eg r o u po fr a t i o n a lp o i n t so nt h ec u r v e 矽：( p ) _ ( p ) w i t ht h eh o m o m o r p h i s m ， w ea p p l yt h eg l vm e t h o dt od e c o m p o s et h es c a l a rk t h i sr e d u c e st h el e n g t ho ft h e s c a l a r ，t h u ss i g n i f i c a n t l yi m p r o v e st h es p e e do fs c a l a rm u l t i p l i c a t i o n u s i n gc mm e t h o d ，w ep r o p o s et h em e t h o dt oc o n s t r u c tp a i r i n g - f r i e n d l ye l l i p t i cc u r v e s o fe m b e d d i n gd e g r e ek = 3 a tt h es e c u r i t yl e v e lo fa e s1 2 8 t h em i l l e rl o o po f c o m p u t i n gt h ea t ep a i r i n go nt h i st y p eo fc u r v e si st h es h o r t e s tc o m p a r e dw i t hc u r r e n t l i t e r a t u r e w ep r o p o s eo p t i m i z a t i o nm e t h o d sf o rt h ea t ep a i r i n gc o m p u t a t i o no nt h i s t y p eo fc u r v e sa n ds h o wt h a ti t i sp r a c t i c a lt ou s es u c hc u r v e sa tt h es e c u r i t yl e v e lo f a e s 】2 8 w ep r o p o s ean e wm e t h o dt oc o m p u t ep a i r i n g s t h i sm e t h o da p p l i e st oe l l i p t i cc u r v e s o fe v e ne m b e d d i n gd e g r e e s s u c ham e t h o do n l yr e q u i r e sz c o o r d i n a t eo ft h e p o i n t sf o r p a i r i n gc o m p u t a t i o n t h i sc o r r e s p o n d st om o n t g o m e r y ss c a l a rm u l t i p l i c a t i o n ，w h i c h r e q u i r e so n l yx - c o o r d i n a t eo ft h ep o i n t t h e o r e t i c a la n a l y s i sa n di m p l e m e n t a t i o nr e s u l t s h o wt h a tw h e nc o n s i d e r i n gp o i n tc o m p r e s s i o n ，o u rm e t h o di sf a s t e rt h e nc o n v e n t i o n a l m e t h o dw h e nt h ee m b e d d i n gd e g r e ei sk = 2 标量乘与双线性对的快速算法研究 第i i 页，共1 1 8 页中山大学博士学位论文 英文摘要 w ec o n s i d e rp a i r i n g so nh y p e r e l l i p t i cc u r v e sg i v e nb ya r e a lm o d e l w eu s es u p e r s i n g u - l a rh y p e r e l l i p t i cc u r v e so fe m b e d d i n gd e g r e e 尼= 6a n dp r o p o s eo p t i m i z a t i o nm e t h o d s f o rt h ec o r r e s p o n d i n gp a i r i n gc o m p u t a t i o n f o rc o m p a r i s o nr e a s o n ，w ea l s oc o n s i d e r p a i r i n g so ns u p e r s i n g u l a re l l i p t i cc u r v ew i t he m b e d d i n gd e g r e ek = 3 w ea n a l y s i st h e e f f i c i e n c yc o m p a r i s o no np a i r i n g so i ls u c ht w ot y p e so fc u r v e s k e y w o r d s ：e l l i p t i cc u r v ec r y p t o g r a p h y , s c a l a rm u l t i p l i c a t i o n ，p a i r i n g ，h y p e r e l l i p t i c c u r v e 标量乘与双线性对的快速算法研究 第i i i 页，共1 1 8 页中山大学博士学位论文 原创性及学位论文使用授权声明原创性及学位论文使用授权声明 原创性及学位论文使用授权声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 学位论文作者签 吼冲厂 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版， 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院 系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采 用复印、缩印或其他方法保存学位论文。 学位论文作者签名 日期力下阳7 日 导师签名： 日期：年月目 标量乘与双线性对的快速算法研究 第3 页，共1 1 8 页中山大学博士学位论文 第一章绪论 1 1 公钥密码学简要回顾 第一章绪论 随着信息技术不断地渗透入人们的日常生活，信息安全成为日益受到重视的问题密 码编码学作为研究如何实现信息的保密和认证的学科，为信息安全的实现提供了重要的支 撑密码分析学作为研究如何破译和制作伪信息的学科，则一直在挑战着密码编码学密码 学包含密码编码学和密码分析学，它正是在这”盾”与”矛”的较量中发展。 1 9 4 9 年，s h a n n o n 在文献保密系统的信息理论 1 中，用信息论的观点阐述了通信 中的信息保密，从而使密码学的研究有了科学的方法在早期的通信系统中，为了保证远程 通信的保密性，采用了秘密密钥算法( 对称密钥算法) 这些算法的共同特点是通信方在 通信之前必须要有双方都知道的共同的密钥 1 9 7 6 年，d i f f i e 和h e l l m a n 在文献密码学的新方向 2 】中提出了公钥密码学的思想利 用公钥密码学，通信的参与方可以公开自己的公钥，只有拥有相应私钥的参与者才能解密 用公钥加密的信息从此密码学进入一个新的发展阶段，对称密钥算法和公钥密码算法也 在不断地结合中发展，有效地实现了信息安全的各种要求 在公钥密码学的思想提出之后，出现了以下一些有代表性的公钥密码体制1 9 7 8 年， r i v e s t ，s h a m i r 和a d l e m a n 在文献 3 】中提出了第一个公开的公钥密码体制，简称为r s a 密 码体制1 9 8 4 年，e 1 g a m a l 在文献 4 1 中提出了e 1 g a m a l 密码体制1 9 8 5 年和1 9 8 7 年，m i l l e r 矛f l k o b l i t z 分别在文献 5 】和 6 】中提出了椭圆曲线密码体1 j ( e l l i p t i cc u r v ec r y p t o g r a p h y ) 1 9 8 9 年，k o b l i t z 在文献f 7 】中提出了超椭圆曲线密码体$ 1 j ( h y p e r e l l i p t i cc u r v ec r y p t o g r a - p h y ) 上述公钥密码体制在具体部署时，需要可信第三方组织认证用户身份与其公钥的关系， 从而带来证书管理的问题 1 9 8 4 年，s h a m i r 在文献f 8 】中提出了基于身份加密体制的思想该密码体制属于非对称 密钥体制，通信方的公钥直接由通信方自己的属性派生出来( 如按照身份信息，邮箱地址 等派生出公钥) 该体制消除了传统公钥体制所带来的证书管理问题目前有着广泛的应用 标量乘与双线性对的快速算法研究第1 页，共1 1 8 页中山大学博士学位论文 1 2 椭圆曲线密码体制及其研究与应用现状 背景虽然这个思想很早就提出，但是直至u 2 0 0 0 年和2 0 0 i 年，s a k a i 、b o n e h 等才分别在文 献 9 ( 1 0 】提出该类体制的具体实现方案此后，基于身份密码体制的研究取得快速发展，也 成为近年来公钥密码体制研究的热点之一目前，广泛应用的基于身份体制的密码方案多 利用基于椭圆曲线( 超椭圆曲线) 所构造的双线性映射 1 2 椭圆曲线密码体制及其研究与应用现状 1 2 1 椭圆曲线密码体制 在本文中，椭圆曲线密码体制泛指利用椭圆曲线所构造的各类密码学应用，特别地指 基于椭圆曲线的密钥协商( e c d h ) 、基于椭圆曲线的数字签名方案( d c d s a ) 和利用双线性 对构造的各类基于身份的密码体s s j ( i d e n t i t y b a s e dc r y p t o g r a p h y ) 超椭圆曲线是椭圆曲线 的推广，很多密码方案可以自然地推广到超椭圆曲线上下面举几个例子介绍椭圆曲线密 码体制这里所描述的椭圆曲线标量乘运算和双线性映射均是抽象表示，将在下一章基础 知识介绍中给出严格的数学定义 1 椭圆曲线密钥协商 在椭圆曲线密钥协商算法中，公开的密码系统参数有：有限域f p 、定义在有限域f p 的 椭圆曲线e f p 、p e ( f p ) 为阶为素数n 的点a l i c e 与b o b 进行如下密钥协商 上述方案并没有对用户身份进行认证，因此容易发生中间人攻击有不少学者研究可 认证的密钥协商方案，因该专题不是本文研究内容，不详细介绍 a l i c eb o b 选择口尺 0 ，佗】选择b r 【0 ，n 】 亟三幽2 q 三 囡呈 k e y = a j q b = i 口b j pk e y = 【6 j 钆= 陋6 用 图1 - 1 椭网曲线密钥协商 标量乘与双线性对的快速算法研究 第2 页，共1 1 8 页中山大学博士学位论文 第一章绪论 2 椭圆曲线签名方案 在签名方案中，a 1 i c e 对消息m ( 假定为比特串) 进行签名，b o b 利用a c e 的公钥对签名进 行验证公开的密码参数有：有限域f p 、定义在有限域f p 的椭圆曲线e f p 、p e ( f p ) 为阶 为素数n 的点、哈希函数日： o ，l + _ 0 ，n 1 假定a l i c e 具有公钥q a = d a i p ，其中以为其 私钥 椭圆曲线签名方案 a l i c e x 寸消息m 签名 1 应片l 哈希函数e = 日( m ) 2 随机选取整数k r 0 ，佗1 3 计算点( z 1 ，y i ) = k i p ，令r = x l ( m o dn ) 若7 = 0 返回第2 步 4 s = k _ 1 ( e + r d a ) ( m o dn ) 若8 = 0 ，返回第2 步 5 a l i c e 将消息m 的签名( ns ) 发送给b o b b o b 验证签名 1 令e = 日( 彳) 2 计算s o ( m o dn ) 3 计算“= s - - 1 e ( r o o dn ) 和口= 8 - 1 r ( m o dn ) 4 计算点( z 7 ，y 7 ) = 【乱 p + v q a 曼：当旦堡当兰：兰! ( 坐q 亟丝) 堕：旦业煎丛垒! i 盟塑筌鱼： 图1 - 2 椭圆曲线签名算法( e c d s a ) e c d s a 算法目前已成为i s o i e c 标准，它已成为我国商用密码管理局规定使用的算 3 利用双线性对构造基于身份的加密方案 先给出抽象的双线性对描述设g ”g 2 和g 3 为阶素数礼的群( 常记g 1 ，g 2 为加法群， g 3 为乘法群) 一个具有密码学意义的双线性对指满足下列性质的映射： e ：g 1xg 2 _ g 3 ( 双线性性) 若对任意p g l ，q g 2 和a z ，有e ( mp ，q ) = e ( p ，【a q ) = e ( p ，q ) 。 ( 非退化性) 对任意p g 1 o ) ，存在qeg 2 ，使得e ( 只q ) 1 对任意q g 2 o ) ， 存在p g 1 ，使得e ( p ) q ) 1 ( 可计算性) 存在多项式时问算法计算映射e ( ) 标量乘与双线性对的快速算法研究第3 页，共1 1 8 页 中山大学博士学位论文 1 2 麓圈曲线密码体制及其研究与应用现状 ( 安全性) 在g t ，g 2 ，g 3 中的离散对数问题是困难的 基于身份的密码体制是椭圆曲线密码( 椭圆曲线上的双线性) 的独特应用例如根据目 前公开的文献，在r s a 密码体系中难以高效地实现基于身份的加密方案a 希望把消 息m 用b o b 的公钥加密。然后把密文传送给b o b 在该方案中，b o b 的公钥直接由b o b 的身份 派生示意图和基本的加密方案如下 a l i c e 利月j b o b 的由i 艄地j | i 作为公蹦加密： “d o l 炮m a i l c o r n ” a l i c e l 讨巾 心认 诬努 圈1 - 3 基。r 身份的加密示意图 心 令i 巾心 i i 颁发 i i 锵觇 i 利j j i 双线性对构造堆于身份的加密办案【1 0 1 系统的参数设定 1 选取两个n 阶群g i 和6 t 2 ( 记g l 为加法群，q 为乘法群) 定义双线性对e ：g l g 1 + c 黾 2 选取哈希函数日i ：( o ，l 。- + g ：，哈希函数日2 ：g 2 一 o ，1 ) ，其i f i l 表示明文m 的长度 3 密钥争成中心选择8 rl o 。，i l ，计算j = ；柚= 【司p 此时，s 称为主密钥，j 6 称为系统公钥 用户密钥提取： 给定用户b o b 身份，d ，密钥生成中心计算b o b 的公钥q j d = 肌f f d ) ，私钏岛d = i s l q w 加密： 1 a l i c e 随机选择7 r1 0 ，n 1 2 a l i c e 计算c ；( h 只moh 2 ( e ( q l o ，昂曲) 7 ) ) = ( 仉y ) 解密： 给定密文似 ，) b o b 计算yo 日2 ( e ( s t o 。，) ) 囝1 - 4 基于身份的加密方案 在文献【1 0 j ，作者给出了对上述方案的f i s a l d - o k a m o t o 转换，使方案的安全性得到更 好的形式化证明 标量秉与双线性对的快速算法研究第4 页共1 1 颁中山大学博士学位论文 第一章绪论 综合分析上述的各类公钥密码系统，可以总结出椭圆曲线密码的优势如下： 在相同的安全度之下，椭圆曲线公钥密码体制具有比r s a 密码体制、e 1 g a m a l 密码 体制更好的效率总体而言椭圆曲线密码需要更少的计算时间、更少的密钥存储空 间、更小的密钥传输带宽要求等同时硬件实现e c c 密码所需逻辑电路的逻辑门数 较r s a 密码也要少得多，功耗更低( 安全度越高，差别越明显) 相比而言，椭圆曲线密 码具有更高的每比特安全。i 生( s e c u r i t yp e rb i t ) 详见 1 1 】 与传统的r s a 密码体制、e 1 g a m a l 密码体制相比，椭圆密码密码体制的密钥具有更强 的随机性r s a 体制在大整数设定之后，其所使用的剩余类环也随之确定同样地对 于素域上的e 1 g a m a l 体制而言，在有限域特征p 给定之后，有限域中元素也随之确定 而对于椭圆曲线来说，给定一个有限域，仍然可以随机地选择在该域上不同构的安全 椭圆曲线，从而使密码系统的参数更具有随机性 基于椭圆曲线的密码体制具有更好的设计灵活性例如可以利用在曲线上的双线性 对来构造基于身份的密码体制 1 0 、利用双线性对实现一轮三方密钥协商 1 2 】、利用 双线性对构造短签名 1 3 1 【1 4 】等 1 2 2 椭圆曲线密码学研究现状 目前，关于椭圆( 超椭圆) 曲线密码学的研究是密码学领域研究的一个热点，相关的 文献浩如烟海，文献 1 5 较为全面地介绍了该领域的内容每年定期召开的专题学术会 议( w o r k s h o po ne l l i p t i cc u r v ec r y p t o g r a p h y ) 为从事该领域研究的学者提供了交流的平 台近年来，国内有不少学者选择该领域作为其博士阶段研究工作，并取得丰富的结果，详 见文献 1 6 】【1 7 1 8 【1 9 【2 0 】 2 1 】【2 2 】【2 3 】【2 4 】 2 5 【2 6 】 2 7 】 2 8 】 关于椭圆曲线密码学的研究按照出发点的不同，分为以下的三大类 从椭圆( 超椭圆) 密码的应用来看，研究的重点包括设计更安全高效的密码协议和利用 椭圆曲线密码构造各种安全有效的信息安全应用如各种智能卡应用、无线传感器 网络应用以及无线通信安全等等目前椭圆曲线密码系统已经被成功地应用到多种 智能卡中、其在无线传感器和无线通信安全中仍将有更广泛的应用 标量乘与双线性对的快速算法研究第5 n ，共1 1 8 页中山大学博士学位论文 1 2 椭圆曲线密码体制及其研究与应用现状 从椭圆( 超椭圆) 曲线密码实现的角度看，主要研究工作在于加速优化椭圆曲线密码 的一些关键算法： ( a ) 椭圆曲线上有理点个数的计算( 超椭圆曲线_ ：j a c o b i a n 群有理点个数的计算) 给 定有限域f p 和定义在该有限域上的椭圆曲线e ：y 2 = z 3 + a z + b ，计算椭圆 曲线上f 口有理点的个数 ( b ) 椭圆曲线标量乘给定有理点尸e ( ) 和整数k z ，计算 k i p ( c ) 双线性对的快速计算给定只q e m ，计算双线性映射e ( 只q ) 此处e h 】指e 上 阶整除于n 的点组成的群，将在下文严格定义 ( d ) 椭圆( 超椭圆) 曲线的构造在双线性对的实现中，常要求所依赖的曲线具有某些 特殊的性质构造合适的曲线可以显著地加速双线性对的计算 从椭圆( 超椭圆) 密码的安全性考虑，主要考虑下列影向其安全性的关键问题 ( a ) 椭圆曲线离散对数1 ；- j 是i l ( e c d l p ) 给定只q e ( f p ) 满足q ( 尸) ，求k z ，使 其满足q = k i p ( b ) 双线性的d i f f i e - h e l l m a n 问题( b d h ) 。给定椭圆曲线上点p ，q 及其上的双线性映 射e ( ) ，并满足e ( p ，q ) 1 。给定p 1 = a i r ，p 2 = 【b i b 求e ( n 6 】只q ) ( c ) 由上述问题所派生的一系列其他问题它们往往是椭圆曲线密码方案安全性的基 础 超椭圆曲线研究的现状见参考文献 17 】 1 8 】 2 8 】 15 1 2 3 椭圆曲线密码体制应用现状 近年来椭圆曲线密码得到了广泛的应用它不仅在一些传统的桌面计算机上得到应用， 更被广泛地使用到各种嵌入式系统之中现在市场上大部分的智能卡都提供了基于椭圆曲 线的密钥交换程序、加解密程序和数字签名程序国内生产的各种信息安全芯片也都配备 了能使用椭圆曲线密码的协处理器目前各个国家都在致力于椭圆曲线密码的理论研究和 应用推广，椭圆曲线密码的标准化工作也取得了快速的进展 例如美国国家安全局( n s a ) 在2 0 0 5 年发布了一套推荐加密算法，这套算法统称s u i t eb 它为美国政府中敏感非保密信息的提供安全保障s u i t eb 包括用于密钥协商的椭圆曲线 标量乘与双线性对的快速算法研究第6 页，共1 1 8 页中山大学博士学位论文 第一章绪论 密钥协商( e c d h ) 、用于签名的椭圆曲线签名算法( e c d s a ) 、用于对称加密的高级加密标 准( a e s ) 以及安全散列算法( s h a ) 在国内，国家密码管理局于2 0 0 6 年发布第7 号公告，明确规定无线局域网产品须采用椭 圆曲线数字签名算法和椭圆曲线密钥交换算法公告中也规定了标准的椭圆曲线参数 基于双线性对的密码体制也逐渐在实际中得到应用2 0 0 8 年5 月，i e e ep 1 3 6 3 t 作小组 公布了基于身份加密体制标准的第一份完整草案商用市场也慢慢开始形成例女i v o l t a g e s e c u r i t y 公司致力于推广基于双线性对密码体制的应用，目前已经开发出基于身份加 密( i d e n t i t yb a s ee n c r y p t i o n ) 的软件工具包该公司开发出了基于身份的邮件系统v o l t a g e s e c u r e m a i l ，该系统已经部署到一些公司之中 可以预见，椭圆曲线密码会更加深入广泛地应用到无处不在的计算与通信之中 1 3 本文工作简介、工作的创新点和意义以及本文结构 1 3 1 本文工作简介 本文的工作在于椭圆曲线密码快速实现方法的研究由以上椭圆曲线密码的几个例子 可见，椭圆曲线点的标量乘与双线性对的计算是影响密码体制效率的关键运算本文围绕 着这两类运算完成了以下的工作： 为了提高有限域上椭圆曲线有理点个数的计算速度，本文提出使用定义在扩域 上的椭圆曲线的算法算法的基本步骤是：( 1 ) 随机选取定义在基域的椭圆曲线， 用s c h o o f - e l k i e s - a t k i n 算法计算其有理点的个数；( 2 ) 利用公式计算得到目标曲线上( 定 义在扩域上) 的有理点个数，若其有理点个数不满足要求，则重复第( 1 ) 步；( 3 ) 利用椭 圆曲线的扭映射( t w i s t e dm a p ) ，得到目标曲线的表示形式在同样的安全度要求下， 运用s c h o o f - e l k i e s - a t k i n 算法输入的规模是传统算法输入规模的一半所以新提出的 算法在选择合适的椭圆曲线方面具有更高效率 为了提高椭圆曲线标量乘运算 k i p 的计算速度，本文利用定义在扩域上的椭圆曲线， 构造了可高效计算的自同态矽：( p ) _ ( p ) 利用该自同态实现实现对标量k 的分解， 从而减少了运算时所需的循环次数，较大地提高了计算速度例如考虑定义在二次扩 域上的椭圆曲线，利用自同态矽，可得 k i p = k o p + 陋1 】矽( 尸) ，这里和后1 的二进制 标量乘与双线性对的快速算法研究第7 页，共1 1 8 页中山大学博士学位论文 1 3 本文工作简介、工作的创新点和意义以及本文结构 表示约为k 的二进制表示长度的一半不同于较早的g l v 算法 2 9 】，本文给出了在一般 的椭圆曲线上构造满足要求自同态的一般方法 为了提高同时计算多个标量乘的计算速度，例如 k i p + 1 q ，本文整合了当前的各种 算法，对各种方法进行实际测试，获得最优的实现参数为了验证本文提出的算法的 有效性，本文利用m i r a c l 软件包 3 0 实现了上述算法，并利用它实现了椭圆曲线密钥交 换协议( e c d h ) 。在欧洲非对称密钥算法实现速度基准平台( e c r y p tb e n c h m a r k i n g o fa s y m m e t r i cs y s t e m s ) 中，该实现是目前同类算法中最快的 为了实现双线性对的快速算法，本文利用复乘方法，提出了一类嵌入次数为= 3 椭 圆曲线的构造方法在该类椭圆曲线上实现双线性a t e 对，所需要的m i l l e r 循环的长 度j 0 t a t e 对算法长度的1 妒( 忍) ，这里妒为欧拉函数在a e s1 2 8 的安全度之下，在该类 曲线上计算双线性a t e 对所要求的m i l l e r 循环长度在目前已有的文献中是最短的在 此类椭圆曲线上，本文提出了改进的m i l l e r 算法，该算法能实现分母消去，从而避免大 量有限域求逆运算同时本文提出了加速最后幂次运算的算法这些优化算法使得这 类曲线能有效地应用于a e s1 2 8 安全度下的双线性对计算 本文提出计算双线性对的一种全新方法。该方法适用于嵌入次数为偶数的一类椭圆 曲线曲线利用新的算法，在计算双线性对时只需要输入参数为椭圆曲线上点的x 坐 标这与椭圆曲线标量乘只需要点的z 轴坐标的蒙哥马利算法相对应理论分析和实 验数据表明，在同样考虑点压缩的情况下，新算法在一类嵌入次数后= 2 的椭圆曲线上 的速度要快于传统m i l l e r 算法 本文考虑了实模型下超椭圆曲线上双线性的实现由于很多的超椭圆曲线都是由实 模型给出，所以实现结果可以考察在超椭圆曲线上实现双线性对的效率本文采用嵌 入次数k = 6 的超奇异超椭圆曲线，对在其上的双线对实现提出了一些优化算法，包括 缩短m i l l e r 循环长度的方法，消去分母以避免有限域求逆的方法等作为比较，该研究 同时给出嵌入次数k = 3 的超奇异椭网曲线上双线性对计算的优化方法本文给出了 在同一平台上实现这两种双线性对计算的效率对比 1 3 2 工作的创新点和意义 与目前公开的研究结果相比，本文的创新性体现在以下几点： 标量乘与双线性对的快速算法研究第8 页，共1 1 8 页中山大学博士学位论文 第一章绪论 关于大特征有限域上椭圆曲线的自同态考虑g l v 方法【2 9 】，之前的学者认为，方法只 适用于一类特殊的椭圆曲线( 自同态环具有小的类数的曲线) 本文提出的方法推翻了 这个说法本文提出了利用定义在扩域上的椭圆曲线来构造有效自同态的一般方法， 该方法能应用于更一般的椭圆曲线上同时该方法可以自然地推广到其他形式的椭 圆曲线和超椭圆曲线上 本文提出了一类嵌入次数为k = 3 i 的适合a t e 对实现的椭圆曲线的构造方法，并给出 了优化的m i l l e r 算法和实现结果之前有学者认为，嵌入次数为奇数的椭圆曲线不适 合于双线性对的实现因此关于这类曲线的研究并没有公开的结果本文所提出的曲 线和优化算法改变了这个看法在a e s1 2 8 的安全度之下，该曲线具有很好的实现 效率 本文提出仅使用椭圆曲线点的x 轴坐标实现双线性对的计算方法，这是计算双线性对 的一个全新的算法从数学的角度来说。是否能只使用x 轴坐标实现双线性对计算是 个未知问题该算法对这个问题给出了正面的回答同时，本文也从理论和具体实现 上分析了在同样的带宽要求下，在嵌入次数为2 的椭圆曲线上实现双线性对，新算法 的计算效率要优于传统的算法 本文提出在实模型超椭圆曲线上实现双线性对的方法这是在公开文献中首次在该 类曲线上考虑双线性对的实现这项研究为在理论上探讨超椭圆曲线双线性对和椭 圆曲线双线性对的实现效率对比提供了进一步的依据 1 3 3 本文结构 第二章介绍椭圆曲线密码的一些预备知识，主要包括有限域及其算术、椭圆曲线定 义、利用复乘理论构造适合双线性对计算的椭圆陆线、椭圆曲线标量乘的快速实现、除 子理论以及双线性对的定义与计算 第三章研究椭圆曲线标量乘的快速实现问题这一章主要给出构造有效自同态的方 法、分析自同态的性质、利用有效自同态对标量乘中标量进行分解、提出随机选取椭圆 曲线的方法、讨论了多点同时标量乘的应用，最后给出具体实现的结果 第四章考虑在一类嵌入次数k = 3 i 的椭圆曲线上计算双线性a t e 对这一章提出该类椭 标量乘与双线性对的快速算法研究第9 页，共1 1 8 页中山大学博士学位论文 1 3 本文工作简介、工作的创新点和意义以及本文结构 圆曲线的构造方法，并优化在该类曲线上计算双线性对的m i l l e r 算法，最后考虑其实现效率 与嵌入次数k = 1 2 的曲线的实现效率的比较 第五章介绍一种计算双线性对的全新算法这一章提出了计算双线性对的新方法，讨 论新方法的应用领域，最后考虑方法在不同应用中的效率 第六章讨论在实模型超椭圆曲线上实现双线性对这一章把双线性对的计算推广到实 模型超椭圆曲线上，给出了在类嵌入次数k = 6 n 超椭圆曲线实现双线性对的优化方法 这一章最后考虑了在一类嵌入次数为k = 3 的椭圆曲线上的双线性对，作为比较分析了两 者的效率对比 第七章是本论文结束语 图1 - 5 本文体系结构 标量乘与双线性对的快速算法研究 9 9 1 0 i f 量，共1 1 8 页中山大学博士学位论文 第二章预备知识 2 1 有限域及其算术 第二章预备知识 弟一早 耿官大u 以 域是代数学的基本概念，它是我们熟悉的代数系统( 如有理数域q ，实数r ，复数域c ) 及其性质的抽象域k 是包含两种运算( 记为加法- f 与乘法) 的集合，且两种运算满足下列 条件： ( k ，+ ) 是加法阿贝尔群，记加法单位元为0 ( k o ) ，) 是乘法阿贝尔群，记乘法单位元为i 对任意a ，b ，c k ，如下分配律成3 一l a ( b + c ) = a b + a c 定义2 1域k 的一个子集如果其自身构成域，则称为k 的子域如果域k 只包含其自 身作为子域，则称k 是素域 给定域k ，可以由不可约多项式定义域的n 次扩张记k 吲为所有系数属于k 的关于z 的 多项式的集合 定义2 2 令f k 吲，称k m ( ，) 为剩余类环如果( 9 l 一眈) 能被厂整除，称9 1 ，9 2 k m 在该剩余类环上是等价的 定理2 1 ( 参见文献 3 1 】) 剩余类环k z 】( 厂) 是一个域当且仅当，( z ) 在k m 上是不可 约多项式 定义2 3 给定k 上n 次不可约多项式，( z ) ，令 l = ak 陋】( ，) 竺a n l x n 一1h - + a l x + a o ia i k ) 则域l 为域k 的n 次扩张 有限域即含有有限个元素的域，本文记有限域为f 因 中每个元素o l 对于加法是有限 阶的，所以存在正整数m ，使得m q = 0 若佗为使得佗1 = 0 的最小正整数，则称有限域f 的 特征为n ，记为c h a r ( f ) = n 标量乘与双线性对的快速算；去研究第1 1 页，共1 1 8 页中山大学博士学位论文 2 1 有限域及其算术 按照习惯，本文中记p 为一素数，q = p m 为素数p 的m 幂次记f p 为由0 ，1 ，2 ，p 一1 所 组成的有限域，其中加法与乘法均在模p 下进行记f g = 跏为f p 的m 次扩张，它是m 维 的f p 向量空间 限于篇幅，下面不加证明地给出有限域的一些结论，在后续章节的讨论中将利用到这 些性质 n i c h a r ( f ) = p ，则对任意o ，b 砸 和佗n ，有( o + 6 ) p n = + 6 p ” 设f q 为一有口个元素的有限域，则对任意a f ，有a q = a 设f q 为一有q = 矿个元素的有限域，那么f 口的任何子域的元素个数为，其中f 为m 的 因子另一方面，若f 为m 的因子，则f q 有唯一的子域z 设屹为一有限域，记为其乘法群，则喵是阶为g 一1 的循环群 若厂为砸 q m 上的m 次不可约多项式，则在域砸q m 上存在厂的一个根q 进一步地 有厂的m 不同根为f q 。的元素q ，酽，q g m 一 定义2 4 设f g 为一有限域，循环群略的生成元称为域 。的本原元 在椭圆曲线密码中，需要用到有限域的四种运算，分别为加法，减法( 加法的逆运算) ， 乘法，除法( 乘法的逆运算) 其中加减法的计算开销比较小，乘法的开销比较大，而求逆 的运算开销是最大的，往往都在乘法运算的数倍到数十倍之间目前，有不少的研究着 重于寻找快速的有限域算术 3 2 】例如对于有限域乘法，目前采用的方法有k a r a t s u b a - o f m a n 方法与m o n t g o m e r y 方法对于有限域求逆算法，目前采用的有扩展的欧几里德算 法和m o n t g o m e r y 求逆算法 下面用一个例子来总结本节所提到的概念与方法 例2 1令p = 1 9 ，则p 三3 ( r o o d4 ) b = o ，1 ，1 8 因z 2 + 1 为f p 陋】上的不可 约多项式，有f p z 竺f p z 】( z 2 + 1 ) 令口满足p 2 + 1 = 0 则f p ：竺a + b oia ，b f p ) 对于扩域元素的运算，例如( n 1 + 6 1 秒) ( a 2 + b 2 臼) 和( n + 阳) 2 ，简单的实现分别需要4 个乘法 和3 个乘法但是利用如t k a r a t s u b a - o f m a n 方法：( 0 1 + b l o ) ( a 2 + b 2 0 ) = ( a l a 2 一b l b 2 ) + ( ( n 1 - 1 - b 1 ) ( a 2 + b 2 ) 一a 1 a 2 一b 1 b 2 ) o ，( a l + 6 1 护) 2 = ( a l + b 1 ) ( a l 一6 1 ) + 2 a x b l o 可见元 素相乘与平方仪分别需要3 个乘法和2 个乘法。 标量乘与双线性对的快速算法研究第1 2 页，共1 1 8 页 中山大学博士学位论文 第二章预备知识 2 2 椭圆曲线 本节简要给出椭圆曲线的一些重要结论，详细证明，请参考文献 3 3 】， 3 2 】， 3 4 】在本节 中，如果不加说明，k 为一域，藤为k 的代数闭域 2 2 1 射影平面 定义2 5 上n 维射影空间定义如下： p 最= ( z 1 ，z n ) kx x ) 定义2 6 多元组 1 ，z 2 ，z n ) 艰和( y 1 ，垅，蜘) 雌称为等价的，如果存 在非零元素入k ，使得( z 1 ，z 2 ，z n ) = ( a y l ，a y 2 ，入) ，记为(