（信息与通信工程专业论文）双线性对理论及其在密码学中的应用研究.pdf

ii 一 一 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：童塞 日期：动【d 年岁月2 1 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盏趣 摘要 摘要 双线性是构造密码协议的一个有用工具，在当代密码学中受到了密切关注它 的重要性在于：可以用它来构建用其它方式很难或不能构建具有新奇性质的密码 体制：即使这样的密码体制能用其它的方法构建，它也可以用来为我们的密码协议 提供更多更好的功能 尽管双线性对的研究取得了长足的进步，但是仍然有很多研究问题未得到解决 至今双线性还难以应用于计算条件受限的环境而且有关双线性对的绝大多数文 献仅集中于探讨双线性对的几个有限和分离的侧面，缺乏文献对双线性对理论进 行系统地阐述这就引起了我们写作本文的第一个目的：以系统和自包含的方式阐 释双线性对理论，为对传统密码系统有经验的程序员提供有益的指导本文的第二 个目的是要说明双线性对在构造安全密码体制的思想和方法 本文所做的工作如下： 详尽地解释了双线性对的基本理论，包含数学背景、双线性对从除子理论的 导出、有效计算、双线性对的优化等； 在本文中提取了很多事实并独立地提供了证明； 本文引入了双线性对优化层次的概念，在此基础上给出了一个易于理解且全 面的双线性对优化技术综述； 总结了构建了基于双线性对的密码体制技巧 具体而言，本文有几个新颖之处： 引入了连续配对的概念；在此基础上分别给出了w a t e r si b e 和b f 0 1i b e 的 一个实现技巧； 结合可证明安全理论，直接应用双线性对构造了一个i n d c p a 的公钥加密 体制，并给出了安全性证明，并利用f u j i s a k i o k a m o t o 转换方法将其转化为 了随机预言模型下可证明为i n d c c a 安全的加密体制； 揭示了变色龙哈稀是构建具有c c a 安全密码体制的一个重要技巧基于 g e n t r yi b e 和b b 0 4 数字签名方案分别构造了一个标准模型下可证明安全的 数字签名方案和基于身份的加密方案； 对w a t e r si b e 提供了一个易读和易于理解的g a m e - b a s e d 安全性证明 、 电子科技大学硕士学位论文 关键词：双线性对m i l l e r 算法可证明安全密码体制 i i a b s t r a c t a b s t r a c t b i l i n e a rp a i r i n gi sau s e f u lt o o lf o rc o n s t r u c t i n gc r y p t o g r a p h i cp r o t o c 0 1 s ，a n d b e c o m e sm o r ec o n c e r n e di nc o n t e m p o r a r yc r y p t o g r a p h y i t ss i g n i f i c a n c el i e si nt h a t o n ec a 3 2u s ei tt ob u i l dc r y p t o g r a p h i cs c h e m ew i t hn e wa n dn o v e lp r o p e r t i e sw h i c h c a l ln o te a s i l yo re v e nn o tb ec o n s t r u c t e db yu s i n go t h e rt e c h n i q u e s ，o ro n ec a n u s ei tt op r o v i d eb e t t e rf u n c t i o n a l i t ye v e nt h o s ec r y p t o g r a p h i cp r o t o c 0 1 sc a nb e c o n s t r u c t e db yo t h e rm e a n s a l t h o u g hm u c hp r o g r e s sh a sb e e nm a d e i nt h ea r e n ao fp a i r i n g ，t h e r es t i l le x i s t s m a n yr e s e a r c hp r o b l e m sn e e dt ob ef u r t h e ri n v e s t i g a t e d ，a n du pu n t i ln o w p a i r i n gi s d i f f i c u l tt ob ea p p l i e di nt h er e s t r i c t e de n v i r o n m e n t s m o r e o v e r ，t h ev a s tm a j o r i t yo f t h el i t e r a t u r eo np a i r i n gf o c u s e ss o l e l yo ns o m el i m i t e da n ds e p a r a t e dp o i n t sa b o u t p a i r i n g ，t h e r el a c k sl i t e r a t u r et oi l l u s t r a t ep a i r i n gi n as y s t e m a t i cm a n n e r t h i s a r i s e so u rf i r s ta i mt ot h i st h e s i s ：t og i v es y s t e m a t i ca n ds e l f - c o n t a i n e de x p l a n a t i o n s a b o u tp a i r i n gi no r d e rt os e r v ea sau s e f u lg u i d ef o rt h o s ep r o g r a m m e r sw h oo n l y h a v ee x p e r i e n c ew i t hc o n v e n t i o n a lc r y p t o s y s t e m t h es e c o n da i mo ft h ew o r ki s t oi l l u m i n a t es o m ei d e ao fp r a c t i c a lu s a g eo fp a i r i n gi nt h ec o n s t r u c t i o no fs e c u r e c r y p t o g r a p h i cp r o t o c o l s w ep r e s e n ts e r v a le x a m p l e st os h o wt h a te f f i c i e n t a n d s e c u r ec r y p t o g r a p h i cs c h e m ec a l lb eo b t a i n e dv i ap a i r i n g 0 u rw o r k sa r eo u t l i n e da sf o l l o w s ： w ee l a b o r a t et h eb a s i ct h e o r yo fp a i r i n g ，i n c l u d i n gi t sm a t h e m a t i cb a c k g r o u n d ， i t sd e r i v a t i o nf r o md i v i s o rt h e o r y ，e f f i c i e n tc o m p u t a t i o n ，p a i r i n go p t i m i z a t i o n w ee x t r a c tm a n yf a c t si nt h et h e s i sa n di n d e p e n d e n t l yp r o v i d et h e i rp r o o f s o nt h eh i g hs t a n d p o i n t ，w ep r o p o s e dt h en o t i o no fp a i r i n go p t i m i z a t i o nh i - e r a r c h y w eg i v eac o m p r e h e n s i v ea n df u l l r e v i e wo nt h ei m p r o v e m e n t so f p a i r i n g sc o m p u t a t i o n w eb u i l ds e v e r a lc r y p t o g r a p h i cs c h e m ea n dd i s c u s st h e i rs e c u r i t ya n de f f i c i e n c y m o r ec o n c r e t e l y , t h et h e s i sc o n t a i n st h ef o l l o w i n gn o v e l t i e s ： t h en o t i o no fs e q u e n c e dp a i r i n gi si n t r o d u c e d i nl i g h to ft h i si d e a ，at e c h n i q u e i sp r o v i d e di nt h ei m p l e m e n t a t i o no fw a t e r si b es c h e m ea n db o n e hf r a n k l i n m 一 ：? 、 电子科技大学硕士学位论文 i b es c h e m er e s p e c t i v e l y a s s o c i a t e dw i t ht h et h e o r yo fp r o v a b l es e c u r i t y , w ed i r e c t l yc o n s t r u c tv i ap a i r - i n gap u b l i ck e ye n c r y p t i o ns c h e m ew i t hi n d c p as e c u r i t y b ya p p l y i n gt h e f u j i s a k i o k a m o t ot r a n s f o r m a t i o n ，w ec o n v e r tt h i ss c h e m ei n t oa c c as e c u r e s c h e m e w bs h o wt h a tt h ec h a m e l e o nh a s hi sag e n e r a la n di m p o r t a n tt e c h n i q u ef o r t h ec o n s t r u c to fc r y p t o g r a p h i cs c h e m ew i t hc c as e c u r i t y m o t i v a t e db yt h i s i d e a ，w ec o n s t r u c tap r o v a b l es e c u r ed i g i t a ls i g n a t u r ea n dai d e n t i t yb a s e d e n c r y p t i o ns c h e m ef r o mg e r r yi b ea n db b 0 4 - s i gr e s p e c t i v e l yi nt h es t a n d a r d m o d e l w ep r o v i d eag a m e - b a s e ds e c u r i t yp r o o fa b o u tw a t e r si b es c h e m e ，t h ep r o o f i sm o r er e a d a b l ea n dc o m p r e h e n s i b l et h a nt h eo r i g i n a lo n e k e yw o r d s ：b i l i n e a rp a i r i n g ，m i l l e ra l g o r i t h m ，p r o v a b l es e c u r i t y , c r y p t o - g r a p h i cp r o t o c o l i v 目录 第一章 1 1 1 2 1 3 第二章 2 1 2 2 2 3 2 4 2 5 2 6 2 7 第三章 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 目录 绪论 1 双线性对研究背景和意义 1 双线性对研究现状 2 本文工作及内容安排 3 椭圆曲线- - - 5 椭圆曲线定义与方程 5 椭圆曲线有理点群 7 有限域上的椭圆曲线 9 超奇异椭圆曲线。 1 0 构建椭圆曲线密码系统 1 2 2 5 1 离散对数1 2 2 5 2用双线性对攻击e c d l p 1 2 2 5 3 椭圆曲线密码系统 1 3 2 5 4实现时的考虑- 1 4 有理函数和除子理论 1 5 本章小结。1 9 双线性对及其有效计算2 0 双线性对概述- 2 0 抽象定义2 1 3 2 1对称双线性对2 1 3 2 2非对称双线性对2 2 w e i l t a t e 对- - - - 2 2 3 3 1w 西1 对2 2 3 3 2t a t e 对- 2 4 m i l l e r 算法 2 6 扭映射和迹映射 3 0 超奇异椭圆曲线类型及数据 3 3 修正的配对 3 4 m i l l e r 算法相关计算实例 3 5 双线性对运算的优化 3 8 3 9 1优化层次及思想 3 8 3 9 2优化技术综述3 9 v 电子科技大学硕士学位论文 3 9 3若干结论及证明 4 4 3 1 0 更快的双线性对 4 5 3 1 0 1 连续配对4 5 3 1 0 2a t e 对4 6 3 1 0 3 压缩配对4 6 3 1 0 4l u c a s 序列4 7 3 1 0 5 基于e d w a r d s 曲线的配对4 8 3 1 0 6 利用椭圆网计算双线性对 5 3 3 1 1 本章小结 5 4 第四章双线性对在密码学中的应用5 6 4 1引言5 6 4 2可证明安全 5 7 4 3公钥加密体制及其安全5 9 4 4数字签名体制及其安全6 1 4 5数学困难问题及假设6 2 4 6本文基于d b p e 的公钥加密体制 6 3 4 7 g e n t r yi b e 及其上的新构造 6 4 4 7 1 g e n t r yi b e 的描述 6 4 4 7 2方案构造和安全性分析6 5 4 7 3 本文基于g e n t r y 方案构造的数字签名方案 6 6 4 8w a t e r si b e 及其g a m e - b a s e d 证明6 8 4 8 1w a t e r si b e 方案的描述6 8 4 8 2本文提供的g a m e - b a s e d 安全性证明6 8 4 9 b b 0 4 - s i g 及其上的新构造 7 3 4 9 1 b b 0 4 - s i g 的描j 丕 7 3 4 9 2 本文基于b b 0 4 - s i g 的i b e 7 4 4 1 0 对构造的方案的技巧分析 7 4 4 1 1 参数选取问题 7 5 4 1 2 个实现时的技巧7 6 4 1 3 本章小结7 7 结束语7 8 致谢7 9 参考文献8 0 攻硕期间取得的研究成果8 5 v i 第一章绪论 第一章绪论 基于双线性对的密码学在密码学中一个新的研究领域，它主要涉及一个具有 特殊性质的函数利用双线性对可以构建那些使用传统技术不能或很难构建的 密码体制对双线性对的研究可以拓展密码学理论和应用领域，因而具有十分 重要的理论和实践意义 1 1双线性对研究背景和意义 随着计算机科学、网络和通信技术的迅猛发展，人类已步入信息社会在信息 社会里，人们越来越多地利用着网络，通过网络实现各种行为例如：网上购物、网 上竞选、网络恰谈、利用公开网络传输机密信息或签署电子协议等网络是一把 双刃剑，一方面人们利用它创新实现了许多繁荣另一方面，它也给人们带来了一 个十分严峻和棘手的问题信息安全问题。公钥密码学应运而生 公钥密码学起源于1 9 7 6 年为解决对称密码密钥分发困难的问题，1 9 7 6 年 d i f f i e 和h e l l m a n 发表了密码学新方向2 8 1 ，提出了一种允许通信双方在不安全 信道上即可安全协商共享密钥的协议，即著名的d i f f i e - h e l l m a n 密钥协商协议( d h 协议) 由于这篇文章引入了公钥、私钥、公钥密码学等基本概念和思想，因而，此 文的发表标志着现代密码学( 也是公钥密码学) 的诞生 双线性对是一种数学对象，本源于代数曲线的研究在所有发现的双线性对中， w e i l 对和t a t e 对最为著名从上世纪9 0 年代起双线性对逐步在公钥密码学中得 到应用早期的应用是“消极”的，直到2 0 0 0 年以后，双线性对在密码学中的积极作 用才逐步显现出来人们发现可以将双线性对作为一种有用的工具来构造各种安 全实用的密码体制用双线性对构造的密码体制具有下述优点： 具有很强的实用性有大量用双线性对构造的形式相当简洁、时间和空间效 率相当高的密码协议，比如短签名【2 0 】 难以有替代品利用其它工具不能构造或很难构造其中的某些协议 具有很高的安全性用它构造的很多密码体制已被证明能够达到公认的安全 标准，比如利用双线性对构造的w - a t e r 8i b e ( 7 0 1 、g e n t r yi b e 3 s 能够在标 准模型下被证明为具有i n d i d c c a 安全性 对双线性对的研究可以分为两类，第一类是研究双线性对的有效计算，第二类 l 效率与实际的计算要求相比仍然存在一定差距另外，尽管目前在双线性对的计算 研究中取得了不少突破性成果，双线性对的计算水平已经提高到了一个新的台阶 但这些成果绝大多数都受到某些条件的限制，势必防碍双线性对在密码学中的更 进一步应用例如，很多算法都只能工作在某特定曲线上，难以适应一般曲线又例 如，利用e d w a r d s 曲线计算双线性对的方法只适应于具有4 阶点的椭圆曲线更甚 至于对于有些与双线性对效率改进密切相关的算法还未受到人们更为深入的研究， 比如对计算双线性对的椭圆网算法的优化还有就是，目前双线性对的计算尚不能 满足计算资源和空间资源受限的环境( 比如智能卡) 的要求，这也迫使人们需要对 计算双线性对的算法的时空效率提出更高的要求总之，对计算双线性对做进一步 研究变得非常必要，研究的成果将会促进双线性对在密码学中更进一步的应用 密码学的宗旨是解决实际中的各种安全问题，为此采用的一条重要途径是去构 造各种满足需求、安全高效的密码协议由于双线性对在密码学中的工具性作用， 目前利用双线性对构造具有高效且安全的密码体制是密码学界研究的热点之一 另外，目前有关双线性对及其密码的标准和规范尚未建立，使用双线性对实现的真 正密码产品也不多见，对双线性对更多的认识将助于标准和规范的制定、密码产 品的实现因此本文对双线性对的研究具有极大的理论意义和现实意义 1 2双线性对研究现状 1 9 4 6 年，著名代数几何学家w b i l 引进了今天称为w e i l 对的双线性对，并用它 证明了代数几何中的某些重要定理以后双线性对家簇中又添加了新的成员：t a t e 对、a t e 对、e t a 对、彻对等 上世纪9 0 年代出现了双线性对的“消极使用：用来攻击有限域上椭圆曲线有 理点群的离散对数问题，即所谓的m o v 归约和f r 归约，前者利用w 宅i 1 对，后者 利用t a t e 对这样的归约将椭圆曲线有理点群中的离散对数问题归结为有限域乘 法群中的离散对数问题由于有限域乘法群中的离散对数问题存在亚指数算法( 例 2 第一章绪论 如指数积分算法) ，这就使得椭圆曲线离散对数问题有可能通过求解有限域乘法群 中的离散对数而得到解决 对双线性对的正面使用始于2 0 0 0 年，s a k a i 、o h g i s h 、k a s a h 甜a ( 5 5 】利用双线 性对构造了基于身份的加密体制( i d e n t i t y b a s e dc r y p t o s y s t e m ，i b e ) ，首次解决了 s h a m i rf 6 3 在1 9 8 4 年提出的如何构造i b e 的公开问题j o u x 4 4 利用对称双线性 对提出了三方密钥分发协议 紧随这些工作，b o n e h 等人显著地加大了双线性对在密码学中应用研究的力度 b o n e h 和f r a n k l i nf 1 9 利用双线性对提出了一个在随机预言模型( r a n d o mo r a c l e m o d e l ，r o m ) 下可证明为i n d i d c c a 安全的基于身份的加密体制( b f 0 1 ) ； b o n e h 、l y n n 和s h a c h a mf 2 0 1 利用双线性对提出了在r o m 下可证明为u f - c m a 安全的短签名方案( b l s 0 1 ) 由于双线性对在密码学中的构建性作用，有关双线性对在密码学应用的文章大 量涌现出来，以至于出现了几个与双线性对有关的密码学研究领域：基于身份的密 码学( i d e n t i t y b a s e dc r y p t o g r a p h y ，i b c ) 、基于双线性对的密码学( p a i r i n g - b a s e d c r y p t o l o g y , p b c ) 双线性对也因此渗透到密码学的方方面面，双线性对不仅可以 用来构造公钥加密( 基于p k i 和基于身份的) 、数字签名( 盲签名、群签名、代理 签名、代理盲签名、环签名以及其它变体) 、签密这些经典的密码要素而且还可以 用来构造认证、密钥协商、密钥封装等在实际应用中发挥着巨大作用的密码协议 有关双线性对在密码学中应用详细的现状可参见f 5 3 】 有关双线性对的有效计算的研究综述可以参见3 9 2 一节从该节的叙述中可 看到：起初双线性对的运算十分缓慢，限制了双线性对在密码学中的实际应用以 后由于很多研究者的努力，双线性对运算速度提升了好几个数量级，一个双线性对 运算只需要几微秒的时间双线性对计算效率已能满足普通p c 机的计算要求，只 是还未能够满足受限环境下的计算要求 1 3本文工作及内容安排 本文在总结双线性对必要数学知识的基础上，详尽地分析了m i l l e r 算法，比较 完整详细地综述了双线性对优化的各种思想和技术为使理论完整，作者独立地补 充了许多定理及其证明，比如：推论2 1 3 并给出了证明；给出了3 1 0 4 一节的所有 证明；给出了w e f t 互反律的一个直观证明；给出了引理3 2 5 的证明；纠正了定理 3 3 5 的证明；给出了w a t e r si b e 方案的一个g a m e - b a s e d 证明等本文对双线性对 3 电子科技大学硕士学位论文 理论详尽的分析和介绍可以为想实现双线性对密码的工程人员提供有益的指导， 工程人员只要理解本文的大部分内容即可实现高效率的基于双线性对的密码体制 本文的第二个工作是研究如何设计基于双线性对的密码方案，我们通过分析已有 方案和构造新方案的方式展示了其中的设计思想和证明安全的方法 基于双线性对的密码学应用具有如图1 1 的框架从这个图可看出，为构建双线 图1 - 1双线性对应用框架图 性对应用，首要工作是建立对大数的支持，然后在此基础上支持有限域的各种操作， 接着是椭圆曲线和超椭圆曲线的支持，最后才是对双线性对的实现可以将提供双 线性对支持的模块看成是双线性对的底层引擎( 图1 1 的虚线部分) 本文关心图1 1 的虚线以外的部分，即关心双线性对的实现和优化以及基于双 线性对的密码体制底层引擎中的大数运算和有限域模块相对简单且有成熟的技 术实现，不是本文关注的重点，但对它们的优化也会带来双线性对计算及p b c 效 率的提升，有时需结合底层引擎来优化高层框图中的椭圆曲线部分由于与双线性 对关系密切且颇具代表性，是双线性对理论必备的基础知识，我们将在第二章对其 做比较详细的介绍本文的第三章将详细地讨论双线性对的理论、计算和优化，这 些讨论有助于工程人员实现快捷的双线性对本文的第四章结合可证明安全叙述 双线性对在密码学的若干应用结束语总结了全文，并展望了未来可进行的工作 4 第二章椭圆曲线 第二章椭圆曲线 目前密码学应用中的双线性对构建于两类代数几何对象：椭圆曲线和超椭圆 曲线其中构建在椭圆曲线上的双线性对由于相对简单且计算方便使其更适合 于密码学应用作为双线性对的预备知识，椭圆曲线理论相对独立和完整本 章回顾了与双线性对密切相关的部分椭圆曲线基础知识 2 1椭圆曲线定义与方程 椭圆曲线的概念可以有多种定义在代数几何中，凡是亏格( g e n u s ) 为1 的代数 曲线均称为椭圆曲线这样的曲线总可以用关于z ，y 的三次或四次代数方程f ( x ，y ) 表示，并且进一步，这样的方程可以转化为( 或有理等价于) w e i e r s t r a s s 方程 令f 是域，f 是其代数闭包f 上的二维射影空间p 2 是集合f 3 ( o ，0 ，o ) ) 一 其中一是f 3 ( ( o ，0 ，o ) ) 上的等价关系，即v ( o ，b ，c ) ，( d ，e ，f ) f 3 ( o ，0 ，o ) ) 具有 关系一当且仅当存在入f 使得( a ，b ，c ) = a ( d ，e ，厂) 射影空间p 2 中的元素可记 为( z ：y ：z ) 或( z ，y ，z ) 引入射影空间后可用统一的方式处理无穷远点理论上， 这种处理常常更自然其实仿射空间是不完备的，有时在它上面工作并不方便 定义2 1 ( 射影形式的椭圆曲线) 域f 上的椭圆曲线由w e i e r s t r a s s 方程给出： e ：y 2 z + a l x y z + a a y z 3 = x 3 + a 2 x 2 z - - i - a 4 x z 2 + a 6 2 3 ( 2 1 ) 或 f ( x ，z ) = y 2 z + a l x y z + a 3 y z 3 一x 3 一a 2 x 2 z a 4 x z 2 一a 6 2 3 ( 2 - 2 ) 这里a i f ，i 1 ，2 ，3 ，4 ，6 ) ，将这样的椭圆曲线记成e f 今l f 是域扩张，那 么椭圆曲线e 上的l 有理点集是指集合 e ( f ) = ( x ：y ：z ) p 2 ( l ) ：f ( x ，rz ) = o ) ( 2 - 3 ) 在几何上，如果曲线( 2 1 ) 或( 2 2 ) 上某点的切线不存在或有多条或重数不为1 ， 就称这点是奇异的在代数上，这个条件可以通过偏导数1 来刻画：曲线上的奇异 点是使得偏导o f a x ，o f o y ，o f o z 同时为。的点不含任何奇异点的曲线称 为光滑或非奇异( n o n s i n g u l a r ) 的椭圆曲线非奇异的椭圆曲线，具有处处存在切线 1 这里的偏导数是形式偏导数 5 电子科技大学硕士学位论文 的良好性质这对于定义椭圆曲线点加运算是有益的非奇异的椭圆曲线是我们期 望的正常的椭圆曲线反之如果椭圆曲线只含有一个奇异点，则称椭圆曲线是奇异 的( s i n g u l a r ) 奇异的椭圆曲线性质与非奇异的椭圆曲线性质有诸多不同，甚至于 迥异，通常区分这两种曲线类型对研究都会是有利的后面将只关心于非奇异的椭 圆曲线，如不特别声明，提及的椭圆曲线均指非奇异的椭圆曲线 根据定义2 1 ，显然对于任何满足f 冬f 7 f 的域f ，e ( f 7 ) 均有意义称 e ( f 7 ) 中的点为椭圆曲线的f 7 有理点特别记 e = e ( f ) = ( x ：y ：z ) 庐( f ) ：f ( x ，z ) = o ) 后面将说明e ( f 7 ) 关于椭圆曲线点加构成交换群，故也将e ( f ，) 称为有理点群 对于椭圆曲线( 2 1 ) ，令z = 0 则得椭圆曲线上唯一的有理点( 0 ：1 ：0 ) ，称为无 穷远点，记为o 当z 0 时，在式( 2 - 1 ) 中置z = x z 及y = y z ，就得到 e ：y 2 + a l x y + a 3 y = z 3 + a 2 x 2 + a 4 x + a 6 ( 2 - 4 ) 这称为仿射形式的w e i e r s t r a s s 方程注意e 现在可以表示为 e = e ( 一f ) = ( x ，z ) p 2 ( f ) ：f ( x ，z ) = o ) u ( ( o ，1 ，o ) ) 若记 e 1 = e 1 ( f ) = ( z ，y ) 一f ： ，秒) 是( 2 - 4 ) 的解) u _ d ) 2 ， ( 2 - 5 ) 那么可作e 到易的映射如下： ( z ，y ，1 ) h ( z ，可) ，( 0 ，1 ，0 ) ho 不难看出这个映射是一对一的因此椭圆曲线的有理点群可以用仿射坐标下的方 程的解集，外加一个无穷远点。来表示类似地，可将式( 2 5 ) 中的f 换成f 的任 何扩域f 7 ，并且混用射影形式下的符号将它记成e ( f ，) 现在考虑椭圆曲线的简化形式当考虑一组复杂对象时，研究者喜欢将这些对 象归类，并考虑其中的一些“典则形式” 如果两条椭圆曲线e 及e 7 经过f 上的一个可逆仿射变换化为另一个，则称这 两条椭圆曲线在f 上是同构的通过推导，可知这种可逆变换一定具有如下的线性 形式： fz = u 2 一+ n 【y = u 3 y 7 + 8 1 5 2 z + t 、。 2 这里仿射坐标下的无穷远点仍记为d ，这并不会导致混淆 6 第二章椭圆曲线 其中r ，s ，t ，u f ，牡0 反之，这样的仿射变换一定是可逆的 定义2 2 令e 和是椭圆曲线，e 的仿射方程为式( 2 4 ) ，而e 7 的仿射方程为 y 忍+ 口i z y 7 - j r o ；y 7 = z 嵋+ n ：z 忍+ 口：z 7 + n ：，a ：ei 1 ，2 ，3 ，4 ，6 ) 如果存在形如( 2 6 ) 的可逆仿射变换，则称椭圆曲线e 及在域f 上是同构的 注意式( 2 6 ) 给出的可逆仿射变换只是有理映射的一种由此可逆仿射变换定 义的同构关系是椭圆曲线集合上的等价关系这样，一个自然的问题就是要找出每 一个等价类中形式较为简单的那个椭圆曲线来表2 1 总结了在变换( 2 6 ) 作用下 化简后的椭圆曲线形式 表2 - 1典则形式的椭圆曲线类型 2 ，31 ，2 = z 34 - a 4 x 4 - a 6 最常用的情形 3 y 2 = z 34 - a 2 x 24 - a 6 非超奇异的 3 y 2 = z 34 - a 4 x - 4 - 0 4 3 超奇异的 2 1 ，24 - x y 。3 4 - a 2 x 2 + 0 6非超奇异的 2 y 2 + a 3 y2 z 34 - a 4 x - 4 - a 6 超奇异的 这种化简后的椭圆曲线形式可以称为典则形式或短的w e i e r s t r a s s 形式表 中示出的各种形式都是短的w e i e r s t r a s s 形式，而式( 2 1 ) ，( 2 2 ) ，( 2 4 ) 可称为长的 w e i e r s t r a s s 形式以后将更关注于短的w e i e r s t r a s s 形式 当w e i e r s t r a s s 方程中诸砚( 其中i 1 ，2 ，3 ，4 ，6 ) ) 取较小值时，这种方程特别 有用当a 取自集合 一1 ，0 ，1 ) 时，相应的椭圆曲线称为k o b l i t z 曲线 2 2椭圆曲线有理点群 法国数学家庞茄莱最早研究了e ( f ) 的结构，发现在集e ( f ) 中可以人为地引 入特殊的加法运算而使e ( f ) 成群这种定义加法的方式称为弦切法 令e 是域f 上的椭圆曲线，p 1 ，p 2 e 令l 是连接p 1 和马的直线( 如果 只= p 2 ，取l 为经过p 1 ，e 的切线) ，r = 一1 3 是l 与e 的交点再令l 7 是连接r 与0 的直线，三7 与e 交于b 则定义加法：p 14 - 马= p 3 ，如图2 1 所示 加法公式由弦切法能够导出点加的加法公式，这里仅以特征非2 和3 的域上 的椭圆曲线y 2 = x 34 - a t , + b 为例给出加法公式，其它情况的推导是类似的令 尸= ( x l ，y 1 ) ，q = ( x 2 ，y 2 ) e ( f ) 若p = 一q ，贝0p - 4 - q = 0 当尸一q 时，令 7 8 n q 晓 j 1f 口n 所以e 是超奇异的 反之，若t 0 ( m o dp ) ，则有s 1 = 亡，s n 三护( r o o dp ) 从而券e ( f 口) = 矿+ 1 一 s n 三1 一t 竹( m o dp ) 取n = p 一1 ，那么俨兰1 ( m o dp ) 于是pi 券e ( 口n ) ，即 孝e ( f g 。) 必有p 阶点，从而e 非超奇异 关于最后一个结论：t 三0 ( m o dp ) q + 1 一孝e ( ) 三0 ( m o dp ) 专 轷e ( f g ) 三1 ( m o dp ) 口 性质2 1 2 ( 【6 9 】) 设p 5 是素数则e f p 超奇异铺= 0 仁净弁e ( f p ) = p + 1 证明若t = 0 ，e 当然超奇异今令e 超奇异，亡0 ，t 三0 ( r o o dp ) 于是p 由定理2 7 ，l t l 2 伽故p 2 伽，从而p 4 口 推论2 1 3 假设p 是任意素数，f 口是f p 的扩域，e f p 是超奇异椭圆曲线如果 t = p + 1 一挣e ( f p ) = 0 ，那么# e ( f a ) = q + 1 证明对v n n ，有8 n = 0 故由w e i l 定理( 定理2 8 ) 知推论成立 口 注意上述推论中，若t 0 ，则一般并无移e ( f 口) = 口+ 1 性质2 1 4 ( 6 9 】) ( 1 ) e f 口超奇异净亡2 = 0 ，口，2 口，3 9 或4 口 ( 2 ) 特征为2 的域上的椭圆曲线是超奇异的兮它具有形式护+ n 3 y = z 3 + a 4 x + a 6 ( 3 ) 特征为3 的域上的椭圆曲线是超奇异的令它具有形式y 2 = z 3 + a 4 x + a 6 ， 即a 2 = 0 3 或称为非超奇异( n o n s u p e r s i n g u l a r ) 的 1 1 电子科技大学硕士学位论文 ( 4 ) 特征为2 或3 的域上的椭圆曲线是超奇异的冷其歹不变量为0 由性质2 1 2 和性质2 1 4 得：特征为p 的有限域f q 上的椭圆曲线e f q 是超奇 异的当且仅当( 1 ) 当p = 2 ，3 时，j ( e ) = o ；( 2 ) 当p 2 ，3 时，t = 0 现在给出z r 1 的结构： 若r 是p 的幂次，则要么e r 】= 0 ) ( 当e 是超奇异曲线时) ，要么e v 】竺z r ( 当e 是非超奇异曲线时) 当p 和7 互素时，e r 】竺z rxz r 这时e v 】有r 2 个元素，但任何元素的阶都 不是7 2 2 5构建椭圆曲线密码系统 2 5 1离散对数 一般群上的离散对数设g = ( g ，) 是群，q ，p g ，如果存在佗z 使得 p = 扩，则称n 是p 相对于底q 的离散对数，可记n = l o g 口卢对于一般的元素 q ，p g ，“离散对数”可能没有定义 在大多数密码应用中，离散对数总定义在循环群中，能够确保“离散对数”的存 在性离散对数的底数也取为循环群的生成元 定义2 1 5 令g 是循环群，9 是g 的生成元，z z r g 中的离散对数问题( d l p 是 指：给定夕，旷，计算z 如果将上述定义中的g 取为椭圆曲线的有理点群，则获得椭圆曲线上的离散 对数问题e c d l p 对一般群的离散对数的攻击能够说明一般群上的d l p 是一困 难问题，例如s h a n k s 大步小步算法、p o l l a r d - p 算法都是指数时间复杂度的另一 方面，p h o l i g - h e l l m a n 归约算法指出d l p 的困难性取决于其最大阶子群中离散对 数的困难性，这也是为什么子群密码系统能够流行的原因针对有限域的乘法群的 d l p 的指数积分算法的复杂度是亚指数时间的但是求解一般的e c d l p 与一般 群上的d l p 的算法具有相同的时间复杂度0 ( 洞因此当群阶相同时，e c d l p 比