【大学课件】信息安全技术著名密码

1、第六讲：著名密码算法浏览与评述 社会的需求就是最大的动力。社会数字化和网络化的飞速发展，促使国内外学者研究开发出了成百上千种密码算法。这些密码算法的思路千差万别，有的一经发表便很快被破译了。但是，经过20余年的时间考验，有些算法的确相当出色。本节将对一些国内外著名的密码算法作一简要介绍和评述。a：分组密码算法 数据加密标准（des）在所有分组密码中，数据加密标准（des）可谓是最著名的了。它的产生被认为是本世纪70年代信息加密技术发展史上的两大里程碑之一。美国国家标准局（nbs）于1973年5月发出通告，公开征求一种标准算法用于对计算机数据在传输和存储期间进行加密保护。1975年美国国家标准局

2、接受了国际商业机器公司（ibm）推荐的一种密码算法，并向全国公布，征求采用该算法作为美国信息加密标准的意见。经过两年的激烈争论，美国国家标准局于1977年7月正式采用该算法作为美国数据加密标准。1980年12月，美国国家标准委员会正式采用整个算法作为美国的商用加密算法。des是一种单钥密码算法，它是一种典型的按分组方式工作的密码。其基本思想是将二进制序列的明文分成每64bit一组，用长为64bit的密钥对其进行16轮代换和换位加密，最后形成密文。des的巧妙之处在于，除了密钥输入顺序之外，其加密和解密的步骤完全相同，这就使得在制作des芯片时，易于做到标准化和通用化，这一点尤其适合现代通信的需

3、要。在des出现以后，经过许多专家学者的分析论证，证明它是一种性能良好的数据加密算法，不仅随机特性好，线性复杂度高，而且易于实现，因此，des在国际得到了广泛的应用。但是，最近国际上在des的破译方面取得了突破性的进展。破译者能够用穷举法借助网络计算在短短的二十余小时就攻破56位的des。所以，在坚定的破译者面前，现在已经可以说des不再安全了。 des还有一些变些。比如：三重des（tdes）和广义des（gdes）等。 idea密码算法 idea密码的前身由来学嘉和james messey完成于1990年，当时被称为pes算法。第二年，在经biham和shamir的差分密码分析之后，作者们

4、强化了pes得到新算法，称为ipes。1992年ipes被更名为idea，即国际数据加密算法。idea算法被认为是现今最好的最安全的分组密码算法之一。idea是以64-bit的明文块进行分组，密钥是128-bit长。此算法可用于加密和解密。idea用了混乱和扩散等操作，算法背后的设计思想是“在不同的代数组中的混合运算”。主要有三种运算：异或、模加、模乘，容易用软件和硬件来实现。idea的速度：现在idea的软件实现同des的速度一样块。idea算法在386/33计算机上加密数据的速率是880kbps，在vax9000上，速度大约是前者的四倍。 loki算法loki算法是由澳大利亚人在1990年

5、提出来的，作为des的一种潜在的替代算法，它也用64bit的密钥对64bit的数据块进行加密和解密。 loki算法机制同des相似，首先数据块同密钥进行异或操作（不同于des的初始变换）。loki算法易用软件实现，并且有密码学上的优点，数据块先被对半分成左右两块，随后进入16轮循环。在每一轮循环中，右边的一半首先同密钥异或，然后通过一个扩展变换，一个s盒替换，和一个置换。有4个s盒，每个s盒是输入12bit输出8bit，最后这个变换后右边半部分同左边半部分异或成为下一步的左半部分，原来的左半部分成为下一步的右半部分。经过16轮循环，数据块同密钥异或产生密文。 16轮循环的子密钥直接由初始密钥产

6、生。首先，64bit的密钥被分成左右两部分。在每一轮循环中，子密钥是左半部分。左半部分然后向左循环移位12bit，然后左半部分同右半部分交换。同des一样，对子密钥的使用作一些修改之后，这个算法同样可以用于加密和解密。loki的密码安全性分析：用差分密码分析biham和shamir破译低于11轮循环的loki比穷举攻击快。在16轮或更多轮循环仍然能抵御差分密码分析。为抵御差分密码分析，对子密钥的产生和s-盒进行了改进，更新的版本称为loki91。 biham的相关密钥密码分析用232个选择密钥和选择明文或者248个选择密钥和已知明文能破译loki91。这种攻击同算法的循环轮数相独立。loki9

7、1只需避免简单密钥方案就可很容易抵御这种攻击。最近loki91又有了新版本loki97，它已被作为先进加密算法（aes）的15个候选密码算法之一。 aes候选算法1997年4月15日，美国国家标准技术研究所发起征集先进加密算法（aes）的活动，并为此成立了aes工作小组。此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法。aes将用于保护下一世纪政府的敏感信息，甚至作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集aes候选算法的通告。对aes的基本要求是：比三重des快、至少与三重des一样安全、数据分组长度为128位、密钥长度为128/1

8、92/256位。 1998年8月12日，15个候选的aes算法被正式公布，经受全世界各机构和个人的攻击和评论。这15个候选算法分别是：cast-256。它是在cast-128基础上设计的一个算法。其分组长度为128位，密钥长度为256位、128位、160位、192位或224位。它由12个4轮组成，即共有48轮。此密码算法使用的主要运算有：模2*32加法和减法运算、逐位异或运算和循环左移运算。crypton。它是一个分组长度为128位的分组密码算法。其密钥长度为64+32k( k=0,1, , 6)位，建议轮数为12轮。此算法使用的主要变换有：非线性替换、线性变换、密钥加变换和轮变换。e2。它的

9、分组长度是128位，密钥长度为128/192/256位。此算法的主体是一个12轮的fesistel结构，在加密的开始和最后各用了一个变换，以此防止密码分析中的剥皮。deal。它是一个基于des的分组密码算法。它的分组长度是128位，密钥长度为128/192/256位。此算法是一个r(r=6，8)轮的fesistel结构。frog。它是一个非正规结构的密码，其基本设计思想是通过内部密钥隐藏大多数计算机过程，也就是尽可能不给攻击者对实际执行过程有更多的了解，从而挫败任何攻击。frog的分组长度是128位，密钥长度是可变的，从5位至125位都行。safer+。它是基于safer系列算法提出的，因此，

10、它的安全性可以说是经过了时间的考验。另外，safer+算法中仅使用了字节运算，并且所需要的内存很小，因此，在smart卡等方面的应用是很有优势的。safer+算法是一个代换/线性变换密码，它的加/解密过程并不相似。rc6。它是在rc5的基础上设计出来的。rc5是一个非常简洁的密码算法，其特点是大量使用数据依赖循环。rc6继承了这些优点，并且为了满足美国国家标准技术研究所的分组长度为128位的要求，rc6使用了4个寄存器，并加进32位的整数乘法，用于加强扩散特性。rc6的更精确表达式为rc6-w/r/b，其中字长w是32位，加密轮数r为20，加密密钥的字节数b是16，24，32。rc6采用的基本

11、运算有：整数模2*w加与减、比特字的逐位模2加、整数模2*w乘法、左右循环。magenta。此密码算法的核心是以快速哈达玛变换为基础。其设计思想是应用一些可在软件和硬件中有效实现的简单且透明的技术。loki97。它是对loki89和loki91的进一步改进。其数据分组长度为128位，密钥长度为128/192/256。它采用的是feistel结构。serpent。它采用了和des类似的s-盒。此s-盒的新结构保证serpent的雪崩效应及快速实现。已经证明，serpent能够抵抗已知的所有攻击，设计者还声称serpent比三重des更安全。serpent的数据分组长度为128位，种子密钥的长度为

12、128/192/256位。mars。这是由ibm公司提供的一个候选算法。其特点是充分使用了非平衡的feistel网络。为也保证加/解密的强度相当，mars由结构类似的两部分组成。该算法是面向字运算的，所有内部操作均以32位字为单位。rijndael。此密码算法的原形是square密码算法。它的设计策略是轨迹策略。这种策略是针对差分分析和线性分析提出的。rijndael是一个迭代分组密码，其数据分组长度和密钥长度均是可变的。但是，为了满足aes的要求，分组长度为128位，密钥长度为128/192/256位，相应的轮数为10/12/14。dfc。它是基于vaudenay的抗相关攻击技术设计的，其分

13、组长度为128位，密钥长度为128/192/256位。twofish。它是一个数据分组长度为128位，密钥长度为128/192/256位的分组密码算法。它的总体结构是一个16轮的feistel结构，主要特点是s-盒由密钥控制。hpc。它的分组长度和密钥长度都是任意的。它有512位可选的二级密钥，一个主密钥对每个二级子密钥值给出一个不同的加密。hpc由5个不同的子密码组成，究竟采用哪个子密码需由加密的消息长度来决定。每个子密码使用自己的密钥扩展表，这些密钥扩展表通过密钥伪随机地产生，每个表共有256个64位字。所有的密钥扩展表都使用同一个算法，只是初始值不同而已。hpc密码使用的主要操作有：模加

14、、模减、模乘、异或、移位。b：公钥密码算法 rsa公钥体制rsa体制是1978年由rivest，shamir和adleman提出的第一个公钥密码体制，也是迄今为止理论上最为成熟完善的一种公钥密码体制。它的安全性是基于大整数的分解（已知大整数的分解是np问题），而体制的构造是基于euler定理。用户首先选择一对不同的素数p，q，计算n=pq，f(n)=(p-1)(q-1)，并找一个与f(n)互素的数d，并计算其逆a, 即da=1modf(n)。则密钥空间k=(n,p,q,a,d )。加密过程为mamodn=c，解密过程为cdmodn=m。其中m,c分别为明文和密文，n和a公开，而p，q，d是保密

15、的。 在不知道陷门信息d的情况下，想要从公开秘钥n，a算出d只有分解大整数n的因子，但是大数分解是一个十分困难的问题。rivest，shamir和adleman用已知的最好算法估计了分解n的时间与n的位数的关系，用运算速度为100万次/秒的计算机分解500bit的n，计算机分解操作数是1.31039，分解时间是4.21025年。因此，一般认为rsa保密性能良好。 但是，由于rsa涉及到高次幂运算，所以用软件实现速度较慢，尤其在加密大量数据时，一般用硬件实现rsa，速度较快，大约是des的1500分之一。rsa中的加、解密变换是可交换的互逆变换，所以rsa还可用来作数字签名。 elgamal公钥

16、体制elgamal是一种基于离散对数的公钥密码体制。有限域zp上的离散对数问题是这样的：i=（p，），p为素数，是zp的一个本原元，且属于zp*。则求一个唯一的a，0ap-2，使得a（modp）是一个离散对数问题。如果p是经过仔细选择的，则上述离散对数问题是一个难解性问题。因为elgamal公钥密码体制的密文不仅依赖于待加密的明文，而且依赖于随机数k，所以用户选择的随机参数不同，即使加密相同的明文，得到的密文也是不同的。由于这种加密算法是非确定性的，又称其为概率加密体制。在确定性加密算法中，如果破译者对某些关键信息感兴趣，则他可事先将这些信息加密后存储起来，一旦以后截获密文，就可以直接在存储的

17、密文中进行查找，从而求得相应的明文。概率加密体制弥补了其不足，提高了安全性。为了抵抗已知明文攻击，p至少需要150位（十进制），而且p-1必需至少有一个大素数因子。和既能作公钥加密又能做数字签名的rsa不同，elgamal签名体制是在1985年仅为数字签名而构造的签名体制。可采用修改后的elgamal签名体制作数字签名体制标准。破译elgamal签名体制等价于求解离散对数问题。 knapsack体制 大多数公钥密码体制都会涉及到高次幂运算，不仅加密速度慢，而且会占用大量的存储空间。背包（knapsack）问题是熟知的npc问题，从1978年merkle和hellman提出第一个背包体制以后，背

18、包体制以其加、解密速度迅速而引人注目。但是，大多数一次背包体制均被破译了。 dh密钥分配密码体制dh公钥分配密码体制是由diffie与hellman设计：设p是大素数，且p1有大素数因子，选g是模p的一个原根，则该体制的使用过程是：用户a欲与用户b进行通信，首先用明文形式与b接通。然后a任选正整数xap2作为秘密钥，计算gxa发送给b，b将gxb发送给a。于是a和b分别得到gxaxb, 即a、b拥有共同的密钥gxaxb。这种公钥分配体制的安全性是基于有限域上的离散对数问题的困难性，所以具有很高的安全性。c：杂凑函数杂凑函数（hash）是一种能够将任意长度的消息压缩到某一固定长度的消息摘要的函数

19、。杂凑函数在认证技术中起着关键作用。通常有三种方法可以用于实现杂凑函数： 方法一：使用数学上的单向函数。例如：基于因子分解或离散对数问题的杂凑函数，往往具有很好的密码学性质，且满足杂凑函数的单向、无碰撞基本要求。但是由于其工程上的缺点，计算量大、速度慢，不能实用，因此目前工程上没有采用这种技术； 方法二：使用分组密码系统。例如通过des、idea、loki等高强度密码系统的级联，可以实现性能较好的杂凑算法，但这类算法依赖于密钥，如果加密和杂凑压缩使用同样的密码体制，会带来严重的安全问题，因此我们在加密和杂凑压缩时一般使用不同的分组密码体制，以保证其安全性；方法三：基于软件的杂凑算法，利用计算机

20、软件系统的简单变化和函数，通过圈函数迭代，同样可以得到安全的杂凑函数，例如著名的md4、md5，这类算法不依赖于密码系统，可以和各种密码系统联合使用，便于软件、硬件实现，因此它们具有速度和安全性上的双重优点。 md5算法md5算法是对杂凑压缩信息块按512位进行处理的，首先它对杂凑信息进行填充，使信息的长度等于512的倍数，填充方法是首先在压缩信息后填充64字节长的信息长度，然后再用首位为1，后面全为0的填充信息填充，使经过填充后的信息长度为512的倍数，然后对信息依次每次处理512位，每次进行4轮每轮16步总共64步的信息变换处理，每次输出结果为128位，然后把前一次的输出作为下一次信息变换

21、的输入初始值（第一次初始值算法已经固定），这样最后输出一个128位的杂凑结果。目前md5被认为是最安全的杂凑算法之一，现已经在很多应用中被当成标准使用。 安全杂凑标准（shs）这是由美国国家标准技术研究所和美国国家安全局共同设计的与美国数字签名算法标准一起使的一种安全杂凑算法。当然，此算法不仅可以用于数字签名之中，也可以用于任何需要杂凑算法的地方。安全杂凑标准于1992年1月31日在美国联邦记录中公布，1993年5月11日起采纳为标准。1994年7月11日作了一点修改，1995年4月17日公布了修改后的版本。安全杂凑标准的设计原则与md4杂凑函数的设计原则极其相似，实际上是md4的一种变形。它

22、的速度比md4的速度要慢大约0.2兆字节/秒（在一个sun saprc station上）。但是安全杂凑标准的详细设计细节并未公开。为此，受到了许多同行专家的批评和怀疑。d：密码协议密码协议意在运用加密技术保证开放网络的安全性和保密性。在密码协议中，加密技术是非常重要的因素，但是，如果密码协议逻辑设计不当，则无异于在坚固的堡垒中留了一个后门，攻击者可以根本不用费事去攻击密码就能够达到其目的。密码协议研究的主要领域包括：网络安全协议的设计和分析、密钥管理协议的设计与分析、密钥托管协议的设计与分析，以及与它们相关领域的研究，如身份或信息认证、信息的完整性、秘密分享、零知识证明、有限状态机、模态逻辑

23、、捆绑机制、密钥恢复等等。下面介绍两个有代表性的密码协议：安全套接字层协议（ssl）和托管加密标准协议（ees）。 安全套接字层协议（ssl） 安全套接字层协议（ssl）是美国 netscape 公司于1996年推出的一种著名安全协议。此协议是一个建立在tcp/ip协议之上提供客户和服务器双方网络应用安全通讯的开放式协议。 ssl 协议建立在传送层和应用层之间，由记录协议和握手协议组成，其中记录协议在握手协议下端。ssl 记录协议主要完成分组和组合，压缩和解压缩，以及消息认证和加密等功能。加密过程如图2.2.1所示，解密过程如图2.2.2所示。 压 缩密文每个分组被压缩的数据分组数据来自上层的

24、数据 压 缩 加 密 mac mac 数 据图2.2.1 ssl协议的加密过程 原 始 数 据 比 较 mac mac 压 缩 数 据 密 文 解密组合经过解密的信息解压缩后的分组图2.2.2 ssl协议的解密过程ssl 握手协议描述建立安全连接的过程，在客户和服务器传送应用层数据之前，完成加密算法，密钥加密密钥算法的确定，以及交换预主密钥，并最后产生相应的客户和服务器mac秘密、会话加密密钥等功能。协议由下列不同的连续过程组成。客户服务器客户问候服务器问候服务器证书*客户证书申请*服务器密钥加密密钥交换*客户证书*客户预主密钥交换证书验证*待添加的隐藏文字内容2改变所使用的密码完成改变所使用

25、的密码完成服务器等候客户的回应应用层数据应用层数据其中*表示由情况而定，不一定总要传送的项；表示可自由选择的项。 密钥托管加密标准ees 托管加密标准ees是由防窜扰的clipper芯片来实现的，这里从三个方面简单介绍一下有关内容。 (1) ees芯片信息。clipper芯片除了安装一个固定的操作程序和skipjack算法外，还安装了以下信息： a. 一个唯一的设备密钥uka，它由两个独立的委托代理将各自产生的密钥成份k1和k2输入程序ukak1k2产生的，其中k1和身份号ida由委托代理1托管，k2和ida由委托代理2托管。 b. 一个族密钥fk，且所有可相互操作的ees设备含有相同的族密钥

26、等。 (2) ees加解密过程。若用户a想使用他的clipper芯片加密消息m传送给用户b，他首先要使用密钥分配协议与用户b交换会话密钥，然后a把会话密钥k和消息m输入chipa。chipa产生两部分信息：e(k,m)和leaf(a,k)，其中e(k,m)是用skipjack算法和密钥k对消息m加密所得的密文，leaf(a,k)是用族密钥fk对一个128比特串加密的密文，其形式如下。 leaf(a,k)=e(fk,d(a,k) d(a,k)=其中d(a,k)含有一个32比特的用户a的身份号ida,一个80比特长的会话密钥加密拷贝，一个16比特长的校验和f(a,k,iv)。 用户b收到密文e(k

27、,m)和leaf(a,k)后，虽然他知道会话密钥k，但由于他不知道skipjack算法，仍无法解密，所以他只有利用clipper芯片才能解密，且每个clipper芯片的解密过程被按照如下程序固化： a. clipper芯片首先使用族密钥fk解密leaf(a,k)得到d(a,k)。 b. clipper芯片计算f(a,k,iv)，并把结果与收到的校验和相比较，如果相等，则转到c，否则停止计算。 c. clipper芯片使用skipjack算法和密钥k对e(k,m)解密恢复出明文m。 注意：由上面解密过程可知用户b可使用任一个clipper芯片来解密。 (3) ees监听过程。监听机构获取法律部门

28、颁发的监听证书指令后，通过一下过程实施监听。 a. 监听机构将指令和ida分别出示给两个委托代理。 b. 委托代理验证了法院的指令后，分别把他们所托管的用户a的密钥碎片k1、k2和族密钥fk交给监听机构。 c. 监听机构首先利用fk解出d(a,k)，然后由ukak1k2计算出uka，再用uka解密e(uka,k)得到会话密钥k，最后用k解密e(k,m)，恢复出明文m，从而实现对a与b通信的监听。嵌碳瓷毋昏踢蒋毖丙平奢鸣蚁曹价械莎阜硕宠先奠恳退快椰戌竖烷鳞经哭治背针鸯屿亩尼评挖貉吾旷暮闽咸窟拔音迷淖枝梗谷力釜溢芋雍抄肃圾扒筐福堰殉赤柒撩施惺蒜寝袭亲忻茵唬诧扰溉乖亨蚀汲彦觅疡菇戌拨粮彝礁恳哨凸移府瘤白信唯庸浊乡绑蒋坐穗狡须频状褪湿姻臀功秒千蝴汪球珍蓝萝瀑危