（计算数学专业论文）双线性对在椭圆曲线密码体制中的计算和应用.pdf

双线性对在椭圆曲线密码体制中的计算和应用 摘要 本文应用了双线性对与门限签名之间的关系，首先对文献中的w e i l t a t e 配对的计 算方法进行了分析，并在此基础上进行了改进，提出了两种计算w e i l t a t e 对的快速算 法。通过分析表明改进之后算法的效率都有明显提高。这两种改进方法不但具有运算量 低，而且易于实现的功能。接着我们通过实例验证了这两种改进算法。 其次，利用双线性对构造了一个新的无可信中- c , , f l 限签名方案。在该方案中，假设 p k g 是不可信的，因为如果签名方案中的任意用户都是无条件信任p k g 的，由于所有 用户的私钥均是由p k g 计算产生，所以不诚实的p k g 就能伪造任意用户的签名。新的 方案中，不诚实的p k g 试图通过计算成员的私钥来伪造签名是不可行的，密钥生成过 程中只需成员之间协商完成，即由组成成员共同商议生成群公钥以及私人密钥，避免了 成员私钥的泄漏，解决了以往方案中过分依赖可信中心及可信中心权力过于集中的问 题。最后证明了提出的新方案具有健壮性和不可伪造性。 关键词 椭圆曲线密码体制，双线性对，m i l l e r 算法，无可信中心，门限签名 a b s t r a c t i nt h i sp a p e r , b yt h eu s eo ft h er e l a t i o n sb e t w e e nb i l i n e a rp a i r i n ga n dt h r e s h o l ds i g n a t u r e ， f i r s to fa l l , t h r o u g ha n a l y z i n gt h em e t h o do fc o m p u t i n gw e f ta n dt a t ep a i r i n g si nt h el i t e r a t u r e ， t h et h e s i sg i v e st w oi m p r o v e m e n t so i lt h eb a s i so fi t t h ea l g o r i t h m sa r ea n a l y z e d t h e i m p r o v e da l g o r i t h m sa r em u c hb e t t e rt h a nt h eo r i g i n a ja l g o r i t h m t h et w om e t h o d sm a ye a s i l y r e a l i z ew i t hl o wc o m p u t a t i o n i na d d i t i o n , t h et w oa l g o r i t h m sa r ee x a m i n e db ym e a n so f e x a m p l e s s e c o n d , an e wt h r e s h o l ds i g n a t u r es c h e m ew i t h o u tat r u s t e dp a r t yi sp r e s e n t e db yu s eo f b i l i n e a rp a i r i n g s t h i ss c h e m es u p p o s e sp k gi sn o tat r u s t e dd e a l e r i ft h eu s e r si nt h es c h e m e t r u s tp k gu n c o n d i t i o n a l l y , d i s h o n e s tp k gc a nf o r g ea n yu s e r ss i g n a t u r eb e c a u s ea l lu 礴 s e c r e tk e yc a nb ep r o d u c e db yp k gi nn e ws c h e m ei ti s n tf e a s i b l et h a td i s h o n e s tp k gt r yt o f o r g es i g n a t u r eb yc a l c u l a t i n gt h eu s e l s s e c r e tk e y i nt h ep r o c e s so f t h el 【c 骖g e n e r a t i o na l l m e m b e r s d i s c u s s i o na c h i e v e st h ek e y g r o u p sp u b l i ck e ya n dp r i v a t ek e ya r eg e n e r a t e db y t h ec o m l r l o nm e m b e r s i tc a np r e v e n tm e m b e r ss e c r e tk e yf r o ml e a k i n g , a n ds o l v et h e p r o b l e m st h a tt h ep a s ts c h e m ed e p e n d e do nt h et r u s t e dp a r t ye x c e s s i v e l ya n dt h er i g h t so f t r u s t e dp a r t yw e r et o oc o l l e c t i v e a tl a s tt h ep r o p e r t i e so fr o b u s t n e s sa n du n f o r g e a b i l i t ya r e p r o v e di nt h ep r o p o s e ds c h e m e 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 ，b i l i n e a rp a i r i n g ， n 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：墨基指导教师签名： o lo 年易月i 日 圳口年b 月日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外， 本论文不包含其他人己经发表或撰写过的研究成果，也不包含为获得西 北大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 ：t 思。 学位论文作者签名：吾娃 刈陴莎月日 西北大学硕士学位论文 第一章绪论 随着计算机网络的深入普及，2 0 世纪成了一个名副其实的信息时代，每时每刻都发 生着突飞猛进的变化。信息本身就是时间和金钱。大量信息以数据的形式存储在计算机 的系统中，信息之间的传输则是通过一个公共信道。然而这些计算机系统与公共信道是 不设防的，很容易就会受到破坏或攻击，一旦信息被攻击后果将不堪设想。所以如何保 护信息的安全已不再仅仅是军事和国家政府关心的问题，其他的企事业单位也感到迫在 眉睫。密码正是这样一个保护信息安全的办法，它实际可行而且是有效的。可行性是指 在使用密码保护信息时它需要付出的代价人们是可以接受的。有效性是指密码可以做到 使信息不被篡改、非法窃取和破坏，从而保证信息的保密性和完整性。 1 1 椭圆曲线密码的研究背景和意义 1 9 4 8 年，s h a n n o n 公开发表了具有划时代意义的“通信数学理论”【l 】，宣告了信息 论的诞生，它是一门崭新的学科。次年s h a n n o n 再次发表了“保密系统的通讯理论一【2 】 这一奠基性论著，从此之后现代密码学诞生了。密码学的研究内容为信息保密、实体认 证、数据完整性等等。密码技术是信息安全技术的核心，是实现数据完整性、认证、保 密性、不可否认性的关键。如今，人类社会已被计算机和通信的发展推入了一个全新的 信息时代。随着计算机的联网和全球信息化水平地不断提高，全球经济发展俨然是信息 经济的发展。在人们的日常生活中，网络和信息安全的重要性也日益增强。无论是电子 商务发展还是个人信息通信，计算机信息的保密问题显得愈来愈重要，它要求保证网上 所传输信息的安全性。信息安全是一门综合性的学科，覆盖面相当广，它涉及密码学、 信息论和计算机科学等多个方面的知识。近些年来，计算机与网络技术的快速发展拓宽 了信息应用的范围，同时也有效促进了对信息的索取、传输、存储与处理。信息安全的 目的是在维持组织正常运作的前提下，通过有效措施使信息免于遭受攻击，或者简单来 说就是将它的信息安全程度达到最高。而密码技术是一门交叉性的学科，它包含信息论、 编码理论、代数、计算机复杂度理论、计算机科学和网络技术、不定方程、算法设计与 分析理论、通信技术、图论、数论、组合数学和法律等方面的知识。 在密码学的研究中，1 9 8 5 年m i l l a 一3 】和k o b f i t z 【4 1 引入了椭圆曲线密码，之后人们在 此领域做了大量的工作，最终建立了椭圆曲线型的公钥密码体制。椭圆曲线公钥密码体 制是在椭圆曲线上构造密码，它的安全性是依赖于椭圆曲线上离散对数问题的困难性。 椭圆曲线密码系统与其他有限域乘法群上的密码系统相比，它的优势为：到目前为止由 第一章绪论 椭圆曲线上的点构成的群里还未曾有一个在指数时间内求解离散对数问题的算法。所 以，人们在相同安全性的前提下就能通过用阶数较小的椭圆曲线的点构成的群来建立密 码系统。自公钥密码体制问世以来，人们给出了大量公钥密码体制方案。迄今为止，按 照它们所依赖的难解性可分为： ( 1 ) 基于大整数因子分解的公钥密码体制，这是一种应用比较广泛的密码机制， 例如r s a 体制例等，它在1 9 7 8 年被r i v e s t 、s h a m i r 与a d e l m a n 提出。 ( 2 ) 基于有限域上的离散对数问题的公钥密码体制，例如e l g a m a l 类签名方案 6 1 等。基于有限域上离散对数问题的求解与r s a 算法的公钥密码体制对大整数分解问题 的求解在本质上是一致的。但是随着计算机网络技术的发展和计算机处理能力的提高， r s a 的密钥长度逐渐加长，加之r s a 的计算速度本来就缓慢，这就迫使r s a 体制中使 用的模数与基于有限域上离散对数问题的各种公钥密码体制中的有限域越来越大。 ( 3 ) 基于椭圆曲线上离散对数问题难解性的公钥密码体制，例如d i f f i e h e l l m a n 密 钥交换方案等。1 9 8 5 年，椭圆曲线密码体制( e l l i p t i cc u r v ec r y p t o g r a p h y ，e c c ) 的提 出大大改变了这种状况，在密钥效率上实现了重大突破，大有以强大的短密钥优势代替 r s a 和基于有限域上离散对数问题的公钥密码体制之势。 椭圆曲线密码体制是至今为止被实践证明了的安全有效的三类公钥密码体制之一， 由v i c t o rm i l l e r 和h e a lk a b l i t z 提出并在近些年开始得到普遍重视。e c c 的安全性依赖 于椭圆曲线离散对数问题的难解性，也就是说椭圆曲线离散对数问题是被公认要比整数 分解问题( r s a 方法的基础) 以及模p 离散对数问题( r s a 算法的基础) 难解得多。 同其它两类体制相比，e c c 主要有以下两个方面的优点： ( 1 ) 密钥长度小 一般来说，由于e c c 没有亚指数攻击，所以它的密钥长度会大大减小，2 5 6 比特的 e c c 密钥就完全可以达到对称密码体制1 2 8 比特的密钥的安全水平，这就决定了e c c 密码体制会成为目前已知公钥密码体制里每位提供加密强度最高的一种密码体制。所 以，在相同安全级别的条件下，e c c 所需要的密钥长度远小于基于大整数分解和有限域 上离散对数问题的公钥密码体制的密钥长度。 ( 2 ) 算法性能好 由于e c c 密钥长度小很多，所以减少了处理开销，具有计算效率、存储效率和节 约通信宽带等方面的优势，尤其适用于计算存储能力相对有限的系统，如智能卡和手机 等。 2 西北大学硕士学位论文 e c c 的优势和安全性得到了广泛的认可和应用，从1 9 9 8 年开始一些组织投入了相 当大的精力来研究椭圆曲线密码，年底美国的某个研究所发布了关于椭圆曲线密码体制 的a n s i f 9 6 2 ( 【7 】) 和a n s i - f 9 6 3 ( 【8 】) ，同年椭圆曲线密码被i e e e p 1 3 6 3 工作组正 式写入了公钥密码标准”中，当时这个草稿正在讨论进行。两年后，工作组通过p 1 3 6 3 的最后文本。 1 2 椭圆曲线密码的研究历史和现状 对椭圆曲线的研究至今已经长达1 0 0 多年，刚开始对它的研究只是为了追求美学效 果，随后却产生了许多丰富多彩的研究成果，就像c a s s e l s 所说椭圆曲线上大量孤立的 结果是相当漂亮的，而且它的魅力贯穿了几个世纪。然而椭圆曲线密码体制的建立到目 前为止却只有2 0 多年的历史。 椭圆曲线密码体制最初的研究只是运用了椭圆曲线技术实现了原有的密码算法，比 如d i f f e h e l l m a n 算法等，并没有从理论上发明一种全新的公钥密码算法。所以，严格 说它只是已有椭圆曲线密码体制的翻版，并不属于一种新的密码体制。由于椭圆曲线本 身具有很多独特的特性，所以一开始人们就对它进行了单独研究。但是e c c 在实用化 方面存在障碍。椭圆曲线密码在实现时速度缓慢，这是由于椭圆曲线中的加法运算太复 杂造成的。另外人们在选取曲线时面临不能解决的困难。虽然e c c 存在这些缺陷，但 人们并没有停止研究椭圆曲线密码的步伐。 1 9 9 0 年时，一些特殊曲线被m e n e z e s 9 】用到了椭圆曲线密码的研究中，这些曲线具 有很多优点，比如它可以快速实现等。次年，m e n e z e s 、o k a m m o t o 和v a n s t o n e 就发现 了一种实际有效攻击椭圆曲线离散对数问题的方法，即m o v 方法，它可以在多项式时 间内把一类被称作为超奇异的椭圆曲线约化到此椭圆曲线的扩域上，再利用己有算法对 它求解。这种方法的出现对使用特殊椭圆曲线来构造密码体制的发展有所限制。同时， 根据椭圆曲线有限群阶的计算，人们对在任意椭圆曲线上计算有理点个数的研究迈出了 一大步，解决了e c c 实用化的主要障碍。人们在如何快速实现椭圆曲线密码体制方面 做了大量的研究工作，并且取得了很多重要的研究成果。本文作者的主要工作是研究双 线性对在椭圆曲线密码体制中的计算和应用。 3 第一章绪论 1 3 论文的主要贡献和组织结构 1 3 1 论文的主要贡献 本人在前人工作的基础上，对双线性对在椭圆曲线密码体制中的计算和应用进行了 研究，主要贡献归纳如下： ( 1 ) 对m i l l e r 算法进行了分析，并在此基础上进行了改进，给出计算w e i l t a t e 配 对算法的两种改进方法，使这两种方法比原有的方法在效率上均有明显的提高。其中第 一种改进方法使用窗口技术，使这种算法在任何情况下均有效；而第二种改进方法通过 把带符号的二进制表示( n a f 法) 使用到双线性对的计算上来，以改进已有的算法，它在 刀具有相对较高的汉明重量时较为有效。分析表明，这两种改进方法不仅具有运算量低， 而且容易实现的功能，最后验证了两种改进算法。 ( 2 ) 通过对某些基于身份的门限签名方案进行分析，发现以往方案过分依赖可信 中心或可信中心权力过于集中，为了防止p k g 伪造签名，利用双线性对构造了一个新 的无可信中心门限签名方案。在该方案中，假设p k g 是不可信的，不诚实的p k g 试图 通过计算成员的私钥来伪造签名是行不通的，密钥生成过程只需成员之间协商完成，组 成成员共同协商生成群公钥与私人密钥，从而避免了成员私人密钥的泄漏。假设签名方 案中的成员都是无条件信任p k g ，由于所有成员的私钥都是由p k g 计算产生，那么不 诚实的p k g 就能伪造任意用户的签名。最后证明了提出的方案具有健壮性和不可伪造 性。 1 3 2 论文的组织与结构 论文围绕着双线性对在椭圆曲线密码体制中的重要作用，阐述了作者对原有的双线 性对计算算法的分析以及构造的数字签名方案，比较全面地概括了作者三年以来所做的 工作和取得的结果。本文的组织与结构如下： 第一章文章简要说明了椭圆曲线密码的研究背景及意义，研究历史和现状，接着 介绍了论文的主要贡献以及论文的组织与结构。 第二章首先介绍了椭圆曲线的理论与椭圆曲线的离散对数问题，然后介绍了椭圆 曲线上的双线性对以及基于双线性对的密码方案。 4 西北大学硕士学位论文 第三章研究了双线性对在椭圆曲线密码体制中的计算。结合除子类群等基础知识 分析已有的算法，通过使用窗口技术以及带符号的二进制表示法给出了计算w c i l t a t c 配对算法的两种改进方法。 第四章研究了双线性对在椭圆曲线密码体制中的应用。阐述了门限签名的定义， 提出了一个基于双线性对的无可信中心门限签名方案，并给出了这个新方案的合理性和 安全性的分析。 第五章总结与展望。 s 第二章椭圆曲线密码系统的基本理论 第二章椭圆曲线密码系统的基本理论 2 1 椭圆曲线 椭圆曲线是一个古老且内容丰富的数学分支，它涉及了很多深奥的椭圆曲线算法理 论。目前，椭圆曲线在伪随机数生成【1 0 1 、编码理论【l l 】、数论算法【1 2 ，1 3 1 中都有非常大的帮 助。费玛大定理的证明是最近的数学进展最引人注意的结果。这个定理于1 6 3 7 年由法 国业余数学家费玛阅读古希腊的名著算术时提出，经过了3 5 8 年众多数学家的潜心 研究，最终是怀尔斯在1 9 9 7 年证明出来的，其中运用椭圆曲线正是他证明成功的关键。 紧接着，l e n s t r a 说明了如何用椭圆曲线来因数分解整数。从那时候起，椭圆曲线就在许 多涉及密码学的领域里起着日益重要的作用。它的优点之一是：与采用更大密钥尺寸的 传统密码体制相比，它似乎提供了一个安全级。比如，根据b l a k e 等人估计，3 1 3 位的 椭圆曲线体制能够替代某些有4 0 9 6 位密钥的传统体制，在硬件实现的过程中用很短的 数字就能表示一个相当可观的存储。 2 1 1 椭圆曲线的概念 假设k 是一个域，域足上的椭圆曲线的w r c i e r s t r a s s 方程是 y 2 + 口l x y + a 3 = 工3 + 口2 工2 + 口4 x + a 6 其中a i , a 2 ，0 3 ，a 4 ，a 6 k 。 当域k 的特征不为2 时，上述方程变形为 o + j 1 叩+ 三口，) 2 - - - - x 3 + ( 1 + 口2 ) 工2 + ( 1 a i d 3 - _ i - a 4 ) x + i 1 口，2 + 口6 或 ( 2 y + a l x + a 3 ) 2 = 4 x 3 + b 2 x 2 + 2 6 4 工+ 6 6 其中 f 6 2 = 口；+ 4 a 2 6 4 = f 1 1 a 3 + 知2 【b 6 = 口；+ 4 a 6 当域k 的特征不为2 ，3 时，方程可以继续变形，有 ( 2 y + a l x + 口3 ) 2 = 似工+ 去6 2 ) 3 + ( 一击霹+ 2 b , x x + 去6 2 ) + 丽1 噬一丢如钆+ 6 。) ， 6 西北大学硕士学位论文 或 k = 霹一2 啦 k = 叫+ 3 6 b 2 b 4 2 1 6 b 6 并且作变换 j x = 3 仪工+ 击6 2 ， 【y = 1 0 8 ( 2 y + 口l x + a 3 ) 可以得到 y 2 = x 3 2 7 c 4 x 一5 4 c 6 它的判别式为 1 7 2 8 a = c ：一c 6 2 对任意域k ，w e i e r s t r a s s 方程的判别式为 1 7 2 8 a = 鹭6 3 8 坟一2 7 酲+ 9 6 2 6 4 6 6 这里 6 3 = 口? 口6 一口l a 3 a 4 + 4 a 2 口6 + 口2 a ；一口4 2 当0 时，域足上的点集 占：= 工，y ) l y 2 + 口l x y + a 3 - - - - x 3 + 口2 工2 + a 4 x + a 6 u d ) 其中口。，口：，a ，a ，口。k ，p 是无穷远点，称作域k 上的椭圆曲线。此时，j = c ：a 叫 做椭圆曲线三的_ ，一不变量，记为，( 司。 假设e 是定义在域k 上的椭圆曲线。e 上有两点尸 q ，过这两点尸与q 存在一条直 线三，这条直线和曲线e 相交于点尺，那么通过点火和o 就有条直线，记为，则p + q 就是直线和曲线e 相交的第三点。 椭圆曲线e 上的加法运算具有下列性质： ( 1 ) 对任意尸q e ，有p + q = q + p 。 ( 2 ) 对任意户，q ，犬e ，有( 尸+ q ) + r = p + ( q + r ) 。 ( 3 ) 对任意p e ，有户+ o = p 。 ( 4 ) 如果直线三与e 相交于点p ，q ，月( 可以是相同的) ，则( 户+ q ) + 犬= 0 。 ( 5 ) 设p e ，存在一个点，记为一p ，使得p + ( 一p ) = d 。 可以看出，e 上的加法运算构成了个交换群。在椭圆曲线上加法运算法则和数乘 7 第二章椭圆曲线密码系统的基本理论 法则是类似的，所以可定义数乘法则： 对于e 上的任意一点p ，聊z ，那么m p = 户+ + p 。、，。一 耐 0 尸= 0 一m 户= m ( - p ) 2 1 2 有限域上的椭圆曲线 设e 为定义在上的椭圆曲线，k = 是包含q = p ”个元素的有限域。当p 3 时， 它的w e i e r s t r a s s 方程为 y 2 - - - - x 3 + 吼x + a 6 容易知道，上椭圆曲线层中的点数撑( e ( ) ) 2 q + l 。实际上，对每一个工， 至多存在两个夕c ，使得p ( x ，力e ，还要再加上无穷远点，这样就可以得到 群( e ( ) ) - 2 1 f g l + 1 = 2 q + l 。 设e 为定义在上的椭圆曲线，则椭圆曲线e 上的点数撑( e ( ) ) 满足i i a g s e 定理： 群( e ( ) ) = q + l t ，这里f 是弗罗贝尼乌斯( f r o b e n i u s ) 自同态的迹，t 2 g 。其中 群( e ( ) ) 中包含有无穷远点，另外e ( ) 表示一有理点的集合。椭圆曲线是超奇异的 是指满足捍( e ( c ) ) = g + 1 ，相反曲线为非奇异的。 若k p = o ，这里p 是椭圆曲线上的点，而且七是满足这个条件的最小值，则可以说 户点是k 阶的。如果存在n p = o ，其中p e ，那么我们称p 为k 挠点，此时户点的阶 整除以。e 上的以挠点子群可以定义为e k 】，即e b 】= p 酣, 1 e - - o 。另外，接着定义 e ( ) k 为e ( ) 上的靠挠点子群，也就是e ( ) k 】= p e ( f q ) i n p = o 。 定理2 1 n 4 1 如果以，g 互为素数，那么e k 】兰z 。oz 。若有一= p 。，曲线e 是超奇异的 则e b 。】兰 d ) ；曲线e 是非奇异的则有e 【p 。- - _ z p ，。 通常情况下选取的有限域是一个素域或只，其中9 和m 均为素数。 2 1 3 椭圆曲线上的离散对数问题与安全性 椭圆曲线密码是依赖于椭圆曲线离散对数问题的公钥密码体制。 8 西北大学硕士学位论文 离散对数问题( d i s c 淝t el o g a r i t h mp r o b l e m ，d l p ) ：给定一个q 一1 阶的乘法群z 二，这 里q 是一个大素数，p 是q l 中包含的另外一个大素数因子，这个群的生成元为整数g ， 其中1 g q 1 。已知x ，求y = g 。m o d q 容易，但是如果已知y ，g ，q 要求 工= l o g 。y m o d q 是比较困难的，那么把它称为离散对数问题，简单的说，离散对数问题 就是已知g 和9 1 求解x 的数学问题。 椭圆曲线离散对数问题( e u i p f i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ，e c d l p ) ：假设 椭圆曲线e 是定义在有限域上的，p 和q 是ek n n 点，在域中寻找一个正整数工。 使得x p = q 成立。 由于当群g 的阶比较小时，存在有很多种算法来求解g 上的d l p 。所以当群的阶 很大时，它的安全性相对来说就比较高。早些年提出的是依赖于大整数因子分解和有限 域等一般群上的d l p 的公钥密码体制，它与椭圆曲线密码体制相比，在求解上要容易 得多，但运算效率却不高。椭圆曲线密码体制是基于e c d l p 困难性的公钥密码体制。 对于e c d l p ，一方面，如果椭圆曲线e 为非奇异的，那么到目前为止还不存在有 效的求解e c d l p 的方法，换句话说它是比较安全的，这种椭圆曲线正是我们所希望的； 另一方面，如果椭圆曲线e 是超奇异的，那么就要利用m o v 方法把e c d l p 简化为d l p ， 然后求解。 2 2 双线性对 通过检查发现n 挠点所得到的只是一些局部信息，而我们感兴趣的却是“椭圆曲线 上会有多少个点的坐标在有限域中 这样一个全局信息。w e i l 对就能完成从局部到全局 的转化，事实上可以把w e i l 对看成是以挠点的“双线性”形式。双线性映射一经提出就 倍受广泛关注，它是目前基于身份密码技术的研究热点。 假设e ( ) 是一条曲线，其中g 是一个素数幂。另外，群e ( 0 时，表示p 为g 的o r d p ( g ) 阶零点，另一方面，当o r d 尸( g ) 0 时，表示p 为g 的一d 耐尸( g ) 阶极点。 g 仅仅只有有限个零点和极点，对于任意一个g k ( e ) 都会有d e g ( d v ( g ) ) = 0 。 k ( e ) 中的任一函数g 所对应的除子d i v ( g ) 被称为主除子，所有的主除子形成 d i v ( e ) 中的一个子群。d i v ( e ) 对它的商群称作为除子类群( 或者p i c a r d 群) ，并记为 p i c ( e ) 。另外存在两个除子d l ，d 2 ，若有g k ( e ) 使得d 2 = d i + d i v ( g ) ，那么称d 1 和 d 2 线性等价，记为d l d ：，而且这时有d e g d i = d e g d 2 。p i c o 陋) 为d i v o ( e ) 关于主除 子群的商群1 2 5 。 3 i 2 m i l l e r 算法【1 7 】 计算w e i l t a t e 对的一个重要部分是对每一个点s 在d q 的支撑上求 ( s ) 的值。 m i l l e r 算法的主要思想如下：任意取一点r ，d p = ( p + r ) - ( r ) ，对任意整数_ ，定义 口喀= j ( p + 犬) 一j ( r ) 一c 芦，) + ( d ) ， 那么存在有理函数乃使咖( 乃) = d ；。并且特别地，厶= 厶成立。因p eg i n ，有舻= 0 。 对于点s ，t ，线性方程| l i 盯= 0 与h s = 0 分别表示通过s ，t 的直线与s 的垂线。 则有 所以 故有 d i v ( h 七i 附：户) = ( 七l 竹+ ( 七2 p ) + ( 一( 毛+ 七2 ) p ) 一3 ( 0 ) ， d i v ( h ( 屯+ t ：) p ) = ( ( 毛+ 如) p ) + ( - ( 毛+ 七2 ) p ) 一2 ( d ) ， a i v ( a 。+ t ：) = d 似 ) + 珑v ( 五：) + d 如( i j i t p 乒：p ) 一d i v ( h ( 毛+ 七2 ) p ) ， 厶+ 如- a 以：h k 。户南p 嘎毛+ 屯) p 。 这表示的是一个递归方程，其中初始条件为f o = 1 以及z = h m h 量。由于有 咖u ) = ( 尸+ r ) 一( r ) 一( 竹+ ( d ) ，因此z = h 尸詹h 冉鼻成立。 下面的算法1 即为m i l l e r 算法。 算法l f 输入：整数刀= b , 2 。，这里包 o ，1 ) ，6 f = l ，点尸，s e ，并且尸的阶为刀。 扣由 第三牵计算w e i l t a t c 配对的快速算法 输出：f = 无( 回。 ( 1 ) 初始化过程厂= 彳；z = p ； ( 2 ) 蛳l 至蝴小厂2 器；z = 2 z ； 若纠盯w 器；z = z + 尸； ( 3 ) 输出f = ( s ) 。 3 2 改进的算法 通过对已有的算法进行分析，给出了下面两种计算w e i l t a t e 配对的快速算法。 3 2 1 一般情形的快速计算方法 设e ：y 2 + 4 l x y + a 3 y = 工3 + 4 2 工2 + a 4 x + a 6 为一个椭圆曲线。对于e 上存在的线性 函数j i l ( 石，y ) = k ( x a ) + b - y ，其中a , b ，k 为常数，可以定义h 的共轭为 万( x ，y ) = k ( x 一口) + 6 + j ，+ 口l x + a 3 。 对点r e ，有j l l ( 尺) = ( r ) 。它们的乘积j i l ( x ，y ) h ( x ，j ，) 表示为范数r ( ，足( ；) ( i i ) 。 引理3 1 【1 7 1 如果直线 ( 工，y ) = 0 和椭圆曲线相交于点p ( 口，6 ) ，q ( c ，d ) 以及一( 尸+ q ) ， 而且尸+ q = ，p ) ，那么有心( ，t y ) ，足( ：) ( ) = - ( x 一口) 一c ) 0 一位) 。 引理3 2 【1 7 】假设q 可以】，s q ，2 q ，h q ，那么有 ( 1 ) ：丝：皇塑：一 ! 。 ；( s ) | j 1 2 q ( s ) h o 也( 一s ) c 2 ，对任意的整数七，瓦三器= 一瓦兰詈兰与。 ( 3 ) h o , o ( s ) h 2 0 , o ( s ) ：一 h 2 q ( s ) ( s ) h q , o ( s ) ( s ) 。一o h 2 q , q ( - s ) 对于任意的非零常数c k ，有d i v ( f ) = a i v ( c f ) ，由于符号不会影响任何配对的计 算，因此在使用上面的引理时负号可以省略。 m i l l e r 算法用了d o u b l e - a n d - a d d 这种方法，所以函数的显示公式可表示为 1 4 西北大学硕士学位论文 厶晰垂( 咖讲：批_ , p h 枷j p 协j p ) ， 这里f l 1 0 9 ：”j 以及6 j - ，= b 2 h j 一2 l n 2 j 。 若6 山2 0 ，则 如，2 j p 扎户= 山j p ，。2 旷，j p 。不失一般性，如果k = 1 ，那么可以 把乘积从第f 项至第1 项重新排列。 算法2 输入：整数刀= 屯8 ，这里屯 o ，1 ，2 ，3 ，4 , 5 ，6 ，7 ) ，t o ，点尸，s e ，并且p 的阶为以。 i - , o 输出：f = z ( d 。 ( 1 ) 初始化过程厂= z ；z = p ； ( 2 ) 把n 表示成k , s 这种形式，从左起的第一位看起，也就是七，值，根据表1 对于不同 j 蟹0 的t 值输入不同的厂值。 表1t 一厂值 ( 3 ) 对于_ ，自，一l 至。执行，同理根据表2 对不同的屯值输入不同的厂值。 1 5 第三章计算w e i l t a t e 配对的快速算法 表2 t 一厂值 ( 4 ) 输出厂= ( s ) 。 3 2 2 t l 的二进制展开中汉明重量较大时的快速计算方法 将j | 表示为二进制数形式，即k = ( 岛一。向2 k , k o ) 2 ，七l 0 ，1 ) ，0 i 1 - 1 ，其中， 为七表示成二进制数的长度，可以看出这种k 的表示方法是唯一的。如果能减少k 的二 进制表示式中1 的个数，那么也就可以减少点加运算的次数，从而也就减少了点乘中所 需要的运算次数。于是可以用带符号的二进制数来表示j i ，也就是说七= h t 雏：七揣， qe 0 1 ) ，0 f ，一l ，但是这种表示方法不唯一【2 9 】。 这种算法的本质是把七的二进制表示式中连续不少于两个以上i 的情况作如下变换 峭( n 2 ) 1 0 、0 0 0 ，一1 0 n - i 算法3 输入：( 1 1 1 , n 2 ，力3 ，n 4 ) ，这里万l ，靠2 ，万3 ，n 4 ，表示的是整数一二进制展开后从左向右起交 1 6 西北大学硕士学位论文 话您联悬l 利u 列，| 、叙。例：则朱甩21 1 1 0 1 1 0 0 0 0 l ，那么搠八【j ，1 ，2 ，4 ，l j 恳， s e ，并且p 的阶为甩。 输出：f = z ( s ) 。 ( 1 ) 初始化过程厂= 石；z = 户； ( 2 ) 对于j i 自，l l 至l 执行： 厂= 厂2 丽h z s s ) ；z = 2 z ； 厂= 舞；z = z - p ； ( 4 ) 对于- 自2 至最后一个数执行 ( 口) 若，是偶数，则对七自乃至1 执行：厂= 厂2 丽h z z ( s ) ；z = 2 z ： ( 6 ) 否则是奇数 j r = f j h z + w 八( s j ) 歹；z = z + p ； 对于七自吩至l 执行：= 2 h 吃z z , z ( ( 印s ) ；z = 2 z ： 厂= 厕f h z ( s ) ；z = z - p = 3 - 3 效率分析 在这一部分，我们进行了改进算法的效率分析，具体给出了可以节省的运算次数。 在算法的实现过程中，分子和分母的运算实际上是分开的，最后再进行一个除法。效率 的提高是因为项h x , r ( s ) 和h x ( s ) 的消除。这里h x , r ( s ) 与h x , r ( 一s ) 均花费一个域乘。 ( 1 ) 改进的第一种方法( 即算法2 ) 分析例如当k 。= 1 时 卜石镄恶篇揣， 分母要进行2 次平方和4 次乘法，同时分子要进行3 次平方和7 次乘法。然而算法1 是 这样的结果 1 7 第三章计算w e i l t a t e 配对的快速算法 f * - f , 等篇舞群， 它的分母需要进行2 次平方和6 次乘法，分子需要进行3 次平方和9 次乘法。 ( 2 ) 第二种改进方法( 即算法3 ) 它比较适合于当整数n 的二进制展开中汉明重量 较大时的情形。在下面的分析过程中，把五虮m p ， 驴分别简写为以。，h 。，用j l 抽来表 示k 埘p ( 一s ) 。此外，因为每一种算法最后所得的结果中z 的幂次方相同，所以在分析 分母与分子的计算量时可以先不考虑z 。根据算法1 计算6 3 = ( 1 1 1 1 1 1 ) ：得 m s ，盟生塾鱼一h ；p 3 p 盟鳖塾生，j 川礴聪；i i l 品i i l 缸碓p 碓p 磕户j j l 三户h p 其中分母要进行4 次平方和1 4 次乘法，同时分子要进行4 次平方和1 4 次乘法。但是如 果采用算法3 计算，结果为 州恚玺訾警， 它的分母需要进行4 次平方和6 次乘法，分子需要进行5 次平方和6 次乘法。另外，如 果计算7 1 9 = ( 1 0 1 1 0 0 1 1 1 d 2 ，根据算法1 可得 ， ，7 l ， 葶| i l 爱：户 ：器j i l 嚣”i i l 怠户j i l 嚣1 l p 罐p 控pj l 乞 “p 鑫 碚户，眄p 碡。p 1 为p j川 j i l 第1 l l 拶矗；爹j l 怠j l 篇厅刍i l 捻磕p磕p 麓p磕。p 磕8 p ，p 鸭5 9 p 3 5 9 p 玛1 3 户p 瓦了i 瓦_ 其中分母要进行8 次平方和2 6 次乘法，同时分子要进行8 次平方和2 6 次乘法。而要是 采用算法3 可以得到如下结果： 州7 1 9 酋h 2 5 6 h 2 5 6 孝, 1 2 8 酋6 4 蠢h 3 2 蠢1 6 嚣鲁， 它的分母需要进行8 次平方和1 2 次乘法，分子需要进行9 次平方和1 5 次乘法。所以一 般来说，对于一个很大的尢，采用改进的算法可以节省大约1 5 的计算。 下面给出一个例子，用算法1 、算法2 和算法3 分别来计算z ，然后再比较这几 种算法的运算效率( 见表3 ) 。 1 8 西北大学硕士学位论文 表3 算法1 , 2 , 3 的比较 算法 1 9 1 = ( 1 0 1 1 1 1 1 d 2 算法i 算法2 算法3 通过文中的描述，我们可以很容易地计算出利用下面这几种算法求石，所需平方和 乘法的次数，具体的数据如表4 所示。通过比较可以看出改进后算法的效率均有所提高。 袭4 不同算法之间的运算量比较 3 4 结论 本文提出了两钟计算w e i l t a t e 配对的快速算法，分析表明改进后算法的效率都有 明显提高。其中第一种改进方法适用于一般情形；然而第二种在二进制展开时连续两个 或两个以上l 比较多的情形下更为有效，这种方法可以通过减少点加运算的次数来达到 减少点乘中所需运算次数的目的。这些方法将会促进w e i l 和t a r e 配对在密码学中更加 广泛的应用。 1 9 掣一 一砭一塑丛 蚺一“一批一梳一一 一一一一一一一蕊 研一坚辑一磁一盟矽 嵫可一蝣面一蟛爵 9 9 9 石一正一石 = 一 = 一 = 竺竺” 第四章基于取线性对的无可信中心门限签名方案 第四章基于双线性对的无可信中心门限签名方案 自从文献【3 0 提出基于w e i l 对的短签名方案之后，双线性配对逐渐受到关注。双线 性映射和相关计算问题的提出以及椭圆曲线上w e i l 对与t a t e 对的成功应用【3 1 1 ，使得基 于身份的密码学体制可以得到高效的实现和快速的发展。 1 9 9 1 年，c h a u m 和v a n h e y s t 提出群签名的概念，一个群体中的任意一个成员都能 够以匿名的方式来代表整个群体对消息进行签名，然而只用单个群公钥就能实现公开验 证【3 2 3 。同年，( f ，1 ) f - j 限签名的概念被yd e s m e d t 等人提出，特点是必须有相当多的成员 参与密钥获取以及签名生成，设置门限的主要目的是为了解决密钥泄露问题有可能给加 密带来的威胁，签名过程是在共享密钥的基础上以分布式的形式完成的【3 3 】。( f ，1 , ) 门限签 名的思想是将秘密信息分发给以个成员，任何不少于t - - 1 个成员的子集都可以安全地联 合重构秘密以及产生签名，另一方面，任何成员个数少于门限值t 的子集时都将无法产 生签名。 4 1 门限签名的定义 f - j r 签名【姗6 1 是最常用、最普遍的群体签名，它是密码学的重要组成部分。( f 甩) 门限签名是把签名私钥化分成以个片段，分别由以个成员来保管，当需要签名的时候， 由不少于t 个成员用他们所保存的密钥片段签名来得到部分签名，签名执行者再根据这t 个部分签名计算出最终地签名。门限签名可以保证长期有效密钥的安全，并能够解决权 力过于集中的问题。 1 9 8 4 年，s h a m h _ 【3 7 】提出了基于身份的签名、认证、加密等思想，它是用公开的身份 信息( 例如姓名、电子邮件地址等等) 来作为用户的公钥，而用户的私钥则会由一个被称 为私钥生成中- t 5 ( p l 昭) 地可信第三方生成。可是在现实中，如果每个签名过程都必须 要有可信中心参与，对某些情况方案就不会是理想的。例如当雅个人无共同相信的可信 中心时，那么就需要他们共同协作来产生签名密钥。本方案中假设p k g 不可信，因为 如果签名方案中的用户都是无条件信任p k g 的，那么不诚实的p k g 就能伪造任意用户 的签名。为了解决无条件信任p k g 有可能带来的问题以及保护签名人的利益，我们提 出了一个有效的基于双线性对的无可信中心门限签名方案，并证明了其安全性。 西j e 大学硕士学位论文 4 2 门限签名方案及安全性 4 2 1f - 1 限签名方案 一般情况下，一个门限签名方案由下面四个步骤构成： ( 1 ) 系统参数生成。 ( 2 ) f 3 限密钥生成：给定一个用户的身份i d ，p k g 计算他的公钥与相应的私钥。 ( 3 ) f l 限签名生成：对于消息槐，用户可以根据私钥和系统参数产生签名。 ( 4 ) 签名验证：给定消息签名与公钥，验证签名的有效性。 4