（信号与信息处理专业论文）基于rsa和椭圆加密算法的数字签名.pdf

摘要 摘要 基于r s a 和椭圆加密算法的数字签名 硕士研究生：孙玉美导师：胡爱群教授 东南大学无线电工程系 本文从当今广泛关注的信息安全问题入手，分析了加密技术在信息安全中的重要应 用，论述了引起信息安全问题的主要因素，并研究了相应的防范措施。在这些措施中一 个重要的手段就是数据加密。加密技术在信息安全中起着重要的作用。本文介绍了加密 的基本概念和当今两种重要的加密体制。数字签名利用加密技术和公钥基础架构以保护 数据的真实性、完整性和受认可性，在电子政务和电子商务等领域得到广泛的应用。基 于椭圆曲线函数实现的数字签名机制利用椭圆曲线上的点构成的a b e l 加法群构造离散 对数问题实现，具有复杂性与d h 算法相同，运算速度快，易于实现等特点。本文着重 研究了r s a 签名算法和椭圆曲线加密算法的数学原理、实现方法和安全分析。对椭圆 曲线加密算法的各方面进行了分析和讨论。首先分析算法的加密原理，对于一个算法， 它的加密原理来自于与它相关的数学问题。如果相关的数学问题难解性越大，该加密算 法被破解的可能性就越小，即它的安全性取决于与它相关的数学问题的难解性。文中引 入了椭圆曲线数、离散对数等概念，来解释椭圆曲线离散对数问题，通过对椭圆加密算 法的复杂性和从破解角度对该算法的强度进行分析证明了椭圆曲线加密算法的安全性。 在此基础上针对椭圆曲线在有限域上的丰富性进行了理论证明，通过计算得到相关数 据。进一步研究了基于椭圆曲线加密算法的数字签名机制实现方案。分析表明，该签名 机制和r s a 、d s a 等签名机制相比，在安全强度、计算花费、密钥大小、通信带宽等 方面都有一定的优势，文中给出了详细的分析和比较。最后，本文论述了基于椭圆加密 算法的数字签名在电子现金体制中的应用。 关键词：椭圆曲线加密算法椭圆曲线离散对数问题数字签名椭圆曲线数字签名 a b s t r a c t a b s t r a c t i n j 、o m a t i o ns e c u r i t yi sb e c o r n j n gm o r ea n dm o r ei m p o r t a l l ta tp r e s e n t t h ee n c r y p t i o n t e c h n o i o g y ，o n eo fm em o s ti m p o r t a n tt e c m q u e so fs e c u r i 饥i sp i a y i n gav i t a i r o i ei n i n f o 订n a t i o ns e c u r i t yt h eb a s i cc o n c e p t i o no fm ee n c r y p t i o ni sd i s c u s s e d ，a n df u n h e rm o r e ， t h em o s tp o p u l a rm e c h a n i s m sh a v eb e e ni n t r o d u c e di nt 1 1 i sp 印e ld i g i t a ls i g n a t u r ew h i c h u t i l i z ee n c r y p t i o na n dp u b l i ck e yi r 出a s 咖c t l i r et op r o t e c tt h ea u t l l e n t i c i 吼i n t e g r a l i t ya 1 1 d a c c 印t a b i l i t yo f t h ed a t a ，i sw i d e l yu s e di nt h en e l d so fe g o v e m m e n ta n de c o m m e r c ee t c t h ed i g i t a ls i g n a t u r eb a s e do ne l l i p t i cc u r v ee n c r y p t i o na l g o r i t h mi sr e a l i z e db yu s 协gt 1 1 e a b e la d d i t i o n 目o u p sc o m p o s e db yt h ep o i m 行o me l l i p t i cc u r v et oc o n s t n l c tt 1 1 ed i s c r e t e l o g a r i t h mq u e s t i o n t m sm e c h a n i s mh a st l ec h a m 吼e r i s t i cs u c ha st h es a m ec o i n p l i c a t i o na s t h ed ha l g o r i t h m ，f a s to p e r a t i o ns p e e d ，s i m p l er e a l i z a t i o na n ds oo n t sp a p e ri sf o c u s e d o nd i s c u s s 恤gm em a 山e m a t c sp r 血c i p l e ，i m p l e m e n t a t i o nm e t h o da j l ds e c u r i t ya n a l y s i so fm e r s as i g n a t u r e a l g o r i t h m a n d e l l i p t i c c u r v e e n c r y p t i o na l g o r i m m t h e e 1 1 i p t i c c u r v e e n c r y p t i o na l g o r i t h mh a sb e e na t l a j i z e da n dd j s c u s s e dc a r e 血l l yf i s to fa 1 1 ，谢t lt h ea 1 1 a l y s i s o ft h ep r i n c i p l eo ft h ee l l i p t i cc u r v ee n c r y p t i o n ，i ti ss h o w e dt h a tt h ep r i n c i p l eo ft h e e n c r y p t i o na l g o r i t h mc o m e 丘o mt h e r e f e r e n c e dm a t h m a t i c sq u e s t i o n i ft h ec o m p l e x i t yo ft | l e m a m m a t c sq u e s t i o ni sh a r d e r ，t h ep o s s i b i l i t yo fm ee n c r y p t i o na l g o r i t l l mc r a c k i n gi sl o w e r t h a ti s ，t 1 es e c u “t yo ft h ee n c r y p t i o na l g o r i t h mi sc o r r e s p o n d i n gw i mt h ec o m p l e x i t yo ft 1 e m a t h m a t i c sq u e s t i o n t h ec o n c e p t i o n so ft 1 1 ee 1 1 i p t i cc u r v ea 1 1 dd i s c r e t el o g a r i t h mh a v eb e e n i n t r o d u c e di n t h i sp 印e rt oe x p la i nt h ed i s c r e t el o g a r i t h mq u e s t i o ni ne l l i p t i cc w v e t h e s e c 嘶t yo ft h ee 1 1 i p t i c c u r v ee n c r y p t i o n a l g o r i t 1 mh a sb e e np r o v e db ya j l a l i z i n gm e c o m p l e x i t yo ft h ea l g o r i t h ma j l dt h ei n t e n s i t yo ft 1 1 ea l g o r i t h mc r a c k i n g f l i r t h e rm o r e ，t h e a b u n d a n c eo f 1 ee l l i p t i cc u r v ei ng a l o i s 矗e l dh a sb e e np r o v e db ym e o 啊a n a l y s i sa n dt h e c o r r e s p o l l d i n gn u m b e r 1 a sb e e nf o u n d ad i g i t a ls i g n a t l 】r em e c h 狐s mb a s e do ne l l i p t i cc u n ，e e n c r y p t i o na l g o r i t h mh a sb e e np m p o s e d i ti ss h o w e dt h a t ，c o m p a r e d 诵t hr s a a n dd s a ，t h i s m e c h a n i s mh a sm ea d v a n t a g e si nt h es e c u r i t yl e v e l ，c o m p u t i n gc o n s u m p t i o n ，s i z eo fk e ya n d c o m m l m i c a t i o nb a n d w i d m f i n a l l y ，t l ea p p l i c a t i o ni np u b l i ck e yi 曲a s t r u c t u r ea n de c a s h m e c h a m s mw i t he l l i p t i cc u r v ee n c r y p t i o na l g o r i t m 1h a sb e e nd i s c u s s e d k e yw o r d s ：e 1 1 i p t i cc u r v ee n c r y p t i o na l g o r i t ，e l l i p t i cc u r v ed i s c r e t el o g a r i m mq u e s t i o n ， d i g i t a ls i g n a t u r e ，e l l i p t i cc u r 旷ed i g i t a js i g n a t u r e i 绪论 绪论 本文从信息安全入手，论述了引起信息安全问题的主要因素，并研究了相应的防范 措施。在这些措施中一个重要的手段就是数据加密。加密技术在信息安全中起着很重要 的作用。在第二章，介绍了加密的基本概念和当今两种重要的加密体制。 本论文主要目的是分析、选择一种适合的加密算法来实现数字签名。通过查找和学 习资料，初步确定选用椭圆曲线加密算法。为了判断这种算法是否适合用于数字签名， 本文对该算法的各方面进行了分析和讨论。首先分析算法的加密原理，对于一个算法， 它的加密原理来自于与它相关的数学问题。如果相关的数学问题难解性越大，该加密算 法被破解的可能性就越小，即它的安全性取决于与它相关的数学问题的难解性。椭圆曲 线加密算法是建立在椭圆离散对数问题上的，因此从第四章引入了椭圆曲线数、离散对 数等概念，目的是为了解释椭圆曲线离散对数问题。在第四章的后半部分，对该算法的 复杂性进行了分析，并从破解的角度对该算法的强度进行了分析。在查阅资料时发现， 许多论文中提到椭圆曲线在有限域上的丰富性，但并没有给出具体的数字，因此论文对 这个问题作了具体的计算，并在6 2 1 节中给出了具体的数字，证明了它的丰富性。同 时，论文还将椭圆曲线加密算法同其他几种较为流行的加密算法进行了对比，分别从密 钥大小、加密后的密文大小及破解时间等几方面进行了比较，有力地证明了该算法在安 全性及密钥大小上具有的优势。 为了实现数字签名，必须分析实现数字签名的要求，所以从第四章开始介绍了数字 签名的概念及应用。通过对比用两种加密体制实现数字签名，发现用公钥加密体制来实 现数字签名更具优势。结合椭圆曲线加密算法在加密及安全上的一些特点，用椭圆曲线 加密算法实现数字签名是可行的。 我的工作着重于三点：一是对椭圆曲线加密算法的研究，分析了其安全性及密钥大 小，并对它在有限域上的丰富性给出了具体的实验数据；二是用椭圆曲线加密算法实现 了数字签名；三是研究p k i 数字证书相关的概念及主要结构和数字证书的典型应用。 本文的主要工作 论文主要是从当今广泛关注的信息安全入手，首先分析了加密技术在信息安全中的 重要作用。选择了一种合适的加密算法来实现数字签名。探讨和研究了密码系统中一种 重要的加密算法椭圆曲线加密算法。在分析了该算法的加密原理之后，对它的安全 性作了进一步的讨论，并将它与其它算法( 如r s a ) 进行了比较，研究了该算法在加密上 的优势。同时还研究了数字签名的概念及其应用。并用椭圆曲线加密算法实现了数字签 名。 东南大学硕士学位论文 本文的具体安排如下： 一、研究电子商务、电子政务等信息安全的相关常识 二、研究加密算法：对称加密和非对称加密算法 三、r s a 算法理论基础 四、椭圆曲线算法理论基础 五、椭圆曲线加密签名算法的实现 六、r s a 和椭圆曲线算法的比较与分析 七、研究数字证书的典型应用 2 第一章综述 1 1 信息安全的重要性 第一章综述 计算机安全问题始于2 0 世纪6 0 年代末期i l j 。当时，计算机系统的脆弱性已为一些 组织所认识，但是由于当时计算机的速度和性能比较低下，使用范围也不广，使计算机 安全的问题一直局限在很小的范围内。 8 0 年代后，计算机的性能得到了成百上千倍的提高，应用的范围也不断扩大，计算 机已遍及世界各个角落。计算机的安全问题也随之日益紧迫起来。 进入9 0 年代以来，随着计算机网络的不断发展，全球信息化已成为人类发展的大 趋势。i i l t e m e t 使我们的计算机可以连接到世界的各个角落，也可以使世界上的任何地 方连接到我们的主机。因特网连接着全世界成千上万的人，人们通过它可以进行实时通 信，并能访问大量的信息资源。数据、影像、声音等不同形式的通信，每分每秒地在因 特网上进行着。信息可以廉价而可靠地在网上传递，使得人们对因特网的依赖程度越来 越高。 电子政务系统是指运用现代计算机和网络技术【2j ，将其管理和服务职能转移到网络 上去完成，同时实现政府组织结构和工作流程的重组优化，包括内部核心政务电子化、 信息公布与发布电子化、信息传递与交换电子化、公众服务电子化等，超越时间、空间 和部门分隔的制约，向全社会提供高效优质、规范透明和全方位的管理与服务，进行国 家有关部门的行政管理与服务活动的网络信息系统。在世界各国积极倡导的“信息高速 公路”的五个应用领域中，“电子政务”被列为第一。通过电子政务的建设还可以促进我 国相关高新技术的发展。 电子政务的物质基础是计算机网络。在实施电子政务之后，意味着政府信息将对外 公开。政务活动不同于其他活动，电子政务网络上有相当多的政府公文在流转，其中不 乏重要情报，内部网络上有着大量高度机密的数据和信息，直接涉及各级政府以及部委 的核心政务，有的甚至涉及国家安全，如果电子政府信息网络的安全得不到保证，那么 将会给国家、社会带来严重威胁，可能造成政治、经济等各方面巨大的损失。目前电子 政务系统面对的主要安全问题包括：1 ) 外部非法侵入；2 ) 外部黑客攻击破坏；3 ) 内部非 法侵入，包括非法窃取信息，破坏数据，植入病毒，破坏软件程序等；4 ) 内外勾结进行 非法活动，包括越权操作窃取机密数据或恶意破坏等。因此电子政务安全措施的实施刻 不容缓。 随着电子商务的兴起，许多公司通过因特网来销售产品和提供服务，但是通信的安 全是电子商务的基本前提。比如象信用卡号这样的敏感信息必须得到有效和安全的保 护，商家必须对每一笔业务进行验证和授权。随着经济全球化的趋势，许多公司和机构 东南大学硕士学位论文 用因特网来连接分散于各地的子公司和办事机构。对于公司内部的安全敏感的资 料，需要安全保密地进行传输。 所以因特网的安全问题不但涉及到公司和机构，而且关系到我们每一个人。每个人 都需要，而且都有权利保护自己在网络上的个人隐私。随着消费类的电器越来越向因特 f 网靠拢，我们可以通过因特网打电话，并且用因特网来遥控我们的家用电器。我们当然 不希望看到，一些喜欢恶作剧的人或是黑客，来侵占我们的电话线路，不定时地开关我 们的家用电器。除此之外，个人隐私还包括匿名的权利。按照传统，我们看过什么、去 过哪里和购买过什么东西，所有这些信息都是不应该公开的。如果在网络上要求人们必 须提供，在现实生活中通常隐匿的信息，便会打击很多用户上网的积极性。网络是为了 广大用户共享资源而建设的，然而网络的开放性与共享性也导致了网络的安全性问题， 网络容易受到外界的攻击和破坏，即使你已将大楼的门完全锁好了，但攻击者还是通过 计算机网络在世界的另一头侵入你的网络翻阅机密资料甚至作出破坏性的动作。 但是在计算机网络技术的发展促进计算机应用日益广泛和深入的同时，也使计算机 网络的安全问题日益复杂和突出。计算机网络的不断发展一方面提供了资源共享，通过 分散工作提高了效率，并且还具有扩充性；另一方面增加了信息安全的脆弱性和复杂性， 增加了威胁和攻击的可能性。因此i n t e m e t 的安全已成为现今信息技术的主要问题之一。 没有绝对安全的网络系统，网络信息对抗是一个长期的研究课题，安全问题多种多 样，且随着时间技术的变化而变化，而黑客的侵入手段也随之不断变化，所以安全防护 也是非常重要的，保持清醒正确的认识，同时掌握最新的安全技术资料，再加上完善有 效的安全策略，是可以阻止大部分的网络入侵，从而保持最小程度的经济损失。 国际标准化组织( i s 0 ) 将“计算机安全”定义为3 1 ：为数据处理系统建立和采取的技术 和管理的安全保护，保护计算机硬件、软件数据不因偶然和恶意的原因而遭到破坏、更 改和泄露。 计算机安全包括物理安全和逻辑安全，物理安全是指系统设备及相关设施受到物理 保护，免于破坏、丢失等。逻辑安全包括信息完整性、保密性和可用性。 因此，网络的信息安全涉及社会的各个领域，它的重要性越来越受到关注。加密技 术有效地解决了网络的信息安全问题。 1 2 信息安全和加密系统 由于政府、商业部门及个人的数据以电子的形式存储，信息安全便成为非常重要的 方面。电子媒体更有利于数据的使用：存储方便，传输迅速，访问数据库便利。商业领 域已经认识到信息是他们最有价值的资本。但是，随着电子的革命，电子信息面临着更 大更新的、潜在的安全威胁。不像写在纸上的信息，电子信息可能被远程窃取，它比纸 上的信息更容易被截取或篡改。 第一章综述 简单地说，信息安全即阻止未经授权使用电子数据不论这个未经授权的使用是 否泄露、改变或替换了有关数据。信息安全应包含下面三个内容： 保密性对未经授权的人或团体保密。 完整性确保数据的真实性。 有效性经过安全处理后，信息仍然有效。 许多措施已经用于提供安全服务，同时也没有一种措旋可以保证绝对安全。在各种 各样的措施中，加密系统提供的安全级别较高，适应性较好。广泛地说，一个加密系统 即将电子数据转换为种改变了的形式。信息的主人要确保信息在改变了的形式下的安 全。信息安全必须确保不能被未察觉地修改数据，或者被未授权组织加密。 加密系统的关键在于使用一个密钥来完成转化过程。这个密钥本身要是一个电子字 符串。当然，信息安全不仅要使用加密系统转化数据，而且密钥的主人必须保护好密钥 本身。可以毫不怀疑地说，一个加密系统的正确使用可以为我们今天使用的电子信息提 供较高级别的安全性。 加密系统提供的服务有三种目标的信息安全：保密性、完整性及有效性。为了进一 步说明加密系统，保密性和完整性又被细分为下面五类，它们能够用于建造一个加密系 统块： 保密性对未经授权的组织或个人保密。 使用者鉴定确保实时传送数据的团体正是要传送数据的团体。 数据来源鉴定确保消息的来源合法。 数据完整性确保数据未被未授权使用者篡改。 不可否认性参与传送的实体含有一个绑定，使得实体不能被否认。既实体的接 收者能够向一个中立的第三方证明传送者为真正的传送者。 东南大学硕士学位论文 第二章加密技术基本原理 加密技术是保护网络信息安全的一种重要手段，因此我们有必要了解加密技术的基 本原理，以便更有效地研究加密算法。 保护信息的安全十分重要，然而信息的丢失却不易被发现，同时它又具有时间性。 同一信息在不同的时间其价值不一样，有时候获得信息的时间比获得信息本身还重要。 一般说来，数据库收集或存储的大量数据，或在传输过程中的数据，由于传输中的 公共信道和存储的计算机系统非常脆弱，容易受到两种形式的攻击：一种是从传输信道 上截取信息，或从存储的载体上偷窃或拷贝信息，我们称之为被动攻击，其结果是导致 数据的暴露和对私有权的侵犯；另一种是对在传输过程中或对存储的数据进行非法删 除、更改或插入等操作，称之为主动攻击，其结果可能引起数据或文件的混乱，严重时 可能导致信息处理系统完全失控。对于这两种可能遭受到的攻击除了制定法律外，还需 要有合适的保护措施。密码技术就是一种有效的方法。事实证明，这也是最经济可行的 方法，它是在一种潜在不安全的环境中保证通信的安全。正是因为密码对于通信安全的 极端重要性，所以应该强调说，不安全的密码技术比没有还要坏，因为它给了人们安全 的假象。 2 1 基本概念 什么是密码 4 ? 简单地说它就是一组含有参数k 的变换e 。设已知信息m ，通过变 换e k 得密文c ，即 c 2 e k ( m )( 2 1 ) 这个过程称之为加密，参数k 称之为密钥。加密算法e 确定之后，由于密钥k 不同， 密文c 也不同。 当然不是所有含参数k 的变换都可以作为密码，它应要求计算e k ( m ) 不困难，而且 若第三者不掌握密钥k ，即使截获了密文c ，也无法从c 恢复信息m ，也就是反过来从c 求m 极为困难。以后称m 为明文。 通信双方一方为发信方，或简称为发方，另一方为收信方或简称收方。传统的保密 通信机理可用图2 1 表示。 6 第二章加密技术基本原理 发方：m 收方：c ( 秘密信道) 图2 1 传统的加密算法( 对称加密) 从密文c 恢复明文m 的过程称之为解密。解密算法d 是加密算法e 的逆运算，解 密算法也是含参数k 的变换。传统密码加密用的密钥k 与解密用的密钥k 是相同的，所 以有时也叫对称密码。 通信双方用的密钥k 是通过秘密方式在双方私下约定产生的，只能由通信双方秘密 掌握。如果丢失了密钥，则密码系统不攻自破。密钥的重要性可想而知。 加密技术的安全性对产品起着至关重要的作用。加密技术的安全性依赖于相应数学 问题的难解性。，我们引入算法的概念来解释数学问题的难解性。一个算法是描述解决 一个问题的步骤。例如一个简单的两个数相加的算法就是，输入两数a 和b ，相加后输 出它们的和a + b 。现在，一个数学问题的难解性即为了解决问题要花很长时间进行快速 运算，并且运算时间与输入值的大小有关。 当今的加密体制有两类基本的加密算法：对称密钥系统( 又称保密密钥) 和公钥密码 系统( 又称公开密钥私有密钥) 。公钥密码系统与使用单独的密钥不同，它使用相互关 联的一对密钥，通过一些数学运算，使用一个密钥加密的不论什么东西都只能用另一个 密钥解开。通常自己保存其中一个密钥为“私有密钥”，公开另一个密钥即“公开密钥”。 2 2 对称密钥加密技术 对称的密钥加密技术早在古代就开始被使用，即用同一个密钥对数据进行加密和解 密。但是，这种密钥加密技术要求用户双方在安全的通信之前，必须事先商定密钥。目 前有很多的对称密钥算法，广泛应用的是d e s ( d a t ae n c r y p t i o ns t a n d 盯d ) 算法和d e s 的 改进算法t r i p 】e d e s 。 发送方 ( 秘密信道) 图2 2 对称加密算法 7 接收方 东南大学硕士学位论文 基于对称密钥算法的系统，例如k e r b e m s ，得到了一定范围的应用。但是，它无法 应用于大范围的开放的互联网上，因为在基于对称密钥算法的系统中所需要的密钥数目 较多，n 个用户间相互通信，需要n ( n 1 ) 2 个密钥，并且对密钥的统一的发放和管理也 比较复杂，需要的额外开销很大。 在对称密钥加密中，使用同样的密钥对数据进行加密和解密( 见图2 2 ) 。它被称为对 称密钥加密，因为在加密和解密时使用同样的密钥。它称为保密密钥加密是因为需要对 密钥保密。对称密码又包含三类。古典密码、流密码和分组密码。古典密码的算法有简 单代换、多表代换、同态代换、多码代换和密码乘积等；流密码的算法有混沌密码、量 子密码、r c - 4 和同步流密码等；分组密码的算法有d e s ( d a t ae n c r l r p o ns t a j l d a r d l 、 i d e a ( i n t e m a t i o n a ld a t ae n c r y p t i o na 1 9 0 r i t h m ) m m s 、b l o w 6 s h 等。 下面介绍最常用的d e s 加密算法： d e s ( d a t a e n c r y p t i o ns t a n d a r d ) 是由i b m 公司在上世纪7 0 年代提出的【5 】，于1 9 7 6 年 “月被美国政府采用，随后被美国国家标准局和美国国家标准协会承认。它一直是国际 上商用保密通信和计算机通信的最常用的加密算法。 d e s 是种分组密码。它用6 4 比特的密钥对6 4 比特的明文加密，其中密钥只有5 6 比特有效，有8 位是奇偶校验位，在算法中不起作用。使用5 6 位密钥并对6 4 位的数据 块进行加密。d e s 对6 4 位的输入数据块进行1 6 轮编码。在每轮编码时，一个4 8 位的“每 轮”密钥值由5 6 位的完整密钥得出来。在每轮编码过程中，6 4 位数据和每轮密钥值被输 入一个称为“s ”盒中，由一个压码函数对数位进行编码。另外，在每轮编码开始、过后 以及每轮之间，6 4 位数码被以一种特别的方式置换( 数位顺序被打乱) 。在每一步处理中 都要从5 6 位的主密钥中得出个唯的轮次密钥。最后，输入的6 4 位原始数据被转换 成6 4 位看起来被完全打乱了的输出数据，但可以用解密算法( 实质上是加密过程的逆过 程) 将其转换回输入时的状态。当然，这个解密过程要使用加密数据时使用的同样的密 钥。 随着计算机通信网的广泛应用，传统的对称密码系统就暴露出了它所存在的缺点， 其中主要的是下面两点： 1 密钥管理和分配问题。在一个具有n 个用户的通信系统中，为了采用传统的密 钥密码系统在所有的n 个用户间进行安全的保密通信，首先每个用户必须与其余的n 一1 个用户建立起用于传送密钥的保密通道和用于加密、解密的密钥，这就需要( 旦) 个密钥 2 和( 兰) 个用于传送密钥的保密信道。而当一个新的用户要加入通信网络时或一个用户要 z 改变他的密钥时，同样地，n 或n 一1 个新的密钥必须通过n 或n 1 个保密信道进行传输、 分配给各个用户。 翟 第二章加密技术基本原理 2 认证问题。传统的密码系统不能自然地提供证实用户身份的功能，因而不能认 证信息来源的真实性能和用户的身份。而在计算机、通信网等信息处理系统的输入端和 输出端，采用数字签名等方法的身份认证和信息的完整性保护都变得必不可少了。 2 3 非对称密钥加密技术 为了解决这个问题，1 9 7 6 年d i 伍e 和h e l l m a n 在“密码学新方向”中提出公钥的思想 拍】，即加密的密钥和解密用的密钥不一样，而且加密用的密钥公开不至于危及解密密钥 的安全。这样每个用户都有两把密钥：加密密钥和解密密钥，将加密用的密钥公开，解 密用的密钥由自已秘密保存。它的做法大致是这样的：假设资料要由a 机器传至b 机器， 那么由b 机器用乱数决定一个密钥，我们称之为私钥，这个密钥自始至终都只留在b 机器里不送出来。然后，由这个私钥计算出另一个密钥，我们称之为公钥。这个公钥的 特性是几乎不可能反演算出私钥来。然后将这个公钥透过网络传给a 机器，a 机器将资 料用这个公钥编码，这个编码过的资料一定得使用私钥才解得开，然后a 机器将编码过 的资料透过网络传给b ，b 再用私钥将资料解码。这时，如果有第三者窃听资料时，他 只能得到b 传给a 的公钥，以及a 用这个公钥编码后的资料，没有私钥，第三者根本 无法解码。所以这个方法确实能防止第三者的窃听。 公钥密码体制由于其运算和时间复杂性较高，通常用于密钥管理、密钥交换、数字 签名和认证等涉及信息较少的场合。 非对称加密技术即公钥加密技术，公钥加密的概念最早是由d j m e 和h e l i m a n 两人 在1 9 7 6 年提出的。1 9 7 7 年，r i v e s t ，s h 姗i r 和a d l e m a n 三人发明了r s a 算法，第一次 实现了公钥加密算法。其他的公钥算法还有e l g m a l 加密算法和余弦曲线算法。不同的 公钥加密算法有不同的技术实现，但是他们的共同的特点是： d s k ( e p k ( m ) ) 2 m ( 2 2 ) d p k ( e s k ( m ) ) 2 m( 2 3 ) 每个用户拥有一对密钥，一个是公钥p k ，向其他用户公开。另一个是私钥s k ，必 须保密。如式( 2 乏) 和式( 2 3 ) ，用其中一个密钥加密的信息m ，只能用另一个密钥解开。 这样，用户不需要事先商定共同的密钥，而只需要用对方用户的公钥加密数据，加密后 的数据只能由对方用户用他的私钥才能解开。用户用他的私钥给数据加密形成签名e s 。 ( m ) ，其他人可用他的公钥验证。因为私钥s k 是保密的，所以用户的签名只有用户自 己才能产生，这样就实现了对网络上传送数据者的认证。在公钥系统中，n 个用户间相 互通信，只需要2 n 个密钥。在互联网用户数每年以指数增长的情况下，公钥体系的密钥 数要大大的少于对称密钥算法。这样就解决了传统密钥算法中密钥的发放和管理困难的 问题。 东南大学硕士学位论文 发送方接收方 图2 3 公钥加密算法 但是公钥算法与对称加密算法相比，运算速度要慢很多。所以，在实际应用中，还是用 对称加密算法来加密大量的数据，而用公钥算法来加密对称加密算法中的密钥。用户在 解密一个数据包之前，需要先用公钥算法解密得到对称加密的密钥，然后用这个密钥来 解密得到数据。在为数据签名时，一般首先采用h a s h 算法，计算数据的h a s h 值，例如 用m d 5 算法，求得一定长度的h a s h 值，然后用公钥算法，对h a s b 值进行签名。用户 验证签名时，先用公钥算法从签名计算得到一个值，然后从数据用h a s h 算法，计算得 到一个值，将两个值相比较，如果相同则判定签名为真。 公钥密码系统与使用单独的密钥不同，它使用相互关联的一对密钥，通过一些数学运 算，使用一个密钥加密不论什么东西都只能用另一个密钥解开。通常自己保存其中一个 密钥为“私有密钥，公开另一个密钥即“公开密钥”。它的主要算法有背包、e l g 锄a l 、 m c e l i e c e 、r s a f 蹦v e s t 、s h 锄i r 、a d l e m a n ) ，椭圆曲线算法等。 公钥加密体制的提出在密码学发展史上是一件大事，毫不夸张地说，没有公钥密码 便没有近代密码学，这主要由于保密密钥存在的弱点。保密密钥在加密和解密时适用同 样的密钥，在网络通信的环境下它便暴露出它所固有的缺点。网络上若有n 个用户，两 两问的保密通信需要c ( n ，2 ) = n ( n 一1 ) 2 个密钥，n - 1 0 0 时，c ( 1 0 0 ，2 ) = 4 9 5 0 ；n = 1 0 0 0 时， c f l o o o ，2 ) = 4 9 9 5 0 0 ，这样巨大数量的密钥的管理是个严重的问题，比如密钥的更换便不 胜其烦，更有甚者，每个用户要和其它用户通信时必需保留n 1 个密钥，这样大量的密 钥必须记录在笔记本或磁盘上，这本身就存在一个安全问题。 目前比较著名的公钥加密算法有r s a 、f e r t e z z a 、e l g 锄a 等。目前对这些算法的 破解都是个案，还未发展出致命性的方法，破解这些算法。 。 公钥加密的处理速度远较对称加密为慢，因此，通常把公钥加密技术与对称加密技 术结合使用。即用公钥技术在通信工程双方之前传送专用密钥来对实际传输的数据加 密、解密。 2 4 加密算法的发展状况 对称密钥体制方面，a e s 被作为美国国家标准技术研究所n i s t 旨在取代d e s 的 第二章加密技术基本原理 2 l 世纪的加密标准。a e s 的基本要求是，采用对称分组密码体制，密钥长度的最少支 持为1 2 8 、1 9 2 、2 5 6 ，分组长度1 2 8 位，算法应易于各种硬件和软件实现。1 9 9 8 年n i s t 开始a e s 第一轮分析、测试和征集，共产生了1 5 个候选算法。1 9 9 9 年3 月完成了第二 轮a e s 2 的分析、测试。 在应用方面，尽管d e s 在安全上是脆弱的，但由于快速d e s 芯片的大量生产，使 得d e s 仍能暂时继续使用，为提高安全强度，通常使用独立密钥的三级d e s 。但是d e s 迟早要被a e s 代替。流密码体制较之分组密码在理论上成熟且安全，但未被列入下一 代加密标准。 公钥体制方面，r s a 算法的专利期限将面临结束，取而代之的将是椭圆曲线密码方 案。i e e e 、i s o 和i e t f 也正在制定基于椭圆曲线的密码草案和标准。 另外量子密码正在发展，量子技术在密码学上的应用分为两类：一是利用量子计算 机对传统密码体制进行分析；二是利用单光子的测不准原理在光纤级实现密钥管理和 信息加密，即量子密码学。量子计算机是一种传统意义上的极大规模并行计算系统，利 用量子计算机可以在几秒钟内分解r s a l 2 9 的公钥，而传统计算机需要数月时间。 由于加密在网络中的重要性，加密技术将随着网络的发展更新，将有更安全更易实 现的算法不断产生，为网络提供更有力的安全保障。 下面将主要介绍r s a 加密算法。 1 r 东南大学硕士学位论文 第三章r s a 加密签名算法 3 1r s a 算法的基本原理 r s a 是公钥体制中最值得一提的算法 7 】0r s a 算法产生于1 9 7 8 年，它是第一个既 能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字 以发明者的名字命名：r o n 础v e s t ，a d is h 砌i r 和l e o n a r da d i e m a n 。虽然r s a 的安 全性一直未能得到理论上的证明，但多年来一直没有有效的破解的方法。r s a 算法的核 心建立在两个足够长( 1 0 0 位十进制) 的大素数基础上，以1 0 0 万步s 的计算资源破译大 约需要1 0 2 3 步( 相当于1 0 0 0 年) 。它的安全性依赖于整数的因数分解问题。整数的因数 分解是这样定义的。 给定一个整数n ，它是两个大素数的乘积，寻找素数p 和q 使得 p 曰= 阳 ( 3 1 ) r s a 算法的具体做法为： 1 、找出三个数p 、q 、r ，其中p ，q 是两个相异的质数，r 是与( p 一1 ) ( g 一1 ) 互质的数， 孙q 、r 这三个数便是私钥。 2 、找出m ，使得r 脚一l m o d ( p 1 ) ( g 一1 ) 。这个m 一定存在，因为r 与( p 一1 ) ( g 一1 ) 互质，用辗转相除法就可以得到。 3 、计算n = 阳。m ，n 这两个数便是公钥。 编码过程是，若资料为a ，将其看成是一个大整数，假设a n 。如果“n ，将a 表 示成s 进位f j m ，通常取j = 2 ) ，则每一位数均小于n ，然后分段编码。接下来，计算 6 = = d ”m o d n ，( o 6 ) ，b 就是编码后的资料。解码的过程是，计算 c b “r c = = 6 “，m o d p g ( 0 c p 9 ) ，于是，解码完毕。 可以证明c 和a 其实相等，即加密解密互为逆运算。 定理 若p ，q 是相异质数，= = 1 m o d ( p 一1 ) ( g 一1 ) ，a 是任意一个正整数， 6 = = d ，”m o d p g ，贝0c = = 6 ，m o d p g ，c = 口m o d p g 。 这个定理说明a 经过编码为b 再经过解码为c 时，“= = c m o d 月( m = p q ) 但我们在做 编码解码时，限制0 d m ，0 c ，所以这就是说a 等于c ，所以这个过程确实能 做到编码解码的功能。 第三章r s a 加密签名算法 如果第三者进行窃听时，他会得到几介数：m 、n ( = p q ) 、b ，他如果要解码的话，必 须想办法得到r ，所以他必须先对n 作质因数分解。要防止他分解，最有效的方法是找 两个非常大的质数p 、q ，使第三者作因数分解时发生困难。 3 2 随机数生成 计算机中随机数的生成一般采取随机种子+ 生成算法取得的。随机种子的选取一般 采用的方法有取时间值，用户的输入值，机器的随机变量如某时刻内存的使用多少、进 程、线程数目、句柄数量、外接传感器的输入、用户键入的时间差等等，把可用的各种 随机因素混在一起把差异放大取得种子。生成算法把种子生成一个伪随机序列，取序列 中的某个值，从而生成随机数。生成算法一般有平方取模算法、数学函数取中间某段数 字作为下一次的输入的生成算法等等。 3 3r s a 的安全性分析 若n 印q 被因子分解，则r s a 便被击破。因为若已知p 和q ，则( d ( n ) = ( p 1 ) ( q 一1 ) 便可 以算出。解密密钥d 关于e 满足： e d 三1 m o d ( p ( n ) ，l o 0 图4 1 ( b ) = o 时有三个实根；特别当( 1 2 9 ) 2 = ( 1 3 p ) 3 o 时， p = q - o 时有三重零根。( 图像形如图4 2 ) ( c ) 0 时，有三个不等的实根。( 图像形如图4 3 ) 若在( 1 ) 中令y 代以( y 一，x 一吩) 2 ，便得 y 2 = 4 x 3 + 6 2 x 2 + 2 6 4 z + 6 6 其中6 2 = 口1 2 + 4 2 ，6 4 = 2 口4 + d l 3 ，6 6 = 口3 2 + 4 盘6 f 3 ) 式所示曲线关于x 轴对称。 三个实根中有两个相等 f 4 4 1 一翌婴差塑型些垡垫垄塞鲨 = o 图4 2 呵 八 。 。i u 图4 3 椭圆曲线上点。的运算 设j d 2 ( 而，乃) ，q = ( 屯，儿) 是e 上任意两点，l 是p q 连线。若p 和q 重合于点， 即p 2 q ，则l 便退化为p 点的切线。设l 和曲线相交于另一点r ，l t 是r 点和无穷远 点o 的连线，也就是说l 是过r 点引y 轴平行线，l 和曲线交于一点，用p 。0 表示。 实际上点p 。q 和点r 关于x 轴对称。曲线e 关于x 轴对称。运算如图4 4 ，4 5 。 若p 和q 关于x 轴对称或重合于x 轴，则p q 垂直于x 轴，这时l 和椭圆曲线交于无穷 远点o 。 图4 4 东南大学硕士学位论文 k y p = q 蠢 【 厂弋 l u 。法 王 。、 l 幽4 5 关于。运算的群的性质 定理若p 和q 是曲线e 上任意两点，p q 连线l 交e 于另一点r ，则： ( a ) ( p o q ) o r = 0 ( b ) p 0 0 = p ( c ) p o q = q o p ( d ) e 上存在一点q ，使得_ p o q = 0 ，这样的点q 表以0 尸。 ( e ) 对于e 上的任意点_ p ，q ，r ，( p oq ) 0 r = p o ( q o r ) 证明 ( a ) _ p o q 和r 作为曲线上两点，它们的连线平行于y 轴，交e 于无穷远点o 。 ( b ) 在曲线e 上取无穷远点o 作为q 点，p q 连线平行于y 轴，交曲线e 于r 点。 此时r 点和p 点关于x 轴对称，l 和l 重合，所以户o d = ，。 ( c ) 根据尸o q 的定义，p o q = q oj p 应成立，即关于+ 运算交换律成立。 ( d ) 可通过p 和q 的直线交曲线e 于r 点，根据性质( a ) 有：( p o q ) o 尺= 0 。根据 性质( b ) 有：尸o d = _ p ，所以，r 是所求的0p 。 ( e ) 证明从略。 从上面定理可知：若将o 点看作为运算。的零运算，性质( e ) 证明关于。运算交换律 成立。性质( e 1 为：若p 点在曲线e 上，刚曲线上关于。结合律成立。为了方便起见，以 后将。简化为+ ， 记为一。同样理由，p o p 记为p + p = 2 p ，依此类推： m p = p + p + p m 次 总之，椭圆曲线上的点关于运算+ 构成a b e l 群。 椭圆曲线