（计算机应用技术专业论文）基于aes与ecc的混合密码体制的研究与实现.pdf

基于a e s 与e c c 的混合密码体制的研究与实现 捅璺 随着i n t e r a c t 越来越被大众所接受与使用，各种商业和社会业务开始转化 为电子形式在网上进行。使用各种各样的加密算法，可以保证这些活动的安全 性。椭圆曲线密码体制是一种公钥密码体制，相对于以往基于有限域上离散对 数问题或大整数分解问题的传统公钥算法，椭圆曲线密码算法具有安全性高、 速度快、密钥短、实现时所需占用资源少的特点。另一方面，最新的密码体制 a e s 具有简洁、高效、安全性高等优点，是对称密码体制中的一个相当好的标 准。 本文通过对现有数据加密体制的分析，提出了一种将a e s 算法和椭圆衄线 密码( e c c ) 体制相结合的混合数据加密体制，从而更为高效地实现了网络通 信系统中的信息加密、数据签名和身份验证，解决了密码体制中速度和安全性 不能兼顾的问题。 本文首先对目前信息安全的现状和数据加密技术的基本概念及数学模型作 了简单综述；其次，研究分析了各种数据加密枝术的思想、方法和应用领域， 给出了对称密码、公钥密码体系的数学描述及其特点；第三，针对数据加密方 法的特点，提出了基于a e s 与e c c 的混合密码体制，并就这两种算法的数学 原理、算法实现、安全性能等方面进行了详细的讨论；最后，给出基于a e s 与 e c c 的混合密码体制的工作流程以及关键算法实现的优化，包括椭圆曲线密码 中的k p 运算、素数检测算法以及大整数间的运算。 关键词：a e s 算法；椭圆曲线密码：混合密码；数字签名 v s t u d ya n dr e a l i z a t i o no fm i x e dc r y p t o s y s t e m b a s e do n a e sa n de c c a b s t r a c t a st h ei n t e r n e tb e c o m e sm o r ea n dm o r ea c c e s s i b l ef o r 吐l ep u b l i c m a n yk i n d s o fc o m m e r c i a la n ds o c i a lb u s i n e s s e sa r et r a n s f o r m e di n t oe l e c t r o n i cf o r ma n da r e c o n d u c t e do nt h en e t w o r k a l lk i n d so fc r y p t o g r a p h i ca l g o r i t h m su s e dc a ni n s u r e s e c u r i t yo f t h e s ea c t i v i t i e s 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 ) s y s t e m s ，w h i c hi sa p u b l i c k e ys y s t e m s ，i sc h a r a c t e r i z e db yh i g h e rs a f e t yp r o p e r t y ，f a s t e rs p e e d ， s h o r t e rk e yl e n g t h sa n df e w e rc o m p u t a t i o n a lr e s o u r c e sf o ri m p l e m e n t a t i o nt h a n o t h e rf o r m e rt r a d i t i o n a lp u b l i c - k e ya l g o r i t h m sb a s e do nt h ed i s c r e t el o g a r i t h mi n f i n i t ef i e l d so rt h eg r e a ti n t e g e rf a c t o r i z a t i o np r o b l e m o nt h eo t h e rh a n d ，t h e a d v a n c e d e n t r y p t i o n s t a n d a r di sag o o d s y m m e t r yc r y p t o s y s t e m w i t hi t s a d v a n t a g e so fs i m p l i c i t y , h i g he f f i c i e n c ya n ds e c u r i t y , t h ep r e s e n td a t ae n c r y p t i o ns y s t e m si sa n a l y z e di nt h ed i s s e r t a t i o nt op r o p o s e t h em i x e dc r y p t o s y s t e mb a s e do nt h ec o m b i n a t i o no ft h ea e sa n de l l i p t i cc u r v e c r y p t o g r a p h y ，w h i c h w i l la c t u a l i z e e n c r y p t o fd a t a , d i g i t a l s i g n a t u r e a n d i d e n t i f i c a t i o nw i t hh i g h e f f i c i e n c yi n i n t e m e tc o m m u n i c a t i o n ，a n ds o l v et h e p r o b l e mo fa n t i n o m yo fs p e e da n ds e c u r i t yi nc r y p t o s y s t e m i nt h i sd i s s e r t a t i o n ，s u m m a r yi sf i r s tg i v e nb r i e f l yo nt h ec u r r e n ts i t u a t i o no f t h e i n f o m m t i o ns e c u r i t ya n dt h eb a s i cn o t i o na sw e l la sm a t h e m a t i c a lm o d e lo fd a t a e n e r y p t i o nt e c h n o l o g y ；s e c o n d l y , r e s e a r c h e sa n da n a l y s e s o nt h et h o u g h t ，t h e m e t l l c ) d o l o g ya n df i e l do fa p p l i c a t i o no fm a n yk i n d so fd a t ae n c r y p t i o nt e c h n o l o g y s h o 、t h en l a t h c m a t i c a ld e s c r i p t i o ng o s y m m e t r yc r y p t o g r a ma n dp u b l i ck y c r 3 ) t c , g r a ma n di t s lh a r a c t e r i s t i c s ；t h r d l y ，t t em i x e dc r y p l o s2 ，s t e mb a s e do na f , s a d i c ci sp u tf o lw a r di na c c o r d i t ! gw i t ht h ec h a r a c t e l i s t i co ft h ee n c r y lj t i o n m e t h o do ft h ed a t aa n dt h ed e t a i l e dd i s c u s s i o ni sh o l do nt w om a t h e m a t i c a l p r i n c i p l e s ，a l g o r i t h mr e a l i z a t i o n ，s a f ep e r f o r m a n c e ，e r e ；f i n a l l y ，w o r k f l o wa n d o p t i m i z a t i o no ft h ek e ya l g o r i t h mr e a l i z a t i o ni sp r o v i d e db a s e do nt h em i x e d c r y p t o s y s t e mo fa e sa n de c c ，i n c l u d i n gk po p e r a t i o n ，t h ed i s p o s i t i o nd e t e c t i o n a l g o r i t h m sa n dg r e a ti n t e g e r so p e r a t i o ni nt h ee l l i p t i cc u r v ec r y p t o s y s t e m k e yw o r d s ：a e s ；e l l i p t i cc u r v ec r y p t ；d i g i t a ls i g n a t u r e ；m i x e dc r y p t v i 插图清单 图1 - 1 加密通信模型3 图2 1d e s 算法流程9 图3 1 椭圆曲线上的点加2 3 图3 - 2 椭圆曲线上点的倍乘2 4 图4 1 ( a ) 1 2 8 位加密过程3 2 图4 一l ( b ) 1 2 8 位解密过程3 2 图4 2 发送方加密、签名流3 8 图4 3 接受方解密、验证签名流3 8 图4 - 4 密钥生成3 9 图4 5 文件加( 解) 密4 0 图4 6 数字签名4 l 图4 7 签名验证4 2 图4 - 8 验证成功4 2 图4 - 9 验证失败4 2 图4 1 0 密钥加密4 3 图4 1 1 密钥解密4 4 表格清单 表2 1 棋盘密码 6 表2 2 单表置换密码表 7 表2 3 三种典型的公钥密码体系性能比较1 3 表3 1 状态矩阵 2 l 表3 2a e s 算法轮数2 l x 独创性声明 本人声明所呈交的学位论文是本人在导师指导一f 进行的研究工作及取锝的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 盒壁至些太堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名：葛尼 签字日期：汐石年多月，舌日 学位论文版权使用授权书 本学位论文作者完全了解盒目b 王些盔堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送变论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金 匿王些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：_ 蓉忘 签字日期：年月日 学位论文作者毕业后去向 工作单位： 通讯地址： l i l = 7 警 电话 邮编 致谢 作为一个同等学历的毕业生，能够完成毕业论文的工作，参加论文的答辩， 我的心情很激动，我在这里要感谢所有帮助我的人。 本人在三年的硕士研究生课程学习和撰写学位论文的过程中，自始至终得 到了我的导师沈明玉副教授的悉- i i , 指导，无论从课程学习、论文选题，还是到 收集资料、论文成稿，都倾注了沈明玉老师的心血，由衷感谢沈明玉老师在学 业指导及各方面所给予我的关心以及从言传身教中学到的为人品质和道德情 操，老师广博的学识、严谨的治学作风、诲人不倦的教育情怀和对事业的忠诚， 必将使我终身受益，并激励我勇往直前。 同时，真诚感谢计算机信息学院的全体老师，他们的教诲为本文的研究提 供了理论基础，并创造了许多必要条件和学习机会；感谢人事处的领导和同仁 们，在我课程学习和论文撰写期间，给予我的大力支持。 我要衷心感谢我工作单位的领导，尤其是安徽师范大学数学计算机学院的 副院长冯年荣老师，他对我的论文工作非常关心，多次给以指导和帮助。 感谢所有的同学给予的帮助。 最后，我要再次感谢我的导师沈明玉副教授，感谢他对我无私的关怀和帮 助! ! 作者： 董尼 2 0 0 6 年4 月2 0 日 1 1 研究背景与意义 第一章综述 随着计算机和通信技术的迅猛发展，大量的敏感信息常常通过公共通信设 旌或计算机网络进行交换，特别是i n t e r a c t 的广泛应用、电子商务和电子政务 的迅速发展，越来越多的个人信息需要严格保密，如：银行帐号、个人隐私等。 因此，如何保护信息的安全使之不被窃取及不至于被篡改或破坏，已成为当今 被普遍关注的重大问题。而目前针对网络的攻击手段更是五花八门，攻击者可 以窃取网络上的信息，如用户口令、数据库信息等：伪造用户身份、否认自己 的签名，这对网络的一步推广和应用构成了严重的威胁。 1 1 1 计算机网络安全防范的基本措施 1 、加强保密管理 要想建立可靠的防范体系，除了在技术上采取必要的措施外，建立与之相 配套的管理措施也是不可或缺的。 2 、安装和应用放火墙技术 适当考虑内网、外网物理隔绝，在连接因特网时，在内网与外网之间建立 防火墙，即在不安全的i n t e m e t 环境下构造一种相对安全的内部网络环境。从 而避免外部网络的安全问题蔓延到内部网络，减少入侵者攻击的路径和机会。 3 、充分利用存驭控剧技术 l 1 ) 身份鉴别方法： 1 2 1 令验证是验谢：用户是否合法，这种验汪方法广泛地应用于各个方面： 通行证验证类似于钥匙，主要是使用磁 和“灵巧卡”， 人类特征验证是验证用户的生物特征或下意识动作的结果如：指纹、视网 膜、语音、手写签名等，人类特征具有很高的个体性和防伪造性。 ( 2 ) 访问权限控制 访问权限控制是指对合法用户进行文件或数据操作权限的限制。这种权限 主要包括对信息资源的读、写、删、改、拷贝、执行等。 ( 3 ) 审计跟踪技术 审计跟踪是一种事后追查手段，它对涉及计算机系统安全保密的操作进行 完整的记录，以便事后能有效地追查事件发生的用户、时间、地点和过程。 4 、数据加密 上述措施虽然有效但有限，主要表现在： 立法和管理只能界定某种行为是否合法，并对非法行为给予处罚并对其损 失进行有限补偿，而无法限制非法行为； 防火墙技术虽然能够阻止外部未授权个人访问内部网络信息，而对来自内 部的攻击根本束手无策； 口令用来防止未授权的个人直接访问敏感数据，然而口令又是非常脆弱的， 特别是在机构内部； 访问控制并不能保证传输数据的安全性，数据在网络上传播时，无论是内 部网还是外部网，任何一个人都可以进行截取或篡改，甚至通信的双方对这种 截取或篡改可能根本一无所知：如果要进行网上交易，必然会遇到更多的安全问 题，如不可否认性，这类问题也不是防火墙和口令所能解决的。 因此，通过采用数据加密技术加强计算机网络安全防范显得尤为重要。使 用数据加密技术，可以很好地实现网络安全防范。数据加密技术被认为是最基 本的网络安全技术，在网络安全中发挥着越来越重要的作用。所谓数据加密技 术，就是对信息重新编码，从而达到隐蔽信息内容，使非授权用户无法获取真 实信息内容的一种手段。数据加密技术不仅用于通信保密，而且还用于信息鉴 别和数字签名等方面。 1 2 基本概念 数据加密技术是以研究数据秘密通信为目的的，即对存储、传输和使用的 信息采取某种秘密的变换以防止第三者的窃取、破坏和篡改。 加密：简单地说，从数学的角度来看，加密就是一组含有参数k 的变换e 。 设已知信息m ，通过变换e k 得密文c ，即c = e k ( m ) ，则，这个过程称之为 加密，e 为加密算法，参数k 称之为密钥，亦即密码：c 为密文，m 为明文。 注：加密算法e 确定后，如果密钥k 不同，密文c 也不同。 解密：从密文c 恢复明文m 的过程称之为解密，即存在变换d 使m = d k ( c ) 解密算法d 是与加密算法e 相反的过程，解密算法也是含参数k 的变换。 发信方：通信双方中发送信息的一方称为发信方，简称发方，另一方为收信方 简称收方。 加密通信模型可用图1 - 1 表示。 图1 - 1 加密通信模型 1 3 数据加密技术的发展 i 3 1 发展概况 数据加密作为一种保障数据安全的技术源远流长，可以追溯到远古时代， 如公元前2 0 0 0 年的古埃及人便使用一些方法来保护他们的书面信息。对信息进 行编码曾被j u l i a n c a e s a r ( 凯撒大帝1 使用，也曾用于历次战争中，包括美国独立 战争、美国内战和两次世界大战。最广为人知的是二战( 1 9 4 2 年) 中德国人用来 加密信息的编码机器g e r m a ne n i g m a ( 英尼格玛) 机。当初，计算机的研究就是为 了破解德国人的密码，当时人们并没有想到计算机给今天带来的信息革命。随 着计算机技术和通信技术的发展，运算能力的增强，过去的密码都变得十分简 单了。于是人们又不断地研究出了新的数据加密方式，如对称密码和非对称密 码。可以说，是计算机推动了数据加密技术的发展。 数据加密研究作为一门新的学科是在2 0 世纪7 0 年代，在近代数据加密研 究中有两件大事值得提：i l j 1 9 7 7 年美国国家标准局和美国国家标准协会a n s i 正式公布实施i b m 公司 研究开发的数据加密标准d e s ，公开它的加密算法，用于非机密单位和商业秘 密通信： d i f i l e 和h e l l m a n 的文章“密码学的新方向”，掀起公钥密码研究的序幕， 各种公钥密码体制被提出，典型的公钥加密算法有r s a 、e t g a m a l 、椭圆盐线 密码等公钥密码体制。 根据加密密钥和解密密钥在性质上的差异，可以将密码体制分为对称密码 和非对称密码两大类。 1 、对称密码 对称密码是指加密密钥和解密密钥相同的数据加密方法称为对称密码，对 称密码体制主要是基于复杂的非线形变换。常用的对称密码算法有a 5 、d e s 、 i d e a 、r c 5 、a e s 等。目前使用最广泛的对称加密算法主要是数据加密标准 d e s ( d a t a e n c r i p t i o ns t a n d a r d ) 。但是由于d e s 中使用的密钥只有6 4 位，加密 强度已经不能满足需要，因此加密强度更高的高级数据加密标准a e s 必将成为 未来对称加密体制的必然选择。 2 、非对称密码 非对称密码又称公钥密码，其基本思想是加密密钥和解密密钥各不相同， 并且从其中一个很难推断出另一个，用其中一个密钥加密的信息只能用与之对 应的另一个密钥解密。公钥密码采用公钥、私钥分别加、解密的方法，使加密 密钥和解密密钥相分离，从而保证保密性，能够很好地解决对称密码所存在的 问题，从技术上打破了对称密码体制的限制。 在公钥密码算法中，目前应用最广泛的是r s a 算法( r i v e s t 、s h a m i r 、 a d l e m a n 三人于1 9 7 8 年提出) 。1 9 8 5 年k o b i t z 和m i l l e r 提出利用椭圆曲线上 的有理点构成a b e l 加法群构造离散对数问题，使其成为构造公开密码体制一个 有力工具。由于椭圆曲线密码体制( e c c ) 具有开销小( 所需计算量小、加密 和签字速度快) 、安全性高( 与同等密钥长度的r s a 相比，椭圆曲线密码安全 性更高) 等优点，所以椭圆曲线密码被普遍认为是经典r s a 系统的最合适替代 者。 1 3 2 密码分析 在信息传输和处理系统中，除了指定的接受者外，还有非授权者。他们通 过各种办法，如搭线窃听、电磁窃听、声音窃听等来窃取机密信息，称其为截 收者。他们虽然不知道系统所用的密钥，但通过分析可能从截获的密文推断出 原来的明文甚至密钥，这一过程称作密码分析。原来的明文经过加密变换显然 掩盖了真面目，然而不是没有留下可以利用的蛛丝马迹。比如字母出现的频率 和前后连缀的关系不会由于简单的置换而不留下痕迹，特别是在单表密码中。 从大量的非技术性英文书记、报刊、文章中摘取适当长度的章节进行统计，发 现英文字母出现的频率有惊人的相似之出，比如e 出现的次数最多，其它如t ， a ，。等出现较多。不仅单个字母如此，相邻的连缀字母也是如此。这就给破泽 密码带来了可乘之机。一般说来，好的加密算法是可以公开的，这种公开主要 是为了方便秘密传输信息双方的加解密操作。 然而实际上，几乎所有的加密方法都是可以攻破的。加密本身的目的是使 密文在有限的时间内不被破译，也就是说如果不能在希望的时间内或实际可能 的经济条件下破译出密文或密钥，这种密码系统是不可破译的，或称这样的密 码系统具有计算安全性( 或实际保密性) 2 1 。 1 4 本文的主要研究工作 近年来，随着i n t e m e t 的日益普及和基于i n t e m e t 的应用的日益增长，网络 4 安全已逐渐成为i n t e m e t 以及各项网络服务和应用进一步发展的关键问题，而 针对网络的攻击手段更是五花八门，攻击者可以窃取网络上的信息，如用户口 令、数据库信息等；伪造用户身份、否认自己的签名，这对网络的一步推广和 应用构成了严重的威胁。 数据加密技术被认为是最基本的网络安全技术，在网络安全中发挥着越来 越重要的作用。本文针对密码学中的各种数据加密的数学方法、实现及其特点 进行了探讨，分析了目前各种数据加密技术存在的问题，并提出了基于a e s 与 椭圆曲线密码( e c c ) 的混合密码体制，然后详细介绍了有关a e s 算法以及椭 圆曲线密码( e c c ) 所涉及的数学原理，在本文的最后，给出了这种混合密码 体制的具体实现方法以及基本的工作流程。 1 5 本章小结 本章主要是对目前信息安全的现状和数据加密技术的基本概念及数学模型 作了一个简单综述，主要包括数据加密技术的研究背景及其意义；数据加密技 术的基本概念及其基本原理；数据加密技术的发展概况。 第二章数据加密体系及其数学原理 数据加密是以研究秘密通信和身份认证等为目的的，主要研究对传输信息 采取何种秘密的变换以防止第三者的窃取、破坏或篡改。 本文所讨论的数据加密技术研究不仅指传统密码技术，而且重点讨论基于 计算机技术和现代数学f 如数论、组合数学等) 方法的数据加密技术，这些数学 基础一方面为加密技术提供了新的概念和工具，当然另一方面也是为了研究改 进、破译现代密码系统的途径打下基础。 2 1 传统密码 2 1 1 传统密码概述 换位和置换( t r a n s p o s i t i o na n ds u b s t i t u t i o nc i p h e r s ) 算法是组成传统密码的 基础。换位和置换在本质上是种字母游戏，数据本身并没有改变，只是被安 排成了另一种不同的格式，所以其破译比较有规律可循相对简单。 主要的换位和置换算法包括棋盘密码、恺撒密码、单表置换等。 2 1 2 几种典型的传统密码 1 、棋盘密码 表2 - 1 棋盘密码 abcde 、 f gh i j k lmnop q rstu wxyz 棋j * ：密即i 【1 1 一在公元前两盼! 出一位希腊入提出，他将2 6 个英文字母排列 在一个5 5 的力1 格里，其中i 和j 填在同一格中，如表2 - 1 所示。于是每个字 母对应个数字lq ，其中e 是该字母所在的行号，n 是列号。如c 对应1 3 ，r 对应4 2 等等。 2 、恺撤密码 恺撒密码 1 1 是每一字母向前推移k 位。例如k = 4 时便有明文和密文对应关 系如下： 明文：a b c d e f g h ij k l m n o p q rs t u v w x y z 密文：ef g h ij k l m n o p q rs t u v w x y z a b c d 不同的k 可以得到不同的密文。若令2 6 个字母分别对应于整数o 2 6 ，则恺 撒加密变换实际上是 c - - - m + km o d2 6 其中，i t i 是明文对应的数据，c 是与明文对应的密文数据，k 是加密用的参 数，亦即密钥。 3 、单表置换密码 这种变换选用一个英文短语( 或单词串) 作为密钥( 称为密钥字或密钥短 语) ，例如h a p p y n e w y e a r ，去掉其中重复的字母得到一个无重复字母的字 符串，即h a p y n e w r 。把它依次写在明文字母表之下，而后再将字母表中未 在字母表中出现过的字母依次写于此短语之后，就可构造出一个字母替换表。 如表2 2 所示【2 1 。 表2 2 单表置换密码表 abcd显，fgh i jklm hapynewrbcdfg no pqrstu vwx yz i jklm0 q s tuvxz 当选择上面的密钥及密钥短语密码进行加密时嘲，若明文为p e n s i o n ，则密文 为j u s k i a s 。实际上：前述两种密码只不过是单表密码的特例。 4 、其他传统密码 1 ) 维吉利5 1 e ( v i g e n e r e ) 密码 维吉利哑密码【2 1 是1 6 世纪法国密码学家b l a s i s ed ev i g e n e r e 所发明l 向，是 典型的多表密码，雉吉利亚密码使：日一个词组作咎钥词组中的每一个字母 都竹- 为移位替换密码的密钥确定一卜替换表，维吉j i j _ f 密码循环使r 日每个替 换表完成明文字母到密文字母们变掺，最后所得到n ，- 密之字母序列引为加密得 到的密文。具体加曾过程如下： 设密钥k = k - k 2 k d ，明文与密文字母表均包含了n 个字母，当使用维吉利亚 密码对明文m = m 衄：进行加密时，得到密文c = c ，c ：，其中 c d = m ”d + k l ( m o dl q ) 其中t 是正整数( 加密算法表示中使用了与移位替换密码相同的明文字母 到数字的转换) 。 例如：假设使用英文字母表( n = 2 6 ) ，选择的密钥字k = s o m u c h 当对 明文m = am a nl i b e r a li nh i sv i e w s 进行加密时，得到密文 c = sa m h n p t s d u np f v u nx p w k e 2 ) 弗纳姆( v e r n a m ) j j f f 密算法 弗纳姆加密算法【2 1 又叫做代数密码。它的编制方法是：将明文和密钥分别 表示成二进制序列，再把它们按位进行模二相加。 设k = k l k 2 k l ，m = m 1 1 1 1 2 , m i ，c = c i c 2 c i 那么c i = m i ok ( i - - o ，1 ，2 ，) 即明文和密钥都是二进制数码，但是，就弗纳姆加密算法而言，只要找到 一组和密码相对应的明文便可破译。 3 ) 希尔( h i l l ) l j h 密算法 希尔加密算法【2 1 的基本思想是将i 个明文字母通过线性变换将它们转换为i 个密文字母，解密只要做一次逆变换就可以了。密钥k 是个变换矩阵。即 m = m l m 2 m i ，c = e k ( m ) = c i c 2 c i ，e 1 2 k l i m + k 1 2 m 2 + + k l i m i( r o o dn ) ic 2 = k 2 m + k 2 2 m 2 + + k 2 i m i( m o dn ) 其中1 l c i = k i l m i + k i 2 m 2 + + k i i m i ( m o dn ) 解密时，先求出密钥k 的逆矩阵k 。( k k = i ，i 为单位矩阵) ，作为解密 密钥。希尔加密算法可以较好地抵抗统计频率的分析，但面对已知明文的攻击 就很容易被破译 2 2 对称密码 2 2 1 典型对称密码 对称密码又杨：保密密码或分绷曾码，它的一个锓老特点是加密毪调阳解密 钥相同上述j 1 中传统加密方。k 都属于对称李i 偶体制，传统密码阵制水质 一j 属于对称密 。e 较典型的著名蚶称密码有d e s 、 d e a 、a e s 等 1 1 e s 概述 d e s ，即d a t ae n c r y t i o ns t a n d a r d 数据加密标准，由i b m 公司研制，1 9 7 7 年美国商业部所属国家标准局正式批准其作为美国联邦信息处理的非机密数据 加密标准。自公布以来，d e s 一直超越国界成为国际上商用保密通信和计算机 通信最常用的加密算法，i s o 也将其作为数据加密标准。 d e s 是一个分组加密算法，他以6 4 位为分组对数据加密。同时d e s 也是 一个对称算法：加密和解密用的是同一个算法。它的密钥长度是5 6 位( 因为每 个第8 位都用作奇偶校验) ，密钥可以是任意的5 6 位的数，而且可以任意时候 改变。其中有极少量的数被认为是弱密钥，但是很容易避开他们。所以保密性 依赖于密钥。 d e s 对6 4 ( b i t ) 位的明文分组m 进行操作，m 经过一个初始置换i p 置换成 m o ，将m o 明文分成左半部分和右半部分m o = ( l o ，r o ) ，各3 2 位长。然后进行1 6 轮完全相同的运算，这些运算被称为函数f ，在运算过程中数据与密钥结合。 经过1 6 轮后，左，右半部分合在一起经过一个末置换，最后所得到的输出即为 密文分组c 。 在每一轮中，密钥位移位，然后再从密钥的5 6 位中选出4 8 位。通过一个 扩展置换将数据的右半部分扩展成4 8 位，并通过一个异或操作替代成新的3 2 位数据，再将其置换换一次。这四步运算构成了函数f 。然后，通过另一个异 或运算，函数f 的输出与左半部分结合，其结果成为新的右半部分，原来的右 半部分成为新的左半部分。将该操作重复1 6 次，具体图2 - l 【lj 所示 2 i d e a 算法概述 图2 - 1d e s 算法流程 1 9 9 0 年x u e j i al a i 和m a s s e y 开发出i d e a 加密算法雏形，称为p e s ，即 “建议的加密标准”。第二年，根据有关专家对这一密码算法的分析结果，设计 9 者对该算法进行了强化并称之为i p e s ，即”改进的建议加密标准”。该算法于 1 9 9 2 年更名为i d e a ，即”国际数据加密算法”1 2 j 。 i d e a 是，一个迭代分组密码，分组长度为6 4 比特，密钥长度为1 2 8 比特。 i d e a 密码中使用了以下三种不同的运算： 1 ) 逐位异或运算； 2 ) 模2 ”加运算； 3 ) 模2 ”+ 1 乘运算，0 与2 ”对应。 具体来说，i d e a 算法是由8 轮迭代和随后的个输出变换组成。它将6 4 比特的数据分成4 个子块，每个1 6 比特，令这网个子块作为迭代第。轮的输h ；， 全部共8 轮迭代。每轮迭代都是4 个予块彼此间以及1 6 比特的子密钥进行异或， 模2 m 加运算，模2 ”+ 1 乘运算。除最后。一轮外把每轮迭代输出的四个子块的第 二和第三子块互换。该算法所需要的”混淆”呵通过连续使用三个”不相容”的群 运算于两个1 6 比特子块来获得，并且陔算法所选择使用的m a ( 乘加) 结构 可提供必要的”扩散”。算法详细描述清参照文献【2 j 。 3 a e s 算法概述 1 9 9 7 年美国国家标准技术研究所发起了征集a e s ( a d v a n e e de n c r y p t i o n s t a n d a r d ) 算法的活动，目的是为了确立一个非保密的、全球免费使用的分组密 码算法。a e s 的基本要求是比三重d e s 快而且安全级别有所提高，分组长度 为1 2 8 比特，密钥长度为1 2 8 1 9 2 2 5 6 比特。a e s 作为d e s 算法的替代者将成 为未来数十年最重要的对称密码算法。2 0 0 1 年夏天，美国国家标准技术协会己 经将j o a nd a e m o n 和v i n c e n tr i j m e n 提出的密码算法r i j i n d a e l ( 算法名称采用了 他们两人姓的组合) 作为下一代对称密码算法的标准。r i j n d a e l 算法在设计时就 考虑到了3 个原n 1 2 1 ： 抵抗己知的密码攻击方法； 兼顾速度和代码大小以适应各种平台的需求： 设计思想简单。 r i j n d a e l 算法是一种迭代分组算法，其分组长度和密钥长度都是可变的， 但是为了满足a e s 的需要，分组长度固定为1 2 8 比特，密钥长度为1 2 8 1 9 2 ，2 5 6 比特，相应的加密轮数为1 0 1 2 1 4 。有关a e s 算法的的详细描述将在第三章给 出。 2 2 2 对称密码的特点 对称密码体制效率高，但通信双方需要事先交换密钥。在告诉接收方密钥 的过程中，还需要防止任何第三方发现或偷听密钥，此过程即密钥发布。此外 对称密钥加密体制中密钥的保存也极不方便，假设网上有n 个用户，为完成两 l o 两通信，需要n ( n 一1 ) 2 个密钥，每个用户需要记录n 1 个密钥【2 】，数量如此之大 只能记录在本子上或存储在计算机中，这本身又是极不安全的。 由此，对称密码体制的特点是： 加密算法和解密算法互逆； 加密密钥和解密密钥相同，效率较高，可以满足大量信息的加密需求 通信双方需要事先交换密钥，密钥容易泄漏而不能确保安全性； 无法实现传输信息的不可否认性： 密钥存储、使用和管理困难。 2 3 公钥密码 2 3 1 公钥密码概述 由于对称密码体制需要事先传送加密密钥而使得保密性受到威胁，再加上 对称密码本身的不足无法实现不可否认的信息传输，因此，在计算机网络上传 输加密数据就迫切需要一种新的加密技术的出现。1 9 7 6 年，d i 衔e 和h e l l m a n 的文章“密码学的新方向”，掀起了公钥密码研究的序幕。 从数论的角度说，任何公钥系统的基础都建立在一个n p 问题f 无法处理的 问题) 之上，即对于特定的问题我们没有办法找到一个多项式时间的算法求解该 问题，一般求解此类问题的算法都是指数时间或者亚指数时间，现有的计算机 体系结构不适于求解此类问题。正因为有了这个理论依据，我们才可以放心地 将公开密钥发送给任何人，而不用担心它利用公钥反推出我们的私钥。 目前比较典型公钥密码体系主要是： 1 1 基于整数因式分解的公钥密码技术，如r s a ； 2 ) 基于离散对数的公钥密码技术，如d s a 、d h 、e i g a m a l ； 3 ) 基于椭圆曲线的公钥密码技术。 公钥密码体系使用的加密技术的安全强度都是基于一些数学难题，这些难 题被专家们认为在短期内不可能得到解决。一些问题( 如因子分解问题) 至今己 有数千年的历史了。公钥密码采用公钥、私钥分别加、解密的方法，使加解密 密钥分离，从而保证保密性。能够很好地解决对称密码所存在的问题。从技术 上打破了对称密码体制的限制。 2 3 2 基于整数因式分解的公钥密码技术 1 r s a 公开密钥密码系统 r s a 算法是r i v e s t ，s h a m i 和a d l e m a n 于1 9 7 7 年提出的一个比较完善的公 钥密码体制。r s a 的基础是数论中的欧拉定理，其安全性基于分解大整数的困 难性，即到目前为止尚无法找到一个有效的算法来分解两个大素数之积。 r s a 算法的过程是： 1 ) 取两个素数p 和q ( 保密) ； 2 ) 计算r l = p q ( 公开) ，币( n ) = 0 1 ) ( q 1 ) ( 保密) ； 3 ) 随机选取整数e 。，满足g c d ( e ，p ( n ) ) = l ( 公开) ； 4 ) 计算d ，满足d e = 1 ( m o d 中( n ) ) ( 保密) 。 利用r s a 加密，第一步需要将明文数字化，并取长度小于l 0 9 2 n 位的数字 做明文块，加密过程和解密过程分别为： 加密：c = e ( m ) - - - r n * ( m o dn ) 解密：d ( c ) = c o ( r o o dn ) r s a 算法之所以具有安全性，是基于数论中的一个事实：即将两个大的质 数合成一个大数很容易，而相反过程则非常困难。由此可见，r s a 的安全性是 依赖于作为公钥的大数1 1 的位数长度的。为保证足够的安全性，一般认为现在 的个人应用需要用3 8 4 或5 1 2 比特位的1 1 ，公司需要用1 0 2 4 比特位的n ，极其 重要的场合应该用2 0 4 8 比特位的n 。 2 保密强度安全评估 r s a 算法的保密强度，随其密钥的长度增加而增强。但是，密钥越长，其 加解密所耗的时间也越长。因此，要根据所保护信息的敏感程度、攻击者破解 所要花的代价值不值得和系统所要求的反应时间来综合考虑决定。尤其对于商 业信息领域更是如此。 r s a 是目前使用最多的公开密钥算法，被应用在加密和数字签名中。随着 因数分解的快速发展，r s a 的安全受到了一定的威胁，目前5 1 2 比特模长已经 不能保证安全。学者们建议使用1 0 2 4 比特模长，预计要保证2 0 年的安全就要 选择1 2 8 0 比特的模长，增大模长带来了实现上的难度。 2 3 3 基于离散对数的公钥密码技术 离散对数问题指的是对于给定大整数g 、x 和素数n ，计算y = g 。m o dn 是容 易的，而反过来，已知y 、g 和n ，求x 使之满足等式y = g 。m o d n 是困难的，离 散对数问题是一个n p 一完全问题。 基于这一技术最著名的算法是美国政府开发的签名算法d s a ( d i g i t a l s i g n a t u r e a l g o r i t l u n ) ，被美国n i s t 作为d s s ( d i g i t a ls i g n a t u r es t a n d a r d ) 。 d s a 是基于整数有限域离散对数难题的，其安全性与r s a 相比差不多。 d s a 的一个重要特点是两个素数公开，这样，当使用别人的p 和q 时，即使不 知道私钥，也能确认它们是否是随机产生的，还是作了手脚，而r s a 算法却作 不到。 2 3 4 基于椭圆曲线的公钥密码技术 1 9 8 5 年。n e i lk o b l i t z 和v i c t o rm i l l e r 分别提出了椭圆曲线密码系统( e e c e l h p t i cc u r v ec r y p t o s y s t e m ) 。椭圆曲线密码系统安全强度不但依赖于在椭圆曲 线上离散对数的分解难度，也依赖于曲线的选择和体制，目前1 6 0 比特长的椭 圆曲线密码体制已经有相当高的安全强度。 椭圆曲线密码体制是一种新的密码算法思想。与传统的密码算法不同的是， 它需要人为构造有限域和定义域中的运算，并将信息通过编码嵌入自构造的有 限域中。椭圆曲线密码体制的安全性由椭圆曲线上的离散对数问题饵c d l p e l 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 ) 确保，这是一个n p 一完全问题，解决 这个问题的时间复杂度为指数级，远远超过了其他公钥密码算法的复杂程度。 椭圆曲线离散对数问题( e c d l p ) 定义：给定素数p 和椭圆曲线e ，对q k p ， 在已知p 、q 的情况下求出小于p 的正整数k 。可以证明，已知k 和p 计算q 比较容易，而由q 和p 计算k 则比较困难，至今没有有效的方法来解决这个问题。 椭圆曲线密码( e c c ) 系统就是以这个数学难题作为基础的。有关e c c 算法的 的详细描述将在第三章给出。 2 3 s 几种典型的公钥密码体系的特点及性能比较 1 公钥密码体制的特点 通信双方不需要事先交换密钥，保密性好； 可以实现数字签名，保证传输信息的不可否认性； 算法基于数学难题，加密效率非常低， 不适合大量信息的加密需求； 密钥管理、信任关系确立需要权威的k d c 支持。 2 三种典型的公钥密码体系性能比较 表2 - 3 t ”l 比较了e c c 、r s a 、d s a 在等价安全强度下所需的密钥尺寸， 假定已知解整数分解问题，离散对数问题和椭圆曲线离散对数问题的最好算法， 考虑需要基于某m i p s ( 每秒运算1 0 0 万条指令) 年破解一个密钥这样的等价强度 下的密钥尺寸。 表2