（计算机软件与理论专业论文）tate对的计算及其在密钥交换协议中的应用.pdf

摘要 t a t e 对的计算及其在密钥交换协议中的应用 专业：计算机软件与理论 硕士生：郑督 指导老师：张治国 摘要 由k o b l i z 和m i l l e r 提出的椭圆曲线密码学是密码学中一个具有重要意义的研究课题。 椭圆曲线上的双线性对在椭圆曲线密码中起着重要意义。一方面，椭圆曲线上的双线性 对被用来攻击椭圆曲线上离散对数问题，将椭圆曲线有理点群上的离散对数问题归约为 有限域乘法群上的离散对数问题：另一方面，双线性对被用作构造密码协议。因此，提 高椭圆曲线上双线性对的计算效率至关重要。本文主要研究了双线。陛t a t e 对的计算及其 在密钥交换协议中的应用，获得如下结果： 1 在雅可比坐标下，给出了计算两类非超奇异椭圆曲线上的双线性t a t e 对，m i l l e r 算法 复杂度的估计值。 2 给出了有限域f 曰上，求逆运算和乘法运算的计算效率的测试结果和分析， 给出上述估计值时用到的假设。 3 指出了一类利用双线一i 生t a t e 对构造的基于身份的密钥交换协议的不足， 析。 关键词：双线性对、t a t e 对、密钥交换协议。 用来支持 并给出分 第4 页，共5 3 页中山大学硕士学位论文 c o m p u t a t i o no ft a r ep a i r i n ga n di t sa p p l i c a t i o ni n k e y - - e x c h a n g ep r o t o c o l 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 d uz h e n g z h i g u oz h a n g a b s tr a c t e l l i p t i cc u r v ec r y p t b g r a p h yp r o p o s e db yk o b l i za n dm i l l e ri sa c r i t i c a lr e s e a r c ht o p i ci n c r y p t o g r a p h y b i l i n e a rp a i r i n g s o ne l l i p t i cc u r v ee x e r ta ni m p e r a t i v er o l ei ne l l i p t i cc u r v e c r y p t o g r a p h y f o ro n et h i n g ，b i l i n e a rp a i r i n g sa r eu s e dt oa t t a c kt h ed i s c r e t el o g a r i t h m p r o b l e mo ne l l i p t i cc u r v e s ，w h i c hr e d u c et h ed i s c r e t el o g a r i t h mp r o b l e mo ne l l i p t i cc u r v e s t ot h ed i s c r e t el o g a r i t h mp r o b l e mo v e rf i n i t ef i e l d f o ra n o t h e rt h i n g ，b i l i n e a rp a i r i n g s a r eu s e dt oc o n s t r u c tc r y p t o g r a p h i cp r o t o c o l s t h e r e f o r e i ti si m p e r a t i v et oi m p r o v et h e c o m p u t a t i o ne f f i c i e n c yo fp a i r i n g s i nt h i st h e s i s ，t h ec o m p u t a t i o no ft a t ep a i r i n ga n di t s a p p l i c a t i o ni nk e y - e x c h a n g ep r o t o c o la r ed i s c u s s e d t h em a i nr e s u l t sa r el i s t e da sf o l l o w s ： 1 i nj a c o b i a nc o o r d i n a t e ，a ne s t i m a t e dc o m p u t a t i o nc o m p l e x i t yo fm i l l e ra l g o r i t h mi s g i v e nc o n c e r n i n gc o m p u t i n gt w ot y p e so ft a t ep a i r i n g sc o n s t r u c t e db yu s i n ge n d o m o r - p h i s mo nn o n - s u p e r s i n g u l a re l l i p t i cc u r v e s 2 t e s tr e s u l t sa b o u tt h ec o m p u t a t i o ne f f i c i e n c yo fi n v e r s i o na n dm u l t i p l i c a t i o no v e rf i n i t e f i e l dw i t hb i gp r i m eo r d e ra r es h o w nt os u p p o r tt h eh y p o t h e s i si nt h ea b o v em e n t i o n e d e s t i m a t i o n 3 p o i n to u ta n da n a l y z et h ed e f i c i e n c yo ft w ok e y - e x c h a n g ep r o t o c o l sc o n s t r u c t e db y u s i n gt a t ep a i r i n g k e y w o r d s ：b i l i n e a rp a i r i n g s ，t a t ep a i r i n g ，k e y - e x c h a n g ep r o t o c 0 1 第5 页，共5 3 页 中山大学硕士学位论文 原创性及学位论文使用授权声明 原创性及学位论文使用授权声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版， 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院 系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采 用复印、缩印或其他方法保存学位论文。 学位论文作者签名：j 锋督 醐：叶一加 导师签名：依别司 日期：舢7 年j 月汕日 第3 页，共5 ：j 页 中山大学硕士学位论文 第一章绪论 第一章绪论 椭圆曲线密码学是由k o b l i z 1 】和m i l l e r 2 】于1 9 8 5 年分别提出。椭圆曲线密码体制的优 点在于，同其他传统的公钥密码体制相比 3 】，在相同安伞性的前提下，椭圆曲线密码体 制可以使用较短的密钥达到同样的安全性。因此，椭圆曲线密码学成为密码学界的研究 热点。 椭圆曲线上的双线性对在早期被用来攻击椭圆曲线有理点群上的离散对数问题。这些 算法思想足将椭圆曲线有理点群上的离散对数问题归约为有限域乘法群上的离散对数问 题 4 】。2 0 0 2 年以来，基于椭圆曲线上的双线性对构造的密码协议在密码学实际应用中起 着越来越重要的作用。 下面给出，两种基于椭圆曲线上双线性对构造的密码体制，来更好的说明椭圆曲线上 的双线性对是如何用米构造密码体制的和提高双线性对的计算在实际应用中的价值；并 在第四章给出两类基于身份构造的密钥交换协议的不足。 1 1 基于w e i l 对的身份加密体制 为了简单起见，我们考虑基于一类特殊椭圆曲线上w e i l 对 5 】构造的基于身份的加密。 令椭圆曲线e ：y 2 = z 3 + 1 定义在有限域上，其中p = 2r o o d3 。再令，峰是 一个三次单位根。 定义如下映射， p ：e ( f p 。) 一e ( 砸) ( z ，y ) 一( u z ，可) ，f l ( o e ) = o e 假设椭圆曲线上有理点p 的阶为n ，贝o f l ( p ) 的阶也为n 。定义约化的w e i l 对为： ( 尸1 ，b ) = e n ( 最，p ( 恳) ) ，其中e n 如通常定义下的w e i l 对，最，局e m 。 当3fn ，且p e ( f p ) 的阶为n ，则e n ( p ，j p ) 是单位元的n 次本原根。 在该基于w e i l 对的身份加密密码体制中，我们假定，每个用户都有一个基于他们身份 的公钥，例如，他们的邮件地址。一个可信赖的机构为每个用户分配一个对应其公钥的 第7 页，共5 3 页中山大学硕士学位论文 1 1 基于w e i l 对的身份加密体制 私钥。在多数公钥密码体制当中，当a l i c e 想要给b o b 发送消息时，a l i c e 首先要查找b o b 的 公钥。然而，a l i c e 需要某种方法来确信这个公钥确实是属于b o b 的，来防止某些人诸 如e v e 来冒充b o b 。在该密码体制当中，认证发生在b o b 和可信赖的机构初始通信阶段。 在此之后，b o b 是唯一拥有用其公开身份进行加密的信息解密密码的人。 一个很自然的问题是，为什么r s a 3 不能被用作来构建这样一个密码体制? 例如， 所有的用户能够使用同一人整数n ，其唯一的素数分解只有可信赖的机构知道。b o b 的身 份，称作b o b i d ，是其公开的加密指数。可信赖的机构将计算其秘密的解密指数，并把 该解密指数传给b o b 。当a l i c e 想要向b o b 发送一个消息m ，a l i c e 首先计算m 6 d 砌m o d 扎。 然后，b o b 将用由可信赖的机构提供的解密指数来解密。问题在于，任一个用户，如 同b o b ，当知道一个加密和解密指数时，就可以采用消息重放攻击来分解大整数n 。因 此，就可以获得整个在该密码系统中传输的消息。因此，如此构建的密码系统，不能够 提供对消息的保密。如果，对每一次的通讯，采取不同的大整数扎，这样问题又回到原来 的问题，如何保证用于每一次通讯的大整数n 的安全传输。 为了解决上述问题，密码学家提出了基于身份的加密，来避免上述提到的诸多问题。 为了构建该密码体制，可信赖的机构做如下步骤： 1 选择e ( f p ) 中一个阶为z 的点p 。 2 选择两个哈希函数皿和凰。其中哈希函数日l 将任意长度的比特串映射到椭圆曲 线e 上的一个阶为z 的点。哈希函数凰将f 护中乘法群的阶为f 的元素映射为一条长度为n 的 字符串，其中n 为将要传送消息的长度。 3 在f 的乘法群中选择一个随机数s ，并计算6 = s p 。 4 公开p ，研，1 1 2 ，n ，p ，6 ，保留8 。 如果一个身份用i d 标识的用户想要获得一个私钥，可信赖的第三方做如卜步骤： 1 计算q ，d = h 1 ( i d ) ，此时q 为椭圆曲线e 上一点。 2 令d i d = s q ，d 。 3 当可信赖的机构验证用户的身份标识无误后，可信赖的机构将d d 发送给用户。 如果a l i c e 想要发送消息m 给b o b ，a l i c e 将做如下步骤： 1 a l i c e 查找b o b 的标识，例如，i d = b o b c o m p u t e r c o m ，然后计算q j d = 第8 页，共5 3 页中山大学硕士学位论文 第一章绪论 - 1 ( j d ) 。 2 在觋的乘法群中选择一个随机数r 。 3 计算g x d = e ( q j d ，) 。 4 令密文信息为：c = ( r p mo 飓( 夕j d ) ) 。 b o b 解密信息c = ( u ，秽) ，做如下步骤： 1 用b o b 的私钥d i d 计算h ，d = e ( d i d ，牡) 。 2 计算m = 钉o n 2 c n i o ) 。 解密过程具体如下：e c d w ，u ) = e c s q i o ，r p ) = e ( o w ，p ) 卵= e ( o w ，6 ) r = g i d r 。 因此，m = 口o n 2 ( e ( d w ，牡) ) = ( m o h 2 ( g w 7 ) ) o 凰( 卯d 7 ) = m 。 1 2 三方d i f f i e - h e l l m a n 密钥交换 为了叙述的完整性，首先给出两方密钥协商的体制，然后，再给出基于双线性对的一 轮三方密钥协商体制。 两方密钥协商体制是由d i 胁h e l l m a j l 6 】提出，采用了有限域上的乘法群来构造。其主 要步骤如下： a l i c e 和b o b 协商一条定义在有限域酩上的椭圆曲线。同时，a l i c e 和b o b 选定该椭圆曲 线上上的一点p ，要求由点p 生成的子群 ，具有较大的阶数。 1 a l i c e 选择一个秘密的整数a ，并计算只= 口p ，发送只给b o b 。 2 b o b 选择一个秘密的整数b ，并计算p b = 6 p ，发送r 给a l i c e 。 3 a l i c e 计算a p b = a b p 。 4 b o b 计算6 只= b a p 。 5 a l i c e 和b o b 使用某种公开的方法，从a b p 中提取一共享密钥。 上述协议分析如下：一个监听者e v e 所能够获得的信息只有a l i c e 和b o b 选取的椭圆曲 线e ，有限域f 口，点p ，n p ，6 尸。但是，监听者e v e 很难获得a b p 。如果监听者e v e 能够 获得a b p ，则相当予监听者e v e 能够解决c o m p u t a t i o n a ld i f f i e - h e l l m a np r o b l e m 。 j o u x 提三方 d i f f i e - h d l m a n 密钥协商 7 】。 第9 页，共5 3 页中山大学硕士学位论文 1 3 本章小结 假设a l i c e ，b o b ，c h r i s 想建立一个共享密钥。使用上述d i f f i e - h e l l m a n 密钥共享协议 需要两轮交互。而使用双线性对，可以通过一次交互来完成三方的密钥协商。 令尸为阶为n 的超奇异椭圆曲线上的点，通常n 被选作大素数。a l i c e ，b o b ，c h r i s ， 做如下操作： 1 a l i c e ，b o b ，c h r i s 相应的选取秘密整数ar o o d 佗，bm o dn ，cm o d 凡。 2 a l i c e 广播( 1 i p ，b o b 广搔b p ，c h r i s 广播c po 3 a l i c e 计算e 。( 6 只c p ) 。，b o b 计算e n ( op o f ) 6 ，c h i t s 计算e n ( n 尸，b p ) 。 4 因此，三个用户每一方通过计算得到同一数值，并通过使用预先协商的密钥提取 算法提取会话密钥。 1 3 本章小结 本章仅通过给出两种常见的双线性对在密码协议中的应用，来说明提高双线性对的计 算效率对于基于身份的密码协议的实现的重要性。 本论文将在下一章给出计算椭圆曲线上双线性对的所需的数学背景知识。 第1 0 页，共5 3 页中山大学硕士学位论文 第二章预备知识 第二章预备知识 弟一早 耿亩大h 以 在此章节，我们给出用于椭圆曲线上双线性对计算所需要的基本背景知识。首先， 我们将给出用于椭圆曲线上双线性对计算所需要的有限域中的相关概念，并介绍椭圆曲 线和除子理论；然后，给出椭圆曲线上双线陛w e i l 对和t a t e 对的定义，以及计算椭圆曲 线上双线性w e i l 对和双线性t a t e 对的m i l l e r 算法；最后，给出在仿射坐标下和雅克比坐标 下m i l l e r 算法中用到的倍点和点加运算的公式。 2 1 有限域 有限域是密码学、编码学和数字通信领域重要的数学工具之一，是代数学领域的一个 重要分支。下面，我将给出将用于计算椭圆曲线上双线性对计算的，有限域中的一些相 关的基本性质。关于有限域理论更详细的介绍，可参考【8 】 9 】。 有限域是指由有限个元素构成的域，有限域也叫加罗瓦( g a l o i s ) 域。 有限域的定义如下： 设f 是一个非空的集合，并假定砸上定义了加法+ 和乘法水两种运算；并要 求f 中任意两个元素经加法运算和乘法运算的结果仍是砸中的元素，即f 中任意两个元 素柳b 的和a + b ，硼b 的积a 宰b ，仍是f 中的元素，这个性质通常称为f 对于在其上定义 的加法和乘法运算是封闭的。并且我们要求砸对于所规定的加法和乘法运算满足如下规则 成立： 1 对任意a f ，b f ，有a + b = b + a 成立。 2 对任意a f ，b 砸，c f ，有( o + b ) + c = a + ( b + c ) 成立。 3 f 有一个元素，把它记作0 。对于任意n ，有a + 0 = a 成立。 4 对于任意a f ，砸中有一个元素一a ，有如下关系成立o + ( 一a ) = a 成立。 5 对任意a f ，b f ，有a 半b = b 木a 成立。 6 对任意a f ，b f ，c f ，有( o 木b ) 木c = a ：i c ( b 木c ) 成立。 7 f 中有一个不等于0 的元素，记为e ，对任意a ，具有性质a 术e = a 成立。 第1 l 页，共5 3 页中山大学硕士学位论文 2 2 椭圆曲线 8 对任意a f ，且a 0 ，存在元素a ，满足a 木a _ 1 = e 成立。 9 对任意a f ，b f ，c f ，有a 宰( b + c ) = a ，l cb + a 木c 成立。 下面给出有限域中一些重要的结论。但由于篇幅的限制，不给出具体证明。具体证明 可参考数学百科全书中的有限域理论 9 】 1 有限域的特征必然是素数。 2 有限域f 的元素个数q ，必然是某一素数的p 的幂指数，h p q = p m ，其中1 1 1 为正整 数。f 口可看作有限域f p 上的i n 维向量空间，f 。的加法群是m 个p 阶循环群的直和。 3 有限域f 的非零元素的全体组成的群称作有限域f 的乘法群，记作p 。 4 假设，助为两个有限域。若为f v 的子域，当且仅当，存在正整数m ，使 御= 矿。特别地，如f p m 是昂n 的子域，当且仅当m i n 。 5 对于整数几1 ，f g m 中必然存在n 次不可约多项式9 ( z ) ，并且对于9 ( z ) 在f 。的代 数闭包中的任一个根o l ，有 o l 】= f q ( a ) = f 口n 。 有限扩域的具体构造 选取素域上的某个m 次不可约多项式厂( z ) 的根o l ，将口添加到素域f p 中，即得到扩 域f p m = ( q ) 竺f p 纠( 厂( z ) ) 。有限扩域的构造，难点在于如何选取素域上的不可约多 项式，可参考 8 】 1 0 】。 2 2 椭圆曲线 数学界对椭圆曲线的研究已有2 0 0 多年的历史。然而，真正将椭圆曲线应用到密码学 领域，却是从2 0 世纪8 0 年代开始的。椭圆曲线最初被用作解决整数分解问题和素数检测 问题。在2 0 世纪8 0 9 0 年代，椭圆曲线在证明费马大定理方面，起了重要作用。下面将给 出有限域上椭圆曲线一些基本知识，可参考 1 1 1 2 1 3 1 。 2 2 1 定义在有限域f 上的w e i e r s t r a s s 方程 设f 为有限域，形如秒2 = z 3 + a x + b 的方程，其中，z ，y ，a ，b f ，a ，b 为常 数，被称作定义在有限域f 一卜的w e i e r s t r a s s 方程。该方程描述了一类常见的椭圆曲线。 如果，我们想描述那些属于域f 日包含于e 的椭圆曲线上的点，记作e ( f ) 。根据定 义，这个集合包括点o e ，这个点的定义将在后面给出。 第1 2 页，共5 3 页 中山大学硕士学位论文 第二章预备知识 e ( f ) = o e ) u ( z ，y ) f fi 矿= 矿十a x + b ，a ，b f ) 。 设r l ，您，1 3 为e i e r s 亡r n s s 方程的三个根，c a - - 次方程的判别式：( ( r 1 一r 2 ) ( r 1 一 n ) ( 您一r 3 ) ) 2 = 一4 a 3 + 2 7 8 2 知；若定义在有限域f 上的w e i s t r a s s 方程无重根，则要 求一4 a 3 - 4 - 2 7 8 2 0 。 2 2 2 定义在有限域f 上的g e n e r a l i z e dw e i e r s t r a s s 方程 形如y 2 + a l x y + a 3 y = 。3 + a 2 x 2 + a 4 x + a 6 的方程，其中a 1 a 6 均为常数，z ，y ，a 1 a 6 f ，被称作定义在有限域f 上的g e n e r a l i z e dw e i e r s t r a s s 方程。 如果，c h a r ( f ) 2 ，方程可转化为( 可+ a l x 2 + - 3 2 ) 2 = z 3 + ( a 2d - a ；4 ) x 2 + ( a 4 + a l a 3 2 ) x + ( a + a e ) 。若记，y l = y + a l x 2 + a 3 2 ，必= ( a 2 + a ；4 ，吐= a 4 - t - a l a 3 2 , o ：= o ；+ 0 6 。原方程可以转化为：贸= z 3 + a 2 x 2 + a 4 x - t - 以。 如果，c h a r ( f ) 3 ，可令z 1 = z + 鸥3 ，方程可转化为， = z + a x l + b 。其 中，a = 口：一a 彪2 3 ，b = 酩一a 3 2 7 。 2 2 3 椭圆曲线上有理点加法 设椭圆曲线e ：y 2 = z 3 + a x + b 为定义在有限域f 上，其z p c h a r ( f ) = p ，a ，b f ， 并i e i 4 a 3 + 2 7 8 2 0 。以e ( ) 表示曲线在f 上的所有的点构成的集合。 e ( f ) = ，y ) f fiy 2 = z 3 + a x + b ) t _ j p e ) 这是一个有限集。可以按照切割线法则，定义两点间的加法运算。可以证 明，( e ( f ) ，+ ) 构成一个加法群。具体证明可参考【1 3 】。下面给出由有限域上椭圆曲 线上有理点构成的有限群群律。 设e ：y 2 = 。3 + a x + b 为一条定义在有限域f 上的椭圆曲线。令r = ( z 1 ，y 1 ) ，1 2 = ( z 2 ，沈) 为椭圆曲线e 上的点，且只，b 0 e 。定义r + p 2 = 忍= ( z 3 ，y 3 ) ，如下： 1 如果x l z 2 ，则，z 3 = m 2 一z 1 一x 2 y 3 = m ( x 1 一z 3 ) 一y l ，其中，m = ( y 2 一 y 1 ) ( x 2 一x 1 ) 2 如果z 1 = z 2 ，但，y 1 y 2 ，贝u ，只+ 1 2 = o e 。 3 如果1 1 = p 2 ，且y 1 0 ，则，z 3 = m 2 2 x l ，y 3 = m ( x l z 3 ) 一y 1 ，其中m = ( 3 z ；+ a ) 2 y l 。 第1 3 页，共5 3 页中山大学硕士学位论文 2 3 除子理论 4 如果b = p 2 ，且秒1 = 0 ，则，只+ p 2 = o e 。 5 定义o e 为椭圆曲线外一点，对所有椭圆曲线e 上的点p ，有p + o e = p 成立。 有限域上椭圆曲线e 上的有理点的加法满足如下的性质： 1 ( 交换律) 对于椭圆曲线e 上的所有点p 1 ，易，有只+ 恳= 易+ 只。 2 ( 存在单位元) 对于椭圆曲线e 上的所有点p 有，p + o e = p 。 3 ( 存在逆元) 给定椭圆曲线e 上的点p ，在e 上存在点p ，满足尸+ p 7 = o e 。这个 点通常被记作一p 。 4 ( 结合律) ( r + 恳) + 忍= 只+ ( p 2 + p 3 ) 。 2 2 4 扭映射 设是指一个从e ( f 口) 到e ( f q * ) 的同态映射。：e ( f 。) _ e ( f q , ) 。该映射将e ( f 叮) 中的 点映射到e ( - 铲) 中的某一点，且这两点线性无关【1 4 】 1 5 】。 。 2 2 5 挠点 令椭圆曲线e 定义在有限域f 上，n 为一正整数。椭圆曲线上的挠点的定义：e n 】= p e ( 面) in p = p e ) 。所要强调的是，驯n 】不只是包含坐标在f 中的点，同样包括坐标 在面中的点。 2 3 除子理论 令e 为定义在有限域f 上的椭圆曲线。对于每一点尸e ( f ) ，定义形式符号 p 】。椭圆 曲线e 上的除子d 足以整数为系数的这类形式符号的有限线性组合。其形式如下： d = 旧】，哟z 。 显然，除子是由形式符号 p 所生成的自由阿贝尔群中的一个元素。除了群记 作d i v ( e ) 。 除予的度( d e g r e e ) 和和( s u m ) i 己作： d e g ( 旧】) = ； s u m ( 哟哆】) = b 。 第1 4 页，共5 3 页中山大学硕士学位论文 第二章预备知识 度为。的除子形成d i v ( e ) 的一个重要子群d i v o ( e ) 。 函数s u m ：d i v o ( e ) 一e ( f ) 定义了一个满同态映射。其中，满射的原因如 v - s u m ( p 一p e 】) = p 。 2 4 椭圆曲线上的有理函数 椭圆曲线上的函数是指有理函数f ( x ，可) 至少在e ( f ) 上有定义。显然，函数1 ( y 2 一 $ 3 + a z + b ) ，在椭圆曲线e ：犷= z 3 - b a z + b 上的任何一点都没有定义，因此，该函数 在椭圆曲线e ：y 2 = z 3q - a x + b 上无定义。如果一个函数f ( x ，可) 在椭圆曲线上的某点尸的 函数值为0 ，则称该点为函数，的零点；如果一个函数f ( x ，可) 在椭圆曲线上的某点p 的函数 值为( 3 0 ，则称该点为，的极值点。令p 为椭圆曲线上的某一点，可以证明存在函数“p ，满 足嘶p ) = 0 t f = u 汐，满足r 属于z 且夕( p ) 0 ，则函数邯被称作函数厂( z ，剪) 在点p 的 一致化子。 函数，在点p 的价，记作0 r 彩( ，) = r 。 如果，是e 上的一个不恒等于0 的函数，定义，的除子为：d i v ( f ) = 凹d p ( ，) 叫，其 中p e ( f ) 。 令e 为一条椭圆曲线，为椭圆曲线e 上到函数，且，不恒等于0 ，则 1 f 有有限个零点和极值点。 2 d e g ( d i v ( ，) ) = 0 。 3 如果，既没有零点，也没有极值点，则，为常数。 令e 为椭圆曲线。d 为定义在e 上的除子，且满足d e g ( d ) = 0 。那么在e 上存在一个 函数，满足d i v ( f ) = d ，当且仅当，s u m ( d ) = o e 。 设，为椭圆曲线e 上的一个函数，假设除子d = 【p j 】，满足d 叼( d ) = 0 。，在除 子d 的赋值为：f ( d ) = n 厂( 弓) q 。 2 5 双线性对 从密码学协议设计的角度来说，协议设计者不需要了解椭圆曲线上双线性对的具体构 造，只需了解其抽象定义。因此，此处先给出双线性对的抽象定义，然后再给出两类基 于椭圆曲线有理点群构造的双线性对定义，双线。 生w e i l 对和双线性t a t e 对。 第1 5 页，共5 3 页中山大学硕士学位论文 2 5 双线性对 假设g 1 和g 2 是两个加法群，g t 是乘法群。如果存在映射e ：g 1 g 2 _ g t ，并且对任 意只，马g 1 ，q 1 ，q 2 g 2 ，满足e ( 毋+ 恳，q 1 ) = e ( 毋，q 1 ) e ( 岛，q 1 ) 和e ( 只，q 1 - f q 2 ) = e ( b ，q 1 ) e ( 日，q 2 ) 成立，则e 被称作从g 1 g 2 到g t 的一个双线性对。 在实际的密码应用中，还要求双线性对e 满足如下性质： 非退化性：一定存在p g l 和q g 2 ，使得e ( p ，q ) l a t ，其中1 g t 为g r d o 的单位 元。 可计算性：存在有效的多项式时问算法可以计算出双线性对e 的值。 由双线性对的定义可知如下性质： 假设p g l 和q g 2 ，o g 。n o a 。分别表示g l 和g 2 中的单位元，则有： e ( p ，o a 。) = e ( o a 。，q ) = 1 g ? ； e ( 一p q ) = e ( p q ) ( 一1 ) = e ( p ，一q ) ； e op ，q ) = e ( p ，q ) j = e ( p j q ) 。 2 5 1 基于椭圆曲线有理点群构造的双线性w e i l 对和t a t e 对 1 双线性w e i l 对 令e 为定义在有限域f g 上的椭圆曲线，其中c h 卵( 峨) = p 。设扎为一正整数，且pt 死， 存在f q 的有限次扩域f g e ，使得e m e ( f q t ) 。由e 【n 】e ( e q t ) ，可以推出，f 矿， 其中p n 为n 次单位根群。双线性w 古i l 1 6 】 1 7 】对的定义如下：e ，；：吲叫xe m p n 。 双线性w e i l 对除了满足双线性性，还满足如下性质： 1 e n ( z t ) = l ，对任意t b i n 成立。 2 e n ( 只q ) = e n ( q ，p ) ( 一1 ) ，对任意p ，q e h 】成立。 3 e n ( 矽( p ) ，( q ) ) = ( e 。( p q ) ) ，其中为_ 口上的自同态映射。 4 对于e 上的所有可分自同态映射a ，必有( 口( p ) ，q ( q ) ) = e n ( 尸q ) 如9 ( 。) 。 2 双线性t a t e 对 令e 为定义在有限域上的椭圆曲线，礼为一整数且满足死i ( 口一1 ) 。 令e ( f 。) n 】表示e ( ) 中的阶整除礼的元素的集合，p 。= z f qi 护= l 。 假i 受e ( f 。) 中包含阶为扎的元素，则存在非退化的双线性t a t e 对 1 8 】。 。： 第1 6 页，共5 3 页中山大学硕士学位论文 第二章预备知识 e ( f g ) i n 】e ( f g ) n e ( f g ) _ + ( f 口) ”和：e ( f q ) h 】e ( ) n e ( f 口) _ 。其中，第一 种p a i r i n g 被称作，i a t 争l i d l t e i l l l 羽衄p a i r n g ，第二种p 心i n g 被称作约化的l i d l t e i l l l a u m p a i r n g 。显然，t a t e - l i c h t e n h a u mp a i r n g ：将p e ( f 口) m ，q e ( f q ) n e ( f q ) 映射到一陪 集，既计算( p ，q ) n 的结果可以得到不同的数值，但这些数值均属于同一陪集。而计算经 约化后的t a | t 争l i c h t e i l l l a u mp a i r n g 将得到集合= z b i x n = 1 ) 中_ 个确定的数值。 2 5 2m i l l e r 算法 由双线i 生w e i l 对和双线性t a t e 对的定义可知，计算双线眭w e i l 对和双线。陛t a t e 对的关 键在于，首先，给出有理函数的确定形式；然后，再将有理点代入进行计算。 首先，引用 1 3 】中一例来说明如何计算双线性w e i l 对的。然后，在给出计算双线性对 的m i l l e r 算法。 令e ：y 2 = z 3 + 2 为定义在有限域f 7 上的椭圆曲线。则有，e ( f 7 ) 3 】= z 3o 磊，计 算e 3 ( ( 0 ，3 ) ，( 5 ，1 ) ) 。 令d ( o ，3 ) = ( o ，3 ) 】一【魄】，d ( s ，1 ) = ( 3 ，6 ) 】一 ( 6 ，1 ) 】。其中，除子d ( 5 ，1 ) ，根据( 3 ，6 ) = ( 5 ，1 ) + ( 6 ，1 ) 得来。d i v ( y 一3 ) = 3 d ( o ，3 ) ，d i v ( ( 4 x y + 1 ) ( 5 x y 一1 ) ) = 3 d i ( 5 ，1 ) 。 因此，取 o ，3 ) = y 一3 ，( 5 ，1 ) = ( 4 x y + 1 ) ( 5 z y 一1 ) 。贝0 有， o ，3 ) ( d ( 5 ，1 ) ) = ( o ，3 ) ( 3 ，6 ) ) ( 灰5 ，1 ) ( 6 ，1 ) ) = ( 6 3 ) ( 1 3 ) = 2m o d7 。类似有， 5 ，i ) ( d ( o ，3 ) ) = 4 。因 此，e 3 ( ( o ，3 ) ，( 5 ，1 ) ) = 4 2 = 2 r o o d7 。 1 9 8 6 年，m i l l e r 在其一篇手稿中 2 】，第一次给出了计算双线性w e i l 对的多项式时间算 法。其主要思想如下： 计算双线性w b i l 对，可归约为寻找函数，满足以u ( ，) = n i p + 捌一乳【捌，其中 点p e m ，点r e 。对应点q 1 ，q 2 计算i ( q i ) i ( q 2 ) 。引入除子d j = “p + 捌一 歹 卅一d 捌+ p e 】。由于d e g ( d j ) = 0 ，j t s u m ( d j ) = o e ，除子b 是一个函数的除了。则 存在函数乃，满, 足d i v ( f j ) = d j 。 假设，我们已经求得f j ( q ) 办( q 。) 和 ( q - ) ( q z ) 。我们将给出如何计 算几+ , o ( q 1 ) ( j + 詹) ( q 2 ) 。 令a x + b y + c = 0 为经过j p 和七p 的直线，令z + d = o 为经过点0 + k ) p 的垂线。 由计算知： 第1 7 页，共5 3 页中山大学硕士学位论文 2 6 椭圆曲线上倍点和点加运算 d i v ( a x + b y + c x + d ) = d p 】+ 啤p 】一【o + 七) p 】一【o e 。 因此， d i v c f j + 南) = 功+ 七= b + d k + d i v ( a x + b y + c x + d ) = d i v ( f j f k ( a x + b y + e x + d ) ) 。 上式等价于，存在常数c ，使得，厶+ 七= c 乃 a x + b y + c x + d ) 。 因此， 厶+ k ( q - ) f j + 知( q 2 ) = ( f ；( q 1 ) f k ( 0 1 ) ( a x + b y + c ) ( z + d ) l ( x ，y ) = q 1 ) ( f 歹( q 2 ) ( q 2 ) ( a x + b y + c ) ( x + d ) l ( x ，y ) = q 2 ) 。 假设椭圆曲线e 定。义在有限域f 上，其中有限域f 的阶为g ，椭圆曲线上的有理点 群( e ( f ) ，+ ) 的阶为n ，存在最小的整数后，满足礼l 矿一1 ，那么，该整数后被称作该椭圆曲 线的嵌入次数。 下面给出计算t a t e 对的原始m i l l e r 算法。 a l g o r i t h m1 原始的m i l l e r 算法 输入：素数p ，椭圆曲线e f p 及嵌入次数七素数，= 匕o r i 2 ，p e ( f p ) r l ，q e ( f p k ) h 尸与q 线性无关d q = 【q 1 】一【q 2 输出：双线性t a t e 对e ( p ，q ) 【1 1r 卜p ，卜1 【2 】f o rif r o mz 一1d o w n t o0 【2 11 ，卜，2 寒r 卜2 r 【2 2 】i fr i = 1 【2 3l ，卜，舞备茏努警爱器r 卜r + p 【3 】t u m ，挚 2 6 椭圆曲线上倍点和点加运算 从上述给出的原始m i l l e r 算法可以看出，完成椭圆曲线上的双线性t a t e 对的计算，主 要的算法复杂度集中在循环部分，该循环称作m i l l e r 循环。因此，提高m i l l e r 循环的计算 效率，将提高整体的计算效率。 第1 8 页，共5 3 页中山大学硕士学位论文 第二章预备知识 直观上可以看出，m i l l e r 循环中使用了有限域上椭圆曲线上的倍点和点加运算。因 此，提高有限域上椭圆曲线上的倍点可点加运算将能够提高m i l l e r 算法的整体上的计算效 率。这一部分给出了有限域上椭圆曲线上的有理点在仿射坐标和雅克比坐标下的倍点运 算和点加运算的公式，以及在有限域f p 上的运算量的表示，为下一章给出两类非超奇异 椭圆曲线上的t a t e 对的计算效率的估计值作基础。 2 6 1 仿射坐标下的倍点和点加运算 首先，记有限域f p 上，其中p 为素数，一次乘法运算的运算量为1 m ，一次平方运算的 运算量为1 s ，一次求逆运算的运算量为l i 。由于，在实际应用中要求素撕为5 1 2 1 ：匕特以上 的大素数。因此，有限域f p 上的加法和减法运算同有限域f p 上的乘法和除法运算相比， 其运算量可以忽略不计。 令p = ( x l ，y 1 ) ，q = ( z 2 ，y 2 ) ，r = ( z 3 ，y 3 ) = p + q 。如果p q ，在仿射坐标下，善 于椭网曲线上的点加运算我们有如下公式： 入= 荨等1 m + 1 i 其中，1 m 的运算量来自( 沈一y 1 ) 盘。一1 z 。1 i 的运算量来自石。 z 3 = a 2 一z 1 一z 21 s 其中，1 s 的运算量来自入2 。 蜘= ( x l z 3 ) a y l 1 m 其中，1 m 的运算量来自( z l z 3 ) a 。 因此，在仿射坐标下，完成点加运算总共需要2 m + 1 s + 1 1 次操作。 同理，当p = q ，关于椭圆曲线上倍点运算，我们有如下公式： 入= 蟹2 y 塑l 1 m + i s + i i 其中，1 m 计算量来自( 3 z + o ) 丽1 ：1 s 的计算量来t l x , 1 i 的计算量来自丽1 。 z 3 = a 2 2 x 1 1 s 其中，1 s 的计算量来自a 2 。 蜘= ( x l z 3 ) a y l 1 m 其中，1 m 的计算量来自( z 1 一z 3 ) 入。 第1 9 页，共5 3 页中山大学硕士学位论文 2 6 椭圆曲线上倍点和点加运算 因此，在仿射坐标下，完成倍点运算需要2 m + 2 s + 1 1 次操作。 2 6 2 雅克比坐标下的倍点和点加运算 首先，在雅克比坐标下，令z = 荟，y = 蒡，则相应的w 色i e r s t r a s s 方程是：y 2 = x 3 + 8 xz 4 + b z 6o 令p = ( x l ，m ，z 1 ) ，q = ( x 2 ，蚝，邑) ，r = ( x 3 ，k ，磊) 。如果p q ，在雅克比坐标 下，关于椭圆曲线上的倍点和点加运算，我们有如下算法【1 9 】 a 1 = x l z 2 2 ，1 m + 1 s 其中，1 s 的计算量来自磊2 ；1 m 的计算量来自x 1 历2 。 入2 = 历2 ，1 m + 1 s 其中，l s 的计算量来自z 1 2 ；1 m 的计算量米自恐历2 。 入3 = 入l a 2 ， k = m 易3 ，2 m 其中，1 m 的计算量来自易易2 ；另外l m 的计算量来自m 易