（计算机应用技术专业论文）基于改进型elgamal数字签名的身份认证研究与设计.pdf

基于改进型e l g a m a l 数字签名的身份认证研究与设计 摘要 身份认证技术是网络安全和信息系统安全的第一道屏障，它是在信息安全 时代备受关注的一个研究领域，而基于密码体制的身份认证，一直是人们研究 的重点，有着广泛的应用前景。 本文首先介绍了论文研究的背景和密码学的相关概念，并对加密算法进行 了分类，重点介绍了几种常用的加密算法及其原理，在加密算法的基础上对数 字签名和身份认证技术进行了详细的介绍，深入分析了e l g a m a t 数字签名机制， 并提出了改进方案，该方案减少了上述方案的模逆运算次数，在确保安全性的 前提下，提高了签名方案的运行效率。最后设计了一种基于改进型e l g a m a l 签 名的身份认证模式，并实现了一个模拟系统对该认证模式进行了验证，实验结果表 明了该认证模式的正确性和高效性。此外，在设计过程中还对伪随机序列和大素 数的产生进行了深入的研究。 关键词：零知识证明、数字签名，身份认证，e l g a m a l 方案 t h er e s e a r c ha n dd e s i g no ft h ei d e n t i t yi d e n t i f i c a t i o ns y s t e mb a s e d o ni m p r o v e de l g a m a l s i g n a t u r es c h e m e a b s t r a c t a u t h e n t i c a t i o ni st h ef i r s tb a r r i e ro ft h en e t w o r k i n f o r m a t i o ns y s t e ms e c u r i t y f i e l d i ti sak e yf i e l di nt h ei n f o r m a t i o na g e a n dt h ec r y p t ol o g i c a la u t h e n t i c a t i o n h a sb e e nr e s e a r c h e da n dh a sp r o m i s i n ga p p l i c a t i o ni nf u t u r e f i r s t ，t h i sa r t i c l ei n t r o d u c e si t sr e s e a r c hb a c k g r o u n da n ds o m ec o n c e p t s c o n c e r n e dw i t hc i p h e r a n dt h e nc l a s s i f i e st h ee n c r y p ta l g o r i t h m s ，e m p h a s i z e so n s e v e r a la l g o r i t h m sa n dt h e i rt h e o r i e si nc o m m o nu s e i ns u c c e s s i o ni td e s c r i b e st h e t e c h n i q u eo fd i g i t a ls i g n a t u r ea n di d e n t i t yi d e n t i f i c a t i o nb a s e do nt h ee n c r y p t a l g o r i t h m s i n t r o d u c ee l g a m a ld i g i t a ls i g n a t u r ei nd e t a i l s a n dp u tf o r w a r da n i m p r o v e dd i g i t a ls i g n a t u r es c h e m ea si n v e r s eo p e r a t i o n sr e d u c e da n di se f f i c i e n t w i t hh i g hs e c u r i t y a tt h ee n do ft h et h e s i s ，d e s i g na ni d e n t i t yi d e n t i f i c a t i o np a t t e r n b a s e do ni m p r o v e de l g a m a ls i g n a t u r es c h e m e a n di no r d e rt ot e s ta n dv e r i f yt h e p a t t e r nw ed e v e l o pas i m u l a t es y s t e m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e i d e n t i t yi d e n t i f i c a t i o np a t t e r ni sc o r r e c ta n dh a sh i g he f f i c i e n c y d u r i n gt h ed e s i g n w ee s p e c i a l l yr e s e a r c ht h ep r o d u c i n go fr a n d o ms e q u e n c ea n db i gp r i m e k e y w o r d s ：z e r o - k n o w l e d g ep r o o f , d i g i t a ls i g n a t u r e ，i d e n t i t yi d e n t i f i c a t i o n ， e l g a m a ls i g n a t u r es c h e m e 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 盒鼹王些盍堂或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所傲的任何贡献均已在论文中作了明确的说明并表示谢意。 学馘嫦者魏倦卫 签翱期：畔白日 学位论文版权使用授权书 本学位论文作者完全了解金肥王些太堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权台肥工业大学可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者躲体卫 签字日期：弦卅哗月1 日 学位论文作者毕业后去向 工作单位： 通讯地址 导师签名 小钆 签字日期：冲i 月f 日 电话 邮编 致谢 本论文是在导师侯整风副教授的悉心教诲和无微不至的关怀下完成的。从 论文的选题，论文的架构及写作等方面，无不凝聚着侯老师的心血。在研究生 学习期间，侯老师不仅授业，更是传道、解惑：始终给予我严格的要求、充分 的信任、热情的鼓励和全面锻炼的诸多机会。在学习和学术研究中，我深受侯 老师严谨的治学态度和勤奋的敬业精神的熏陶和激励，从中收益良多；在生活 和为人方面，侯老师更是言传身教，鼓励我积极上进；在此，谨向侯老师表示 最诚挚的感谢和最崇高的敬意。 此外，在论文的写作过程中，还受到了杨明玮，丁凉，刘项洋等多位同学 的无私帮助，在此，对他们表示最诚挚的感谢。 感谢我的爱人卫敏在我研究生学习期间对我的支持和鼓励! 正是他默默的 付出和全力支持，才使我解除了后顾之忧，从而全身心地投入到学习中去。 感谢计算机学院的王新生老师、徐静老师、费敏老师以及合肥工业大学研 究生院的老师们所付出的辛勤工作。 最后，再次衷心感谢所有关心和帮助过我的师长、同学、朋友和亲人们! 作者：陈卫 2 0 0 4 年5 月 第一章绪论 1 1 课题研究的目的和意义 电子计算机的出现是二十世纪的大事，它改变了我们这个世界的 面貌。毫不夸张地说，它的影响遍及所有的角落，几乎无处不感觉到它 的存在，它的应用已从科学计算、过程控制、数据处理等方匿，广泛深 入到政治、经济、军事、科学技术、文化教育、医疗、交通乃至家庭生 活等社会的各个领域。 而计算机网络技术的广泛普及和应用、跨国跨地区的世界互联网 的发展。使得计算机技术为促进社会的繁荣与迸步产生了极深远的影 响。特别是近年来，网络信息技术正以前所未有的速度广泛应用于社会 政治经济生活的各个领域，深刻地影响着人们的工作方式、生活方式、 管理方式和恩想观念，有力地摆动了人类的文明进步和社会发展。 与此同时，计算机网络技术的广泛应用，要求计算机系统具有开 放性，但是，其体系结构的开放性也暴露了许多脆弱、易被攻击的薄弱 环节。在计算机系统资源高度共享的同时，也存在着许多人为故意的未 授权窃取、篡改、破坏及其敌对佳活动带来的危害。加之近年来计算机 病毒发作的猖獗，使得计算机系统的不安全性显得越来越突出。计算机 网络的安全问题也日益引起人们的密切关注，人们对网络的安全性提 出了如下要求： ( i ) 、通信线路最明显的一个不安全因素是他人可以很容易地窃听而 获得有价值的信息，所以要设法保护通信的信息不被窃取或者被篡改 破坏。 ( 2 ) 、人们希望对于自己拥有的资源具有特权，担心他人通过网络非法 入侵自己的资源，所以希望网络能提供对访问者的合法性检查。 ( 3 ) 、人们担心入侵者可能访问的信息资源中存在隐含通道，这使得进 入者可能窃取高度机密的信息，亦可能被设置病毒而使信息系统陷于 崩溃。 ( 4 ) 、人们心理上要求一种互相信任感，反映在网络技术上，不仅要求 网络有能力确认用户的合法性，而且网络也不可能对用户进行欺骗。用 户希望对自己拥有的信息在网络中的流向或存留有一个完全确切的了 解和掌握。这些担忧提出了网络的安全性问题。随着i n t e r n e t 的迅猛 发展，使得人们更加意识到网络安全的重要性。 国际社会和各个国家都相继建立了各种学术团体、研究机构以及 相应的标准化组织，深入广泛她开展了计算机数据安全的研究。从8 0 年代初。国际信息处理协会( i f i p ) 每年组织召开关于信息处理系统的 安全和保护方面的技术交流会。我国从1 9 8 i 年开始着手计算机安全方 面的工作。以公安部计算机监察司为主，在中国电子学会、计算机学会 以及中央各有关部委的支持下做了大量的工作，多次召开了全国性计 算机安全技术交流会。而计算机安全问题也引起了全社会的关注，在 2 0 0 1 年3 月的全国政协九届四次会议上涉及计算机网络的内容安全、 技术安全和国家安全的提案就有1 0 0 多个。目前有关计算机安全的研究 包括：数据安全技术、道德规范与教育等等。这些为建立一个安全的计 算机系统提出了技术上、管理上、政策法律上的各种方法与对策。总之， 计算机安全问题己成为当今丞待解决的重大课题。”3 在众多的计算机安全方面的研究中，密码技术是有效保护计算机 信息安全的一个重要研究课题。近年来，由于计算机科学的蓬勃发展以 及防止日益严重的计算机犯罪的需要，密码技术的研究十分活跃，并 有了突飞猛进的发展。特别是七十年代以来的二十多年，美国国家标准 局公布实施了美国的数据加密标准d e s ，而d i f f i e 和h e l l m 8 n 也提出 了公钥密码思想，受其启迪各种公钥密码体制被提出。从而奠定了近代 密码学的基础，在计算机信息安全成为全社会关注问题的同时，有着 几千年历史的密码学这门古老的学科也成为一门新的学科，引起了数 学界与计算机科学工作者的高度重视。 密码技术的应用可以对存储在计算机系统中的信息和在通信网络 中的传输信息实施保护，使其不被泄露、篡改、窃取乃至破坏。密码技 术还有效地被用于身份认证、数字签名等领域，用以防止非法的用户入 侵和电子欺骗，这对信息处理系统的安全起到了极其重要的作用。事实 证明，密码技术是计算机安全中最有效也是最经济可行的方法，它使 得在一种潜在的不安全的环境下保证通信的安全。”3 随着信息技术日新月异的发展，人类正在进入以网络为主的信息 时代，基于i n t e r n e t 开展的电子商务( e c ：e l e c t r o n i cc o m m e r c e ) 已 成为人们进行商务活动的新模式。越来越多的人通过i n te r n e t 进行商 务活动，电子商务的发展前景十分诱人，但随之面来的是其安全闯题 也变得越来越突出。如何建立一个安全、便捷的电子商务应用环境，保 证整个商务过程中信息的安全性，使基于i n t e r n e t 的电子交易方式和 传统交易方式一样安全可靠，已经成为大家十分关心的热门话题。据权 威机构调查表明，目前国内企业发展电子商务的最大顾虑是安全问题。 因此，信息的安全性是当前发展电子商务最迫切需要研究和解决的问 题。由于i n t e r n e t 本身的开放性以及目前网络技术发展的局限性，使 网上交易面临着种种安全性威胁，其中主要包括：机密信息的泄露、交 易信息的非法篡改、冒充合法用户参与交易以及对交易的故意抵赖等。 针对这些威胁，也由此提出了相应的安全需求，包括身份的可认证性、 信息的保密性、信息的完整性、不可抵赖性、不可伪造性等。迄今为止， 国内外学术界和相关厂商也因此提出了很多相应的解决方案，并且基 本上满足了人们在i n t e r n e t 上开展安全的电子商务活动的愿望。 认证技术是信息安全理论与技术的一个重要方面，也是电子商务 安全的主要实现技术。从某种意义上说，认证技术可能比信息加密本身 更加重要。采用认证技术可直接满足身份认证、信息完整性、不可否认 和不可修改等多项网上交易的安全需求，较好地避免了网上交易面临 的假冒、篡改、抵赖、伪造等种种威胁。 1 2 国内外研究现状及存在问题 随着计算机网络的普及和电子商务的蓬勃发展，网络的安全性日益 成为人们关注的焦点，而对用户的身份认证是保证通信网和系统数据 安全的首要条件。特别是最近几年，由于网上商务的日益火爆，从某种 意义上说，认证技术可能比信息加密本身更加重要。因为，很多情况下 用户并不要求购物信息保密，只要确认网上商店不是假冒的，这就需 要身份认证。在计算机网络中，身份认证是一种证实用户所声称的身份 是否真实的技术。结合密码学技术，各国专家和学者提出了多种身份认 证方案。f a i t 和s h a m i r 等人首先提出了实用的基于身份认证的方案， 该方案实现了用户身份信息零知识泄漏，它的安全性是基于分解大数 的困难性。o h t a 又扩展了该方案使之适合于智能卡的应用。此后，t s u j i i 又提出了基于离散对数的身份认证方案“1 ：h a r n 和y a n g 提出了一种可用 于身份认证、数字签名、密钥分配的密码方案印1 。然而，以上各种方案 均有不足之处。 e l g a m a l 签名是1 9 8 5 年由e l g a m a l 等人提出的，它是基于离散对数问 题且主要是为数字签名的目的而设计的，是继r s a 之后最著名的数字签 名方案，后来又产生了许多对e l g a m a i 进行改进和推广的各种方案，如 h a r n 方案、a m v 方案、y e n - l e i n 方案和著名的d s s d s a 方案。此后，h a r n 对e l g a m a l 方案及其类似的方案进行了分析总结，给出了1 8 个安全可行 的方案，称之为广义e l g a m a l 签名方案，它是许多实用签名方案和协议 的基础。本课题就是对基于e l g a m a l 数字签名的认证方案的研究，该方 案借助于零知识证明的思想，使得用户不必暴露自己的秘密信息就可 向认证方证明自己的身份。采用该方案目的是使用户认证过程既具有 较好的安全性又具有较高的效率。由于在本方案中减少了类似于在 e l g a m a l 签名中的模逆运算次数，从而使得在身份认证过程中也减少了 模逆运算次数，使认证的效率得到提高。 基于e l g a m a l 数字签名的身份认证研究虽于很多年前就已兴起， 而且目前国内外已出现了很多种有实用价值的身份认证机制。但在实 际的应用中还存在很多问题，特别是安全和效率问题始终不能得到统 一解决。随着电子商务的快速发展，对这一类课题的研究将至关重要。 1 3 论文安排 本文第章为绪论，主要介绍了课题研究的目的、意义、国内外 研究状况及存在的问题；第二、第三章分别介绍了本课题所依据的数 论知识和密码学理论；第四章首先介绍了e l g a m a l 数字签名机制，分 析了它的不足，并在此基础上给出了改进的签名方案，并对该方案进行 了安全性和效率分析，最后涉及了一种基于该改进方案的身份认证模 式；第五章涉及了一个模拟系统验证模式的正确性；第六章总结了本 文的工作，并对以后的工作进行了展望。 4 第二章身份认证的数论基础 2 1 素数和唯一分解定理 对素数的研究。一直都是数学领域非常吸引人的一个研究领域， 同时在计算机安全领域起着特别重要的作用，并广泛应用于计算机加 密等领域。 一、定义 一个大于1 的整数，如果它的正因数只有l 和它本身，就叫做素 数，否则就叫做复合数。 二、几个重要定理 1 、设a 是任一大于1 的整数，则a 的除1 以外的最小正因数q 是素数， 并且当a 是复合数时，q a “2 。 2 、若p 是一素数，a 是任一整数，则有p fa 或( p ，a ) = 1 。 3 、( 整数唯一分解定理) 任一大于l 的整数能表示成素数的乘积，即对 于任一整数a 1 有 a = p i p 2 p 。，p i p 2 p 。 其中p ，, o z p 。是素数，并若 a = q l q 2 q q l q 2 q 其中q ，q 2 q 是素数，则m = n ，q i = a ( i = l ，2 ，3 1 1 ) 。 2 2 有限域中的离散对数闯题 设p 是一个素数，g 是有限域g f ( p ) 的本原元，g f ( p ) 上的指数可以 表示为如下形式 y = g 。i n o d p ( 2 2 1 ) 其中0 x p 一1 。根据2 2 1 式可知x 也可以表示为有限域g f ( p ) 上以 g 为底的对数 x = l o g 。ym o dp ( 2 2 2 ) 其中0 y p 一1 。 按2 2 1 式在已知x 的条件下求y ，按照 1 中提供的多项式算法只 需2 l o g 。( p 1 ) 次乘法运算，然而，若已知y 按2 2 2 式求x 是极其困难 的。在密码学中，当求解一个变量的最快算法为指数或次指数算法时， 刚认为该算法在实现上是不可能的，因为在资源有限的情况下，当你 花费极长时间求解出该变量时，该变量已经失去了保密意义。 按2 2 2 式，在已知y 的条件下，求在有限域g f ( p ) 上的整数解x 的问题，就是密码学上所说的离散对数问题。这是个极其困难的问 题，e l g a m a l 数字签名方案就是建立在这难解问题基础上的。 2 3e u c l i d 算法 设z 是整数集合，a ，b z ，b 0 ，则存在唯一的整数对q ，r 使 a = q b + r ，0 r 2 16 0 。 元素b 为q 阶元素，1 b p 一1 ，即令d 为g f ( p ) 的生成元，则 b = a ”。“4 m o dp ：由可信赖中心t 向各用户分发系统参数( p q ，b ) 和证实函数( 即t 的公钥) ，用此证实t 对消息的签字；选用参数t ，t 至4 0 且2 q 。 预计算参数的选定：对每个用户给用唯一的身份i ；用户a 选定 秘密密钥a ，0 a q 一1 ，并计算v = b1 m o dp ：a 将i 和v 可靠地送给t ， 并从t 获得证书，c e r t = ( i ，v ，s ，( i ，v ) ) ( 1 ) 、a 选定随机数r ，0 r q 一1 ，计算x = b 7 m o dp ，并将( c e r t ，x ) 送给b 。 ( 2 ) 、b 以t 的公钥解s ，( i ，v ) ，实现对a 的身份i 。和公钥v 的认证， 并选定随机数e ，1 e 2 ，送给a ； ( 3 ) 、a 验证1 e 2 ，并将y = a e + rm o dp 送给b ； ( 4 ) 、b 计算z = b v 。，若z = x ，则认可a 的身份合法。 t 要选得足够大，以使正确猜对询问值e 的概率足够小，通常选 t = 4 0 ，为了抗击随机离散对数攻击，要求q 耋2 1 6 0 。应答时间可以在数秒 钟内完成。此协议是一种对a 的知识证明，即参加协议者像a 一样在协 议完成时能计算a 。因为x 是随机数，y 又被随机数r 搅乱，因此协议 未暴露有关a 的有用信息。破解该算法的难度大约是2 。 在i n t e r n e t 时代，网络通讯中的实体迫切需要用一种可靠的身份 鉴别方法来向对方证明自己的身份，作为网络上最基本最必须的功能， 身份鉴别问题得到广泛和深入的研究，特别是出现了许多基于零知识 证明的方案，f e i g e f i a t s h a m i r 算法是第一个基于零知识证明的算 法。但由于与外部信息交换很耗时，对于诸如智能卡的应用，该算法不 甚理想。此后l o u isg u i l l o u h 和j e a n j a c q u e sq u is q u r e 研究出的零 知识证明身份鉴别的算法更适合于这些应用。后来c 1 a u ss c h n o r r 提出 了一个安全性基于离散对数的零知识证明身份鉴别方案。最近，d a e h u n n y a n g 和j o o s e o ks o n g 提出了一个基于零知识证明身份鉴别方案，该 方案需要较小的通讯量和计算量，可以应用于智能卡系统。凹1 第三章身份认证系统的密码学理论 3 1 密码学理论及技术 密码技术是一门古老的技术，自从人类有了战争，就有了密码，所以 密码作为一种技术源远流长，可以追溯到远古时代，而且有过自己的辉 煌历史这门古老的技术随着密码学、数学和计算机技术的发展促成了 今天密码技术的繁荣。从二十世纪五十年代起至今，是传统密码学高水 平快速发展和现代密码学的产生和研讨时期。7 0 年代后期，密码技术 的发展出现了两个重要的转变：一是密码技术由过去单一面向军事、政 治、外交等重要的机密部门转向同时面向金融、商业、科技、经济等民 用和商用等社会各个领域；二是密码技术的研究本身由秘密转向公开。 正是这两个转变，特别是电子计算机技术的高速发展，促使密码这一 古老的技术焕发出空前的青春与活力。从加密体制和加密算法来讲，这 时期最具有代表性的两大成就是 ( 1 ) 、1 9 7 7 年由美国联邦标准化局( n b s ) 颁布的数据加密标准( d a t a e n c r y p t i o ns t a n d a r d ) ，简称d e s 。它的出现把传统密码学的研究推进 到一个新的阶段。它是密码历史上应用最广，影响最大的传统密码算 法，被誉为密码历史上的第一个里程碑。 ( 2 ) 、1 9 7 6 年狄菲( d i f f i e ) 和赫尔曼( h e l l m a n ) 创立的公开密码体制 的新思想，从此奠定了公开密钥密码体制的基础，开创了密码学理论 研究的新纪元。这是密码发展史上划时代的革命性的新概念，它标志着 现代密码学的诞生，被誉为密码史上的第二个里程碑。 所谓密码技术，就是对信息进行重新编码，从而达到隐藏信息内 容，使非法用户无法获取信息真实内容的一种手段。近代密码技术已经 发展成为一门系统的技术科学，除了和数学紧密相关而外，还涉及到 通信、计算机、微电子学等多种技术门类；所应用的数学工具也从简单 的代数发展到近代代数、信息论、数论、组合学、计算机复杂性理论等 多个领域。密码技术随着人类社会的发展而诞生，并在政治、军事、外 交斗争中作为重要工具被充分使用，经过长期的实践，已经形成一门 科学一密码学。而今，人类社会步入信息化时代，是密码学成为一门 非常重要的实用技术科学。从通信安全保密、计算机安全保密，直到信 息系统的安全保密，社会的发展对信息系统的安全保密提出了越来越 高的要求，对密码学也提出了越来越高的要求。 加密实质是一种数据形式的变换，把数据和信息( 称为明文) 变 换成难以识别和理解的密文并进行传输，同对在接收方进行相应的逆 变换( 称为解密) ，从密文中还原出明文，以供本地的信息处理系统 9 使用。加密和解密过程组成为加密系统，明文和密文统称为报文，任何 加密系统，不论形式多么复杂，至少包括一下4 个组成部分 ( 1 ) 、待加密的报文，也称明文： ( 2 ) 、加密后的报文，也称密文； ( 3 ) 、加密和解密的算法( 或装置) ，也称为密码体制； ( 4 ) 、用于加密和解密的钥匙，也称为密钥。密钥是用于加解密的一些 信息，它是控制明文和密文之间变换的关键，它可以是数字、词汇或语 句。密钥分为加密密钥和解密密钥。 加密是在不安全的信息渠道中实现信息安全传输的重要方法。例 如，发送方向接收方发送信息，发送方用加密密钥把信息加密后发送 给接收方；接收方在收到密文后，用解密密钥把密文恢复为明文。如果 在传输过程中有第三者试图窃密，他只能得到一些无法理解其意义的 密文信息，这个过程可以表示为图3 1 的情况。 图3 1 数据加密过程 3 1 1 密码体制 在古老的密码发展史上，有很多经典、传统的密码，其中有：凯撒 密码、单表置换、维吉利亚密码、普莱费厄加密算法、希尔加密算法、 维尔加密算法等等。在这种密码体制下，按照生成密文所采用的不同方 法，数据加密的基本技术可以分为三种：即替代式密码、置换式密码和 乘积式密码。 替代式密码( 又称换字密码) ，其基本思想是根据某种算法，用另一 个字符或另一组字符去取代明文中一个字符或一组字符，明文与密文 中的各对应字符的相对位置保持不变，使明文中的各个字符“变形不 变位”从而得到密文。如凯撒密码和维吉利亚密码就属于替代式密码。 置换式密码( 又称移位密码或互换密码) ，其基本思想是按照某种 算法使明文中的各个信息“变位不变形”，即不改变明文中每个信息本 身的形式，仅改变它在明文中的位置，将重新排列后所得到的信息作 为密文。实现这种密码的方法很多，可以有矩阵式、栏栅式等。普莱费 厄加密算法和希尔加密算法就属于置换式密码。 乘积式密码是替代密码和转换式密码的有限次组合。它是一种混 合式密码，在一定程度上可以提高密码的抗破译攻击强度。d e s 算法就 是重复使用移位的替代变换的一种抗破译能力强的乘积式密码体制。 1 9 7 6 年，美国著名密码学家狄菲( d i f f i e ) 和赫尔曼( h e l l m a n ) 提出了令人耳目一新的公钥密码体制，它开辟了新的密码应用领域。因 此，数据加密技术根据加密算法、加密密钥和解密密钥的异同分为两大 体制，即对称加密体制和非对称加密体制1 。 3 1 1 1 对称密码体制( 加密密钥= 解密密钥) 一、基本概念 所谓对称加密体制，即加密和解密使用的密钥是相同的，因此该体 制又称作单密钥加密体制。它属于传统密码，在这种体制中，即使有时 加密、解密密钥不相同，但它们之间仍存在着一定的联系，是容易相互 推导出来的。d e s 就是这种加密体制的代表。 二、加密算法 实现对称密钥加密体制的典型算法主要有以下两种： 1 、d e s ( d a t ae n c r y p t i o ns t a n d a r d ) d e s 是1 9 9 7 年美国国家标准局宣布用于非国家机密机关的数据保 护，作为美国数据加密标准。它综合运用了置换、代替、代数多种密码 技术，把明文以6 4 位为单位分成组，而后用密钥把每一组明文转化成 同样6 4 位的密文组，使用5 6 位密钥，迭代轮数为1 6 轮的加密分组算 法。d e s 是一种世界公认的好的加密算法，自它问世以来经受住了许多 科学家的研究和破译，曾为全球贸易、金融等部门提供了可靠的通信安 全保障。但它也有明显的缺点，密钥太短，只有5 6 位。目前已有许多 d e s 被破译的报道，因此为了提高安全性，d e s 又有了新的发展。比如： 三重9 e s 使用双密钥加密的方法，即使用两个5 6 位的密钥k ，、k 。，发 送方用k 加密，k 。解密，再使用k 。加密。接收方则使用k 。解密，k 。加 密，再使用k ，解密，其效果相当于将密钥的长度增加到1 1 2 位。还有 三重d e s 的变形算法，使用三个独立密钥，相当于密钥长度增加到1 6 8 位等。 2 、i d e a ( i n t e r n 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 ) 算法 i d e a 是一种国际信息加密算法u ”，其安全强度高于d e s 算法，它 是1 9 9 1 年在瑞士e t hz u r ic h 由j a m e sm e s s e y 和x u e i i al a i 发明，于 1 9 9 2 年正式公开，是一个分组大小为6 4 位，密钥1 2 8 位，迭代轮数为 8 轮迭代型密码体制，此算法使用长达1 2 8 位的密钥，有效地消除了任 何试图穷尽搜索密钥的可能性。这种算法是在d e s 算法的基础上发展 起来的，类似于三重d e s 。发展i d e a 也是因为感到d e s 使用的密 钥太短。i d e a 的密钥为12 8 位，这么长的密钥在未来若干年内应 该是安全的。i d e a 算法也基于分组，它采用软件和硬件实现都同 样快速，目前软件实现的i d e a 比d e s 快两倍。由于i d e a 是在美国 之外提出并发展起来的，避开了美国法律上对加密技术的诸多限 制。因此，有关i d e a 算法和实现技术的资料可以自由出版和交流， 可极大地促进i d e a 的发展和完善”。 三、对称密钥加密体制的优缺点 对称密钥加密体制具有加密速度快，密钥容易生成，安全强度较高 等优点。在军事、外交以及商业应用中使用越来越普遍。但由于存在以 下缺点而限制了它在一些情况下的应用。 ( 1 ) 密钥分布问题。如上所述，传送信息的双方在不安全的信道上交 流之前，需要预先选定某一秘密密钥。在某些情况下，选用秘密密钥的 秘密信道不存在。 ( 2 ) 密钥管理问题。对于有n 个网络用户的网络系统来讲，每一对用 户之间存在着一个秘密密钥，总共需要n ( n 1 ) 2 个秘密密钥。如果系 统比较大的话，密钥则会因为变得太大而不容易管理。 ( 3 ) 难以实现数字签名。数字签名是手写体的电子信号，它可以使信 息的收到方向第三者确认该条信息是从发送者传送来的。在一个私钥 密码系统中，a 和b 双方具有相同的加密和解密能力，也就是说b 无法 向第三方证明来自a 的信息确实是由a 发出的。 私钥密码体制的一个严重缺陷是在任何密文传输之前，发送者和 接收者必须使用一个安全信道预先传送密钥，在实际应用中这一点是 很难做到的。例如，假定发送者和接收者之间的距离很远，他们要使用 电子邮件来通信，在这种情况下，通信双方可能没有合理的安全信道。 3 1 1 2 非对称密码体制( 加密密钥解密密钥) 一、基本概念 所谓非对称加密体制，即加密和解密使用的密钥是不相同的，也 称为双密钥加密体制。非对称加密体制的基本思想是：不仅公开加密算 法，而且加密用的密钥也公开。即可以将每一用户的加密密钥作为公钥 文件。象电话号码簿一样公开，只要解密密钥保密就可以了，而且各 用户的解密密钥由各用户自己保密保管。若用户a 要向用户b 发送信 息，a 可以从公钥文件中查到b 的加密密钥，利用它向b 发送密文，b 收到密文后利用只有自己知道的解密密钥解密缛到明文。由于这种加 密体制的加密密钥是公开的，因此又称这种加密体制为公开密钥加密 体制，简称公钥体制。它在密钥管理与使用方面为用户带来了明显的好 处，在数字签名与身份认证领域有着广阔的前景。 二、加密算法 自公钥密码体制问世以来，密码学家们提出了许多种加密方法， 这些加密方法的安全性都是基于复杂的数学难题。对于某种数学难题， 如果利用通用算法计算出密钥的时间越长，那么基于这一数学难题的 公钥密码体制就被认为越安全。根据所基于的数学难题来分类以下三 类密码体制目前被认为是安全的和有效的： ( 1 ) 、基于整数因子分解的密码体制( 如；r s a 密码体制) ； ( 2 ) 、基于离散对数问露的密码体制( 如：e l g a m a l 密码体制) ； ( 3 ) 、基于椭圆曲线离散对数问题的密码体制( 如椭圆曲线密码体制) 。 公钥密码体制采用的加密密钥和解密密钥是不同的。由于加密密 钥是公开的，密钥的分配是公开的，密钥的分配和管理就很简单，而 且能够很容易地实现数字签名，因此最适合于电子商务应用的需要。在 实际应用中，公钥密码体制并没有完全取代私钥密码体制，这是因为 公钥体制基于尖端的数学难题，计算非常复杂，它的速度远比不上私 钥密码体制。下面对几种典型豹公钥密码体制进行分析讨论。 1 、r s a 密码体制 实现公开密钥加密体制的典型算法是r s a 加密算法。r s a 是由 r r i v e s t 、a s h a m i r 和l a d l e m a n 于1 9 7 8 年提出的。其安全性是基于 数论和许算复杂性理论中的下述论断：求两个大素数的乘积是计算上 容易的。但要分解两个大素数的积求出它的素因子则是困难的。 r s a 体制的密钥对的产生过程如下： ( i ) 选两个大素数，p 和q ，通常均大于1 0 ”o ； ( 2 ) 计算n = p + q 和z = ( p 1 ) ( q 一1 ) ： ( 3 ) 选一个与z 互质的数令其为d ； ( 4 ) 找到一个e ，满足e d = 1m o dz 。 选好这些参数后，将明文划分成块使得每个明文p 长度m 满足 0 i l l n 。加密p 时计算cz p 。( m o dn ) ，解密c 时计算p - - - c ( i n o dn ) 。 由于模运算的对称性，可以证明加密解密在一定范围内是可逆的。 破译r s a 体制的一个直接方法是使用现有的一些分解方法分解模 r l 。可见，r s a 的强度依赖于完成大素数分解的设各的价格和所需的时 间。随着设备的价格的降低和计算能力的提高，r s a 体制的模n 必将随 之增大。目前可分解1 5 5 位十进制的大整数。人们建议使用1 0 2 4 位以 上的模。 与对称密码体制如d e s 相比，r s a 的缺点是加、解密的速度太慢。 因此，r s a 体制很少用于数据加密。然而，r s a 体制有很多重要的应用， 如数字签名、密钥管理和认证。 2 、d i f f ie h e l l m a n 算法 该算法是第一个公钥算法，由美国的d i f f i e 和h e l l m a n 于1 9 7 6 年提出。其安全性源于在有限域上计算离散对数比计算指数更困难，该 算法主要用于密钥交换。协议如下：首先a 与b 协商两个大的素数n 和g ，g 是模n 的本原元；a 选取一个大的随机数x 并且发送给b ：x = 9 1m o dn ；b 选取一个大的随机数y 并且发送给a ：y = g m o dn ；a 计算k ，= y 1i n o dn ：b 计算k 2 = x n l o dn ，k 。和k ：都等于g ”m o dn ，偷 昕者即使知道n ，g ，x 和y ，也无法计算出k ，除非他们计算离散对数， 因为k 是a 与b 的秘密密钥。 3 、椭圆曲线算法 椭圆曲线原是代数几何中的难题，l9 8 5 年由k 0 b liz 和m i l ler 各自将其引入到公钥密码学中，利用椭圆曲线离散对数问题来构造 公钥密码体制。椭圆曲线加密系统是一种相对比较新的技术，已经 逐渐被人们用做基本的数字签名系统。椭圆曲线作为数字签名的基 本原理大致和r s a 与d s a ( d i g i t a ls i g n a t u r ea 1 9 0 t i t h m ) 的功能 相同，并且数字签名的产生与认证的速度要比r s a 和d s a 。 椭圆曲线的吸引人之处在于提供了由“元素”和“组合规 则”来组成群的构造方法，即利用椭圆曲线上的点构成a b e l i a n 加法群构造离散对数问题。基于有限域g f ( 2 n ) 的椭圆曲线算术 运算器很容易构造，并且n 在13 0 位至2 0 0 位之间的实现相当简单， 它提供了一个更快的具有更小密钥长度的公钥算法1 。 4 、e l g a m a l 密码体制 e l g a m a l 算法既可用于数字签名又可用于加密，其安全性依赖计算 有限域上离散对数的难度。 设g 是一个阶为1 3 的有限域，假定g 上的离散对数问题是不可解的。 1 9 8 5 年e l g a m a l 提出了下述基于离散对数问题的公钥密码体制方案， 表现出了陷门函数的特点。 ( 1 ) 、对于一个有限域和其中一个元素a g ，每个用户选定某一随机整 数x ( 秘密密钥) ，公开a 1 ( 公开密钥) 。假定信息为g 中元素，用户a 希望传递信息m 给用户b 。 ( 2 ) 、a 产生一个随机数k 并且计算出七( a 。 ( 3 ) 、a 查找b 的公开密钥a ，计算( a ) 。和1 t l a “。 ( 4 ) 、a 将元素对( a ，m a “) 传递给b 。 ( 5 ) 、b 计算( a ) ，拒此复元信息i n 。 e l g a m a l 密码体制是在密码协议中有者大量应用的一类公钥密码 体制，其安全性是基于离散对数问题的难解性。离