（计算数学专业论文）双线性对在密钥管理中的应用.pdf

西北大学硕士学位论文 双线性对在密钥管理中的应用 摘要 密钥管理是密码学的重要核心，公钥密码就是为了解决密钥管理而提出的 所有的密码技术都依赖于密钥，而密钥管理本身是一个很复杂的课题，而且是保 证安全性的关键点在密钥管理整个过程中，密钥交换具有极其特殊的意义本 文首先研究了现有的三方密钥交换方案，指出了密钥交换方案安全性与会话密钥 表达式之间的关系，证明了仅通过引入长期密钥不能构造出一个安全的三方密钥 交换方案，并提出了一个基于数字认证的三方密钥交换方案然后研究了基于身 份的密钥交换方案，将现有的基于身份的密钥交换方案分解成几个基础密钥交换 方案，指出基础密钥交换方案的安全性能，并将基础密钥交换方案适当组合，构造 出一个安全高效的密钥交换方案由于基于身份的密码系统都必须无条件相信系 统中心，本文提出了一个自证明身份的密钥交换方案，该方案无需可信中心最 后，研究了双线性对分级密钥管理中的一些应用，针对现有的分级密钥管理方案 在组密钥生成和动态密钥管理阶段需要安全信道的限制，提出了两个不需要安全 信道的分级密钥管理方案，并给出了动态密钥管理算法 关键词：椭圆曲线，双线性对，密钥管理，分级控制，密钥交换 i i s o m ea p p l i c a t i o n so fb i l i n e a rp a i r i n gi nk e ym a n a g e m e n t a b s tr a c t k e ym a n a g e m e n ti sc e n t r a lt oc r y p t o s y s t e m s t h ep u b l i c k e yc 盯p t o s y s t e mi s j u s ti n t m d u c e dt os o l v et h ep r o b l e m si nk e ym a n a g e m e n t b e c a u s ea ue n c u p t i o n t e c h n o l o 斟r e l i e so ns e c r e tk e y s ，k e ym a n a g e m e n t ，w h i c hi sac o m p l e xi s s u ei t s e l f ， i st h ek e yp o i n tt oe n s u r et h es e c u r i t y i nt h ew h o l ep r o e e s so fk e ym a n a g e m e n t ， k e ya g r e e m e n th a sv e r ) rs p e c i a ls i g n i f i c a n e e i nt h i sp a p e r ，t h ee ) ( i s t i n gt r i p 盯t i t e k e ya g r e e m e n tp r o t o c o l sa r es t u d i e d ，t h er e l a t i o n s h i pb e t w ，e e nt h es e c u r i t yo ft h e p r o t o e 0 1a n dt h ee x p r e s s i o no ft h es e s s i o nk e yi sr e s e a r c h e d ，t h a tn os e c u r et r i p 钳t i t ek e ya g r e e m e n tp r o t o c o lc a nb ec o n s t r u c t e do n l yb ya d d i n gl o n g - t e r mk e y s i sp r ( e d ，a n dat r i p a t t i t ek e ya g r e e m e n tp r o t o c o lb a s e do nd i g i t a lc e r t i 丘c a t i o ni s p r o p o s e d t h e nt h ee x i s t i n gi d e n t i t y b a s e dk e ya g r e e m e n tp r o t o c 0 1 sa r es t u d i e d ， t h ep r o t o c o l sa r es e p a r a t e di n t os o m eb a s i cp r o t o c 0 1 s ，t h es e c u r i t yo fe a c hb a s i c p r o t o c o li sp o i n t e do u t ，as e c u r ea n de m c i e n tk e ya g r e e m e n tp r o t o c o li sp r o p o s e d b yc o m b i n i n gt 、ob a s i cp r o t o c o l s b e c a u s ea l li d e n t i t y - b a s e dk e ya g r e e m e n tp r 伊 t o c 0 1 sn e e dt ot r u s tt h ec e n t e ra u t h o r i t y ，as e l f - c e r t i 最e dk e ya g r e e m e n tp r o t o c o l ， w h i c hn e e dn o tt r u s tc e n t e ra u t h o r i t y ，i sp r o p o s e d a t1 a s t ，8 0 m ea p p l i c a t i o i l s o fb i l i n e a rp a i r i n gi nh i e r a r c h i c a lk e ym a n a g e m e n ta r er e s e a r c h e d b e c a u s ea u e 虹t i n gh i e r a r c h i c a lk e ym a n a g e m e n tp r o t o c 0 1 sn e e da s e c u r ec h a n n e l i nk e yg e n e r a t i o na n dd y n a m i ck e ym a n a g e m e n tp r o c e s s ，t w oh i e r a r c h i c a lk e ym a n a g e m e n t p r o t o c 0 1 s ，w h i c hd on o tr e ( 1 u i r es e c u r ec h a n n e l s ，a r ep r o p o s e d t h ed y n a m i ck e y m a n a g e m e n t 甜g o r i t h m so ft h ek e ym a n a g e m e n tp r o t o c o l sa r ea l s or e 8 e a r c h 叫 k e y 、o r d s ：e l l i p t i cc u r v e s ，b i l i n e a rp a i r i n g ，l 。e ym a n a 琴i i n e n t ，h i e r a r c h i c a la c c e 鼹 c o n t r o l ，k e ya g r e e m e n tp r o t o c o l i i i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 ， 学位论文作者签名：煎鱼指导教师签名：聋兰! 鎏 。口易年月f 日 y 口8 年乡月厂日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：饿伟 枷 8 年月5 日 第一章引言 第一章引言 1 1密钥管理的研究背景和意义 随着计机联网的逐步实现以及全球信息化水平的不断提高，全球经济发展正 在进入信息经济时代，网络与信息安全的重要性日趋增强计算机信息的保密问 题显得越来越重要，无论是个人信息通信还是电子商务发展，都迫切需要保证网 上信息传输的安全信息安全技术是一门综合学科，它涉及信息论、计算机科学 和密码学等多方面知识，信息安全的任务就是要采取技术手段及有效管理让信息 资产免遭威胁，或者将威胁带来的后果降到最低程度，以此维护组织的正常运作 凡是涉及到保密性、完整性、可用性、可追溯性、真实性和可靠性保护等方面 的技术和理论，都是信息安全所要研究的范畴，也是信息安全所要实现的目标 信息加密是保护信息的安全性的最核心、最基本的技术方法对数据的加密 过程就是利用加密密钥和加密算法将明文转换成其他用户不可理解的密文形式， 而解密是其反过程，利用解密密钥和解密算法将密文恢复成明文用户之间传输 的是密文，而只有拥有解密密钥的用户才能够解密密文以获得明文通常，将密 码系统分为两大类型：一类是对称密码系统，另，类是公钥密码系统 通常认为，在1 9 7 6 年以前的密码系统都是对称密码系统( 也叫单钥密码系 统) ，对称密码系统是一种比较传统的加密方式，其加密运算、解密运算使用的是 同样的密钥，信息的发送者和信息的接收者在进行信息的传输与处理时，必须共 同持有该密码( 称为对称密码) 因此，通信双方都必须获得这把钥匙，并保持钥匙 的秘密对称密码系统的安全性依赖于以下两个因素：第一，加密算法必须是足 够强的，仅仅基于密文本身去解密信息在实践上是不可能的；第二，加密方法的 安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确保算 法的秘密性( 事实上，现实中使用的很多单钥密码系统的算法都是公开的) ，但是 我们一定要保证密钥的秘密性从对称密码的这些特点我们容易看出它的主要问 题有两点：第一，密钥量问题在单钥密码系统中，每一对通信者就需要一对密钥， 当用户增加时，必然会带来密钥量的成倍增长，因此在网络通信中，大量密钥的 产生、存放和分配将是一个难以解决的问题第二，密钥分发问题对称密码系统 中，加密的安全性完全依赖于对密钥的保护，但是由于通信双方使用的是相同的 密钥，人们又不得不相互交流密钥，所以为了保证安全，人们必须使用一些另外 的安全信道来分发密钥，例如用专门的信使来传送密钥，这种做法的代价是相当 大的，甚至可以说是非常不现实的，尤其在计算机网络环境下，人们使用网络传 送加密的文件，却需要另外的安全信道来分发密钥 针对对称密码系统中密钥的分发和管理非常复杂这一难题，d i m e 和h e l l m a n 在密码学的新方向一文中提出了“公钥密码”的概念【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 设计出了第 一个实用的公钥密码方案一一r s a 【2 | 二十多年以来，r s a 仍然是应用最广泛的 密码体制此后，人们基于不同的计算问题，提出了大量的公钥密码算法其巾具 有代表意义的有基于整数分解问题的r a b i n 算法【3 】 基于有限域上离散相关难题 的e l g a m a l 算法 4 】和目前被视为可以代替r s a 算法的椭圆曲线算法( e c c ) 【5 ，6 1 近几年米，基于配对的密码学一直活跃在密码学研究的领域中【7 】早期，双线 性配对，如代数曲线上的w b i l 对和t a t e 对，在密码学中被认为是“不好 的，常被 用来进行m o v 攻击和f r 攻击，然而近年来，研究人员发现可以利用双线性配对 来构造许多性能良好的密码学方案 密钥管理是密码的重要核心，公钥密码就是为了解决密钥管理而提出的现 阶段，密码技术是进行保密通信的主要手段，除了加密技术和解密技术之外，密钥 管理在保密通信中也具有重要的地位主要是因为：所有的密码技术都依赖于密 钥，而密钥管理本身是一个很复杂的课题，而且是保证安全性的关键点密钥管 理是在一种安全策略指导下进行密钥的产生、存储、分配、删除、归档及应用 等活动的总称涉及密钥自产生到最终销毁的整个过程中的有关问题，包括系统 的初始化，密钥的产生、存储、备份恢复、装入、分配、保护、更新、泄漏、 撤销和销毁等内容 1 2密钥交换与分级密钥管理的发展现状及存在的问题 密钥交换在密钥管理中具有重要的意义但现有的密钥交换方案还存在一些 公开问题： 一、j o u x 在2 0 0 0 年提出三方一轮密钥交换方案【8 】，由于该方案无法验证参与 者的身份，研究人员提出了许多改进方案，其中之一是通过加入长期密钥来代替 身份验证然而，已提出的通过加入长期密钥来代替身份验证的密钥交换方案都 被证明是不安全的仅通过加入长期密钥能否构造出一个安全的密钥交换方案是 一个值得研究的方向 二、s m a r t 提出了一个基于身份的密钥交换方案【9 】，但该方案不满足前向安 2 第一章引言 全性s h i m 【1o 】、c h e n - k u d l a 【1 1 】等分别提出了一系列的密钥交换方案，但这些方 案都被证明存在安全隐患c h o i e 提出了一个安全的密钥交换方案【1 2 】，但该方案 需要两次耗时的配对运算，且在实际应用中不满足密钥控制安全性如何构造一 个安全高效的基于身份的密钥交换方案是研究的一个热点 三、在基于身份的密钥交换方案中，会话成员必须无条件相信系统中心，由 于系统中心存在泄漏用户密钥的可能，基于身份的密钥系统只能用在联系紧密的 小用户群中，只能提供有限的安全保障如何构造一个不需可信中心的基于身份 的密钥交换方案是一个值得研究的问题 四、当密码学中一个新的思想或者方法提出以后，研究人员会根据该思想或 方法提出一个密码方案但这些方案中有些在后来被证明是不安全的，有些不能 满足发展中的安全需求，研究人员会仿照原始的方法或思想提出一些改进方案 但后来这些方案的产生和安全性证明大多是采用的构造法，需要大量的精力和技 巧特别的，当已提出的方案不满足安全性需求时，没有人知道在该思想或方法 下，是否存在一个安全的方案冈此，如何构造出一定条件下全部的密码方案是 一个值得研究的问题当全部的密码方案提出之后，要筛选出好的密码方案必须 进行安全性分析，找出安全性与密码方案特征之间的关系也是一个值得研究的问 题 在实际应用中，系统成员往往是按等级组织的分级系统已广泛应用于分布 式数据库的管理、分布式操作系统和网络通信等各个方面，具有广阔的发展前 景上级用户为了解密下级用户存储的数据，他必须先获得该下级用户的密钥， 最容易的办法是上级用户将他的所有下级用户的密钥全部存储起来随着分级系 统不断扩大，上级用户的密钥存储开销也越来越大，给密钥管理带来了困难同 时，大量的密钥也增加了密钥泄漏的风险 为了解决分级密钥管理问题，a k l 和t a y l o r ( 1 9 8 3 ) 第一次提出了一个分级 密钥管理方剩1 3 1 但是，当系统等级类增长时，公共信息也会显著的增长 m a c k i n n o n ( 1 9 8 5 ) 【14 】、l i n ( 1 9 9 0 ) 【1 5 】分别提出了自己的分级密钥管理方案，但这 些方案都有一个共同的缺点：当增加一个中间等级类或删除一个中间等级类 时，整个系统的密钥都必须重新生成最近，蒙杨( 2 0 0 1 ) 【1 6 】、j e n g ( 2 0 0 6 ) 【1 7 】、卢建 朱( 2 0 0 6 ) f 1 8 j 、c h u n g ( 2 0 0 8 ) 【1 9 j 、等分别提出了自己的分级密钥管理方案，这些方 案可以很方便的进行动态密钥管理，但在密钥生成和更改、增加和删除等级类时 都必须有一个安全的信道来传递密钥参数，限制了其应用范围如何构造出一个 不需要安全信道的分级密钥管理方案是一个值得研究的方向 1 3本文研究内容及研究创新 1 3 1 本文研究内容 本文针对密钥交换方案和分级密钥管理方案上进行深入研究，具体作了如下 工作： 3 西北大学硕士学位论文 一、深入研究了基于双线性对的三方密钥交换方案分析现有的三方密钥交 换方案，指出了现有的三方密钥交换方案在方案构造及安全性证明时的不足之 处，提出了一个基于认证的密钥交换方案 二、进一步研究了基于身份的密钥交换方案基于身份的公钥密码在密钥生 成和密钥管理上有很大的优势，本文分析了现有的基于身份的密钥交换方案，分 析了会话密钥的表达式与安全性之间的关系，并提出了一个基于身份的密钥交换 方案 三、分析现有的基于身份的密钥交换方案的基础上，提出了一个自证明身份 的密钥交换方案自证明身份的密码系统克服了基于身份的密钥系统必须无条件 相信系统中心的缺陷，最近许多自证明身份的密码系统被提出，但自证明身份的 密钥交换方案很少有人研究，我们提出了一个基于双线性对的自证明身份的密钥 交换方案，并分析了其安全性 四、提出了一个基于双线性对的分级密钥管理方案指出了密钥交换与密钥 管理之间的关系，分析了现有的分级密钥管理方案，利用双线性对提出了一个不 需要安全信道的密钥交换方案，并对其进行了安全性分析 五、提出了一个基于身份的分级密钥管理方案，该方案同样不需要安全信 道，并且可以更方便的进行动态密钥管理 1 3 2 研究创新 本文的创新点在于以下几个方面： 一、本文提出了基于双线性对的三方密钥交换方案的特征集的概念，指出了 三方密钥管理方案的安全性能与特征集之间的关系利用特征集构造出加入长 期密钥的全部的密钥交换方案，并证明了这些方案都不满足全部的安全性需求 s h i m 说构造一个满足全部安全性需求的三方密钥交换方案仍然是是一个未解决 的问题【2 0 1 ，本文证明了仅通过引入长期密钥无法构造出足够安全的密钥交换方 案进一步，本文提出了一个基于数字认证的三方密钥交换方案以往一次只能够 构造个别的方案，本文给出一定条件下全部的密钥交换方案，并简化了安全性分 析，所做工作具有理论创新性和方法创新性 二、本文将现有的基于身份的密钥交换方案分解成基础密钥交换方案，给出 了每个基础密钥交换方案的安全性由于所有的基础方案都不能满足全部的安全 性能需求，本文将基础的密钥交换方案进行组合，得出了满足全部安全性能需求 的密钥交换方案所采用的研究方法具有创新性 三、本文提出了一个自证明身份的密钥交换方案自证明身份的密码系统实 际上是将把基于p k i 的公钥密码和基于身份的公钥密码结合起来提出了公钥密 码系统与p k i 相比，该系统不需要证书来实现公钥的认证；与现有的基于身份的 公钥加密算法相比，该方案克服密钥托管的局限本文基于双线性对提出了一个 自证明身份的密钥交换方案，所做的工作具有理论和实践价值 四、本文提出了一个不需要安全信道的分级密钥管理方案该分级密钥管理 方案在密钥生成和动态密钥管理时不需要安全信道，可以用在不安全的网络环境 4 第一章引言 中，具有理论和实践价值 五、本文提出了一个不需要安全信道的基于身份的分级密钥管理方案该方 案将基于身份的密码体系应用于分级密钥管理中，所提出的方案同样不需要安全 信道，且公共信息少、效率高，具有理论和实践价值 1 4 论文章节安排 本论文对双线性对在密钥管理中的应用进行了深入地研究，论文内容安排如 下： 第一章为绪论，介绍了密钥管理的研究背景和意义，分析了密钥管理基现状 及存在的问题，指出了本论文的主要研究内容和创新点，概括了论文的整体安排 第二章首先介绍了椭圆曲线的理论和椭圆曲线的离散对数问题，然后介绍了 椭圆曲线上的双线性对以及一些必备的基础知识和基本工具 第三章研究了双线性对在密钥交换中的应用首先提出了密钥交换的研究背 景和安全性需求，然后研究了三方密钥交换方案和基于身份的密钥交换方案，最 后提出了一个自证明身份的密钥交换方案 第四章研究了双线性对在分级密钥管理中的应用，提出了一个基于双线性对 的分级密钥管理方案和一个基于身份的分级密钥管理方案，并给出了动态密钥管 理算法 第五章对全文进行总结，并指出需要进一步研究内容 5 西北大学硕士学位论文 第二章椭圆曲线密码系统的基本理论 2 1椭圆曲线 椭圆曲线是一门古老的研究方向，很早以前就有相当多的数学家对其复 杂的性质进行研究最早研究的动机非常单纯，仅仅是因为椭圆曲线本身深奥 而有趣的性质吸引了数学家的眼光，而没有任何的实际应用随着数学理论 的深入和发展，椭圆曲线逐渐得到了人们越来越多地注意，在实际应用中开始 发挥重要的作用目前，椭圆曲线在编码理剥2 1 】、伪随机数生成【2 2 】、数论算 法【2 3 i2 4 】中都有非常大的帮助最近的数学进展，最引注意的结果就是费玛大定 理的证明这个定理于1 6 3 7 年由法国业余数学家费玛( p i e r r e d ef e r m a t ) 阅读古 希腊名著算术时提出的，经过3 5 8 年众多数学家的潜心研究，终于由英国数 学家怀尔斯于1 9 9 7 年6 月2 7 曰证明成功而怀尔斯证明的关键就是椭圆曲线椭 圆曲线密码，即基于椭圆曲线离散对数问题的各种公钥密码体制，最早于1 9 8 5 年 由k o b l i t z f 2 5 】和m i l l e r f 2 6 】分别独立地提出，它是利用有限域上的椭圆曲线有限群代 替基于离散对数问题密码体制中的有限循环群所得到的一类密码体制在椭圆 曲线密码提出的当初，人们只是把它当作一种理论上的选择，并未引起太多的注 意一是在当时还没有一种实际有效的计算椭圆曲线有理点个数的算法；二是 由于椭圆曲线中的加法运算过于复杂，使得实现椭圆曲线密码的速度较慢但是 到1 9 9 5 年时，人们己经能够比较容易地计算出满足密码要求的任意椭圆曲线有理 点的个数了椭圆曲线上有限群阶的计算，进而椭圆曲线的选取问题也不再是椭 圆曲线密码实用化的主要障碍另方面，自从1 9 7 8 年r s a 体制提出之后，人们对 大数分解问题的研究产生了空前的兴趣对于有限域上的离散对数问题，很多学 者也做了大量的研究借助于计算机技术的不断提高和人们的不懈努力，人们对 这两类问题的求解能力较过去有了很大的改观这迫使r s a 体制中使用的模数 和基于有限域上的离散对数问题的公钥密码体制中有限域的大小越来越大，以至 于目前不得不使用1 0 2 4 比特或2 0 4 8 比特大小的密钥相反的，一直到现在，人们 求解椭圆曲线离散对数问题的能力的提高非常有限，对椭圆曲线密码体制来说， 1 6 0 比特长的密钥所具有的安全性与r s a 体制中的1 0 2 4 比特长的密钥所具有的安 全性相当，2 1 0 比特长的密钥所具有的安全性与r s a 体制中的2 0 4 8 比特长的密钥 所具有的安全性相当椭圆曲线密码体制的优势逐渐凸现了出来 2 1 1椭圆曲线的定义 设k 是一个域域k 上椭圆曲线的w | e i e r s t r a s s 方程是 可2 + 口1 2 秒+ 知= z 3 + 0 2 2 2 + n 4 z + 其中o l ，口2 ，n 3 ，q 4 ，奶k 6 第二章椭圆曲线密码系统的基本理论 当域k 的特征不为2 时，上述方程可变形为 ( 掣+ 丢。- z + 扣2 = z 3 + ( 扣+ 蚴z 2 + ( 三郴3 + ) z + 三n ；+ n 6 或 ( 2 蓦，+ 口1 z + n 3 ) 2 = 4 2 3 + 6 2 2 2 + 2 6 4 z + 6 6 其中 i6 2 = n ；+ 4 口2 6 4 = 0 1 口3 + 2 啦 【6 6 = n ；+ 4 0 6 一 当域k 的特征不为2 ，3 时，方程可继续变形，有 ( 2 秒+ n z + n 3 ) 2 = 4 扛+ 去6 2 ) 3 + ( 一击磋+ 2 6 4 ) + 壶b 2 ) + ( 去碹一丢6 2 6 4 + 6 6 ) ， 或 ， jc 4 = 碹一2 4 6 4 lc 6 = 二碹+ 3 6 6 2 6 4 2 1 6 6 6 并作变换 ， jx = 3 6 ( z + 击6 2 ) iy = 1 0 8 ( 2 可+ n l z + n 3 ) 、，iu ， 我们得到 y 2 = x 3 2 7 c 4 x 一5 4 c 6 其判别式为 1 7 2 8 = 鼋一磊 对于任意域k ，w e i e r s t r a 8 s 方程的判别式是 1 7 2 8 = 一磋6 3 8 磋一2 7 酲+ 9 6 2 6 4 6 6 其中 如= o ；口6 一口1 幻口4 + 4 0 2 0 6 + n 2 霹一 当0 ，域k 上的点集 e ：= ( z ，可) l y 2 + 口1 2 暑，十n 3 = z 3 + 口2 2 2 + 0 4 z + 0 6 ) u o ) 其中n 1 ，n 2 ，n 3 ，啦，0 5 k ， 0 ) 为无穷远点，叫做域k 上的椭圆曲线这时， 歹= 西叫做椭圆曲线e 的歹一不变量，记作歹( e ) 设e 是由以上w e i e r s t r a s s 方程定义的域k 上的椭圆曲线，我们定义e 上的加 法运算法则： 1 西北大学硕士学位论文 设p ，q 是e 上的两个点，l 是过p 和q 的直线( 过p 点的切线，如果p = q ) ， 冗是己与曲线e 相交的第三点设三7 是过r 和d 的直线，则poq 就是己7 与e 相交的 第三点 e 上的加法运算具有如下性质： ( 1 ) 如果直线l 交e 于点只q ，r ( 不必是不同的) ，则( p + q ) + 兄= d ( 2 ) 对任意p e ，尸+ d = 尸 ( 3 ) 对任意p ，q e ，p + q = q + p ( 4 ) 设p e ，存在一个点，记作一p ，使得p + ( 一p ) = d ( 5 ) 对任意p ，q ，r e ，有( p + q ) + q = p + ( q + r ) 这就是说，e 对于运算加法规则构成一个交换群既然椭圆曲线上加法运算， 也就能在椭圆曲线上定义数乘法则也就是 对任意p e ，m z ，m p = p + + 尸( m 个尸相加) 0 p = d m p = m ( 一p ) 2 1 2有限域上的椭圆曲线 设k = 日是口= 矿元有限域设e 是定义在玛上的椭圆曲线当p 3 时， 其w b i e r s t r a u s s 方程为 2 = z 3 + 0 4 z + 0 6 易知，局上椭圆曲线e 中的点数移( e ( f g ) ) 2 9 + 1 事实上，对每个z 岛， 至多有两个秒岛，使得p ( z ，可) e ，再加上无穷远点，我们有券( e ( 最) ) 2 j 局i + 1 = 2 9 + 1 设e 是定义在局( g = 矿，止的椭圆曲线，则椭圆曲线e 上的点数移( e ( 局) ) 满 足h a s s e 定理： 孝( e ( 日) ) = 口+ 1 一亡，亡2 饷 其中，亡是n o b e 矗i u s 自同态的迹孝( e ( b ) ) 中包含无穷远点，e ( 日) 表示日一有理 点的集合，也就是坐标在r 中的点的集合根据定义我们可以写成e = e ( 瓦) ，其 中瓦是日的代数闭包 对于椭圆曲线上的点p ，如果满足后p = d ，并且是满足条件的最小值，那么 我们就说p 点是后阶的如果对于尸e ，有n p = d ，那么我们称尸为n 挠点，这 时尸点的阶整除n e 上的仇挠点子群定义为e m ，也就是 e n 】= 尸e l 死p = 0 ) 另外我们定义e ( 岛) m 为e ( 岛) 上的礼挠点子群，即e ( 日) h 】= p e ( 岛) i 佗p = o ) 定理2 1 ：，2 刀如果佗，g 互素，则e f n j 竺磊。磊如果n = 矿，e 是超奇异的 则e 矿】竺 0 ) ，e 是非奇异的则e 囟e 】笺名一 8 第二章椭圆曲线密码系统的基本理论 2 1 3椭圆曲线离散对数问题 尽管最初d i m e 和h e l l m a n 在他们的密钥交换方案中采用离散对数问 题d l p 的时候，精确定义了d l p 是寻找在模素数乘群中生成元的对数问题，但是 这个想法可以被扩展到任意群中 设g 是一个阶为他的有限群，q 是g 中的一个元素我们可以这样描述g 上的离 散对数问题( d l p ) ：给定p g ，寻找这样的整数z ，0 z 佗一1 ，使得扩= p 容易看出，如果这样的z 存在，那么卢就属于由a 构造的g 的子群中 椭圆曲线上的离散对数问题( e c d l p ) 可以描述为：给定有限域日上的椭圆 曲线e ，点p e ( r ) 的阶为n ，对于点q = f p ，0 f 礼一1 ，确定f 的问题 与d l p 相比，e c d l p 的安全性更高，因为d l p 问题的计算复杂度为亚指数时间， 而e c d l p 问题的计算复杂度为全指数时间 目前，所有椭圆曲线密码体制的安全性都是建立在对椭圆曲线上的离 散e c d l p 求解困难性假设基础上的对r 上d l p 的求解，目前有被称为亚指数 型的i n d e x 算法 2 8 】对于一般的离散对数问题在1 9 7 6 年公钥密码体制发明之前就 已经成为了数学中的一个研究课题，但是，到目前为止，对一般离散对数问题的求 解仍然没有很好的办法对一般的e c d l p ，目前最好的求解方法仍是对任何有限 群都有效的p o l l a r d p 方法【2 9 】及其并行化处理相比而言，如果单从安全性角度考 虑，椭圆曲线密码体制目前仍然是最好的公钥密码体制当然，经过十几年的研 究，虽然对一般e c d l p 的求解没有找到好方法，但是对两类特殊的椭圆曲线己经 有比较有效的方法，它们是针对超奇异曲线的m o v 演化算法和针对“畸形”曲 线的s m a r t 方法和s e m a e v 方法 2 2 双线性对 近年来，双线性配对，如代数曲线上的w e i l 配对，在密码学研究领域里开辟了 一些新的应用本节将介绍椭圆曲线上双线性配对的基本理论 2 2 1 w e i l 对 m e n e z e s ，o k 锄o t o 和v 吼s t o n e 给出了定义在有限域上的一类特殊的椭圆曲 线，存在一个有效算法，将曲线上的两点映射到基域中的一个元素 3 0 1 这类特 殊的曲线被称为超奇异曲线假设e ( 日) 是一条曲线( g 是一个素数幂) 对于某个 大素数仡j 券e ( b ) ( 佗，g 互素) ，可以知道群e ( r ) 包含许多阶数为n 的点，这些点p 满 足死尸= 0 此外，群e ( 碍) 是非循环群且包含不相交的阶为礼的点的子群( 基域 是日的个扩域碍，其中f 是某个整数，即一个曲线上的点的坐标( z ，) 是e 上的 元素) 也就是说，在群e ( ) 中存在阶为礼点的p jq 满足p 隹 且q 隹 因为对于所有的整数钆， ，这些点满足p u q 和q u p ，这就是说它们是线 性无关的两个线性无关的阶为n 的点形成一个产生群e ( e ) 上所有阶为n 的 一组基对于这个素数n ，扩域作为一个非零元素的乘群也是一个阶为佗的 9 西北大学硕士学位论文 子群，而且这个子群是唯一的我们知道，e ( 碟) 曲线中的所有n 阶点和曩中 的佗阶子群之间存在一一且保持运算的映射，w b i l 对就是这样的映射m e n e z e s ， o l c a m o t o 和v a n s t o n e 证明了对于超奇异椭圆曲线e ( 日) 在z 6 的小扩域上能够构 造w ，e i l 对映射【3 0 1 、e i l 对把e ( 一) 上的阶为n 的两个点映射到阶数为n 的子群碍中 的一个元素假设尸7q 是e ( ) 中阶为n 的两个点，我们表示w e i l 对为e n ( p ，q ) 在 这个表示中，下标死指定了p q 是礼阶子群中的点这些点可能在同一个子群中( 包 括p = d 或q = d ) ，这时它们是线性相关的，当它们在不同的扎阶子群中时，则线 性无关 定义2 1 ：p j ，肌i 对e n 定义为 e n ：e 叫e h 】肛n 其中表示中礼次单位根构成的乘法子群 假设尸q ，兄e m ，w 苟l 对e 佗满足如下性质： ( 1 ) 单位元：对于所有的p ，有( p ，p ) = 1 ( 2 ) 双线性：e n ( p 十q ，r ) = e n ( p ，冗) e n ( q ，r ) ，e n ( p q + r ) = ( p ，q ) e n ( p ，r ) ( 3 ) 交换性：e n ( p q ) = e 他( q ，p ) 一1 ( 4 ) 非退化型：对于所有线性无关的p ，q ( 它们在不同的n 阶子群中) ， e n ( 只q ) 1 ( 5 ) 可计算性：e n ( p ，q ) 是实际有效可计算的 关于w b i l 对的可计算性，m i l l e r 曾给出一个有效的计算w r e i l 对的方法【3 2 1 ， b 1 a k e d 【3 3 】和l i u 【叫等分别对该算法进行了改进 由e n 的双线性，我们有： e n ( o p q ) = e n ( 只q ) 口= e n ( p n q ) 进而，由非退化性我们知道，只要只q 线性无关且nta ，这个“对映射”的 结果不是b 中的乘法单位，在非退化情况下，映射结果是素数阶礼中的一个非单 位元，因此，该对映射不是无意义的 w b i l 对的这些特性能够实现从椭圆曲线上的离散对数问题e c d l p 到有限 域上的离散对数问题的规约，这种规约被称为m o v 规约在已知阶为n 点的 对( p ，o p ) 的情况下，为了应用m o v 规约到e c d l p ，对某个与尸线性无关的点x ， 我们可以计算w b i l 对= ( p ，x ) 和叩= e n ( o 只x ) ，叩= e n ( n 只x ) = e n ( p ，x ) a 因为p ，x 线性无关，由非退化性可知，e 礼( p ，x ) 1 ，因此在碍中的对( 荨，7 7 ) 提供了 有限域中的离散对数问题我们知道对于后者，有一个亚指数时间的解法因此， m o v 规约是一个强有力的方法：它把普遍认为的指数复杂度问题归结为一个f 不 超过6 的亚指数问题，通常2 = 2 考虑到硬件计算技术的进步导致口的长度可以增 大，一个超奇异曲线的参数也必须根据有限域的变化而变化因此，在m e n e z e s 等 研究人员的密码分析工作后，超奇异椭圆曲线被认为是“弱曲线”而被排除在密 码应用之外 3 0 1 1 0 第二章椭圆曲线密码系统的基本理论 2 2 2修正的w - e i l 对 w e i l 对的单位元性质有时是难以实施的令g 1 是e ( 础) 上的一个佗阶子群，对 于g 1 中的p ，q ( 对于某个数n 满足q = o p ) ，有e n ( 尸，q ) = ( p ，p ) 口= l 口= 1 为 了获得一个非退化的映射结果，必须找到另外一个阶为n 的点x ，且x 与g 1 中的元 素线性无关这在很大程度上限制了w b i l 对在密码应用中的积极作用v e r h e u l 设 计了一个他命名为“变形映射”的方法【3 5 】一个变形映射就是对曲线上点的坐 标进行修正( 这种修正在基域日上进行) 假设( 尸) 表示这种修正对于e ( ) 中 的一个点p ，只要p 的阶大于3 ，那么( p ) 也就是e ( 曩) 中的一个具有相同阶的点 通常的处理方法是在“基域”日中进行修正也就是说，选择一个p 日并修正 它的坐标，以使咖( p ) e ( ) ，这种通常的处理保证了p 和( p ) 是线性无关的这 是因为现在尸的坐标和( p ) 的坐标( z ，可) 在不同的域中，因而点乘u 尸，u ( p ) 不在 同一个交域上在这个变形映射下，w - e i l 对被修正为： 爸( p p ) = e n ( 只( 尸) ) 令g 1 表示e ( ) 的一个n 阶子群( 事实上，为简明起见，总有g l e ( 岛) ) ， 令g 2 表示的一个n 阶子群我们知道修正过的w 宅i l 对实际上是g 1 与g 2 间的一 个同型，修正的w b i l 对定义为： 仑：e 扎】e 【佗】p 竹 其中 色( p ，尸) = e n ( p ( p ) ) 修正的w r e i l 对具有强非退化性：对于所有的p 有爸( p ，p ) = e n ( p ( p ) ) 1 除上述w b i l 对外，还存在另外一种双线性对一一t a t e 对【3 6 3 7 1 t a t e 对具有 和w e i l 对类似的性质而且t a t e 对更加有效在本文中，我们把w r e i l 对和t a t e 对统 称为双线性对 d i m e h e l l m a n ( d h ) 组：( p 1 ，忍，恳，只) ，其中p 1 = p ，尼= o 只忍= 6 p 只= c p 都是g 1 中的元素，o ，6 ，c 露且满足c 三0 6 ( m o df ) 考虑g 1 中的d d h 问题，为了回答一个四元组( p ，n 只6 p c 尸) 是否是一个d h 四 元组，我们计算7 7 = 爸( n p 6 p ) ，毒= 芭( p ，c p ) 由于叩= 芭( p ，p ) ，f = 芭( p ，p ) c 且仑( p ，p ) 1 ，四元组是一个d h 四元组，当且仅当叩= f ，即当且仅当0 6 = c ( m o d 移g 1 ) 就修正的w a i l 对的实际效率来看，可以有效地回答d d h 判定性问题 自从2 0 0 0 年，j o u x 第一次将椭圆曲线上的w b i l 对和t a t e 对用于密码方案的构 造以来【8 】，椭圆曲线上的双线性对有了许多新的意义的密码应用，这些新的应用 基于一个事实和迄今为止我们所讨论的一个困难性假设，归纳如下： d i 伍争h e l l i i l a n 计算性( c d h ) 难题：给定( d h ) 组中的任意三个元素，计算第四 个元素 双线性d i 伍昏h e l l i i l a d l ( b d h ) 难题：给定( 只n 只6 只护) ，口，6 ，c 均未知，计 算芭( p 尸) 出 1 1 西北大学硕士学位论文 对于曲线e ( f q ) 而言，它的困难性可以表示为s 钆6 一e 印( g 。) ，其中z 6 在c d h 问题、d l 问题仍然困难的假设下，由于m o v 演化和求解有限域上离 散对数的亚指数算法的影响，复杂度的表达式是s 越6 一e 印( 口c ) 因此，与通常的曲线 相比现在我们必须增大超奇异曲线的安全参数( 曲线的大小) 这个加强的安全参 数应该满足s u 6 一e 印( 矿) 是一个不可行的量 2 2 3抽象的双线性对 在这节中，我们讨论在密码中常用的( 修正的) 双线性对在( 修正的) w b i l 对 和t a t e 对抽象性质的基础上，我们定义两种密码中常用的双线性对一一非对称对 和对称对 非对称对：假设e ( r ) 是个椭圆曲线，七= 移e ( f g ) 是椭圆曲线的阶佗是个素 数满足n i 惫而且几十口则佗挠群e m 满足结构e m 竺磊。磊，因而该群由两个元素 假设为s ，t 生成，也就是g 1 = ，g 2 = 对于任意元素p g 1 ，q g 2 ， 根据w d l 对的性质，只有p = o 或者q = d 的情况下才有e n ( p ，q ) = 1 而且n 次 单位根构成的乘法群也是阶为礼的循环群，把这个群表示为g 3 我们在w b