（计算机软件与理论专业论文）双线性对的有效计算.pdf

摘要 双线性对的有效计算 专业：计算机软件与理论 博士生：赵昌安 指导老师：张方国教授黄继武教授 摘要 近年来，基于双线性对的特殊性质，诸多有趣的密码协议被构造出来这些协议利用其 他基本数学工具是难以构造的而实现它们的有效性取决于双线性对的计算效率本文主 要研究了双线性对的快速算法，获得如下结果： 1 利用某些椭圆曲线上具有非平凡自同构这一事实，构造了新的双线性对，计算这些新的 双线性对所需要的循环次数仅为t a 七e 对的一半，故计算效率获得提高 2 对一类嵌入次数为3 的超奇异椭圆曲线上的双线性对，构造了新的直线方程赋值，并利 用共轭元技巧避免扩域中的除法运算，提出了比以前更有效的算法 3 提出了基于双重基链的m i i l e r 算法，与传统的算法相比，在嵌入次数为6 的椭圆曲线上， 双线性对的计算效率提高9 4 a t e 对是目前计算效率最高的双线性对之一，但原始a t e 对的计算有效性取决于曲 线f r 0 6 e 疵u s 迹的大小我们提出了广义的a t e 对，在曲线f 7 d 6 e n i 钆s 迹较大的情形下， 计算广义的a t e 对比原始的a t e 对要有效得多 5 从抽象的角度论证了双线性对集合组成一个群，基于这一观察我们构造了一些新的双 线性对，计算这些新的双线性对仅需要非常少的循环次数它们的计算效率与r - a e 对 一样高 关键词：双线性对，1 a t e 对，a t e 对，有效算法，基于双线性对的密码系统 双线性对的有效计算第i 页，共9 8 页中山大学博士学位论文 英文摘要 e m c i e n tc o m p u t a t i o n so fb i l i n e a rp a i r i n g s m a j o r ： n a m e ： s u p e r v i s o r ： c o m p u t e rs o f t w a r ea n dt h e o r y z h a oc h a n 分a n p r o f z h a n gf j a n g g u o ，p r o f h u a n gj i w u a b s t r a c t i nr e c e n ty e a r s ，m a n yi n t e r e s t i n gc r y p t o g r 印h i cp r o t o e o l sb a s e do np a j r i n g sh a v eb e e n p r o p o s e d ，w h i c hc a n n o tb ea c h i e v e du s i n go 七h e rm a t h e m a t i c a lp r i m i t i v e s t h ee m c i e n c yo f i m p l e h l e n t i n gt h e s ep r o t o c o l si sd e t e r m i n e db yt h es p e e do fp a i r i n gc o n l p u t a t i o n s 、7 娓f o c u s o ni m p r o v i n gt h ee m c i e n c yo fp 出r i n gc o m p u t a t i o n s t h em a i nr e s u l t sa r ei i s t e da sf o l l o w s ： 1 u s i n gn o n t r i v i a la u t o m o r p h i s m so fs o m es p e c i a le l l i p t i cc u r v e s ，t h en e wp a i r i n g s a r e c o n s t r u c t e dw h i c hh a v eah a l fl e n g t ho fm i l l e rl o o pr e q u i r e df o rt h et a 七ep a i r i n g w 色 h a 鹏! p r o v e dt h a tc o m p u t i n gt h en e wp a i r i n g si 8m o r ee m c i e n tt h a nc o m p u t i n gt h e o r i 舀n a l ，i h t ep a i r i n g 2 n e wl i n ee v 出u a t i o n sa r ep r e s e n t e df o rc o m p u t i n gt h e1 、a t ep a i r i n go ns u p e r - s i n g u l a r e l l i p t i cc u r v e sw i t he m b e d d i n gd e g r e e 忌= 3 ，a n ds o m ec o n j u g a t et e c h n i q u e sa r ep r o p o s e df b ra v o i d i n gt h ed i v i s i o ni ne x t e n s i o nf i e l d s e ；a s e do nt h e s eo b s e r v a t i o n s ，a r n o d i f i e dm i l l e ra l g o r i t h mi sp r o p o s e d ，w h i c hi si n o r ee m c i e n tt h a nt h ep r e v i o u sf a s t e s t a l g o r i t h m 3 m i l l e ra 1 9 0 r i t h mb a s e do nd o u b l e b a s ec h 缸n si s 舀v e n f o rp a i r i n 分f r i e n d l yc u r v e sw i t h e m b e d d i n gd e g r e e 尼= 6 ，t h en e wa l g o r i t h mi s 9 f a s t e rt h a n 七h ep r e 讥o u sf a s t e s t r n e t h o d 4 t h ea t ep a l i r i n gi so n eo ft h ef a s t e s tp a i r i n gt i l ln o w h o 、v e v e r ，t h ee m c i e n c yo fc o m p u 七i n g 七h eo r i 百n a la t ep a i r i n gd e p e n d so nt h ev a l u eo ff l o b e n i u st r a e eo fe l l i p t i cc u r v e s w 色 h a v eg e n e r a l i z e dt h ea t ep a i r i n g t h em i l l e rl o o po ft h ev a r i a t i o n so ft h ea t ep a i r i n g c o u l dr e a c ht h el o w e rb o u n do ns o m ep a i r i n 分f r i e n d l yc u r v e sw i t hl a r g en o b e n i u st r a u c e 5 f l o ma na b s t r a c ta n g l e ，、) l r ep r o v e dt h a ta up a i r i n g sa r ei nag r o u p b a s eo nt h ef a c t s ， s o m en o v e lp a i r i n 伊w i t hs h o r tm i l l e rl o o p sa r e 舀v e nw h i c h i sa se m c i e n ta st h e 王0 a t e p a l n n g k e y w o r d s ：b i l i n e a rp a j r i n g s ，t a t ep a i r i n g ，a t ep a j r i n g ，e m c i e n ta l g o r i t h m s ，p 出r i n 分 b a 8 e dc r y p t o s y s t e r n s 双线性对的有效计算第i i 页，共9 8 页 中山大学博士学位论文 原创性及学位论文使用授权声明 原创性及学位论文使用授权声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体己经发表或撰写过的作品成果。对本文的研究作出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 学位论文作者签名：赵昌安 日期：沙睁歹月7 日 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版， 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院 系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采 用复印、缩印或其他方法保存学位论文。 学位论文作者签名起马孽 导师签名：纭青固 y 、 日期：的咯年f 月j ( 7 日 日期：矽。年石月岁日 双线性对的有效计算第3 页，共9 8 页中山大学博士学位论文 第一章绪论 第一章绪论 随着计算机科学、通信和网络技术的迅速发展，人们开始将一些现实行为在网络上实 现例如网上付款、网络投票等；或者由于地域及其他条件的限制，需要在网络上进行信 息传输和电子签名等然而我们在利用网络进行创新和实现着许多繁荣的同时，也遇到了 严竣的、不可忽视的问题信息安全问题公钥密码学应这种需求而产生 公钥密码学起源于1 9 7 6 年d i m e 和h e l l m a n 在文献f 1 1 提出了两个相距遥远的用户在没 有秘密安全信道的情况下，并且彼此不需要预先见面的条件下，如何达成一个公共的密 钥而这一点正是传统密码学难以克服的缺点他们工作中的第二个重要思想就是希望利 用公开信息作为加密密钥 1 9 7 8 年，r i v e s t 、s h a m i r 和a d l e m a n 在文献 2 1 中提出了第一个公开的公钥加密体制，并 且给出了第一个数字签名算法，使得现实生活中的签名能够电子化，网络化自此，公钥密 码学在近三十多年取得了蓬勃发展关于公钥密码学的更多内容，可参见 3 】 椭圆曲线密码学是公钥密码学中的一大热门领域，且有重要的应用前景它在某些方 面已取代r s a 等现存的公钥密码系统，逐渐成为研究重点这种密码系统的诱人之处在于 安全性相同的前提下，可使用较短的密钥文献4 ，5 1 详尽地综述了椭圆曲线在公钥密码学 中的各方面应用 近年来基于椭圆曲线构造的双线性对在公钥密码学中取得了长足的应用椭圆曲线 上的双线性对早期被用来攻击椭圆曲线有理点群上的离散对数问题，即所谓的m o v 攻 击f 6 1 和f r 攻击 7 1 ，前者利用椭圆曲线上的双线性w 西l 对，后者则利用椭圆曲线上的双线 性t a t e 对，其主要思想是将椭圆曲线有理点群中的离散对数问题归约到有限域乘法群中 的离散对数问题由于有限域乘法群中的离散对数问题存在亚指数时间内的指标计算攻 击( 【8 】的1 0 9 页) ，故这种归约使得某些椭圆曲线有理点群中的离散对数问题变得相对容易 而在2 0 0 0 年，s a k a i ，o h g i s h ，k a s a h a r a 9 】和j o u ) ( 【1 0 】分别独立提出基于双线性对的密码 协议这些协议借助于其他数学工具是难以构造的自此以后，双线性对被用来构造各种各 样的密码协议，比如基于身份的加密体制 1 l 】，短签名 1 2 ，1 3 】等等双线性对由此引起了密 码学者们的极大兴趣文献f 1 4 1 对基于双线性对的密码协议给出了很好的综述 双线性对的有效计算第1 页，共9 8 页中山大学博士学位论文 1 1 抽象的双线性对定义 1 1 抽象的双线性对定义 从抽象角度来看，双线性对是如下形式的映射【1 5 1 ： e ：g 1 g 2 一g t ， 其中g l ，g 2 是加法群，g t 是乘法群双线性对满足如下基本特性： 双线性性：对任意p g l ，q g 2 ，n z ，有e ( 佗p ) q ) = e ( p ，佗q ) = e ( 只q ) n 非退化性：一定存在p g l 和q g 2 使得e ( p q ) 1 g t ，其中l g t 表示g t 中的单位元 可计算性：存在有效的多项式时间算法计算出双线性对的值 在实际密码应用中，往往还要求g 1 ，g 2 和g t 中的离散对数问题是困难的因为这些密 码协议的安全性正是依赖于数学问题的难解性对密码协议设计者来说，双线性对可以看 作是一个”黑盒子 ，毋需了解其内部结构但是在设计协议时，也需要避免滥用现有的双线 性对所不具有的性质文献【1 5 l 综述了使用双线性对设计密码协议时应该注意的问题 1 2 双线性对的有效应用 基于椭圆曲线的双线性对，研究者们构造很多密码协议我们兹举几例说明 1 2 1 三方一轮密钥协商 密钥协商是密码学中最基本的问题之一公钥密码学中第一个密码协商 是d i m e 和h e l l m a n 所提出的，后来被称之为d i 伍e h e l l m a n 密钥协商| 1 1 我们首先回顾d i m e h e l l m a n 密钥协商，然后介绍j o u ) 【利用双线性对构造的三方一轮密钥协商f 1 0 1 假设需要通信的双方a l i c e 和b o b 通过不安全信道建立一个公共密钥他们可首先选取 某一公开的乘法循环群g ，夕是群g 的生成元孝g 定义为群g 的阶注意我们假设g 中的离 散对数问题( d l p ) 是困难的，即己知危= 旷和9 ，求解整数z 是困难的目前大多数密码协议 的安全性都依赖于数学中某些问题的难解性 然后，a 1 i c e 随机选取z a l ，2 ，榉g 一1 ，计算夕霉a 并发送给对方b o b 而b o b 随机 选取z b l ，2 ，券g 一1 ) ，计算旷且并发送给a l i c e 越i c e 可通过计算( g z 且) z 获得公共密 双线性对的有效计算第2 页，共9 8 页中山大学博士学位论文 第一章绪论 钥旷 如，而b o b 可通过计算( 9 z a ) z b 获得同样的密钥图l l 给出了d i m e h e l l m a n 密钥协商 的示意图 a l i c eb o b 图1 1d i m e - h e i l m a n 密钥协商 若有一攻击者e v e 也希望知道a l i c e 和b o b 所协商的公共密钥，那么就必须在已 知g ，夕，旷a ，旷b 的条件下，去计算9 z 加 这个问题被称为是计算d i 币e h e l l m a n 问 题( c d h p ) ，目前认为此问题也是难解的当然这个协议容易受到中间人攻击，如何 构造完善的d i 伍e - h e l l m a n 密钥协商可参见【3 】 假如需要秘密通信的三方试图建立一个公共密钥，那么仅仅通过离散对数系统这一模 型解决此问题是比较繁琐的j o u x 基于双线性对的特殊性质，提出了三方一轮的密钥协 商 1 0 】 首先设定公开系统参数选择加法群g 1 和乘法群g t ，这两个群的阶都是q ，选择一 固定生成元p g l ，存在一有效可计算的双线性对e ：g l g l _ g t ，而且e ( p p ) = 9 ， 9 是g t 中的生成元g 1 和g t 中的离散对数问题是困难的 需要秘密通信的三方a l i c e ，b o b ，c h r i s 各自随机选择三个正整数n ，6 ，c | 1 ，2 ，q 一 1 然后，a l i c e 计算n p ，发送给b o b 和c h r i s ；b o b 计算6 尸并发送给a l i c e 和c h r i s ；c h r i s 计 算c p 并发送a l i c e 和b o b a l i c e 计算密钥心= e ( 6 只c p ) 口；b o b 计算密钥= e ( a 只c p ) b ；c h r i s 计算密钥= e ( o 尸，6 p ) 。由双线性对的基本性质，易验证三方建立了一个公共密钥e ( p ) p ) 如该协 议的安全性依赖于双线性d i m e h e l l m a n 问题( b d h p ) 的难解性即己知尸j op ) 6p j c p ，计 算e ( p p ) 如是困难的同经典的d i f f i e h e l l m a n 密钥协商一样，这个协议不能抵抗中间人 攻击三方一轮的密钥协商利用双线性对的特殊性质，即群g l 中的决策d i m e h e l l m a n 问 题( d d h p ) 是容易的，但计算d i m e h e l l m a n 问题( c d h p ) 是困难的如果不利用双线性对这 一数学工具，三方一轮的密钥协商是很难设计的 双线性对的有效计算第3 页，共9 8 页 中山大学博士学位论文 1 2 双线性对的有效应甩 图1 2 给出了三方一轮密钥协商的示意图 c h r i s 图1 2三方一轮d i f f l e _ h e l l m a n 密钥协商 1 2 2 基于身份的加密体制 就通常的公钥密码体制而言，公钥的生成一般由私钥所决定，即 用户公钥= f ( 用户私钥) ， b 其中f 表示一个从私钥空间映射到公钥空间的有效单向函数比如基于离散对数问题 的e l g 锄a l 密码体制 1 6 】，这个密码体制是d i m e h e l l m a n 单向陷门函数的应用，把此单向 函数转换为公钥加密体制假设密码体制的系统参数为群g ，生成元为9 用户a l i c e 为了创 建自己的公钥，可随机选取z a 1 ，2 ，移g 一1 作为私钥，然后以z a 作为函数可= 旷的 输入，计算其对应公钥戌= 旷 但是我们必须注意到所得到的公钥r 与用户a l i c e 的身份 并没有必然的联系因此需要一种可信和可验证的方式使得二者关联起来 在实际应用的公钥密码系统中，通常需要一种能验证公钥与身份相关联的确认机制 目前有两种办法来建立这种机制，一种称为公钥证书基础设施( p k i ) ；另一种称为基于身份 的密码体制在这里我们重点讨论基于后一种方式的公钥密码体制 如果一个用户的公钥本身就与该用户的身份信息比如姓名，电子邮件地址或电话号码 等附属信息相关联，也就是把公钥和身份信息统一起来，这样就无须对公钥进行认证 s h a 觚r 于1 9 8 4 年提出了第一个基于身份的数字签名方案 1 7 】，在这个方案中，密钥的生 成过程为： 用户私钥= f ( 系统主密钥，用户公钥) ( 1 2 ) 双线性对的有效计算 第4 页，共9 8 页中山大学博士学位论文 第一章绪论 该公钥体制的密钥生成过程与一般公钥密码体制中的生成过程( 1 1 ) 完全相反，它们是以用 户公钥为函数的输入，而私钥为函数的输出当然为了使所计算的私钥保密，这个计算过程 不能公开，只允许可信任的权威机构( 即系统t a ) 知道既然用户公钥可以作为函数的输入， 那么我们就可以把用户的某一部分公开信息作为用户自身的公钥，比如用户的姓名，电子 邮件地址，电话号码和住址等等因此s h a 嘶r 把这样的密码方案称为基于身份的公钥密码 学 由于用户的私钥是由t a 所生成的，那么用户不得不无条件的信任t a 因此用户产生的 通信内容可被t a 完全获悉，并且t a 也可轻易伪造用户的签名等等这也是基于身份的公 钥密码学的一个弱点 s h a r n j r 当时猜想基于身份的加密体制也是存在的后来有两个基于身份的加密体制被 提出，一个是基于二次剩余问题的c o c k s 方案 1 8 】；另一个是由b o n e h 和f r a n k l i n 利用双线性 对性质所提出的基于身份的加密体制i b e 【1 1 ，1 9 】由于基于双线性对的加密体制效率较高， 因此仅介绍后者 b o n e h 和n a n k l i n 所提出的基于身份的加密体制由如下几部分组成： 系统参数设定：可信任的t a ( 或p k g ) 生成系统的全局安全参数和系统主密钥 用户密钥生成：t a 输入系统主密钥和与用户身份相应的比特串i d o ，1 ) + ，并输出相应的 用户私钥 加密过程：用公钥加密信息，这是一个概率型的加密算法 解密过程：把密文和私钥作为输入，计算得到相应的明文 图l 一3 详细描述了b o n e h 和n a n k l i n 所提出的基于身份的加密体制 现在我们验证基于身份的加密体制的正确性首先利用双线性对的性质，我们有： e ( 岛d ，) = e ( 。身d ，r p ) = e ( s q ，d ，r p ) = e ( q ，d ，s 尸) = e ( q ，d ，最砌) 从而在解密过程中，有 y o 岛( e ( d ，u ) ) = mo 巩( e ( q j r d ，) 7 ) o 飓( e ( q r d ，) r ) = m 双线性对的有效计算第5 页，共9 8 页中山大学博士学位论文 1 2 双线性对的有效应用 b o n e h 和n a n k l i n 提出的基于身份的加密体制 系统参数设定 1 生成两个群g 1 和g 2 ，群的阶都为q ，任意选择一个生成元p g l ，双线性对e ：g l g l g t 2 选择一个强杂凑函数日l ：( o ，l + _ g 1 这个函数把用户身份i d 映射到g l 中的一个元素 3 选择另一个强杂凑函数飓：g t _ 0 ，1 ) 他，这个函数使得明文空间是长度为n 的比特串 o ，1 n 4 t a ( 或p k g ) 随机选择s 猫，并计算系统公钥昂曲= s p 用户密钥生成 用户递交个人信息i d 给t a t a 确认用户身份信息的真实性后，为用户生成密钥： 1 根据用户的身份信息生成用户的公钥q ，d = 日l ( ，d ) ； 2 计算用户的私钥研d = s q ，d ，并把私钥返回给用户 加密过程 为了给接收方用户发送秘密信息，发送方首先获取公开参数g l ，g t ，e ，q ，p ，p p t 6 ，日l ，飓，然后随机 选择r z ；，对需要加密的信息m ，计算对应的密文为p = 】 解密过程 接收方得到c = 后，利用其私钥s ，d 计算矿oh 2 ( e ( 研d ，【厂) ) 来获取明文 双线性对的有效计算 图1 3 基于身份的加密体制 第6 页，共9 8 页中山大学博士学位论文 第一章绪论 这说明了加密和解密算法设计的正确性b o n e h 和n a n k l i n 在文献 1 1 】中还提供了此加密体 制安全性的形式化证明因这不是本文的研究重点，所以我们忽略安全性证明部分的介绍 1 3 双线性对有效计算的重要性及现状 椭圆曲线理论在基础数学中的代数几何领域已经发展了大约1 5 0 多年，最近二十年作 为基本工具在公钥密码学领域大放异彩1 9 8 5 年，基于有限域上椭圆曲线群中的离散对 数问题，k o b l i t z 2 0 】和m i l l e r 2 1 】独立提出了椭圆曲线公钥密码体制有趣的是，也就在这一 年，m i l l e r 在一篇没有发表的手稿中给出了椭圆曲线上双线性w 萌l 对计算的多项式时间算 法2 2 1 但因为当时双线性对在公钥密码学中尚未取得任何有效应用，因此没有研究者关注 此算法双线性对在公钥密码学获得诸多应用后，其计算的重要性也日趋显著在2 0 0 4 年， m i l l e r 重新整理了当年的手稿，详尽地讨论双线性w d l 对的计算及其应用 2 3 】 双线性对在上个世纪九十年代曾被用于椭圆曲线上离散对数的攻击，即所谓的m o v 攻 击和f r 攻击自此，椭圆曲线上的双线性对引起了密码学家的关注在2 0 0 1 年，s a l ( a i 等人 和j o u x 同时分别利用椭圆曲线上的双线性对设计了密码方案，这开创了椭圆曲线密码学上 的新篇章这也是基础理论在密码学中取得新应用的又一典型例子此后，椭圆曲线上的双 线性对被用来设计各种各样的密码协议，比如前面介绍的基于身份的加密体制，三方一轮 密钥协商等等 正因为双线性对作为一基本工具在协议设计中取得了广泛应用，为了使这些协议具有 实用性，就必然要求提高双线性对的计算效率人们由此开始关注当初m i l l e r 所提出的双线 性对计算方法因此双线性对计算方面的发展正是由应用要求所促成的 虽然计算椭圆曲线上的双线性对是一多项式时间算法，但是其计算效率与真正应用中 的要求相比，仍然有一定差距目前关于双线性对计算已经取得了一些很好的结果但这些 结果都受一定条件的影响和限制，比如有的算法仅适用于超奇异曲线f 2 4 】，有的算法受曲线 的m b e n i u s 迹大小的影响2 5 1 等等另外，在资源受限制的条件下，比如计算资源或者存储 资源或者带宽有限的情形下，双线性对的计算效率更有待提高基于双线性对的公钥密码 学标准i e e ep 1 3 6 3 3 正在筹备之中，有不少双线性对计算标准正作为草案提交所以，我 们更需要努力提出新的算法，并向国际化标准发展 双线性对的有效计算第7 页，共9 8 页中山大学博士学位论文 1 4 本论文的体系结构 1 4 本论文的体系结构 第一章概述信息安全的背景以及双线性对在密码学中的基本应用，并阐明本论文的研 究意义第二章将简要给出与双线性对计算相关的背景知识第三章将分析加快双线性对 计算的各种可能性，并综述目前已有的研究成果第四章将讨论在一些特殊的椭圆曲线上 双线性对的快速算法在第五章中，我们将讨论一般曲线上的双线性对的快速算法第六 章将总结整个论文以及展望将来的工作 双线性对的有效计算 第8 页，共9 8 页中山大学博士学位论文 第二章预备知识 第二章预备知识 在这一章节，我们将给出本论文所需要的基本背景知识首先将讨论有限域的相关概 念和有限域中的基本算术，然后介绍椭圆曲线和除子理论，最后讨论基于椭圆曲线的传统 双线性w e i l 对和双线性t a t e 对及计算这些双线性对的基本算法 2 1有限域 有限域是计算机科学和数字通讯领域最基本的数学工具之一下面给出有限域的概念 和有限域中的一些基本性质更多的介绍可参见【2 6 ，2 7 j 所谓有限域就是有限个元素所组成的域设1 是有限域f 中的单位元，f 对加法运算来 说是有限交换群，所以中每个元素q 对加法都是有限阶的，即存在正整数佗，使n q 为0 这也是有限域与无限域( 比如复数域等) 的不同之处 f 中满足n 1 = 0 的最小正整数佗叫做有限域f 的特征 下面给出有限域中的一些结论，限于篇幅，不给出具体证明 ( 1 ) 有限域f 的特征必然是素数，从而f 必有p 元子域b ，其中p 为一素数 ( 2 ) 有限域f 的元素个数q 必然是某一素数p 的方幂：q = p m ，其中m 为正整数f 可看为 有限域f p 上的m 维向量空间，f 的加法群是m 个p 阶循环群的直和 ( 3 ) q 元有限域f 的非零元素全体形成的乘法群砸 + 是( g 一1 ) 阶循环群存在a f ，使 得f = f p ( q ) ( 4 ) 对于每个正整数m ，存在睇上的唯一代数闭包f 口( 其中q = 矿) ，它是由方 程一z = 0 的全部解组成的集合 ( 5 ) 设f 口和g ，是有限域则f 口为 q ，的子域当且仅当存在正整数f ，使g ，= 特别 地，f p n 是f p m 的子域当且仅当佗l m ( 6 ) 对正整数m 1 ，f g m 中必存在m 次不可约多项式，( z ) ，并且对于， ) 在的代数闭 包中的任一个根a ，有f g 【q 】= f 口( a ) = 一 双线性对的有效计算第9 页，共9 8 页中山大学博士学位论文 2 1 有限域 2 1 1 有限扩域的具体构造及算术 由上一小节的事实6 ，可构造素域f p 的佗次扩域其中p 为一素数可选取素域f p 上 某个n 次不可约多项式厂( z ) 的根q ，将a 添加到素域f p 中，即得到扩域矿= f p ( d ) 竺 ( t 厂 ) ) 为了快速计算双线性对的需要，下面讨论n 为2 和3 时有限域中的具体构造和 基本算术 2 1 2 二次扩域 假勘为一素数，厂( z 为上的二次不可约多项式，q 为厂( z ) = o 的一个根则二次扩 域。= ( 口) 竺f p 旧( t 厂( z ) ) 假定基域f p 中的乘法，平方和求逆所耗费的运算量分别 为m 、s 和i 假鳓为一素数且满足p 兰3 ( m o d4 ) 由 ( 一1 ) ( p 一1 ) 2 三一l( m o dp ) ， 可知z 2 + 1 为f p 上的不可约多项式假设z 为z 2 + 1 = o 的一个根，则吩竺( i ) 即有 ：= ( a + 6 i i 口，6 ，z 2 + l = o ) 在有限域的基本算术运算中，加法和减法的运算量与乘法和求逆相比可忽略，故在此 仅讨论乘法与求逆的快速运算技巧 假设n + 跣和c + 也是f p 。中的两个元素，直接计算 ( a + 跣) ( c + d i ) = ( 口c 一6 d ) + i ( 6 c + a d ) 则需要4 m 如果用k a r a t s u d a 技巧 2 8 】可减少1 m ，其计算公式则变为 ( 口+ 兢) ( c + 出) = ( 口c 一6 d ) + z ( o + 6 ) ( c + d ) 一一6 明 二次扩域中的平方运算仅需2 m ，其计算公式为 ( o + 跣) 2 = ( 口+ 6 ) ( o 一6 ) + t 2 n 6 二次扩域中的求逆可用如下的转换公式： 1 o 一跣 _-_ o + 跣0 2 + 6 2 由上可得，二次扩域中的求逆运算需要l ，+ 2 s + 2 m 双线性对的有效计算 第l o 页，共9 8 页中山大学博士学位论文 第二章预备知识 2 1 3 三次扩域 在双线性对的计算中，往往也涉及到三次扩域中的运算因此，下面我们讨论三次扩域 的构造和基本算术技巧 假定厂 ) = z 3 + e 为上的三次不可约多项式，且q 为， ) = o 所在分裂域中的一根 则 3 = n + 她+ 倒2 i o ，6 ，c f p ，a 3 + e = o ) 在实际应用中，e 通常取较小的数值，故忽略与e 的乘法运算量如果应用k a r a t s u d a 技 巧 2 8 】，三次扩域中的乘法需要6 m 如果用t o o m - c o o k 技巧 2 9 】，则可减为5 m 下面考虑三次扩域中的平方运算( n + 6 a + 伽2 ) 2 如下的快速运算技巧是 由c h u n g 和h a s a n 在文献【3 0 】中给出的预计算a = a 2 ，b = 2 6 c ，c = c 2 ，d = ( o 一6 + c ) 2 ，e = ( a + 6 + c ) 2 ，则 ( n + 她+ c q 2 ) 2 = ( a j e 7 佗) + ( ( e d ) 2 一b 一佗c ) q + ( e a c 一( e d ) 2 ) q 2 因此三次扩域的平方运算需要4 s + l m ( 在此忽略被2 除的运算量及加减法的运算量) 对于三次扩域中的求逆1 ( 口+ 6 a + 锹2 ) ，可先计算a = 口2 + n 6 c ，b = 一佗c 2 一0 6 ，c = 6 2 一口c ，再求f = 一仃6 c + o a 亿c b 那么 1a + b q + c a 2 i 而i 五万2 r 一 2 2 椭圆曲线 由n e a lk o b l i t z 2 0 】和v i c t o rs m i l l e r 【2 1 】分别独立提出了椭圆曲线密码体制就是利用 有限域上的椭圆曲线中的点按照某种运算( 即切割线法) 构成的有限交换群，也存在形 式的离散对数计算困难问题这一事实关于椭圆曲线密码学更详细的介绍可参见 4 ，3 l 】 s i l v e h n a n 在文献【3 2 ，3 3 】中讨论了椭圆曲线的算术理论在实数域r 上的椭圆曲线的形 式如下： 定义2 1实数域r 上的一条椭圆曲线，是指实平面上由方程： e ：可2 = z 3 + a z + 6 给出的曲线e ，其中。和6 是实数，并且4 0 3 + 2 7 6 2 0 由这个曲线上的全部( 实坐标) 点 双线性对的有效计算第l l 页，共9 8 页中山大学博士学位论文 2 2 椭圆曲线 和一个无穷远点d 构成的集合表示成e 俾，即： e 俾) = p = 0 ，秒) r r i 夕2 = z 3 + o z + 6 ) u ( p ， 而在公钥密码学中，主要是使用定义有限域乃上的椭圆曲线 假设q = 矿，其中p 为素数，m 为正整数又设f q 是含有q 个元素的有限域，p 是这个域 的特征，m 为扩张次数 定义2 2假设e 为定义在有限域f 口上的椭圆曲线，椭圆曲线e 的方程为： e ：y 2 + 口l x y + 0 3 y = x 3 + n 2 x 2 + 口4 x + 0 6 其中瓯f 口，曲线的判别式o 定义2 2 所定义的椭圆曲线方程也称为长w 文e r s t r a s s 方程，此方程适用于任意有限域 当有限域的特征p 5 时，有如下的短w | e i e r s t r a s s 方程 定义2 3 设p 为素数，p 5 ，有限域f p 上的一条椭圆曲线是指： e ：秒2 = z 3 + o z + 6( m o dp ) ， 其中o ，6 并且4 n 3 + 2 7 6 2 0 以e ( f p ) 表示曲线e 在上的所有点( 加上无穷远 点o ) 构成的集合 e ( ) = 尸= ( a ，p ) ：p 2 = q 3 + o q + 6 ) u p 】- 这是一个有限集合同样地，可按照实数域中的切割线法来形式地定义两点之间的运算 可证明有限集合按照这样的运算形成一交换群，零元素为p 元素之间的运算如下： 1 假设p 1 = 1 ，可1 ) ，则一p l = 如l ，一可1 ) 2 1 阪设尸1 一( z l ，秒1 ) 局= ( z 2 ，驰) ， 当p l p 2 时，定义a = ( 耽一耖1 ) ( z 2 一z 1 ) ； 当p 1 = 岛时，定义a = ( 3 z ；+ o ) 2 秒1 如果p l + 恳= b = ( z 3 ，秒3 ) ，掣 j z 3 = a 2 一z 。一z 2 ， 1 蜘：( z 1 一z 3 ) 入一可1 双线性对的有效计算第1 2 页，共9 8 页 中山大学博士学位论文 第二章预备知识 定义2 4设q = 2 竹，n l ，此时在f g 上的非奇异椭圆曲线方程为： e 眈，口6 ：犷+ z 可= z 3 + 0 2 2 2 + 0 6 ， 其中口2 ，口6 睇以e ( f 2 n ) 表示曲线e 在f 沙上的所有点( 加上无穷远点o ) 构成的集合 下面同样给出其中点的基本运算： 1 假设p 1 = l ，可1 ) ，则一p l = ( z l ，秒l + z i ) 2 假设r = l ，秒1 ) ，恳= ( z 2 ，s ，2 ) ， 当z l z 2 时，定义入= ( 耽+ 可1 ) ( z 2 + z 1 ) ，p = ( 秒l z 2 + 耽z 1 ) ( z 2 + z 1 ) ； 当z l = z 2 ，耖1 o 时，定义a = ( z + 秒1 ) z 1 ，肛= z ； 如果p 1 + 恳= 尼= ( z 3 ，钠) ，则 i 黝= a 2 + a + 口2 + z l + z 2 ， i 蜘= ( 入+ 1 ) z 3 + 肛= ( z 1 + z 3 ) 入+ z 3 + 可1 、 我们用e ( ) 表示曲线e 在上的所有点( 加上无穷远点p ) 构成的集合显然，这是 一个有限集合，即 e ( i g ) = p = ( z ，秒) f 口g ，可2 + 口l z 可+ 0 3 秒= z 3 + 口2 2 2 + 0 4 z + n 6 ) u p ) e ( 巧) ( 简写为e ) 表示曲线e 在巧中的所有点( 加上无穷远点p ) 构成的集合，即 e = e ( 巧) = p = ( z ，可) 巧巧：可2 + n l z 可+ 0 3 秒= z 3 + 0 2 2 2 + n 4 z + 口6 】u p e 【f 】表示在e 中所有阶能整除c 的点的集合，即 e 2 】= p e ( 巧) ：【f 】p = p ) e ( ) 【f 】表示在e ( 峙) 中所有阶能整除c 的点的集合，即 e ( ) 【f 】= p e ( f q ) ：【2 】p = p 】 定义2 5假设p 是e ( n ) 中的一点，阶为2 ，且f 与g 互素f 不整除g l ，我们定义满 足如下条件的最小正整数忌 f 妒一1 兮e f 】ce ( 砸 g t ) 为e ( ) 的m 0 y 次数 6 】，又称为e ( f g ) 的嵌入次数 对于通常的椭圆曲线，其嵌入次数是非常大的 3 4 】，实现其双线性对的计算不切实际 目前一般有两种曲线存在较小的嵌入次数，第一种是超奇异( s u p e r s i n g u l a r ) 椭圆曲线， 双线性对的有效计算第1 3 页，共9 8 页 中山大学博士学位论文 2 3 除子理论 其嵌入次数不超过6 ( 参见【3 5 ，3 6 】) ；另一种就是所谓的m n t 曲线，m i y a j i 等人首先在【3 7 】中 用复乘的方法给出了后分别等于3 ，4 ，6 的非超奇异( n o n s u p e r s i n g u l a r 或o r d i n a r y ) 椭圆曲线 n e e m a n 等人在文献 3 8 】中综述了如何寻找适于双线性对计算的曲线 下面介绍变形映射( d i s t o r t i o nm a p ) 的概念 3 9 j ，v e r h e u l 曾用其比较x t r 密码体制与超 奇异曲线密码体制的安全性后来，b a r r e t o 等人借助这一工具加速双线性对的计算 4 0 1 定义2 6 变形映射( d i s t o r 七i o nm a p ) 是指一个从e ( 虬) 到e ( f 口t ) 非有理的( r a t i o n a l ) 同 态： ：e ( ) 一e ( f g t ) 使得e ( f 口) 中的点被映到e ( f 驴) 中的某一点，与原来的点线性无关 2 3 除子理论 除子理论在代数几何中是非常重要的一部分在此我们介绍和除子相关的基础知识， 为后面定义具体的双线性对做准备更多内容请参考【3 2 ，3 5 】 定义2 7假设e 为定义在有限域砸 口上的椭圆曲线对任意点p e ( 瓦) ，定义形式符 号( p ) 那么e 上的除子d 是如下的形式和： d = ( 弓) ， z 弓e ( 可) 其中仅有有限多个仃f 0 因此一个除子是由椭圆曲线e 上的点所生成的自由a b e l 群中的 某个元素假设d l = b e ( _ ) ( 弓) 和d l = 马e ( 瓦) 叻( 弓) ，其中，z ，定义形 式加法d l + d 2 = b e ( 瓦) ( 哟+ ) ( b ) 按照这样的形式加法运算，e 上的所有除子形 成自由a b e l 群 定义2 8 一个除子d = 马e ( 巧) ( 弓) 的次数定义如下： d e 9 ( d ) = z ， j 除子的和函数定义如下： 8 钆m ( d ) = 嘞b j 注意在和函数中的加法即为椭圆曲线有理点群中的加法运算， 下所得到的结果为椭圆曲线上的点，而不再是除子 双线性对的有效计算第1 4 页，共9 8 页 一个除子在和函数的作用 中山大学博士学位论文 第二章预备知识 定义2 9在椭圆曲线e 上的一个函数是指有理函数 ，( z ，秒) = ( z ，秒) m ( z ，秒) f 口( z ，秒) 至少在e ( 巧) 中的一点有意义( 比如，函数1 ( 可2 一z 3 一口z 一6 ) 是不允许的) 如果一个函 数，( z ，芗) 在某点尸( 黝，跏) 取函数值，( 黝，踟) = 0 ，则称，以点尸为零点如果取值为无穷大， 则称，以点p 为极点 如果厂是e 上一个非零函数，则卯如