（计算机软件与理论专业论文）基于椭圆曲线密码体制的密钥管理方法研究.pdf

原创性声明 j j j j j j i j j j j i j j 舢舢删洲删 y 18 8 7 4 5 。 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已 经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得凼墓直太堂及 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 学位论文作者签名：多盥指导教师签名： 日期：2 里! ! ：i ：! s 白期： 勘鳅 趣月l f 曰 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的全 部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行检索， 也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作者在学期 间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古 大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名： 日 翻、但思 指导教师签名：锄职 内蒙古大学硕士学位论文 基于椭圆曲线密码体制的密钥管理方法研究 摘要 信息经济时代网络与信息安全的重要性日趋增强，因此，保护信息的安全 就成了信息时代的迫切要求。密码学的原则要求密码系统的保密性不依赖加密 体制或算法的保密，而依赖于密钥的保密。密钥管理是密码技术的重要组成部 ， 分，它要求密码系统应具有良好的密钥分配和管理措施。密钥管理不仅影响密 码系统的安全性，而且涉及到应用密码的系统的可靠性、有效性和安全性。密 码学发展至今，密钥管理始终是一个不断出现新问题和挑战的复杂课题。 本文首先总结了分级系统结构上密钥管理方案的发展现状，给出了经典的 分级密钥管理方案的描述，1 并对其进行了安全性分析，给出了该方案的优点和 ， 存在的缺点，并针对j e n g - w a n g ( 2 0 0 6 ) 方案和c h u n g l e e ( 2 0 0 8 ) 方案提出可能存 在的一种在多项式时间内求根攻击状况。本文基于椭圆曲线密码体制和单向散 ， ， ： 列函数提出一种新的密钥管理方法，更好的解决动态访问控制下的密钥管理问 题。本文提出的密钥管理方法中，基于用户等级权限，构造了一个函数，使得 当系统中等级关系结构发生临时变更时，代理职责人能够既保证原有应用系统 的安全性，又能够很好的处理职责所在。， 关键字：密码学，椭圆曲线密码，密钥管理，动态访问控制，哈希函数 一 基于椭圆密码体制的密钥管理方法研究 _ 二二二- 二二_ 二二二二_ 二一一 r e s e a r c h0 fk e ym a n a g e m e n t m e t h o db a s e do n e l l i p t i cc u r v ec r y p t o s y s t e m a b s t r a c t i nt h ei n f o r m a t i o n e c o n o m yo fs o c i e t y , n e t w o r ka n di n f o r m a t i o ns e c u r i t yb e c o m e s i n c r e a s i n g l yi m p o r t a n t ，s oi ti sa nu r g e n tr e q u i r e m e n tt h a ti n f o r m a t i o ns e c u r i t yi sp r o t e c t e df o rt l i e i n f o r m a t i o na g e t h ep r i n c i p l eo fc r y p t o g r a p h y r e q u i r e st h a tt h es e c u r i t yo fc r y p t o g r a p h i cs y s t e m d o e sn o tr e l yo nt h ec o n f i d e n t i a l i t yo fc r y p t o s y s t e mo ra l g o r i t h m ，b u tr e l i e so ns e c r e tk e y s k e y m a n a g e m e n tw h i c hi sa l li m p o r t a n tp a r to fc r y p t o g r a p h yr e q u i r e st h a tt h ec r y p t o g r a p h i cs y s t e m c o n t a i ng o o dm e a s u r e sa b o u tk e yd i s t r i b u t i o na n dk e y m a n a g e m e n t n o to n l yk e ym a n a g e m e n t s y s t e m a f f e c t st h e s e c u r i t y o ft h e c r y p t o g r a p h i cs y s t e m ，b u ta l s o a f f e c t s t h e r e l i a b i l i t y , e f f e c t i v e n e s sa n ds a f e t yo ft h ea p p l i c a t i o ns y s t e m s of a r , k e y m a n a g e m e n tr e m a i n sac o n t i n u o u s e m e r g e n c eo fn e wp r o b l e m sa n dc h a l l e n g e so fc o m p l e xi s s u e s 内蒙古大学硕士学位论文 目录 摘要。i a b s t r a c t 。：i i 目录j i i i 图表目录：v 符号说明v i 第一章引言k ：1 1 1 密钥管理的研究背景及意义1 1 2 分级密钥管理的发展现状及存在的问题2 1 3 本文研究内容3 1 4 论文章节安排4 第二章相关知识点：5 2 1 离散对数问题：j _ 。5 2 2 牛顿插值多项式。j 5 ， 2 3 哈希函数( o w h f ) ：- ：5 。 2 4 椭圆曲线密码系统理论6 2 4 1 椭圆曲线及其相关定义6， 2 4 2 椭圆曲线的运算法则：7 2 4 3 椭圆曲线离散对数问题( e c d l p ) 8 2 4 4 椭圆曲线密码体带i j ( e c c ) ：8 第三章经典分级密钥管理方案：_ 1 1 3 1 分级系统原理1 1 3 2 经典分级密钥管理方案以及分析1 2 3 2 1 基于离散对数问题的分级密钥管理方案：1 3 3 2 2 基于牛顿插值多项式和哈希函数的分级密钥管理方案二，1 4 3 2 3 基于椭圆曲线的分级密钥管理方案1 5 3 3 现有的密钥管理方案面临的求根攻击1 7 3 4 本章小结t ：18 i i i 基于椭圆密码体制的密钥管理方法研究 第四章一种新的基于e c c 的密钥管理方案1 9 4 1 本文提出的密钥管理方案- 19 4 1 1 初始化阶段1 9 4 1 2 密钥生成阶段_ 2 0 4 1 3 密钥推导阶段：2 1 4 2 动态密钥管理，：2 1 4 2 1 密钥更新o _ 2 2 4 2 2 特殊状况安全等级类之间的关系暂时破坏。2 3 4 2 3 添加和删除安全等级类2 5 4 2 4 添加和删除等级关系2 8 4 3 安全分析j j 3 0 4 3 1 方案抵抗的攻击j 。3 1 4 3 2 方案实现的保密性：3 3 4 4 性能分析：3 4 4 5 本章小结。3 6 第五章总结：3 7 参考文献_ 3 8 7 j l i 谢：。：z 1 1 i v 图2 1 椭圆曲 图3 1 分级系 图4 1 密钥更 图4 2 等级关 图4 3 添加安 图4 4 删除安 图4 5 ，添加等 图4 6 删除等 表4 1 各方案 表4 2 各方案 v 基于椭圆密码体制的密钥管理方法研究 符号说明 e ：椭圆曲线； 粑：椭圆曲线e 的阶，即椭圆曲线e 上点的个数； n ：用户等级结构中安全等级类的个数； m ，：多项式删的阶( 即x 的最高次幂) ； t a ：在椭圆曲线e 上执行转换点到数算法的时间； t h ：执行哈希函数运算的时间； t m ：在有限域上执行乘法运算的时间； 一 t i n v ：在有限域上执行逆运算的时间； t e c c ：m ：在椭圆曲线e 上执行倍点运算的时间； t e c c a d d ：在椭圆曲线e 上执行加法或减法运算的时间 v i 内蒙古大学硕士学位论文 第一章引言 随着互联网和全球信息技术的不断发展，尤其是随着电子商务等具有高安全等级应用 的普及和经济信息化进程的推进，全球经济发展正在进入信息经济时代。计算机网络逐渐 应用于社会各个领域，它给社会带来无限财富的同时，网络与信息系统的安全性受到极大 关注。信息的保密通信问题显得越来越重要。 在今天的信息社会里，对通信安全保密问题的研究已经不在是仅出自于军事、政治和 外交上的需要，也与科学研究、经济发展息息相关。所以信息就是生命，信息就是时间， 信息就是财富。因此保护信息的安全已经成为信息时代的迫切要求。信息安全技术已成为 计算机理论研究和应用领域的学术前言和热点，而密码技术正是信息安全技术的核心。 1 1 密钥管理的研究背景及意义 数据密码技术是为了保证互联网体系中比较敏感的数据的保密性、完整性和真实性，避 免窃听、冒充、篡改、抵赖等手段造成的侵犯与危害的重要技术。目前密码技术已成为信 息安全技术研究的焦点之一。它广泛地运用于工作和生活之中，承担对军事、商业机密和 个人隐私的保护任务。 根据著名的k e r c h h o f f 原则，密码系统的保密性不依赖于加密体制或算法的保密，而依 赖于密钥的保密 1 】。加密算法和解密算法一般都是公开的，当合理的密码算法确定后，密码 系统的保密程度就完全取决于密钥的保密程度。如密钥得不到合理的保护和管理，即使算 法再复杂，保密系统也是脆弱。一旦密钥丢失或出错，导致合法用户不能提取信息，而且 可能致使非法用户窃取合法用户的信息；密钥得不到合理的管理，可能导致某软件的大量 盗版，致使正版软件开发商利益受损。因此，密钥管理就成了密码系统中保证信息安全性 的关键点。 密钥管理是处理密钥自产生到最终销毁的整个过程的相关问题，包括系统初始化，密 钥生成、存储、备份、恢复、装入、分配、保护、更新、控制j 丢失、销毁、保密及应用 等内容 2 1 。密钥管理是密码技术的重要核心之一。它要求密码系统应具有良好的密钥分配和 管理措施。设计安全的密码算法和协议并不容易，然而有效的进行密钥管理则是一件更困 难的事情。密钥管理不仅影响密码系统的安全性，而且涉及到应用密码的系统的可靠性、 有效性和安全性。密钥管理的目的是保证应用系统的安全性，维持系统中各实体之间的密 基于椭圆密码体制的密钥管理方法研究 钥关系，以抗击各种可能潜在的威胁，比如：私钥的泄露、私钥或公钥未经授权使用、使 用失效的密钥或违例使用密钥。密码学发展至今，密钥管理始终是一个不断出现新问题和 挑战的复杂课题。 现今好的密钥管理方案应该保证：( 1 ) 密钥难以被窃取；( 2 ) 密钥有使用范围和时间的 限制，即便密钥被窃取也没有用；( 3 ) 密钥的分配和更换过程对用户透明，用户不一定要亲 自掌管密钥j 。 1 2 分级密钥管理的发展现状及存在的问题 ， 在实际应用系统中，很多系统成员往往是按等级组织的，不同等级的系统成员获取信 息的能力是不同的。将分级思想应用到密码技术上，能够很好的实现密钥管理，合法成员 获取系统信息，但未经授权的成员将无法获取未经许可获取的信息。目前分级系统已广泛 应用于分布式数据库的管理、分布式操作系统和网络通信等各个方面，具有广阔的发展前 景。 1 9 8 3 年，a k l 和t a y l o r 【3 】首先提出解决分级访问控制下动态存取密钥分配问题的方案， 主要是针对于安全等级类上的用户如何派生出低等级安全类的加密密钥。然而随着安全等 级类数量的增加，公共参数的长度成线性增长，存储空间需要线性增大。此外，用户等级 类添加或删除时，系统需要重新分配所有安全等级类的密钥。 1 9 8 5 年；m a c k i n n o n 等人 4 1 提出一个优化算法，称为规范分配，该方案主要的目的是 解决a k l 和t a y l o r ( 1 9 8 3 ) 【3 】方案的缺陷，借助规范算法来减少公共参数的长度。然而寻找最 优化规范算法是很困难的，而且该方法没有解决用户等级类添加或删除时，系统需要重新 分配所有安全等级类的密钥这一缺陷。因此在访问控制中，动态访问控制问题没能够得到 有效地解决。 以上两种方案均采用自上而下的方法生成安全等级类的密钥。为提高计算效率以及减 小存储的复杂性，1 9 9 0 年，h a m 和l i l li s 】提出了自下而上的密钥生成方案。同a k l 和t a y l o r ( 1 9 8 3 ) 3 1 方案相比，h a m 和l i n ( 1 9 9 0 ) 7 寺 案【5 】减少了存储空间。但是当系统中的用户等级类 比较多的时候，该方案仍然需要大量的存储空间。 自此以后，一些方案被提出以便有效地处理动态访问控制下密钥管理问题。l i w a 、 w a n g 和l e i ( 1 9 9 1 ) 6 基于牛顿插值多项式和单向散列函数提出了一个密钥分配方案。在此 方案中，为了得到低安全等级类的私有密钥，高安全等级类的用户必须迭代执行密钥推导 过程，迭代算法导致密钥推导过程十分低效。s h e n 和c h e n ( 2 0 0 2 ) t 7 1 提出使用多项式插值来 内蒙古大学硕士学位论文 解殃访问控制协议中的密钥分配方案。在此方案中，系统并不需要维护安全类以及用户的 私钥，也就是说，任何用户都可以出于某些安全因素而自由地变更私钥。然而h s u 和 w u ( 2 0 0 3 ) 【8 】指出了这个方案存在着安全漏洞，即攻击者能够在多项式的时间内篡改预定义 的访问控制协议，以获得未经授权的信息。y a n g 和l i ( 2 0 0 4 ) 【9 】基于单向散列函数提出了 密钥分配方案，该方案取决于单向散列函数。h s u 、t s a i 和c h o u ( 2 0 0 8 ) 1 0 1 指出y a n g 和l i ( 2 0 0 4 ) 唧方案的一些安全缺陷，并且一些声明的安全要求是违反的。也就是说，用户可以 通过加强他的权限来访问未经授权的信息。h s u 等人进一步提出两方面的改进，以消除所指 出的安全缺陷。 2 0 0 6 年，j e n g 和w a n g 1 1 1 基于椭圆曲线密码体制提出了一种有效的密钥生成和管理方 案。在此方案中，每个安全等级类均可自由决定其密钥，而不是依赖一个值得信赖的权威 中心c a 。该方案的优点在于有效且灵活的解决了动态密钥管理问题，当添加或删除安全类 时，不需要更新所有安全类的密钥。2 0 0 8 年，c h u n g 和l c 占等人【1 2 1 同样基于椭圆曲线密码 体制也提出了一种有效的密钥生成和管理方案，在该方案中，每个安全等级类的密钥不是 自己决定，而是由权威中心c a 来决定，该方案也有效的处理了动态密钥管理问题。 通过对上述经典密钥管理方案的分析，可以得出，一个有效的密钥管理方案应该满足( 1 ) 密钥生成和推导算法简单；( 2 ) 有效地解决动态存储访问控制问题；( 3 ) 存储空间小，计算 ， 效率高；( 4 ) 抵抗各种内外攻击。 1 3 本文研究内容、 ： 椭圆曲线密码体制【1 3 】 1 4 】的安全性是基于椭圆曲线点群上的离散对数问题，目前求解该 问题的最好算法也需要完全指数时间，椭圆曲线密码体制又具有比特安全强度高、密钥长 度短、运算速度快、带宽要求低和节省存储空间等优点。一个安全的单向散列函数 1 5 1 基于 安全假设定理( d i f f i e 和h e l l m a n ，1 9 7 6 1 6 】) 是难以逆转的。 鉴于上述现状，本文在总结了经典分级用户系统结构上的密钥管理方案并分析了这些 方案的优点以及存在的缺陷的基础上，提出j e n g w a n g ( 2 0 0 6 ) 1 1 】方案和c h u n g l e e ( 2 0 0 8 ) 1 2 1 方案可能面临的一种求根攻击的安全漏洞，并试图在以上的基础上寻找一种基于椭圆曲线 密码体制的分级密钥管理方法。在该方法中，同样采用分级思想，不同权限等级的用户拥 有不同的密钥权限，在一个复杂系统中不同结点或不同岗位上的用户按照分类管理也相应 拥有不同的密钥权限，具体内容如下： 。 - 、 3 基于椭圆密码体制的密钥管理方法研究 1 、分析了现有经典分级结构下密钥管理方案，指出了j e n g w a n g ( 2 0 0 6 ) 1 1 】方案和 c h u n g l e e ( 2 0 0 8 ) 1 2 】方案可能面临一种在多项式时间内敌手利用求根算法进行攻击的安全漏 洞。 2 、基于椭圆曲线密码体制和单向散列函数提出一种新的密钥管理方法，该方法能够抵 抗上述所提到地安全漏洞，并且动态访问控制下，该方案能够很好的解决密钥管理问题， 包含安全类的添加或删除、密钥更新、安全类等级关系变更等，并对其进行了安全和性能 分析。 3 、在本文提出的密钥管理方法中：针对实际应用系统中的状况，基于用户等级权限， 构造了一个函数，使得当用户等级系统中等级关系结构发生临时变更时，代理职责人能够 较好地处理职责所在。 1 4 论文章节安排 本文基于椭圆曲线密码体制和单向散列函数针对椭圆曲线密码体制下的密钥管理方法 进行了研究，论文章节安排如下： 第一章为引言部分，介绍了密钥管理的研究背景和意义，回顾了分级密钥管理的发展 现状以及存在的问题，概括了本文的主要研究内容，最后给出论文的整体章节安排。 第二章我们给出本文所用到的相关基础知识，首先介绍了离散对数问题、牛顿插值多 项式和哈希函数，然后给出椭圆曲线密码系统理论知识，其中包括椭圆曲线的相关定义， 运算法则；椭圆曲线离散对数问题以及椭圆曲线密码体制。 第三章给出分级系统原理，并对现有经典分级用户系统上密钥管理方案进行了分类， 给出各个方案的描述并分析了这些方案的优点以及存在的缺陷，3 3 节中提出j e n g - w a n g ( 2 0 0 6 ) 1 1 】方案和c h u n g l e e ( 2 0 0 8 ) 1 2 】方案可能面临一种在多项式时间内敌手利用求根算法 进行攻击的安全漏洞。 第四章介绍新的密钥管理方法。首先在第三章提出的安全漏洞的基础上基于椭圆曲线 密码体制以及哈希函数提出一种新的密钥管理方法，给出密钥生成和推导算法；接下来4 2 节描述动态访问控制下密钥管理的相关问题，包含安全等级类的增加或删除、密钥更新、 安全类等级关系变更等状况，还处理了安全等级类临时代理的特殊状况，最后4 3 节和4 4 节给出该方法的安全分析和性能分析。 第五章针对全文进行总结，并指出需迸一步研究的内容。 4 内蒙古大学硕士学位论文 第二章相关知识点 本章将介绍本文所用到的相关基础知识点，包括离散对数问题、牛顿插值多项式、哈 希函敫和椭圆曲线密码系统理论知识。 2 1 离散对数问题 至今为止在密码学中，离散对数仍是难解问题。r s a 1 心密码体制所依赖的就是离散对数 的难解性。该问题简要描述为【1 刀：p 是一个大素数，g 是有限域g f ( p ) 的生成元，对手 y = 罟。m o d p ，通过x ，g ，p 计算很容易得到y ；而通j ，g ，p 计算得到工是很难得。密码学上很 多的体制都是基于离散对数问题的难解性【1 8 】【1 9 1 。 2 2 牛顿插值多项式 牛顿插值多项式2 0 1 是利用己知点( ，y 。) ( 工。，y 。) ( x 。，y 。) ，采用递归的方式来构建的多 ： 项式厂( x ) ，使得厂棚( ) = y 。o = o ，1 ，柳) ，- 厶( 工) = 口o = y o ，口o = y o ( 2 1 ) 石0 ) ：p o ( x ) + a i ( z x o ) ，口i = 丛丛 z l x o， l ( x ) ；? ( x ) + 口z ( x 一而) ( x 一，口：= 舌乏宅裂 。r a - 1i - ! 。一。y m y 。一ea ，兀( 一x ，) 厶( z ) = 巴一。( 石) + 兀( 石一吒) ，口。= k = o ，历2 ( 2 2 ) ( 2 - 3 ) ( 2 - 4 ) 2 3 哈希函数( o w h f ) 个安全的哈希函数( o n e - w a y h a s hf u n c t i o n ) h 1 5 】( 也称为单项散列函数) 具有以下性质： 1 ) 给定输入数据x ，很容易计算出它的哈希值 ( 功i 2 ) 给定哈希函数h 的一个输出哈希值j i l ( d ，从 ( 功+ 倒推出输入数据石则很难，计算上 不可行( 这就是哈希函数的单向性，此在技术上称为抗原像攻击性) ； 穗 5 茹 基于椭圆密码体制的密钥管理方法研究 3 ) 给定一个哈希值h ( x ) ，想要找出能够产生同样的哈希值的两个不同的输入数据石和 ，则很难，计算上不可行( 这种情况称为碰撞，此在技术上称为抗碰撞攻击性) 。 ， ， 2 4 椭圆曲线密码系统理论 2 4 1 椭圆曲线及其相关定义 椭圆曲线密码体制的数学原理【1 4 】【2 l 】_ 【2 5 1 涉及到了代数结构中群、环和域的概念。椭圆曲 ( 2 - 5 ) 其中：e ( x ) 是x 的二次多项式或者四次多项式。我们知道这样的积分是不能用初等函数来表达， 为表达此类积分，因而引入了椭圆曲线。椭圆曲线的形状并非是椭圆，如此命名的原因是因 为它们是由三次方程表述的，而这些三次方程类似于计算一个椭圆周长的方程。一般的，椭 圆曲线是由两个变量z ，y 表示的，定义如下： e ： y 2 + 口1 砂+ a 3 y = x 3 + 口2 x 2 + 口4 x + a 6( 2 6 ) 、 即椭圆曲线是由上述韦尔斯特拉斯( w e i e f s 仃a s s ) 方程所确定的平面曲线。其中变元x ，y 和 系数a ，o = 1 , 2 ，6 ) 均定义在某个域上，该域可以是有理数z 域，实数尺域，还可以是有限 域g f ( q ) 。椭圆曲线e 除了满足等式( 2 6 ) a i 拘所有的点( x ，y ) 的集合外，还包含一个无穷远 点o ( p o i n ta ti n f i n i t y ) 或零点( z e r op o i n t ) , 在这里无穷远点的定义为其y 坐标无穷大。 若我们强制把域限制在素数z 。域( p 为大素数) 上，椭圆曲线e ( 2 6 ) 被限制为如下形 式： ey 2 = z 3 + a x + b ( m o d p ) ( 2 7 ) 其中系数口，6 和变元x ，y 均属于z p ，口和b 满足判别式4 口3 + 2 7 b 2 ( m o d p ) 0 。满足等式( 2 - 7 ) 的所有的点( 工，y ) 的集合外加一个无穷远点0 的椭圆曲线通常记为e p ( a ，功。该类型的椭圆 曲线点的个数只有有限个数，称之为椭圆曲线的阶( 撑e ) ，阶与椭圆曲线的安全性有关，撑e 懿 越大，e 的安全性越高。如果粗略估计，那6 # e 近似为p 。我们可以使用h a s s e 定理得到旭 6 内蒙古大学硕士学位论文 的精确范围。 h a s s e l 2 6 1 定理：如果e 是确定在唰上的椭圆曲线，n 是e 上的点的个数，则有 l n 一( p + 1 ) i 2 i 。那么e 的阶撑e 满足下列不等式： p + 1 2 4 p e p + 1 + 2 p ( 2 - 8 ) + ， 素数z p 上的椭圆曲线e 可以采用参数集合表示，即t = p ，a ，b ，n ，g ，h ) ，其中p ，口，b 的 含义如上描述，它们用来确定一条椭圆曲线；g 为椭圆曲线e 的基点，g = ( x o ，y g ) ；素数 t ? 是g 的阶，即满足m g = 0 成立的最小素整数；h 是聊关于阶托的协因子，即h = # e m 。 对于软件应用来说，z p 域上的素椭圆是最好的。然而并不是z ，域上的任何椭圆曲线都 能应用到密码学应用软件上。 2 4 2 椭圆曲线的运算法则 假设椭圆曲线e 定义在实数域k 上，e 的加法概念定义如下：如图2 1 ( a ) 所示，设 p ( 五，y ) ，。q ( x 2 ，y ：) 为皂上互不相同的两点，连接点p 和q 的直线交e 于另一点m ，过m 作平行于x 坐标的直线与曲线e 交r ( x 3 ，y 3 ) ，则尺称为p 和q 两点之和，记作r _ p + q 。 如图2 1 ( b ) 所示定义了一种点乘运算，点乘运算是点加运算的一种特例。设尸和q 为e 上 相同的两点( x 1y 。) ，过点p 作曲线e 的切线与e 交于点m ，过m 作平行于工坐标的直线 与曲线e 交r ( x ：，y ：) ，记为月= p + 尸。如果切线和x 坐标平行即交曲线e 于无穷远点，则 p + p = o ，即点尸为椭圆曲线e 上阶为2 的点。给定一个整数k ，k 个p 点相加，即p + 尸+ + 尸， 表示为舻，称为数乘或点乘。 、。 椭圆曲线e 上的点在特定的加法运算下，构成一个a b e l 群( 交换群) 。若e ( k ) ： y 2 = z 3 + 骶+ b ，则有如下规则成立： 1 ) 单位元：p + o i = d + p = p ； 2 ) 负元：如p ( i ，夕1 ) 0 ，那么一p = ( x l ，- y 1 ) ，尸+ ( 一尸) = 0 ； 3 ) - o = o ； 4 ) 点加：p q ，q o ，q - p ，则尸+ q = r ( x 3 ，y 3 ) ； 7 。 基于椭圆密码体制的密钥管理方法研究 5 ) 倍点：p 一p ，贝02 p = p + p = r ( x 3 ，y 3 ) 。 ( x 2 ，y l 蔓，二多f 。 ， i r i 乞 ， r ( x 3 ，) ( a ) ：点加运算 jl - 。一_ 一“岁彳 ! i l f - ； r ( x 2 ， ) ( b ) ：点乘运算 ， 图2 1 椭圆曲线运算法则 f i g u r e 2 1e l l i p t i cc u r v ea l g o r i t h m 2 4 3 椭圆曲线离散对数问题( e c d l p ) 根据上述椭圆曲线点乘运算的定义，在e 上能找到一点p ，给定一个整数k ，满足 k p 号p + 尸+ p ( k 个p 相加) ，即在椭圆曲线e 上存在一点q ，满足a = 护。 椭圆曲线离散对数问题【1 4 】【2 2 】( e 1 l i p t 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 ) 定义如下：给定 素数p 和椭圆曲线e ，对于q = k pi 在已知p 和q 的情况下求出正整数k 的过程，即 k = l o g p q 。可以证明，已知k 和p ，计算q 比较的容易，而已知p 和q 计算k 则比较困 难，最好的算法仍旧需指数时间。至今还没有更为有效的方法来解决这个问题。这就是椭 圆曲线加密原理所在。 2 4 4 椭圆曲线密码体制( e c c ) 密码学上通常将数据加密技术分为两大类：即对称密码体制和公钥密码体制。对称密码 体制是一种传统的密码体制，如：d e s ( d a t ae n c r y p t i o na l g o r i t h m ，数据加密算法) 、 a e s ( a d v a n c e de n c r y p t i o na l g o r i t h m ，高级加密算法) ，加密和解密使用相同的密钥，这样当 系统成员比较庞大的时候，密钥管理将会出现问题，限制了对称密码系统的应用范围，如不 内蒙古大学硕士学位论文 能应用到数字签名。公钥密码体制中加密和解密使用不同的密钥，即公钥对( 公钥、私钥) ， 如r 3 a 。公钥密码系统通常包括密码管理、加解密方案和数字签名三类协议 2 】。 同r s a 相比较，如果将椭圆曲线上的点加运算和离散对数上的模乘运算相对应，椭圆曲 线中的点乘运算和离散对数中的模幂运算相对应，那么就可以建立基于椭圆曲线的密码体制 。【2 7 】。19 8 5 年k o b l i t z t 2 3 1 和m i l l d 驯提出了椭圆曲线密码体制( 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 d l p 是比整数因子分解问题难的多的数学难题，所以椭圆曲线离散对数问题是椭圆曲 线密码体制的核心。与一般的有限乘法群上的离散对数问题不同，有限域上的椭圆曲线离散 对数问题的求解更难，不能被所有已知算法在多项式时间内破解，在一般的离散对数问题中， 有限域的代数对象由域的加法和乘法两种基本运算构成，这使得离散对数问题在亚指数时间 内就可以破解。在椭圆曲线离散对数问题中，有限域的代数对象只有一种椭圆曲线上的加法 运算构成，这使得除了少数非常特殊的椭圆曲线( 如：奇异椭圆) 外，亚指数时间的离散对 数破解算法对椭圆曲线是无效的。 既然椭圆曲线密码体制是一种公钥密码系统，那么它具有一般公钥密码系统的特点，即 具有两个密钥：公钥和私钥。在加密和解密的过程中，分别使用不用的密钥，想要由加密密 钥推导出解密密钥在计算上是不可行的。既然椭圆曲线密码体制的安全性依赖于椭圆曲线离 散对数问题的难解性，而e c d l p 描述为：由目纠、p 和q ，确定k 。那么可以将( 露，q ) 作为 一个密钥对，公开密钥对辑，q ) 中的q 作为公钥，保留k 作为私钥。这样基于椭圆曲线离散 对数问题，构造了椭圆曲线公钥密码系统【2 7 1 。 椭圆曲线密码体制与其他密码体制相比较具有以下优势： 1 ) 比特安全强度高，e c c 中1 6 0 比特的密钥的安全强度相当于r s a 或d s a ( d i g i t a l s i g n a t u r ea l g o r i t h m ，数字签名算法) 密码体制中1 0 2 4 比特的安全强度；2 1 0 比特的 密钥的安全强度相当于r s a 或d s a 密码体制中2 0 4 8 比特的安全强度。 2 ) 密钥长度短，e c c 的密钥长度和系统参数与r s a 、d s a 相比要小得多，这也就意味 着e c c 能够节省存储空间。 3 ) 运算速度快，r s a 体制可以通过选取长度较短的公钥来提高公钥计算速度，以便提 高加密或数字签名验证的速度，使其在加密或签名验证速度上与e c c 平衡，但安全 性却降低；在私钥的处理速度上( 解密或签名) ，e c c 远比r s a 、d s a 快得多。因此 e c c 总的速度比r s a 、d s a 要快很多。若在相同的安全强度下，采用1 6 0 比特e c c 进行加解密或数字签名要比用1 0 2 4 比特r s a 或d s a 大约要快1 0 倍。 9 基于椭圆密码体制的密钥管理方法研究 4 ) 带宽要求低，当对长消息进行加解密时，e c c 和r s a 、d s a 密码系统有着相同的带 宽要求；但对短消息进行加解密时，e c c 的带宽要求相对于r s a 、d s a 却低很多。 而公钥加密系统多甩于短消息，如用于数字签名和用于对称系统的会话密钥传递。 上述可以看出椭圆曲线密码体制具有比特安全强度高、密钥短、运算速度快、带宽要求 低和节省存储空间等优点，e c c 的这些特性使它在密钥交换、身份认证。数字签名、智能卡 的安全保密等领域，具有广阔的市场前景。 1 0 内蒙古大学硕士学位论文 3 1 分级系统原理 第三章经典分级密钥管理方案 在实际应用中，系统成员多数情况下是按照等级进行分类，不同等级的系统成员获取 信息的能力是不同的。分级用户访问控制结构应用于很多的领域，比如：政府，军队，学 校，企业，计算机网络通信系统，数据库管理系统，分布式操作系统等各个方面，目前来 说该结构具有很广阔的发展前景。在分级用户系统中，为保证信息的安全及信息的便捷使 用，通常采用合适的密码技术( 如加密解密、数字认证和数字签名) 构建管理机制，比如： 利用分级加密来确保信息的机密性，用签名算法或确保信息的完整性。 在分级用户系统【3 1 中，访问控制机制用来为授权用户提供敏感信息的管理，合法成员获 取系统信息，但未经授权的成员将无法获取未经许可获取的信息。按照不同的权限职责，用 户和他们自己的信息可以被组织成一类不相交的安全等级类集合。具体而言：在分级用户系 统中，用户按照安全等级被分配成一类互不相交的安全等级类，所有的安全等级类作为一个 ， 集合，即肥= s q ，s q ，s c 。) ，并在这些等级类之间定义种偏序关系，即( s c ，) ，、“” 表示一个二元偏序关系，s q 踞表示等级类踞的安全级别高于或等于等级类蚂的安全 级别，即等级类s q 比等级类s c ，具有更高的特权。换而言之，等级类s q 里的用户能够访问 等级类孵。里的用户所持有的加密信息，但反之却不允许等级类s q 里的用户得到等级类s q 的加密密钥，访问加密信息。此时，我们称s q 是s c ，的前继者( 也就是所谓的上级) ，或者 s q 是踞的后继者( 下级) 。如若s q s q ，且不存在安全等级类，使得蚂s q s q ， 那么则称踞是s q 的直接前继者，或者配，是s q 的直接后继者。每一个安全等级类蛙中 ， 的用户共享密钥k ，他们用k ，来加密或解密自己的敏感信息。当s q 中的某一用户想要恢复 被其后继者贮，所加密的数据时，他必须得到正确的密钥足，才能访问s q 的加密信息。如图 3 1 展示了一个分级系统的实例。 等级类里的用户共享密钥k ：，踞里的用户共享密钥k 。，跽里的用户共享密钥 k ，。现踞中的一个用户a 想将他持有的敏感信息朋通过某种安全信道广播出去，首先他 基于椭圆密码体制的密钥管理方法研究 使用k 。将信息加密成密文m ，然后广播密文m 。等级类中的用户b 要想访问a 的敏 ， 感信息聊，必须获得访问权限k 。才可以对m 进行解密从而获得m 。同理b 要想获得s c ，中 用户c 的加密信息，必须先获取k ，。 图3 1 分级系统结构层次关系 f i g u r e 3 ih i e r a r c h i c a ls y s t e ms t r u c t u r e 换而言之，在分级用户系统中，前继者为了访问后继者加密的数据，他必须获得相应 的访问权限，也即后继者的加密密钥。最简单的方法就是s c 2 将其所有下级用户的密钥全部 存储起来。这样，随着系统中等级类的不断扩大，前继者的密钥存储开销也随之增加，致 使密钥管理困难性提高，从而密钥的保密性减低。 3 2 经典分级密钥管理方案以及分析 为了解决分级系统中密钥管理的一系列问题，比如密钥的存储，保密，更新，添加等等， 一些方案相序的提出。现有的分级密钥管理方案中，大致可以分为以下几类：基于离散对数 问题提出的分级密钥管理方案，基于牛顿插值多项式和哈希函数的分级密钥管理方案和基于 椭圆曲线的分级密钥管理方案。下面我们将分别介绍几类经典的密钥管理方案，并且对其进 行分析。 1 2 内蒙古大学硕士学位论文 3 2 1 基于离散对数问题的分级密钥管理方案 1 、a j d 和t a y l o r 的密钥分配方案 1 9 8 3 年，a k l 和t a y l o r 3 】首先提出了解决分级访问控制下动态密钥存储分配问题的方 案，该方案主要解决密钥推导问题。即安全等级类上的用户如何推导出后继等级类的加密 密钥。该方案基于大整数分解和离散对数问题，分为密钥生成和密钥推导阶段，生成算法 和推导算法都很简单。密钥生成阶段：每个安全等级类s c , 通过权威中心c a 分配到_ 个公 共参数以，通过该参数和权威中心c a 的密钥s k 可以获得一个加密密钥颤；密钥推导阶段： 如果s c ，s c , ，且t ，f ，是一个整数，那么安全类s c ；能够成功的使用它的密钥和公共参数 推导出安全类蚂的加密密钥。 a i d 和t a y l o r 方案确实是能够很容易的推导出后继者的加密密钥，然而随着系统中安 全等级类数量的增加，公共参数的长度必然有着线性增长的趋势，此外，添加或删除安全 类时，系统需要重新分配所有安全等级类的密钥，这给动态存储控制带来很大的不便。 、 2 、m a c k i n n o n 等人的密钥管理方案 1 9 8 5 年m a c k i n n o n 等人4 1 提出了一个优化算法，称为规范分配，该方案主要的目的是 解决a i d 和t a y l o r 方案的缺陷，借助规范算法来减少公共参数的长度。然而寻找最优化规 范算法是很困难的，而且该方法没有解决用户等级类添加或删除时，系统需要重新分配所 有安全等级类密钥这一缺陷。因此在访问控制中，动态访问控制问题没能够得到有效地解 ， 。 决。 3 、h a m 和l i n 的密钥管理方案 t ， 一 a i d 和t a y l o r ( 1 9 8 3 ) 方案1 1 以及m a c k i n n o n ( 1 9 8 5 ) 等人【4 】方案均采用自上而下的方法获 取安全等级类的密钥，而且这两个方案的计算效率很低，需要的存储空间很大。为了提高计 算效率和减小存储空间的复杂度，1 9 9 0 年，h a m 和l i n ( 1 9 9 0 ) 5 1 同样基于离散对数问题提出 了自下而上的密钥生成方案。该方案同样分为密钥生成和密钥推导两个阶段，具体步骤如下。 密钥生成阶段：每个安全等级类s c , 仍然分配到一个公共参数t ，通过该参数和权威中心c a 的密钥s k 可以获得一个加密密钥氟，该阶段类似与a k l 和t a y l o r 方案的密钥生成阶段； 1 3 基于椭圆密码体制的密钥管理方法研