（计算机应用技术专业论文）椭圆曲线密码体制及其应用研究.pdf

椭圆曲线密码体制及其应用研究 摘要 自1 9 7 6 年d i f f l e - h e l l m a n 提出公开密钥密码体制的思想以来，先后陆续 出现多种公钥密码体制。其中，椭圆曲线公钥体制以其理论上的高度安全，兼 有存储效率，通信带宽等方面的诸多优势，越来越受到关注，并具有广泛的应 用前景。 本文的主要研究工作包括： ( 1 ) 对椭圆曲线加密中点的嵌入方法进行讨论，并选择了适合的方案；对椭 圆曲线加密和签名过程中对效率影响最大的单点乘及多点乘的优化进行了分析 和探讨。 ( 2 ) 对椭圆曲线数字签名引入前向安全的思想，提出了基于二次剩余的前向 安全的椭圆曲线数字签名方案。 ( 3 ) 分析了各种电子邮件协议的特点，利用椭圆曲线数字签名和加密及a e s 加密算法，提出一个安全电子邮件协议s m a i l 。该协议能实现邮件的保密传输 和收发双方不可抵赖，并可抵御对邮件的各种攻击。最后，利用v i s u a lc + + 6 0 在2 2 4 位素数域上完整实现了该协议。 关键词：公钥密码体制，椭圆曲线，数字签名，前向安全 r e s e a r c ho nt h ee l l i p t i cc u r v e c r y p t o g r a p h y a n di t s a p p l i c a t i o n a b s t r a c t s i n c et h ei d e ao fp u b l i c - k e y c r y p t o g r a p h yw a sp u tf o r w a r db yd i f f l e h e l l m a ni n19 7 6 ，m a n yt y p e so fp u b l i c k e yc r y p t o g r a p h yh a v eb e e nr a i s e df r o m t h e no n a m o n gt h e m ，t h ee l l i p t i cc u l w ec r y p t o g r a p h yi sb e i n gt a k e ni nm o r ea n d m o r ea c c o u n ta n dw i l lb em o r ew i d e l yu s e di nt h ef u t u r ed u et oi t sh i g hs e c u r i t yi n t h e o r ya n di t sa d v a n t a g e si ng o o dp e r f o r m a n c ei ns t o r a g ea n dl i t t l en e e d si n c o m m u n i c a t i o n i nt h i st h e s i s ，o n rm a i nw o r ki sa sf o l l o w s ： ( 1 ) d i s c u s st h em e t h o di nc o n v e r t i n gd a t at ot h ep o i n t so nt h ee l l i p t i cc u r v e a n ds e l e c tap r o p e r s c h e m e a n a l y s ea n dd i s c u s st h eo p t i m i z a t i o no f p o i n t m u l t i p l i c a t i o na n di t sa d d i t i o nw h i c hh a sg r e a t e s ti n f l u e n c et ot h ep e r f o r m a n c e d u r i n ge n c r y p t i o na n ds i g n a t u r ew i t he l l i p t i ec u r v e s ( 2 ) b r i n gt h ei d e ao ff o r w a r ds e c u r i t yt oe l l i p t i cc u r v es i g n a t u r e ，a n dr a i s e f o r w a r ds e c u r es c h e m e sf o re l l i p t i cc u r v es i g n a t u r eb a s e do nt h es q u a r er e m a i n t h e o r y ( 3 ) a f t e ra n a l y z i n gt h ec h a r a c t e r i s t i c so fm a n yt y p e so fe m a i lp r o t o c o ，w ep u t f o r w a r das e c u r ep r o t o c o ls m a i lf o re m a i ls y s t e mb a s e do nt h ee l l i p t i cc a r v e d i g i t a ls i g n a t u r ea n de n c r y p t i o na n dt h ea e se n c r y p ta l g o r i t h m i na d d i t i o nt o i m p l e m e n t i n gt h es e c u r et r a s i t i o nf o re m a i la n dt h ei r r e p u d i a t i o nf o rb o t ht h e s e n d e ra n dr e c e i v e r ，t h ep r o t o c o lc a l lr e s i s t m a n yk i n d so fa t t a c kt oe m a i l s y s t e m i nt h ee n d , t h ep r o t o c o lh a v eb e e nf u l l yi m p l e m e n t e do nt h e2 2 4b i t s p r i m i t i v ef i e l dw i t hv i s u a lc + + 6 0 k e y w o r d s ：p u b l i c k e yc r y p t o g r a p h y ，e l l i p t i cc u r v e ，d i s t a ls i g n a t u r e ，f o r w a r d s e c u r i t y 插图清单 图2 1s h a n n o n 保密通信系统模型5 图2 2r s a ，d s a ，e c c 的安全性比较1 3 图3 1椭圆曲线几何示意图1 5 图5 1s m a i l 协议3 7 图5 2t c 端主界面4 l 图5 3t c 端保存的邮件信息界面4 2 图5 4客户端主界面4 3 图5 5 客户端增加帐号界面4 4 图5 6客户端上传下载公钥界面4 4 图5 7 客户端收发邮件界面4 5 图5 8 客户端已发送邮件信息界面4 6 图5 9 客户端已接收邮件信息界面4 7 表2 表2 表4 表4 表格清单 各种公钥密码体制密钥长度的比较1 2 几种体制下的签名长度和加密消息长度1 3 椭圆曲线y 2 = x 3 + a x + b 的点加和倍点的运算量2 7 各种方法计算n p 和n p + m q 所需时间3 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得盒胆王些盍堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签字：脚字日期岬年弓月 角 学位论文版权使用授权书 本学位论文作者完全了解盒胆王些盔堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金日b 互些盘 堂一可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存，汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名 匕瓠愀 导师签名 签字日期：6 年3 月；。日 签字日期 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话 邮编 致谢 衷心感谢我的导师侯整风教授。几年来，不论是在学习上还是在生活 上侯老师都给了我极大的关心和帮助。侯老师在学术上的严谨踏实的作 风，敏锐的洞察力和认真负责的精神，更给我留下了很深刻的印象。 本论文是在侯老师的悉心指导下完成的。在论文的撰写过程中，侯老 师提出了很多重要的指导性的意见，并对文稿进行了悉心的审阅。没有他 的帮助和提携，就不会有这篇文章。在此谨向侯老师表示最真诚的感谢! 衷心感谢计算机学院和合肥工业大学研究生部的各位老师们默默的 付出和辛勤的奉献! 读研期间，我的家人在生活上和精神上给了我巨大的支持。无论我成 功与否，他们都始终如一地帮助我，从来没有任何埋怨。我只有以加倍的 努力来回报他们对我的期望。 感谢陈刚，林雅榕，陈海兵同学，他们在学习上也给了我巨大的帮助。 最后要衷心感谢的是各位评审委员，你们于百忙之中抽出时间，评阅 我的论文，并提出了有益的建议，也是我极大的荣幸。 再次真诚感谢所有给我以关心和帮助的人们! 作者：张朝培 2 0 0 7 年月日 第一章绪论 1 1概述 随着计算机的普及与使用，网络技术广泛应用于政府，军事，文教，商业， 金融，和日常生活等诸多领域，成为促进社会发展的强大动力并深刻地影响着 人们的工作生活各个方面。特别是最近几年，由于i n t e r n e t 的迅猛发展，网络 以其无与伦比的高效率和无比丰富的信息资源，给人们提供了一种全新的交流 和获取信息的手段。电子邮件，即时通讯工具，电子商务，电子政务，网上银 行，网络会议等一系列新技术的出现和流行表明：网络以其无处不在的触角对人 们传统的交流和生产生活方式进行颠覆和革命。现在，越来越多的个人，商业 组织，研究机构和政府部门都利用和依赖i n t e r n e t 进行通信和研究工作，社会 的信息化程度也越来越高，社会对计算机和网络系统的依赖性也将越来越大。 在网络高速发展和广泛应用的同时，i n t e r n e t 的安全性越来越成为不能回 避的问题。一方面，由于网络分布的分散，网络体系结构的开放和各种信息资 源的共享，使得大量信息必须在各节点之间流动，而节点的软硬件配置也是各 种各样。这样，任何一点软件和硬件的漏洞和故障都将成为攻击的目标。实际 上，操作系统提供商如m i c r o s o f t 也在不断公布并弥补其软件的漏洞，但新的 漏洞又不断出现。而有的软件和硬件提供商为了某种目的，可能在出口的产品 中故意留下后门。如前几年，传出消息称i n t e l 在其c p u 中包含了一个全球唯 一的序列号，通过该序列号可以收集机器的一些信息。这类情形对网络信息的 安全危害更大。另一方面，由于用户的大量增加和对网络安全的深入研究，针 对脆弱的网络不断出现一些新的攻击方法。由于t c p i p 协议产生时没有考虑安 全的问题，所以在传输层和应用层存在一些漏洞。如针对t c p 连接时的“三次 握手”，现在在拒绝服务攻击( d o s ) 的基础上派生出了分布式拒绝服务攻击 ( d d o s ) 。应用层协议如s m t p ，p o p 3 ，f t p ，t e l n e t 等对用户身份认证，访问控 制和信息的保密等方面都没有深入的规定，很容易受到各种攻击。 黑客们利用网络系统中的各种漏洞和使用者的低水平，或窃取机密信息， 或篡改，伪造，泄露信息，或侵入，瘫痪政府，军队，金融等重要部门的服务 器。近年以来，攻击政府网络系统，q q 号和网络游戏装备被盗，电子邮件被非 法窃取，虚假网上银行窃取帐号和密码等事件时有发生，已经对社会的安定， 国家的安全产生了不良的影响。也因为对网络安全的顾虑，人们对电子商务的 应用持谨慎的态度，电子商务业务也远没有达到传统商业的规模和影响力。 因此，如何保证机密信息在网络上安全传输，也是网络安全领域需要解决 的问题，也是涉及到网络能否更进一步发展和广泛应用的问题。 对计算机和网络系统的安全威胁各式各样，概括起来主要有以下几类： ( 1 ) 窃密和破坏。系统内部人员有意或无意泄密，更改信息，更改网络配 置，或直接破坏系统软硬件。 ( 2 ) 非法访问。非法用户侵入系统或者合法用户以未授权的方式进行操作。 ( 3 ) 截获信息。通过搭线或安装截收装置等方式，截获重要信息如密码， 帐号等。 ( 4 ) 破坏信息的完整性。攻击者可能篡改信息的内容和形式；删除某个信 息或信息的某部分；在消息中插入一些信息。这些都使信息接收者对 原始信息误解。 ( 5 ) 冒充。攻击者欺骗合法用户或主机，获得非法利益。 ( 6 ) 重放。攻击者截获信息，然后在必要的时候重新发送这些信息以扰乱 或欺骗接收者。 ( 7 ) 抵赖。发信者否认曾发送过某条信息或信息的内容，接收者否认接收 过某条信息或否认消息的内容。 针对上述威胁，目前各方通常综合采用加密和数字签名技术作为确保网络 安全的手段。 加密的目的就是防止信息的非授权访问，它是实现信息安全的核心技术。 一般地，加密总是采取某种算法对信息进行变换，攻击者即使截获经过加密的 信息，如没有私钥也无法获得真实内容。当前的加密算法分为公钥体制，私钥 体制和混合密码体制三种。 数字签名是实现信息安全的另一核心技术，可以用来保证信息的完整性， 准确性和数据来源的可靠性。日常生活中存取款项，收发信件，商业领域内的 签定合同和契约，以至国家之间签署的外交文件，这些场合往往都需要签名， 这类签名以手工签名为主。签名者通过签名来表明对相应条款的认可与承认， 并承担相应的义务。因而，签名必须具有可信的，不可伪造，不可篡改，签名 者不能抵赖，不可重复的特点【l j 。 数字签名是对手工签名的模拟，包括生成签名和验证签名两个过程。生成 签名时，发送方先通过单向散列函数对要签名的消息产生唯一的，不可伪造的 散列值，再利用公钥密码技术和私钥对散列值进行变换得到签名。验证签名时， 接收方先计算出消息的散列值，再使用发送方的公钥对签名和散列值进行验证 运算，确认消息是否来自发送方。 从数字签名的过程可以看到，因接收方没有发送方的私钥，从而不能伪造 发送方的签名；如消息或签名被篡改，则接收方验证时可以发现；如接收方或 第三方用发送方的公钥验证签名通过，则发送方不能否认该消息和签名。同时， 与手工签名相比，而安全的数字签名方案将使伪造签名的可能性降低为零。因 此，在电子商务，电子银行，电子政务等应用领域，数字签名的使用极为广泛， 选择合适的数字签名方案方案成为保证系统安全的关键。 公钥密码体制是数字签名技术的理论基础，其思想起源于d i f f l e 和 h e l l m a n 的论文“密码学的新方向”1 2 j 。因此，数字签名方案的安全性和效率 2 往往取决于它所采用的公钥密码体制。当前安全有效的公钥密码体制主要有 r s a 体制，e i g a m a l 体制和e c c ( 椭圆曲线加密体制) 体制，其中e c c 成为当前研 究的一个热点领域。与r s a ，e i g a m a l 相比较，在私钥长度相等的条件下，e c c 的安全性更好，实现效率更高。一般地，1 6 0 位私钥的e c c 就可以与1 0 2 4 位的 r s a 安全性相当。因而，基于椭圆曲线的数字签名e c d s a 也比r s a 签名和e i g a m a l 签名及其变体更有优越性，特别适合于一些资源受限制而安全性要求较高的场 合，如无限通信，智能卡等。 目前，国外对e c c 的应用都取得了不少成果，其中最突出的是加拿大的几 位学者开设的c e r t i c o m 公司。c e r t i c o m 已经开发出在商业领域内高效，安全 实现e c c 技术的方法，并推出一系列的安全产品。从1 9 9 7 年开始，数百家全球 性大公司和美国政府都采用了c e r t i c o m 的e c c 技术。相比之下，国内对e c c 基本上仅限于理论研究，但实用信息安全产品大多数是基于r s a 公钥体制的， 利用e c c 体制的很少。因此，对e c c 体制和基于e c c 的数字签名进行深入研究 具有很重要的理论和应用前景。 在i n t e r n e t 所提供的各种服务中，电子邮件是最早最广泛的服务之一。近 年来，随着i n t e r n e t 的发展，电子邮件也以惊人的速度发展，同时也衍生出了 一些新的功能，如邮购，下定单等。这样，电子邮件系统的安全成了一个日益 突出的问题，并引起人们极大的关注。现实生活中，也经常生现邮件内容泄密， 冒充收件人或发件人，发件人否认发过某邮件，收件人否认收到某邮件等问题。 这些安全问题已经对人们的生活和工作造成严重的影响，因此人们提出了一些 改进电子邮件安全性的协议，目前广泛使用的有p g p ，s m i m e 和p e m 三种。这三 种协议都利用了加密和数字签名技术，能够实现电子邮件的机密性和发件方不 可抵赖，但收件方阅读过邮件后，则完全可以否认收到过邮件。这就限制了电 子邮件在贸易和商务中的使用范围，使它们不能替代纸质的合同文本。 本文的研究目的就是以椭圆曲线密码体制为基础，提出一个安全电子邮件 协议。该协议运用对称加密及椭圆曲线加密和数字签名技术，不仅可实现电子 邮件的机密性和发件方不可抵赖，而且收件方也不可抵赖。最后，以所提出的 协议为基础实现了一个原型系统，其运行结果也验证了协议的可行性和有效性。 i 2 论文的组织结构 本文共分为六部分： 第一章首先对论文要研究的问题进行简单介绍，并对本文内容进行安排。 第二章介绍计算机密码学基本理论，包括对称密码体制和公钥密码体制 中的r s a 体制和e l g a m a l 体制。 第三章介绍椭圆曲线公钥密码体制，包括椭圆曲线数字签名和加密方案， 提出了一个前向安全的椭圆曲线签名方案。 第四章分析椭圆曲线公钥密码体制实现中存在的问题，并对关键算法的 优化和坐标的选择进行研究。 第五章提出了一个基于椭圆曲线数字签名的安全电子邮件协议，文中详 细描述了协议的基本假设和步骤，并对安全性进行分析，说明该 协议满足预定要求；同时，对该协议实现了一个原型系统。 第六章对本文的协议中存在的不足进行总结，提出了今后深入研究的方 向。 4 第二章数据加密技术 自从人类有了战争，就有了密码，所以密码作为一种技术源远流长，但作 为一门学科则是近3 0 年的事，这是受计算机科学蓬勃发展的影响。今天在计算 机被广泛应用的信息时代，大量信息用数据形式存放在计算机系统中，信息的 传输则通过公共信道进行。这些计算机系统和公共信道是不设防的，是很脆弱 的，很容易受到攻击和破坏。尽管信息的丢失不容易被发现，但其后果极其严 重。如何保护信息的安全已不仅仅是军事合作政府部门感兴趣的问题，各企事 业单位也愈感迫切。而密码学相关技术则是有效而可行的保护信息安全的办法。 2 1密码学基础 密码学是信息安全的基础，其起源可以追溯到古罗马时代，但直到1 9 4 9 年s h a n n o n 在 上发表了一篇具有划时代意义的文章“保 密系统的通信理论”1 3 ，提出了通信系统模型，才标志着密码学研究开始走上 了科学的轨道。 图2 1s h a n n o n 保密通信系统模型 上图即为s h a n n o n 的保密通信系统模型。双方h l i c e 和b o b 共享一个密钥。 根据这个模型，设h l i c e 欲发送明文m ，则可通过变换e k 得密文c 即c = e k ( m ) ， 将c 通过公共信道发送给b o b 。这个过程称为加密，参数k 称为密钥。b o b 获得 密文c 后，利用k 和解密变换d k ，恢复出明文m = d k ( c ) ：d k ( e k ( m ) ) 。当然， 窃听者e v e 也可能通过公共信道获得该密文信息。但由于她不知h l i c e 和b o b 间的共享密钥，因而难以确知信道上所传送的明文信息。 通过这个模型，可以给出密码体制的基本概念。一个密码体制可以有如下 几个部分： ( 1 ) 所有可能的明文的集合p ，称为明文空间。 ( 2 ) 所有可能的密文的集合f ，称为密文空间。 ( 3 ) 所有可能的密钥的集合，称为密钥空间。 ( 4 ) 加密算法：e ：尸k _ c ，( m ，k ) i - - ) e k ( m ) ， 解密算法：d ：c k 斗p ，( c ，k ) 卜d k ( c ) ， 5 对v m 只k p ，有d k ( e k ( m ) ) = m ，则五元组( 尸，f ，f ，口) 称为一个密码体制。 通过s h a n n o n 模型可以看出，一个完整的保密通信系统是由一个密码体制， 一个收方，一个发方，和一个攻击者构成。一般地，对一个保密通信系统我们 都假设：对密钥空间所有的密钥，加解密算法迅速有效；密码体制的安全性不依 赖于加密算法的保密，只依赖于密钥的保密。这样，破译者可以掌握密码算法 的所有内容和细节，而系统的安全性完全依赖于密钥的保密。 根据加密密钥和解密密钥的关系，现代密码体制可分为对称密码体制和非 对称密码体制。前者称为传统密码体制，后者又称为公钥密码体制。 2 2传统密码体制 在传统密码体制中，任意一对通信实体共享一个密钥，加密密钥和解密密 钥相同。因此加密密钥和解密密钥都必须保密。这种密码体制又成为对称密码 体制。 以对称密码的典型代表d e s 为例，该密码算法由i b m 公司研制，并在1 9 7 7 年被美国国家标准局颁布为商用数据加密标准。自公布以来，它因为实现容易 和使用方便，一直超越国界成为保密通信和计算机通信的最常用的加密算法 4 1 1 5 】。d e s 的实际密钥长5 6 位，加密长度为6 4 位的明文，获得长度为6 4 位的 密文。 假设明文m 和私钥k 均为0 ，1 组成的长度为6 4 位的符号串，记做m = m l m 2 m 6 4 ，k = k l k 2 k 6 4 ，其中k 只有5 6 位有效，k s ，k 1 6 ，k 2 4 ，k 3 2 ，k 4 0 ，l 【4 8 ， k 5 6 ，k 6 4 是奇偶校验位，在算法中不起作用。 加密过程可以表示为； d e s ? r m = i p 。丁”r ”ro i p 伽 其中i p 和ip - l 是两个互逆的置换矩阵。t i 是迭代过程，每次迭代的输入是 上次迭代输出的6 4 位字符串和相应的子密钥k i ，将6 4 位分为左右各3 2 位， 计算： l i = l k l ，r i = k l o 研0 l ，k i x o 是按位作异或运算。) 为使算法同时用于加密和解密，在最后一轮迭代时左右两部分不交换。 迭代中数据与子密钥结合的函数f 是d e s 算法的关键，它包含算法中唯一 的非线性部件s 盒。子密钥的产生是利用6 4 位的初始私钥产生1 6 个4 8 位的子 密钥，在加密的过程中分别与每轮迭代的数据结合。 解密过程与加密过程相仿，唯一的区别在于子密钥的使用顺序相反。 d e s 设计的原则是混乱和扩散。混乱是指密钥和明文及密文之间的依赖关 系应该尽量复杂，以破坏分组间的统计规律，通常依靠多轮迭代和左右交换来 实现；扩散则应使密钥和明文的每一位影响密文中尽可能多的位数，这样可以 防止逐段破译，并通过s 盒中的非线性变换来实现。d e s 的这些设计原则对其 6 它对称密码算法也有很大影响。 因为密钥长度过短，随着硬件价格的下降和分布式计算的发展，使得穷举 d e s 密钥空间成为可能。特别是1 9 9 8 年5 月，美国电子边境基金会宣布，他们 已用价值2 0 万美元的计算机改装成专用设备，仅用5 6 小时就破译了d e s ，这 彻底宣布了d e s 的终结嘲。 除了d e s ，还有a e s ，i d e a ，r c 5 等一些对称密码算法，其特点同d e s 类似， 虽然在加密强度，效率和灵活性等方面有些改进，但在理论和技术上都没有根 本性的变化。 从总体上看，传统密码体制的优点是加解密速度快，保密强度高。但也有 一些严重的缺点：( 1 ) 密钥管理和分配问题。传统密码体制要求双方用相同的密 钥应通过秘密信道传输。在一个具有n 个实体的网络中，每个都必须保存其余 的n 一1 个实体的密钥，这就共需要n ( n - 1 ) 2 个密钥和同样数目的保密信道。 而当一个用户要加入到通信网络或一个用户要改变他的密钥时，1 3 或n 一1 个新 的密钥必须通过同样数目的信道进行传输。这样密钥的分配，传送，管理就非 常困难。( 2 ) 签名和认证问题。传统的私钥密码系统可对数据进行加解密处理， 提供数据的机密性，但因为由两个实体共享密钥，这样收方可以伪造原文，发 方也可以否认，从而在没有仲裁者的情况下不能直接提供认证和数字签名服务。 而在网络通信发展中，特别是电子商务，电子政务，电子银行的发展，认证和 签名的需求是必不可少的，这就限制了传统密码体制的应用范围。这些缺点促 使了密码研究人员寻找新的加密算法。 2 3 公钥密码体制 2 3 1 公钥密码体制的概念 公钥密码体制的思想起源于d i f f l e 和h e l l m a n 在1 9 7 6 年1 1 月发表的论文 “密码学新方向”。在公钥密码体制中，任何一个通信实体都有一对密钥，其 中一个公开发布作为加密密钥；一个为用户专用并且保密，作为解密密钥，通 信双方无需事先交换密钥就可以进行通信。系统的安全性完全依赖于解密的密 钥。 一般地，公钥密码加密算法总是基于一种特殊的单向陷门函数f ，该函数 都是建立在某个数学问题的难解性的基础上的。 设加密变换，解密变换，公钥和私钥分别为e ，d ，p k ，s k ，满足p k = f ( s k ) ， e ，d 都很容易计算，则由s k 很容易计算出p k ：而若不知道陷门信息，由p k 推出s k 或从密文分析出明文，在计算上是极其困难甚至是不可能的。在这种体 制下，任何人都可以用其他用户的公开密钥对数据进行加密，但是，只有拥有 解密密钥的用户才能对加密的数据解密。因此，即使知道了加密算法和加密密 钥也不会泄露解密密钥。 7 公钥密码系统加密，解密的一般过程如下：假设用户a 1 i c e 要向用户b o b 发送机密消息n l ，用户a 1 i c e 可以在公钥本上查到b o b 的公钥p k b ，用p k b 对消 息m 进行加密得到密文c = e p k b ( m ) ，将密文c 发送给b o b 。用户b o b 收到密文 后，用自己的解密私钥s k b 进行解密变换得到原来的消息 m = d s k b ( c ) 2d s k b ( e p k b ( m ) ) 可以看出，若其他用户以用户a 的公开密钥作为加密密钥，则加密的消息 只有用户a 可以解密；反之，若用户a 以秘密密钥对消息或消息的摘要加密， 则多个用户可以解密。前一种情况可用于保密通信，而后者则可用于数字签名 和身份认证。 2 3 2 公钥签名中的h a s h ( 散列) 函数 在数字签名中，如消息很短，则可直接对其签名；若消息很长，为了提高 效率则先利用一个函数从消息产生一固定长度的消息摘要，然后对消息摘要签 名，该函数称为h a s h 函数。 h a s h 函数实际上是从一个消息空间a 到另一个消息空间b 的一个映射h ， 并满足1 7 ： ( 1 ) 对v x a ，3 y e b ，使y = h ( x ) ，且a 中的元素为任意长度的0 ，l 符号 串，b 中元素是固定长度的0 ，l 串。 ( 2 ) y = h ( x ) 很容易计算，并具有雪崩效应，即消息x 改变一位，将导致y 的一半以上的位发生改变，从而表现出统计上的随机性。 ( 3 ) 已知y = h ( x ) ，求x 在计算上是不可能的，即映射h 在计算上不可逆。 因h a s h 函数是一个多对一的映射，所以，可能出现多个消息具有同样的 h a s h 值的情况，称为碰撞。一般地，h a s h 函数碰撞和相应的攻击可分为两类： ( a ) 对一给定的消息x 和签名s ，若攻击者可以找到消息x x ，满足h ( x ) = h ( x ) ，则s 也是对x 的可验证的签名，这类碰撞称为弱碰撞。 ( b ) 若攻击者找到两个消息x x ，满足h ( x ) = h ( x ) ，并从签名者得到x 的 合法签名s ，则s 也是对x 的可验证的签名，这类碰撞称为强碰撞。 为防止这两类对h a s h 函数的攻击，密码学意义上的安全h a s h 函数在前面 ( 1 ) ，( 2 ) ，( 3 ) 的基础上，还必须满足： ( 4 ) 弱无碰撞性，即对给定的消息x ，找到一个碰撞x x ，满足h ( x ) = h ( x ) ， 在计算上是不可能的。 ( 5 ) 强无碰撞性，即在消息空间a 中，寻找一对碰撞x ，x ，满足x x ， h ( x ) = h ( x ) ，在计算上是不可能的。 将h a s h 函数引入到数字签名中可以有如下优点：【8 l ( i ) 可以提高数字签名的速度。签名者对消息i n 签名时，先利用h a s h 函 产生m 的摘要h ( m ) ，再计算出签名s i g ( h ( m ) ) 。 8 ( i i ) 可以将签名公开，而不会泄露签名的消息。如对消息i n 的签名是 s i g m ( h ( m ) ) ，则可将签名和h ( m ) 公开，保密m 。 h a s h 函数在数字签名，身份认证等领域有着广泛的应用，其安全性和速度 对这些应用有着直接的影响，因此对h a s h 函数的构造和攻击的研究受到各方面 的高度重视。当前常用的h a s h 函数有s h a 系列和m d 4 ，m d 5 等。s h a 系列h a s h 函数 包括s h a 一1 ，s h a - 2 5 6 ，s h a - 3 8 4 ，s h a - 5 1 2 。s h a - 1 是由n i s t 颁布的与数字签名 标准d s s 相配套的h a s h 函数标准，接受长度小于2 6 4 位的消息，输出1 6 0 位的 h a s h 值，是一个强无碰撞的散列函数。s h a 一2 5 6 ，s h a 一3 8 4 ，s h a 一5 1 2 是s h a 一1 的后续版本，其区别在于初始常数，运算函数和输出长度，而基本运算步骤大 体上相同。 2 4目前几种典型的公开密钥系统 1 r s a 公钥体制 r s a 是由m i t 的r i v e s t ，s h a m i r 和a d l e m a n 于1 9 7 8 年提出的，它是第一 个成熟的，迄今为止理论上最成功的公钥密码系统。它的数学基础是数论中的 欧拉定理，安全性依赖于大整数分解的困难性【9 i 。 r s 算法的公钥，私钥产生过程如下： ( 1 ) 选取两个随机大素数p 和q ( 保密p ，q ) 。 ( 2 ) 计算n = p q ，和欧拉函数m ( n ) = ( p 1 ) ( q 1 ) ( 公开n ，保密m ( n ) ) 。 ( 3 ) 随机选取整数e ，使满足g c d ( e ，m ( n ) ) = 1 ，且o e 中( n ) ，e 即为加 密密钥( 公开e ) 。 ( 4 ) 计算d ，满足e d ；1 ( r o o dm ( n ) ) ，d 即为解密密钥( 保密d ) 。 利用r s a 加密第一步需对明文数字化，并将待加密的明文分块，使每块小 于n ，即块长为 1 ，n - 1 。若m 为明文块，c 为密文，则 加密算法为：c = e ( m ) em 。( m o dn ) ， 解密算法为：m = d ( c ) ；c 4 ( m o dn ) 若对消息m 签名，公钥参数同上，则计算 ( 1 ) h = h ( 珊) ，h 是h a s h 函数。 ( 2 ) 计算sih om o dn ，则签名为s 。 验证过程( 输入n ，e ，m ，s ) ： ( 1 ) 计算h = n ( m ) 。 ( 2 ) 计算h is 。m o dn ，若h = h ，则接受签名，否则拒绝签名。 从参数的产生可以看出，n ，e 组成公钥，而p ，q ，d ，o ( n ) 构成秘密陷门。 如果知道p ，则其余三项可立即求出，解密密钥d 和e 满足e d ；1 ( m o do ( n ) ) ， d 不难求出。 如果不知道o ( n ) ，由已知的加密密钥e ，很难求出解密密钥d 。如果获得 9 了m ( n ) ，则由 p q 2 1 1 ， p + q = n m ( r 1 ) + l 可知p ，q 是二次方程x 2 + ( o ( n ) 一n 1 ) x + h = 0 的根，可以求出p ，q 从而 将n 分解。所以r s a 公钥密码的安全性依赖于因子分解的困难性。 目前因子分解速度最快的方法，其时间复杂性为e x p ( s q r t ( 1 n ( n ) l n l n ( n ) ) ) 。在2 0 0 3 年，能分解的r s a 模n 已达到5 3 0 位二进制数( 1 6 0 位十进制数) 。 为保证r s a 应用的安全性，要采取以下措施： 由于因子分解的技术的不断进步和处理器运算速度的提高，必须不断增 加大素数的位数。 为抗击p + l ，p 一1 攻击，所选参数必须是强素数，即p - 1 有大素因子r ， p + l 有大素因子s ，且r 一1 有大素因子t 。这样的因子p ，q 可以极大地 提高r s a 体制的安全性。 r s a 的素数p ，q 的差必须很大，否则受到攻击。 解密密钥d 和加密密钥e 的规模不能过小。w i e n e r 证明了，若d 的长度 小于模n 长度的时，利用连分数可在多项式时间内计算出d 。若e 过 q 小，则可能使1 1 1 。 n ，这时c ；m 。m o dn ，使得m = 刈c 成为普通开 方，降低了系统的安全性。 因此在r s a 的应用过程中，必须选择合适的参数，并要提高大数模幂运算 速度。目前，一般认为r s a 需要模n 在1 0 2 4 位以上才是安全的，而对于安全性 要求很高的部门，则要求采用2 0 4 8 位。而且随着因子分解能力的提高，这个数 字还在不断刷新。这势必会对r s a 的应用造成很重的负担，从而使其应用范围 越来越受到制约。 2 离散对数公钥体制 第一个离散对数体制是d i f f l e 和h e l i m a n 于t 9 7 6 年提出的密钥交换协议。 1 9 8 4 年e 1 g a m a l 提出了基于离散对数的公钥密码体制方案：i l o l ( 1 ) 设p 是大素数，g 是z 。的一个生成元，每一个用户选定随机整数n 仨 1 ， p - 1 ，计算p = g4 m o dp 。保密a ，公开p 。 ( 2 ) 若用户a 传递信息m e o ，p - 1 给用户b ，则随机地选择正整数k 1 ， p 一1 ，并且计算y l = g 。m o dp 。 ( 3 ) 用户a 查找b 的公钥p ，计算y ：= ( m p 。) m o dp ，将( y 。，y ：) 发送给b ； ( 4 ) 用户b 计算m = y 2 * ( y t ) m o dp ，得到消息m 。 设公钥参数同上，消息为m ，则e 1 g a m a l 签名方案为： ( 1 ) 计算h = h ( m ) 。 ( 2 ) 随机整数k e 1 ，p - 2 ，且k 与p l 互素，计算r = g 。m o dp 。 1 0 ( 3 ) 计算s = ( h c t r ) k - 。m o dp - i ，则( r ，s ) 即为对m 的签名。 要验证签名，只要验证等式 r 8 = g “b 。m o dp 是否成立。 e i g a m a l 体制是在各类密码协议中有着大量应用的一类公钥密码体制，其 安全性是基于有限域离散对数问题的难解性。在上述体制中，已知求b 是容 易，而由p 求a 则很困难，这就是有限域上的离散对数问题。目前还没有找到 计算离散对数问题的多项式时间算法，求解该问题的最好算法是数域筛法，仍 具有亚指数的复杂度。为了抵御已知方法的攻击，p 至少应当是1 0 2 4 位二进制 整数，并且p - 1 至少有一个大素数因子。现实中，数字签名使用较多的是e i g a m a l 的变体d s a 签名，要求p 为5 1 2 到1 0 2 4 位的大素数，q 为1 6 0 位素数且是p 一1 的因子，g = h ( p 。1 ) 7 q m o dp ( 1 h p 一1 ) ，生成3 2 0 位的签名j 1 2 1 。 3 椭圆曲线公钥体制 椭圆曲线理论是一直作为纯理论学科被少数科学家掌握，自1 9 8 5 年， k o b l i t z 和m i l l e r 把椭圆曲线理论引入公钥密码理论以来，该领域已成为公钥 密码学的一个重要课题【1 3 1 【h 1 。利用椭圆曲线点群的离散对数问题( e c d l p ) 构成 公钥密码系统，引起人们极大的关注。本文在以下章节对此进行详细的讨论， 这里不再赘述。 2 5椭圆曲线公钥体制与其他公钥体制的安全性比较 从总体上看，构成公钥密码基础的困难问题有如下三类数学问题： ( 1 ) 整数的因子分解问题( i f p ) ，是r s a 公钥密码安全性的基础。 ( 2 ) 有限域乘法群上的离散对数问题( d l p ) ，是e i g a m a l 体制及其变体( 如数 字签名算法d s a ) 安全性的基础。 ( 3 ) 椭圆曲线点群上的离散对数问题( e c d l p ) ，是椭圆曲线公钥体制安全性 的基础。 在上述公钥体制中，由于椭圆曲线密码体制所依赖的e c d l p 问题比i f p ， d l p 困难得多，该密码体制的单位b i t 加密强度目前在所有的公钥体制中是最高 的。 若将椭圆曲线密码体制( e c c ) 与r s a ，d s a ( 数字签名标准，基于d l p r 3 题) 相 比较，则可看到e c c 有着一些突出的技术优点： 1 、安全性能更高 加密算法的安全性能一般通过该算法的抗攻击强度来反映。e c c 和其它公钥 系统相比，其抗攻击性具有绝对的优势。椭圆曲线离散对数问题的计算复杂度 是完全指数级的，而r s a 和e i g a m a l 均有亚指数算法。这体现为e c c 的每b i t 安全 强度更高。这在实际中也得到验证：截至2 0 0 3 年，可求解的r s a ，d l p 和e c d l p 问题的二进制位长度分别为5 3 0 ，3 9 7 和1 0 9 位。 2 、计算量小和处理速度快 在相同的计算资源条件下，虽然r s a 可以通过选取较小公钥( 显然会降低安 全性) 来提高加密和签名验证运算速度，使其效率略高于e c c ，但在解密和签名 方面，e c c 比r s a ，d s a 快得多。同时e c c 系统的密钥生成速度也比r s a 快得多。因 而，从总体上看，e c c 具有更好的性能。 3 、存储空间小 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 具有相同的安全强度，而2 2 4 位e c c 则与2 0 4 8 位r s a ，d s a 具有相同的 安全强度。这也意味着它所占的存储空间要小得多。 表2 1 是在同等安全的前提下，各种公钥密码体制密钥长度的对比。可以 看到，同等安全时，对称密钥长度要小于公钥密码体制的密钥长度，e c c 的密钥 长度小于r s a ，d s a 的密钥长度。 表2 1 各种公钥密码体制密钥长度的比较 对称密钥长度r s a d s a 密钥长度e c c 密钥长度r s a e c c 密钥长度比 5 35 1 21 0 65 ：l 6 67 6 8 1 3 26 ：l 8 0 1 ，0 2 4 1 6 0 7 ：l 1 1 2 2 ，0 4 8 2 2 4l o ：i 1 2 8 3 ，0 7 2 2 5 61 2 ：l 1 9 2 8 ，1 9 2 3 8 42 l ：l 2 5 6 1 5 ，3 6 0 5 1 23 0 ：l 图2 2 比较了r s a ，d s a ，e c c 的抗攻击性： 1 2 6 0 0 0 善5 0 0 0 却 髦4 咖 翻 3 q q o 2 0 0 0 1 0 0 0 破译时间( m i p sy e a r s ) 图2 2r s a ，d s a ，e c c 的安全性比较 4 、带宽要求低 当用于对长消息进行加解密时，e c c ，r s a ，d s a 三类密码系统有相同的带宽 要求，但应用于短消息时e c c 带宽要求要小得多。为具体比较，设待签名消息为 l o o b i t ，待加密消息为l o o b i t ，r s a 的模为1 0 2 4 位，e c c 的基点阶为1 6 0 位， 则e c c ，d s a ，r s a 的带宽要求如下： 表2 2 几种体制下的签名长度和加密消息长