（计算机应用技术专业论文）椭圆曲线在wsn密钥管理中的应用研究.pdf

河南大学研究生硕士学位论文 摘要 随着传感器技术、数据处理技术以及无线通信技术等的迅猛发展，信息对人 们越来越重要，得到信息的途径越来越多。无线传感器网络是新兴的一种网络方 式，该网络技术发展很快，并且正成为人们研究的热点。随着无线传感器网络的 广泛应用，其安全性问题也受到越来越多的关注。密钥管理是其中最重要的部分， 也是首要解决的问题，是保证节点之间安全传输数据的关键。 目前无线传感器网络的密钥管理方法多是以对称加密为基础，但是随着技术 的发展，这些方法已经不能满足网络的安全性需求。现在已有人通过算法的优化 把非对称加密算法应用到无线传感器网络的密钥管理中，使网络的安全性得到提 高。在阅读了大量相关文献的基础上，对非对称密码体制进行对比，椭圆曲线密 码体制比较适合无线传感器网络的特点。本文的主要工作如下： l 、本文对现有无线传感器网络密钥管理算法进行研究，并对各方案的优缺点 进行研究。 2 、提出一种新的密钥管理方案，把椭圆曲线密码体制和h a s h 函数应用到无 线传感器网络的密钥管理中，应用椭圆曲线上d i 伍e h e l l m a n 密钥交换产生节点信 息交换时的会话密钥，增加了节点间信息交换的安全性。本方案降低了节点的计 算量，节约了节点的存储空间，提高了节点问的连通概率，对网络的拓扑更方便， 并减少了节点的能量消耗。 3 、使用o m n e t + + 仿真工具对节点连接率、抗俘获性等性能进行仿真实验， 验证了该方案的优越性。 关键词：无线传感器网络；椭圆曲线；h a s h 函数；密钥管理；密码学 第1 i 页河南大学研究生硕士学位论文 a b s t r a c t a st h er a p i dd e v e l o p m e n to fs e n s o rt e c h n o l o g y , d a t ap r o c e s s i n ga n dw i r e l e s s c o m m u n i c a t i o n t e c h n o l o g i e s ，t h ei n f o r m a t i o n i sm o r ea n dm o r ei m p o r t a n tf o re v e r y o n e o fu s a n dm o r ea n dm o r ea r ep r o p o s e dt og e tt h eu s e f u l li m f o r m a t i o n ，w i r e l e s ss e n s o r n e t w o r k sa r ei m p o r t a n to n eo ft h e m i ti sb e c o m i n ga na n a c t i v er e s e a r c ha r e ai nt h ef i e l d o fc o m p u t e rs c i e n c ea n dd e v e l o p sr a p i d l y w i mt h ew i d ea p p l i c a t i o no fw i r e l e s ss e n s o r n e t w o r k s ，t h es e c u r i t yi s s u eh a sb e e nm o r ea n dm o r ea t t e n t i o n k e ym a n a g e m e n ti so n e o ft h em o s ti m p o r t a n tp a r ta n dt h ee s s e n t i a lp r o b l e m 。i ti st oe n s u r es e c u r et r a n s m i s s i o n o fd a t ab e t w e e nn o d e sk e y t h ec u r r e n tk e ym a n a g e m e n ti nw i r e l e s ss e n s o rn e t w o r k sb a s e do ns y m m e t r i c e n c r y p t i o nm e t h o db a s e do nm u l t i p l e ，b u ta st h et e c h n o l o g yd e v e l o p s ，t h e s em e t h o d s c a nn o tm e e tt h ed e m a n df o rn e t w o r ks e c u r i t y h a sb e e na d o p t e di nt h eo p t i m i z a t i o n a l g o r i t h mt on o n - s y m m e t r i ce n c r y p t i o na l g o r i t h mi sa p p l i e dt ow i r e l e s ss e n s o rn e t w o r k k e ym a n a g e m e n t , s on e t w o r ks e c u r i t yi si m p r o v e d i nr e a d i n gal o tr e l e v a n tl i t e r a t u r e ， o nt h eb a s i so fc o m p a r i n ga s y m m e t r i cc r y p t o s y s t e m ，e l l i p t i cc u r v ec r y p t o s y s t e mi s s u i t a b l ef o rw i r e l e s ss e n s o rn e t w o r k s t h i sa r t i c l em a i n l ya sf o l l o w s ： f i r s t , b a s e do ne x i s t i n gw i r e l e s ss e n s o rn e t w o r kk e ym a n a g e m e n t ，a n dt os t u d yt h e a d v a n t a g e sa n dd i s a d v a n t a g e so fe a c hs c h e m e s e c o n d ，p u tf o r w a r dan e wk i n do fk e ym a n a g e m e n tp l a n , t h ee l l i p t i cc u r v e e r y p t o s y s t e ma n dh a s hf u n c t i o n i s a p p l i e dt o w i r e l e s ss e n s o rn e t w o r k so fk e y m a n a g e m e n t ，乃ea p p l i c a t i o no fe l l i p t i c c u r v ed i f f i e - h e l l m a ne n c r y p t i o ne x c h a n g e p r o d u c en o d ec o m m u n i c a t i o ns e s s i o nk e y s ，i n c r e a s et h ec o m m u n i c a t i o nb e t w e e nn o d e s i ss a f e t y 眦ss c h e m el o w e r st h en o d ec a l c u l a t i o n , s a v eas p a c e ，i n c r e a s et h es t o r a g e n o d e sb e t w e e nn o d e so nt h en e t w o r k , c h i n au n i c o r np r o b a b i l i t yo ft o p o l o g ym o r e c o n v e n i e n t ，a n dr e d u c et h en o d ee n e r g yc o n s u m p t i o n 1 1 l i r d ，o m n e t - hs i m u l a t i o nt o o l su s e di nc o n j u n c t i o nn o d er a t e ，c a p t u r e da n d p e r f o r m a n c es i m u l a t i o ne x p e r i m e n tp r o v e st h i ss c h e m e ，t h es u p e r i o r i t y k e y w o r d s ：w t r e l e s ss e n s o rn e t w o r k s ；e l l i p t i cc u r v e ；h a s hf u n c t i o n ；k e ym a n a g e m e n t ； i n f o r m a t i o ns e c u r i t y 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请本人郑重声明：所呈交妁学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成景。也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 擘位中请人( 学位论文作者) 釜名：，孟盔丝： 弧k 年k al 咖 关于学位论文著作权使用授权书 本人经河南大学审核批准授子硕士擘住。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 甄质文 本和电子文本) 阻供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) ( 涉及保密内睿的学住论文在解密后适用本授权书) 学位获得者( 学位论文作者) 鍪名：t 宗瘃继 弧| 口冬匕ai 讯 学位黻指导教师荽名：丑么通 弧f d 每0a 弘 河南大学研究生硕士学位论文第1 页 第1 章绪论 随着现代科技的发展、信息化的进步，信息安全越来越重要，不但关系国家 的政治安全、经济安全、军事安全、社会稳定，也关系到社会中每一个人的数字 化生存的质量。信息安全成为全社会的焦点问题，是信息化社会发展中不可缺少 的技术基础。 1 1 研究背景介绍 随着计算机网络的逐步发展以及全球信息化水平的不断提高，已经进入信息时 代，随之带来了网络与信息安全的重要性日趋增强，网络中传输信息的保密问题 显得越来越重要，不管是通信双方个人通信信息，还是电子商务的发展，都需要 在i n t e r n e t 网络中保证信息的安全传输，在传输中需要对信息的加密，使敌手截获 信息时也没法知道信息的内容。进而引入了密码学中加密算法在网络中的应用， 特别是现在飞速发展的无线传感器网络，因为网络中节点的各方面的限制，安全 性更显得格外重要。 信息安全技术是一门综合学科，它涉及信息论、计算机科学和密码学等多方 面知识，信息安全面临的攻击可能会来自独立的犯罪者、有组织的犯罪集团和国 家情报机构。对信息的攻击具有以下新特点：无边界性、突发性、蔓延性和隐蔽 性。因此要了解信息安全，首先应该知道信息安全面临那些威胁，信息安全技术 就是为了解决信息安全面临的威胁而产生的。让信息免遭威胁，或者将威胁带来 的后果降到最低程度是信息安全的任务，使得整个网络有效的正常的运行，使网 络中每个使用者都得到安全的保护。信息安全所实现的目标和研究的范畴是：网 络中信息的保密性、完整性、可用性、可追溯性、真实性和可靠性保护等方面的 技术和理论。随着传感器技术、数据处理技术以及无线通信技术等的迅猛发展， 无线传感器网络已经广泛地应用于气候观测、环境监测、军事、医疗等各个领域， 必将成为2 1 世纪最有发展前景的技术之一。由于无线传感器网络自身的特点，传 统网络中用到的许多成熟的安全方案不能直接应用于传感器网络，这就要求设计 出能够满足实际应用的无线传感器网络安全方案。无线传感器网络的安全问题中 第2 页河南大学研究生硕士学位论文 密钥管理是其中最重要的部分，也是首要解决的问题，是保证节点之间安全传输 数据的关键。本选题主要是把椭圆曲线密码体制应用到无线传感器网络的密钥管 理方面，该方案使节点的能量消耗得到降低，而且密钥的更新方法得到更大改善， 还实现了认证功能。 1 2 课题研究现状 随着传感器网络的发展，无线传感器网络的安全问题也越来越突出，人们提 出了多种无线传感器网络的密钥管理方案，大致可以分为：确定性方案、随机密 钥预分配方案和混合方案；按照管理密钥的密码体制分：对称密码体制管理方案、 非对称密码体制管理方案。确定性方案是保证网络的全连通性，但是节点的开销 比较大，整个网络的扩展性受到很大限制，该方案比较有代表性的是使用矩阵或 者多项式等数学工具来实现网络中任意两个节点之间都有唯一一个共享密钥。该 方案使每个节点的存储量大大增加，如网络中有1 0 0 0 个节点，设节点的密钥长度 为1 6 比特，则网络中的每个节点必须存储其他节点的密钥大小约为1 6 k ，这样节 点的寿命被大大降低。随机密钥预分配方案基本思想就是在节点进入网络时，从 基站生成的大密钥池中随机获取部分密钥作为自己和其他节点通信时的密钥存储 起来，当两个节点要进行通信时，首先在各自的密钥环中找共同的密钥，如果有 就进行通信，否则取其他路径：该方案要求通信的两个节点必须至少要有一对共 享密钥，在这类方案中还有的是把网络中节点的共享密钥对数不小于一定的数q ， 如果小于q 就表示两节点不能通信；这类方案解决了网络中节点的大量存储密钥 的问题，避免的节点单个密钥的不安全性，但是该方案的缺点还是有的，即网络 的连通性和健全性受到削弱。该类方案的代表有：基本随机密钥预分布模型，简 称为e g 方案；q - c o m p o s i t e 随机密钥预分布模型；基于节点位置的密钥分布模型 和随机密钥对模型等；混合方案，这些方案的基本思想取了前两类的优点。 在2 0 0 2 年，e s c h e n a u e ra n dg l i g o r 等人【1 1 首先提出关于无线传感器网络中密钥 管理的随机预分配密机制的思想，这类方案的基本思想是，在节点布置之前，基 站生成一个大的密钥池，节点从中随机地选出部分密钥，以备在节点通信时寻找 共享密钥；节点布置网络中后，相邻的两个节点互相交互各自的信息，即从密钥 池中所取的密钥，如果两者有共享部分，则该两个节点就可以建立安全连接，即 河南大学研究生硕士学位论文第3 页 两节点可以进行通信。否则要通过中间节点进行连接通信，即链路连接通信。在 此方案的思想基础上，c h a n e t a l t 2 1 研究并提出了“q - c o m p o s i t e 密钥管理思想机制 来改善网络各方面性能。在这种机制中，两个节点之间至少要有q 个共享密钥对， 才可以建立安全链接。 接下来，有更多不同的密钥预分配方案被提出，d u p l 和c h e n g 卜就是代表。 在c h e n g 提出的方案中，网络中通信节点之间的密钥形成分为四个阶段进行，前 两个阶段和一般的采用密钥预分配的密钥管理机制相同。第三个阶段的在节点找 到共享密钥后，又对该密钥进行计算变形形成会话密钥，这样做防止节点被敌手 捕获攻击；当节点间通信结束后，节点把他们的通信密钥给删除，这样减少了内 存的占用空间，这就是第四阶段。它的不足之处是用了一个密钥分配服务器来统 一管理所有的这些任务，如果敌手在网络链接没有形成之前就捕获了一些节点的 话，整个网络就存在安全性的威胁。 2 0 0 4 年，d u e t a lp 1 提出了基于布置信息的密钥预分配机制。这一机制的基本思 想是：网络中的节点被分成许多组，从密钥池中为每个组分配一个密钥子集。因 为整个密钥池中的密钥数量很大，两个节点只能分到小部分的密钥，所以，共享 密钥就比较少，甚至就没有；因此把密钥池给分开，使节点的连通性增加，节点 间的共享密钥的概率得到了提高。 文献【6 。9 】也都利用了节点的布置信息来进行密钥管理。但在这些方案中都片面 的实现了网络的链接性或者安全性，没有对连接性和安全性进行协调。这些方案 为了保证节点的连通性使网络中节点的存储密钥数量增加，降低了节点的寿命。 z h e n gy u t l o i 等提出的密钥管理机制中，不同于其他方案，该方案是把目标区域分 成了连续的正六边形，使节点中所存储的密钥数量大大减少。 在1 9 8 5 年，n e a lk o b l i t z 和v i c t o rm i l l e r 分别独立提出了椭圆曲线密码体制 ( e c c ，e l l i p t i cc u r v ec r y p t o g r a p h y ) ，它是目前已知的所有公钥密码体制中，能 够提供最高比特强度( s t r e n g t h - p e r - b i t ) 的一种公钥体制，在问题的一定情况下，需要 实现同等安全性的指标，所需要的椭圆曲线的密钥尺寸是最短的，所以说，椭圆 曲线是比较安全和方便的。e c c 作为公开密钥密码体制中的一种，在丰富的理论 基础上可以实现高度的安全性，它具有存储效率、通信带宽的节约以及计算效率 等多方面的优越性，是一种非常有前途的密码体制。 第4 页河南大学研究生硕士学位论文 文献【1 3 】提到在e c c 方案的基础上改进，初始密钥链的计算和密钥的更新都是 在基站( a s ) d e 完成，极大降低了节点的能量消耗，而其密钥的更新方法得到极大的 改善。该选题用到有关算法有基于有限域上离散对数的e i g a m a le 1 6 】算法和椭圆曲 线算法e c c i l 7 a s l 。 1 3 本文研究内容和组织结构 目前针对无线传感器网络的密钥管理技术可以分为预共享和随机密钥预分配 模型。它们都建立在对称密码技术上，存在安全性低、适用网络规模小、可扩展 性弱和缺乏节点身份认证等问题。本选题在详细分析无线传感器网络现有安全解 决方案不足的基础上，提出解决安全问题的新途径。从资源消耗和安全等方面研 究椭圆曲线密码在无线传感器网络中应用的可行性和必要性，并基于椭圆曲线密 码研究设计一种适用于无线传感器网络的动态密钥管理方法。最后，对所提方案 进行验证分析。 本文的组织结构如下： 第1 章主要介绍了选题背景和国内外的研究现状，并阐述了密钥管理的发展 史和一些主要密钥管理算法。最后叙述了本论文的主要内容。 第2 章介绍密码学领域的相关基础数学知识，主要包括椭圆曲线、椭圆曲线 上离散对数问题、h a s h 函数等数学知识和概念。 第3 章介绍了无线传感器网络的有关知识，其中有无线传感器网络的生成、 结构和特点；还有关于无线传感器网络的密钥管理的介绍，分别阐述了预共享密 钥模型和随机密钥预分布模型。 第4 章结合前面的密钥管理算法提出基于椭圆曲线的密钥管理算法，分别通 过网络的建立、簇的划分、节点间的通信、节点的更新和删除来进行本方案的叙 述。 第5 章对本文提出的方案进行性能方面的分析，并和以往的方法进行比较。 在总结与展望部分，给出了全文的总结和进一步的研究方向。 河南大学研究生硕士学位论文第5 页 第2 章数学基础知识 密码学是以数学知识为基础的，在描述新方案之前，先了解一下所需数学基 础知识，如椭圆曲线、h a s h 函数等。 2 1 椭圆曲线的概念和性质 对称密钥密码体制虽然加密算法比较简单，加密解密高效快速，密钥简短， 破译困难；但是它同样存在着问题：对称密码体制要求密钥在分配的时候，必须 要安全的，也就是秘密分发给用户，如果被泄露密码就没任何意思，没有任何价 值，用户交流的信息还存在很大的威胁。但是，无线传感器网络的有开放性和随 机性等性质，不能实现密钥分发的秘密性，所以在无线传感器网络中应用对称密 码体制是有一定的困难性的。当敌手在信道中攻破密钥，他们就很容易就可以伪 装起来，骗取对方的信任，进行信息的交流，从中得到利益。并且，对称密码体 制的密钥还需要节点花费大量的存储空间来对密钥进行管理，当网络扩展的足够 大的时候，节点的存储空间就不能够满足这一要求了，进而使节点的各方面性能 大大的降低。另外对称密钥密码体制不易实现数字签名，这也是限制其应用的一 个原因。 为此，人们设计了公开密钥密码体制，从根本上克服对称密码体制的各种不 便，且适应网络环境的应用。由于公钥密码具有良好的密码学特性和广泛的应用 前景，自从问世以来吸引了密码学爱好者。人们提出了大量不同的公钥密码体制， 这些公钥密码体制的安全性都是基于数学问题的难解性。其中数学问题过于简单 往往是密码体制被攻破的重要原因，但是，数学问题要是过于复杂，密码体制得 不到实现。所以至今为止，那么多的公钥密码体制只有三类体制被证明是安全有 效的1 9 1 。 1 基于整数因式分解的公钥密码体制，典型的是1 9 7 8 年r r i v e s t ，a s h a m i r 和l a d l e m a n 提出的一种用数论构造的r s a 算法。 2 基于有限域上离散对数问题( d l p ) 的公钥密码体制。 3 基于椭圆曲线离散对数问题( e c d l p ) 的公钥密码体制，包括椭圆曲线型的 第6 页河南大学研究生硕士学位论文 数字签名方案，椭圆曲线型d i f f e r - h e l l m a n 密钥交换方案。 在1 9 7 6 年由d i f f i e 和h e l l m a n 提出公钥密码体制的思想。此后，公钥密码体 制不断被提出，其安全性依赖于不同的计算问题，其中，最著名的是r s a 密码体 s 0 ( 及其变种) ，其安全性基于分解大整数的困难性：e i g a m a l 密码体制( 及其变种， 例如，椭圆曲线密码体制) ，其安全性基于离散对数问题。 基于r s a 算法的公开密钥密码体制在被提出后得到了广泛的应用，但随着计 算机处理能力的提高和计算机网络技术的发展，r s a 的安全性受到了挑战，为了 安全使用r s a 体制，人们不断增加r s a 的密钥长度，密钥长度的增加带来了很大 的计算量，要求的存储空间也越来越大，使人们感到非常的不便，所以说r s a 的 发展面临着非常严峻的挑战。而椭圆曲线密码体制( 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 所面临的困境。 在近年，椭圆曲线密码体制越来越被人们所重视，并应用到很多方面。椭圆 曲线密码体制是迄今被时间证明安全有效地三类公钥密码体制之一，以高效性著 称，e c c 的安全性基于椭圆曲线离散对数问题的难解性，即椭圆曲线离散对数问 题被公认为要比证书分解问题( r s a 方法基础) 和模p 离散对数问题( d s a 算法基础) 难解的多，无论是在计算量上，还是在存储空间上，e c c 都要比他们优越的多， 因为在相同安全的情况下，需要e c c 的加密密钥长度要比他们短的多。一般来说， e c c 在亚指数的时间内不会被攻破，被破解的花费时间在同等级别上比r s a 要少 些的，而且e c c 的密钥长度也远小于r s a ，由于e c c 的这些性质和安全系数确 定了e c c 密码体制成为当前密码体制中最受欢迎的一种，也是公钥体制中最高加 密强度的一种加密体制。表2 i 给出了e c c 密码体制和r s a 体制、d s a 体制在 保证同等安全的条件下各自安全系数。 表2 - 1e c c 、r s a 和d s a 的安全系数比较 e c c 密钥长( 位)r s a 密钥长度( 位)r s a e c c 密钥尺寸比率破解时间( u i p s 年) 1 0 65 1 25 ：l1 0 4 1 6 01 0 2 47 ：l 1 0 1 1 2 1 0 2 0 4 81 0 ：11 0 2 0 6 0 02 1 0 0 03 5 ：11 0 7 8 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周 河南大学研究生硕士学位论文第7 页 长的方程类似。一般情况下，椭圆曲线的曲线方程是以下形式的三次方程： y 2 + 咧+ b y = x 3 + 掰2 + 出+ p ( 2 1 ) 其中a , b ，c ，d ，e 是满足某些简单条件的实数。定义中包括一个称为无穷远点的元素， 记为d 。图2 1 是椭圆曲线y 2 = x 3 一x 的一个例子。椭圆曲线被描述为一个二元方 程解的集合。模p 定义的椭圆曲线在公钥密码中非常重要。椭圆曲线分别可以定 义在实数上、模素数上。首先来看一下定义在实数上的椭圆曲线。 | | 。形 厂久叉 k 。 图2 - 1 椭圆曲线的例子 2 1 1 椭圆曲线的分类 一、实数上的椭圆曲线 定义2 1 设a ，b e r 是满足4 口2 + 2 7 b 3 0 的实数。方程y 2 = x 3 + 烈+ 6 的所 有解( x ，y ) e r r 的集合e ，加上一个无穷远点0 ，组成了一个非奇异椭圆曲线。 可以证明，条件4 口2 + 2 7 b 3 0 是保证方程y 2 = x 3 + 缎+ 6 有三个不同解( 实数 或复数) 的充要条件。如果4 口2 + 2 7 b 3 = 0 ，则对应的椭圆曲线称为奇异椭圆曲线。 假设e 是一个非奇异椭圆曲线。我们在e 上定义一个二元运算，使其成为一 个阿贝尔群。这个二元运算通常用加法表示。无穷点d 将是单位元。因此有 p + o = o + p = p ，对于所有p e 。 假设p , q e ，其中p - - - ( x 。，y ，) ，q ：电：，y ：) 。我们分三种类型进行讨论： 1 x 1 x 2 2 x l = x 2 ，且y 1 y 2 3 x 1 = x 2 ，且y l = y 2 类型1 定义l 是通过p 和q 的直线。l 交于p 和q ，容易看书，l 还交e 第8 页河南大学研究生硕士学位论文 于第三点，记作r 。对x 轴反射r ，得到一点r 。定义p + q = r 。我们给出一个计 算r 的代数公式。首先，使方程l 为y = 缸+ u ，其中l 的斜率是： 五= 2 - y 1 ) 0 2 - - x 1 ) ，并且f = y l 一缸l = y 2 一触2 ，为了算出e f il 中的点，将 y = 2 x + f 代入到e 的方程中，得到( 触+ 功2 = x 3 + a x + 6 等价于： x 3 一, t 2 x 2 + ( 口一2 2 0 ) x + 6 一d 2 = 0( 2 2 ) 公式2 2 的根是enl 中点的x 坐标，我们已经知道enl 中的两个点，即p 和q ，因此x l 和x ，是公式2 2 的两个根。 公式2 2 的实数域上的三次方程，具有两个实根，那么第三个根也应该是实根， 记为x 3 。三根之和是二次项系数牙的相反数。所以x 3 = 牙- - x ，- - x 2 ，x 3 是点r 。的 x 坐标。r 的y 坐标记作一y ，则r 的y 坐标就是y ，。求儿的一个简单的办法是 利用l 的斜率是由l 上的两点确定这个事实。有点( x 1y 。) 和( x 3 ，一y 3 ) 计算这个斜 率，得n - 五= ( - y 3 - y 1 ) ( x 3 - - x ! ) ，即y 3 = 名( 茗l - x 3 ) - y l 。 所以对类型l ，我们到出p + q 的一个计算公式：如果x ，x ：，那么 ( x 1y 1 ) + ( x 2 ，y 2 ) = ( z 3 ，y 3 ) ，其中：x 3 = 名- - x 1 - - x 2 ，x 3 ；y 3 = 五( x l - - x 3 ) - y l ； 允= ( y 2 一j ，1 ) ( x 2 一墨) 。 类型2 当x l = x 2 ，y _ y2 时，我们定义( x ，y ) + ( x ，一y ) = o ，( x ，y ) e 。因此， ( x ，y ) 和( x ，y ) 是关于椭圆曲线加法运算互逆的。 类型3 我们要把一个点p = ( x 1 ，y ，) 与自己相加。假设y 0 ，否则就是类型2 。 类型3 与类型1 非常类似，只是我们定义l 是e 在p 点的切线。运用微积分的知 识可以使计算简单一些。计算l 的斜率要利用对e 的方程隐微分： 2 鲁如2 + 口 把2 3 式中进行替换，x ； ，y = y l ，得到切线的斜率为：五= ( 3 彳+ a ) ( 2 y 1 ) 。 余下的分析与情形1 完全相同。得到的公式也是一样的，只是斜率的计算不 同。 诚如上述定义所示，加法运算的下列性质应该是明确的： 1 加法在集合e 上是封闭的。 2 加法的可交换的。 3 0 是加法的单位元。 河南大学研究生硕士学位论文第9 页 4 e 上每个点有关于加法的逆元。 要证明( e ，+ ) 是阿贝尔群，还须证明加法的结合的。用代数方法证明这一点比 较繁杂。利用一些几何结果可以使证明得到简化；但是，我们不在这里讨论这个 证明。 二、模素数的椭圆曲线 设p 3 是素数。z 。上的椭圆曲线可以与实数上的一样定义( 加法定义的方式 也相同) ，之是r 上的运算用z 。中的类似运算代替。 定义2 2 p 3 是素数。z 口上的同余方程y 2 = x 3 + a x + b ( m o d p ) 的所有解( x ， y ) z p z p ，连同一个特殊的点o 即无穷远点，共同构成z ，上的椭圆曲线 y 2 = x 3 + a x + 6 ，其中a ，b ez 。是满足4 口2 + 2 7 b 3 0 的常量。 e 上的加法定义如下( 这里的所有运算都在z 。中) ：假设p = ( ，y 。) 以及 q = ( x 2 ，y 2 ) 是e 上的点。如果x 1 = x 2 且奶= - y l ，则p + q = o ；否则h q = ( x 3 ，y 3 ) ， 其中x 3 = 磐一毛一x 2 ；y 3 = 旯( - - x 3 ) - y l ；且当p * q 时，a = ( x 2 - - x 1 ) ( y 2 一y 1 ) ； 当p = q 时，名= ( 3 x ? + a ) ( 2 y 1 ) ；最后，对于所有的p e ，定义p + o = o + p = p 。 注意，z 。上的椭圆曲线没有实数上椭圆曲线的直观的几何解释。然而，同样 的公式可以用来定义加法运算，( e ，+ ) 仍然是一个阿贝尔群。 2 1 2 椭圆曲线的性质 定义在z 。q 是素数，p 3 ) 上的椭圆曲线，e 大致有p 个元素。更精确地，有 一个由h a s s e 提出的著名定理断言，e 上的点数如果记做撑e ，那么它满足下面的不 等式：p + l 一2 p 撑e p + l + 2 p 。 计算群e 的准确值较为困难，但有一个有效的算法计算它，这个算法由s c h o o f 发现( 这里“有效的意思是，算法的运行时间是】0 9p 的多项式。s c h o o f 的算法运行 时间为0 ( ( 1 0 9p ) 8 ) 多个位运算，即d ( ( 】0 9p ) 6 ) 多个z p 中域运算) 。对于数百位的素 数p 来说，这个算法比较实用。 如果可以计算拌e ，进一步要找到e 的一个循环子群，在其中离散对数问题是 难解的。所以要对群e 的结构有所了解。下属定理给出了有关e 的结构的许多信 息。 定理2 1e 是定义在z p 上的一个椭圆曲线，其中p 是素数，p 3 。则存在正 第1 0 页河南大学研究生硕士学位论文 整数n 1 和n 2 ，使得( e ，+ ) 同构于z lx z 。：，并且有n 2i n l 和n ：l q - 1 ) 。 注意，在上述定理中n ，- - 1 是可能的。事实上，当且仅当e 是循环群时，n ，= l 。 还有，如果耀或者是一个素数，或者是两个不同素数的乘积，e 也必定是循环群。 无论如何，一旦整数n ，和n ：算定，我们就知道e 具有一个循环子群同构于 z 。，这意味着它可以用于e 1 g a m a l 密码体制的情形。 2 1 3 椭圆曲线上的密码 我们要是使用椭圆曲线构造密码体制，必须要找出椭圆曲线上的数学困难问 题。在椭圆曲线构成的a b e l 群e p ( 砧b ) 考虑方程其中p q e p ( 毛b ) ，k p ， 则由k 和p 易求q ，但由p 和q 求k 则是困难的，这就是椭圆曲线上的离散对数 的问题，可应用于公钥密码体制。d i f f i e h e l l m a n 密钥交换和e 1 g a m a l 密码体制是 基于有限域上离散对数问题的公钥体制，下面分别讲述用椭圆曲线来实现 d i f f i e h e l l m a n 密钥交换和e 1 g a m a l 密码体制。 1 d i 伍e h e l l m a n 密钥交换 首先取一素数p 2 瑚和两个参数a ， b ，则得方程 y2 - - - - x3 + a x + b ( 毛b g f ( p ) ，4 a 3 + 2 7 b 2 0 ) 表达的椭圆曲线及其上面的点构成的a b e l 群e ，( 如b ) 。第2 步，取e ，( 柚) 的一个生成元g ( x ，y 1 ) ，要求g 的阶是一个非常 大的素数，g 的阶是满足n g = - o 的最小正整数n 。e ，( 如b ) 和g 作为公开参数。 两用户a 和b 之间的密钥交换如下进行： a 选一小于n 的整数, 月，作为秘密钥，并由只= 刀爿g 产生e p 瓴b ) 上的一 点作为公开钥： b 类似地选取自己的秘密钥和公开钥； a ，b 分别由k = n a p b 和k = 只产生出双方共享的秘密钥。 这是因为k 2 h b = n a ( n b g ) = n b ( n g ) = 只。 攻击者若想获取k ，则必须由只和g 求出1 2 a ，或由b 和g 求出肌，即需要求 出椭圆曲线上的离散对数，因此是不可行的。 2 e i g a m a l 密码体制 ( 1 ) e 1 g a m a l 密码体制的原理 河南大学研究生硕士学位论文第页 密钥产生过程：首先选择一素数p 以及两个小于p 的随机数g 和x ，计算 y 毫g m o d p 。以( y ，g ，p ) 作为公开密钥，x 作为秘密密钥。 加密过程：设需要加密的明文消息m ，随机选一个与p 1 互素的整数k ，计算 c l 毫g 。m o d p ，c 2 兰y k m m o d p ，密文为c = ( c 1 ，c 2 ) 解密过程：m = 寻m o d p 乙l 这是因为百c 2m o d p = y k f mm o d p = 了y k 厂m m o d p = m m o d p 。 ( 2 ) 利用椭圆曲线实现e 1 g a m a l 密码体制 首先选取一条椭圆曲线，并得e ，( 咖) ，将明文消息m 嵌入到曲线上得点匕， 在对点己做加密变换。 取e p 瓴b ) 的一个生成元g ，ep 伍b ) 和g 作为公开参数。 用户a 选n 。作为秘密钥，并以只= r a g 作为公开钥。任一用户b 若想向a 发送消息只，可选取一随机正整数k ，产生以下点作为密文： c 。= k g ，己+ 蛾) a 解密时，以密文点中的第2 个点减去用自己的秘密钥与第1 个点的倍乘， 即：己+ 厄巴- - i k g = 己+ k ( n _ g ) - r 彳k g = 己。 攻击者若想由c 。得到己，就必须知道k 。而要得到k ，只有通过椭圆曲线上 的两个已知g 和k g ，这意味着必须求椭圆曲线上的离散对数，因此不可行。 2 2h a s h 函数 密码学上的h a s h 函数能保障数据的完整性。h a s h 函数通常用来构造数据的短 “指纹；一旦数据改变，指纹就不再正确。即使数据被存储在不安全的地方，通 过重新计算数据的指纹并验证指纹是否改变，就能够检测数据的完整性。 设h 是一个h a s h 函数，x 是数据。作为一个直观的例子，不妨设x 是任意长 度的二元串，相应的指纹定义为y = h ( x ) 。通常指纹也被称为消息摘要( m e s s a g e d i g e s t ) 。一个典型的消息摘要是相当短的二元串，通常是1 6 0 比特。 我们假设y 被存储在一个安全的地方，而对x 没有这个要求。如果x 改变为x ， 则我们希望“旧 的消息摘要y 并不是x 的摘要。如果真是这样的话，则通过计 第12 页河南大学研究生硕士学位论文 算消息摘要y - h ( x ) 并验证y y 就很容易发现x 被改变这个事实。 上面所讨论的例子假定存在一个单一固定的h a s h 函数，这也有助于研究带密 钥的h a s h 函数族。一个带密钥的h a s h 函数通常用来作为消息认证码，即m a c 。 假定a l i c e 和b o b 共享密钥k ，该密钥确定了以个h a s h 函数h 。，对于消息x ，a l i c e 和b o b 都能够计算出相应的认证标签y = h k ( x ) 。二元组( x ，y ) 可以在不安全信道上 从a l i c e 传送给b o b 。当b o b 接收到( x ，y ) 后，他能够验证是否有y = 魂( 力。如果这 个条件满足并且所用到的h a s h 族是“安全的，那么他就可以确信x 和y 都没有 被篡改。 注意，由不带密钥的h a s h 函数和带密钥的h a s h 函数各自提供的数据完整性 保证是有区别的。用不带密钥的h a s h 函数时，消息摘要必须被安全地存放，不能 被篡改。另一方面，如果a l i c e 和b o b 用密钥k 来确定所用到的h a s h 函数，他们 可以在不安全的信道中同时传送数据和认证标签。 密码学上的h a s h 函数是一种将任意长度的消息压缩到某一固定长度的消息摘 要( m e s s a g ed i g e s t ) 的函数。 h a s h 函数经常用于签名方案中，以提高签名方案的安全性和速度。当然，h a s h 函数也广泛地应用于其他方面，如消息的完整性检测、消息的起源认证检测等。 定义2 3 原像稳固给定一个h a s h 函数h 和消息摘要y ，如果不能找到一个x 使得h ( x ) = y ，则称该h a s h 函数是原像稳 ( p r e i m a g er e s i s t a n t ) 的或单向( o n e - w a y ) 的。 定义2 4 第二原像稳固给定一个h a s h 函数h 和消息x ，不能找到一个x x ， 使得h ( x 。) = h ( x ) ，则称该h a s h 函数是第二原像稳 司( s e c o n dp r e i m a g er e s i s t a n t ) 的。 定义2 5 碰撞稳固给定一个h a s h 函数h ，如果不能找到两个消息x 和z ，且 x x ，使得h ( x ) = 办( x ) ，则称该h a s h 函数是碰撞稳固( c o l l i s i o nr e s i s t a n t ) 的。 从理论上讲，如果一个h a s h 函数满足了碰撞稳固、第二原像稳固和原像稳固 的话，这个h a s h 函数就被认为是安全的。 2 2 1h a s h 函数的分类 根据h a s h 函数的安全水平将h a s h 函数分为两类：一类是强碰撞自由的h a s h 函数( s t r o n gc o l l i s i o n - f r e eh a s hf u n c t i o n ) ；另一类是弱碰撞自由的h a s h 函数( w e a k 河南大学研究生硕士学位论文第1 3 页 c o l l i s i o n - f i c ch a s hf u n c t i o n ) 。 一个强碰撞自由的h a s h 函数是满足下列条件的一个函数h ： ( 1 ) 的输入可以是任意长度的任何消息或文件m ； ( 2 ) 乃的输出的长度是固定的( 该长度必须足够长，以抵抗生日攻击) ； ( 3 ) 给定h 和m ，计算h ( m ) 是容易的： ( 4 ) 给定h 的描述，找两个不同的消息m l 和m 2 ，使h ( m 1 ) = h ( m 2 ) 是计算上不 可行的( 如果有两个消息m l ，m2 ，m ，m 2 ，使得h ( m 1 ) = h ( m 2 ) ，我们就说这 两个消息是碰撞消息或这两个消息碰撞) 。 一个强碰撞自由的h a s h 函数暗含着单向性【1 3 】，所以强碰撞自由的h a s h 函数 又称强单向h a s h 函数。 一个弱碰撞自由的h a s h 函数与一个强碰撞自由的h a s h 函数的前三个条件 ( 1 ) - ( 3 ) 完全一样，不同的只是第( 4 ) 个条件。在一个弱碰撞自由的h a s h 函数中，( 4 ) 给定h 的描述和一个随机选择的消息m l ，找另一个消息m 2 ，m l m 2 ，使得 h ( m 1 ) = h ( m 2 ) 是计算上不可行的。 显然，强碰撞自由的h a s h 函数要比弱碰撞自由的h a s h 函数的安全性强。一个 弱碰撞自由的h a s h 函数不能保证找不到一对消息m ，m ，m m ，使得 h ( m 。) = h ( m ：) 。这说明也许有消息m l ，m2 ，m 1 m 2 ，使得h ( m 1 ) = h ( m 2 ) 。