计算机网络与信息安全课件-第章 密码学.doc

.第四章 密码学密码学的起源可追溯到人类语言的出现。当人们想确保他们通信的机密的时候，密码学的诞生就是不可避免了。古希腊人的斯巴达人可能是最早有意识地使用一些技术方法来加密信息的人。他们的加密设备是一根叫的棍子。写信人先将一个纸条绕在棍子上，然后把要写的信在棍子表面上按照与纸条缠绕方向垂直的方向写在纸上，接着将纸条取下，送给收信人。如果不知道棍子的宽度（这里作为密钥）是不可能解密信里面的内容的。后来，罗马的军队用凯撒密码（三个字母表轮换）进行通信。在随后的19个世纪里面，主要是发明一些更加高明的加密技术，这些技术的安全性通常依赖于用户赋予它们多大的信任程度。在19世纪Kerchoffs写下了现代密码学的原理。其中一个重要的原理是：加密体系的安全性并不依赖于加密的方法本身，而是依赖于所使用的密钥。一般说来为了实现保密的通信必须提供下面三种服务：数据保密 传输的信息除了指定的接收者其他人无法解密。身份鉴别 传输通信的双方能够相互鉴别身份。保证数据完整性 保证接收者收到的信息与发送者发送的信息相同，并且能够检测到信息被破坏。密码学的研究目标就是设计能够实现上述三种服务的各种算法。在本章介绍的算法包括：分组加密算法、公开密钥加密算法、文摘算法。通过组合使用这些算法可全部实现这些服务。4.1密码理论与技术研究现状及发展趋势现代密码学主要包括两部分，即基于数学的密码理论与技术（包括公钥密码、分组加密算法、流加密算法、认证码、数字签名、Hash函数、身份识别、密钥管理、PKI技术等）和非数学的密码理论与技术（包括信息隐形，量子密码，基于生物特征的识别理论与技术）。自从1976年公钥密码的思想提出以来，国际上已经出现了许多种公钥密码体制，但比较流行的主要有两类：一类是基于大整数因子分解问题的，其中最典型的代表是RSA；另一类是基于离散对数问题的，比如ElGamal公钥密码和椭圆曲线公钥密码。由于分解大整数的能力日益增强，所以对RSA的安全带来了一定的威胁。目前768比特模长的RSA已不安全。一般建议使用1024比特模长，预计要保证20年的安全就要选择1280比特的模长，增大模长带来了实现上的难度。而基于离散对数问题的公钥密码在目前技术下512比特模长就能够保证其安全性。特别是椭圆曲线上的离散对数的计算要比有限域上的离散对数的计算更困难，目前技术下只需要160比特模长即可，适合于智能卡的实现，因而受到国内外学者的广泛关注。国际上制定了椭圆曲线公钥密码标准IEEEP1363，目前许多公司开发出了符合该标准的椭圆曲线公钥密码产品。公钥密码主要用于数字签名和密钥分配。目前数字签名的研究内容非常丰富，包括普通签名和特殊签名。特殊签名有盲签名，代理签名，群签名，不可否认签名，公平盲签名，门限签名，具有消息恢复功能的签名等，它与具体应用环境密切相关。数字签名的应用涉及到法律问题，美国联邦政府基于有限域上的离散对数问题制定了自己的数字签名标准（DSS），部分州已制定了数字签名法。法国是第一个制定数字签名法的国家，其他国家也正在实施之中。在密钥管理方面，国际上都有一些大的举动，比如1993年美国提出的密钥托管理论和技术、国际标准化组织制定的X.509标准（已经发展到第3版本）以及麻省理工学院开发的Kerboros协议(已经发展到第5版本)等，这些工作影响很大。密钥管理中还有一种很重要的技术就是秘密共享技术，它是一种分割秘密的技术，目的是阻止秘密过于集中，自从1979年Shamir提出这种思想以来，秘密共享理论和技术达到了空前的发展和应用，特别是其应用至今人们仍十分关注。文摘函数主要用于完整性校验和提高数字签名的有效性，目前已经提出了很多方案。美国已经制定了Hash标准-SHA-1，与其数字签名标准匹配使用。由于技术的原因，美国目前正准备更新其Hash标准，另外，欧洲也正在制定Hash标准。近年来，我国学者在文摘函数方面的研究上做出了重大的突破，2004年，以山东大学的王小云为首的团队破解了MD5、SHA-1两大文摘算法，震惊了世界。在身份识别的研究中，最令人瞩目的识别方案有两类：一类是1984年Shamir提出的基于身份的识别方案，另一类是1986年Fiat等人提出的零知识身份识别方案。随后，人们在这两类方案的基础上又提出了一系列实用的身份识别方案，比如，Schnorr识别方案、Okamoto 识别方案、Guillou-Quisquater识别方案、Feige-Fiat-Shamir识别方案等。目前人们所关注的是身份识别方案与具体应用环境的有机结合。美国早在1977年就制定了自己的数据加密标准（DES，一种分组加密算法），但除了公布具体的算法之外，从来不公布详细的设计规则和方法。随着美国的数据加密标准的出现，人们对分组密码展开了深入的研究和讨论，设计了大量的分组密码，给出了一系列的评测准则。其他国家，如日本和苏联也纷纷提出了自己的数据加密标准。但在这些分组密码中能被人们普遍接受和认可的算法却寥寥无几。何况一些好的算法已经被攻破或已经不适用于技术的发展要求。比如DES已经于1997年6月17日被攻破。美国从1997年1月起，开始征集、制定和评估新一代数据加密标准（称作AES）。2001年由两位比利时密码学家设计的Rijdael算法最后胜出。AES活动使得国际上又掀起了一次研究分组密码的新高潮。同时国外为适应技术发展的需求也加快了其他密码标准的更新，比如SHA-1和FIPS140-1。目前最为人们所关注的实用密码技术是PKI技术。国外的PKI应用已经开始，开发PKI的厂商也有多家。许多厂家，如Baltimore、Entrust等推出了可以应用的PKI产品，有些公司如VeriSign等已经开始提供PKI服务。网络许多应用正在使用PKI技术来保证网络的认证、不可否认、加解密和密钥管理等。尽管如此，总的说来PKI技术仍在发展中。按照国外一些调查公司的说法，PKI系统仅仅还是在做示范工程。IDC公司的Internet安全资深分析家认为：PKI技术将成为所有应用的计算基础结构的核心部件，包括那些越出传统网络界限的应用。B2B电子商务活动需要的认证、不可否认等只有PKI产品才有能力提供这些功能。目前国际上对非数学的密码理论与技术（包括信息隐形，量子密码，基于生物特征的识别理论与技术等）非常关注，讨论也非常活跃。信息隐藏将在未来网络中保护信息免于破坏起到重要作用，信息隐藏是网络环境下把机密信息隐藏在大量信息中不让对方发觉的一种方法。特别是图象叠加、数字水印、潜信道、隐匿协议等的理论与技术的研究已经引起人们的重视。1996年以来，国际上召开了多次有关信息隐藏的专业研讨会。基于生物特征（比如手形、指纹、语音、视网膜、虹膜、脸形、DNA等）的识别理论与技术已有所发展，形成了一些理论和技术，也形成了一些产品，这类产品往往由于成本高而未被广泛采用。1969年美国哥伦比亚大学的Wiesner创造性地提出了共轭编码的概念，遗憾的是他的这一思想当时没有被人们接受。十年后，源于共轭编码概念的量子密码理论与技术才取得了令人惊异的进步，已先后在自由空间和商用光纤中完成了单光子密钥交换协议，英国BT实验室通过30公里的光纤信道实现了每秒20k比特的密钥分配。近年来，英、美、日等国的许多大学和研究机构竞相投入到量子密码的研究之中，更大的计划在欧洲进行。到目前为止，主要有三大类量子密码实现方案：一是基于单光子量子信道中测不准原理的；二是基于量子相关信道中Bell原理的；三是基于两个非正交量子态性质的。但许多问题还有待于研究。比如，寻找相应的量子效应以便提出更多的量子密钥分配协议，量子加密理论的形成和完善，量子密码协议的安全性分析方法研究，量子加密算法的开发，量子密码的实用化等。总的来说，非数学的密码理论与技术还处于探索之中。密码技术特别是加密技术是信息安全技术中的核心技术，国家关键基础设施中不可能引进或采用别人的加密技术，只能自主开发。我们必须要有我们自己的算法，自己的一套标准，自己的一套体系，来对付未来的挑战。目前我国在密码技术的应用水平方面与国外还有一定的差距。4.2分组加密算法密码学的基本目标是使两个在不安全信道中通信的人，通常称为Alice（A）和Bob（B），能够保密通信，也就是使窥探者无法理解通信的内容。A向B发送的信息称为明文，A使用事先商量好的密钥对明文进行加密，加密的结果称为密文。在传送密文的过程中，窥探者即使窃听到密文，也无法得到明文。而由于B知道密钥，则他对密文解密得到明文。对称密钥加密算法在加密和解密时使用同一密钥。对称密钥加密算法包括分组加密算法和流加密算法。分组加密算法每次对固定长度的明文加密。流加密算法每次加密的单位是字节。对称密钥加密系统的模型如图4-1所示。A将明文x通过以密钥k为参数的加密函数E变换成密文y=E(k,x)，B得到密文y，通过以密钥k为参数的解密函数D变换成明文x=D(k,y)。图4-1对称密钥加密模型当今大多数分组加密算法都是迭代型加密算法。迭代型加密算法定义了一个轮函数和一个密钥扩展算法，对一个明文块的加密结果是通过多轮（Nr）迭代调用轮函数对明文加密得到的。下面看一下一个典型的迭代型加密算法是如何加密的。设加密算法的输入是块w，密钥为K。首先通过密钥扩展算法将K扩展为一组等长的轮密钥：K1，K2，,KNr。轮函数g以当前状态wi-1和轮密钥Ki作为输入。下一个状态定义为：wi=g(wi-1,Ki)。初始状态w0设为明文x，密文y定义为经过所有Nr轮后的状态。整个加密过程如下：w0xw1g(w0,K1)w2g(w1,K2).wNr-1g(wNr-2,KNr-1)wNrg(wNr-1,KNr)ywNr为了能解密，轮函数g在密钥固定的条件下，必须是单射函数，这等价于存在函数g-1,对于所有的w和y，有g-1(g(w,y),y)=w。解密过程如下：wNrywNr-1g-1(wNr,KNr).w1g(w2,K2)w0g(w1,K1)xw0对称密钥加密算法的主要参数是密钥长度和块长度。密钥的长度对应着算法抵抗密钥穷举蛮攻击的能力。上世纪70年代美国的数据加密标准（DES）算法的密钥长度是56位。随着计算能力提高，DES的加密强度已经不能满足安全的需要，因此在上世纪90年代出现了一批128位密钥长度的算法，其中包括IDEA、RC2、RC5、CAST5和BLOWFISH 等。而最新的高级数据加密标准AES的候选算法的密钥长度更是达到了256位以上。4.2.1 IDEA算法IDEA(International Data Encryption Algorithm)是由中国学者来学嘉和著名密码学家James Massey于1990年联合提出，后于1992年修改完成。它的明文与密文块长度都是64位，密钥长度为128位。加密与解密使用相同算法，但使用的子密钥不同。这是与多数分组加密算法不同的。子密钥由算法的128-bit密钥通过密钥扩展生成。IDEA算法的的加解密运算是8重循环。IDEA的加密循环如下图:图4-2 IDEA算法，M1M4是由64bit明文块经字节顺序变换生成的4个16bit整数，C1C4为加密结果，是4个16bit整数，可经过反变换的到密文（字节顺序变换在4.5节介绍）。Ki,j代表密钥，其中i 代表该密钥在哪一轮被使用。IDEA使用的三种计算操作是异或，模65536加法和模65537乘法。65537是一个质数，以它为模保证了取模乘法的可逆性。IDEA算法的128-bit密钥通过密钥扩展算法生成52个加密子密钥，其中每个加密循环使用6个，最后的变换用4个。IDEA算法的密钥扩展将128-bit密钥看作一个环形，从第二个字节向后每次取16-bit作为一个加密子密钥，直到全部得到52个加密密钥。解密子密钥和加密子密钥是不同的，可通过加密子密钥得到，其对应关系如下: 加密密钥: K1,1 K1,2 K1,3 K1,4 K1,5 K1,6 K2,1 K2,2 K2,3 K2,4 K2,5 K2,6 ： ： ： ： K8,1 K8,2 K8,3 K8,4 K8,5 K8,6 K9,1 K9,2 K9,3 K9,4 解密子密钥 K9,1-1 -K9,2 -K9,3 K9,4-1 K8,5 K8,6 K8,1-1 -K8,2 -K8,3 K8,4-1 ： ： ： ： K2,5 K2,6 K2,1-1 -K2,2 -K2,3 K2,4-1 K1,5 K1,6 K1,1-1 -K1,2 -K1,3 K1,4-14.2.2 IDEA算法的可逆性IDEA算法的加密过程与解密过程相同，但使用不同的密钥。这有助于减少硬件实现的器件数量。设X1，X2，X3，X4为最后一个IDEA加密循环的输入，密钥为K8,1 K8,2 K8,3 K8,4 K8,5 K8,6，X1 X2 X3 X4 为此循环的输出。由算法可知:A = (X2X4+(X1X3)* K8,5)*K8,6B =(X1X3)* K8,5 + AX1 = X1AX2 = X3BX3 = X2AX4 = X4B C1 = X1* K9,1 C2 = X2+ K9,2 C3 = X3+ K9,3 C4 = X4* K9,4解密时使用同一算法，但使用不同的密钥。在解密过程第一轮的密钥为K9,1-1，-K9,2，-K9,3，K9,4-1，K8,5，K8,6，输入为C1C4，则解密运算为: C1* K9,1-1 = X1 C2- K9,2 = X2 C3- K9,3 = X3 C4* K9,4-1 = X4由IDEA算法可知：(X2X4+(X1X3)* K8,5)* K8,6 = (X2X4+(X1X3)* K8,5)* K8,6= A(X1X3)* K8,6 + A = (X1X3)* K8,6 + A=B因此：X1A = X1X3B = X2X2A = X3X4B = X4结果为IDEA加密循环倒数第二轮的输出。由此上推，可以证明IDEA算法的解密过程的最终结果是明文M1M4。因此可知IDEA算法是正确的。4.2.3 IDEA算法的实现在IDEA算法中最耗时的一种操作是模65537乘法，提高此操作的速度是提高IDEA算法实现速度的关键。下面给出几种提高模65537乘法速度的方法。 1 高低算法 两个十六位的整数相乘结果为32-bit的整数，设为p。其高16 位为a，低16 位为b，则p=a(216+1)+(b-a) ，即b-a= p mod 65537。如果ba， 则b-a=b-a + 216+1 = b-a +1 mod 65537。 2 查表法 预计算指数表和对数表: 1 计算3的指数表。即：计算从30（mod 65537）到365536（mod 65537）。 2 根据3的指数表计算1到65536在模65537乘法下的底数为3的对数表。 基于指数对数表的两个16位整数A，B的乘法算法为： 1 查对数表得到LOG3(A)，LOG3(B)。 2 将二数相得到LOG3(A*B)。 3 由LOG3(A*B)查指数表得到A*B 这样模65537乘法就变成了三次查表一次相加。在当今的CPU上只须很少的指令周期，而65537乘法则至少20个指令周期。由于预计算量很大，两个表存储空间需求很大，因此要根据具体情况来决定是否采用这种算法。 IDEA算法是128-bit算法中安全性最好的，它在设计期间就考虑了如何抵抗各种现有攻击方法。因此IDEA算法能够抵御现有的攻击方法。到目前还未有对IDEA算法的成功攻击的报道。已知的IDEA的缺点是算法存在251个弱密钥。但IDEA有2128个密钥，通过简单的方法就可以避免使用这些弱密钥。IDEA算法在理论和应用上都是安全的，并且被广泛深入地研究。4.3高级加密标准1977年颁布的数据加密标准DES算法，其56位长的密钥空间在计算技术高速发展的今天，越来越不适应安全需求。1997年9月美国国家标准技术研究所(NIST)提出了征求新的加密标准-AES（Advanced Encryption Standard）的建议，作为一种取代DES的二十一世纪加密标准技术。其目标是：（1）执行速度快；（2）易于设计；（3）从大型计算机到智能IC卡（CPU卡）都可实现。在1998年8月举行的第一次AES会议（AES1）上，宣布了来自12个国家的15种候选AES算法。于1999年8月举行的第二次AES会议（AES2）上，从中筛选出5个候选算法，下边列出了这些算法，每个条目的内容为：算法名，作者，（国家）。(1) MARS IBM (美国)(2) RC6 RSA Laboratories(美国)(3) Rijndael John Danemen,Vincent Rijmen(比利时)(4) Serpent Ross Anderson(英国),Eli Bihan(以色列), Lars Knudsen(挪威)(5) Twofish Bruce Schneier,John Kelsey, Doug Whiting, David Wagner, Chris Hall,Nids Ferguson经过大量的分析及评估后，NIST最终选择了Rijndael。这是在考虑安全，性能，效率，易用和灵活等诸多方面做的一种权衡选择,正如NIST在其报告中称：将这五种算法的任何一个作为AES都是安全的。Rijdael的设计中贯穿着三个标准： 能够抵抗现有的各种攻击; 在各种平台上都可高速度实现，并且代码占用空间小; 简单。Rijndael之所以最后当选是由于它集安全性、性能、效率、可实现性以及灵活性于一身。4.3.1 AES数学基础知识AES的许多运算是字节运算，还有一些运算是按32位字定义的。其中一个字节看成是有限域GF(28)中的一个元素，一个4字节的字看成是系数在GF(28)中并且次数小于4的多项式。有限域GF(28)中的元素可以用许多种不同的方式来表示，但不同的表示方式对实现的复杂度是有影响的。AES选择用多项式表示有限域GF(28)中的元素。GF(28)中的所有元素为所有系数在GF(2)中并且次数小于8的多项式。字节bb0b1b2b3b4b5b6b7对应于如下多项式：b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x + b0例如: 字节57 (01010111) 对应多项式:x6 + x4 + x2 + x + 1 .运算有限域GF(28)中的两个元素相加，结果是一个多项式，其系数是两个元素中对应多项式的系数的模2加。显然，有限域GF(28)中两个元素的加法与两个字节的按位模2加法是一致的。两个字节的按位模2加用表示，例如：57 83 = D4, 对应的多项式加法为:( x6 + x4 + x2 + x + 1 ) + ( x7 + x + 1) = x7 + x6 + x4 + x2 .有限域GF(28)中两个元素的乘法为模为GF(2)上的一个8次不可约多项式的多项式乘法，乘法用表示。一个多项式是不可约的，如果它除1和其自身之外没有其他的因子。对于AES，这一不可约多项式选取为：m( x ) = x8 + x4 + x3 + x + 11加法 在多项式表示中，两个元素的和是一个多项式，其系数是两个元素的对应系数的模2加(即异或)。 例如：“57”和“83”的和为：53+87=D4 或者采用其多项式记法：(x6 + x4 + x2 + x + 1)+( x7 + x + 1)= x7 + x6 + x4 + x2显然，该加法与简单的以字节为单位的比特异或是一致的。2.乘法例如：57*83C1，或者： 3乘x如果我们用多项式x乘以b(x)，我们有b7 x8+ b6 x7+ b5 x6 + b4 x5+ b3 x4+ b2 x3 + b1 x2 + b0 x将上面的结果进行模m(x)化简就得到x*b(x)。如果b7=0，则x*b(x)本身就是化简得结果。如果b7=1，则必须减去m(x)(或者说是异或m(x)。由此乘x运算可以用字节内左移和紧接着的个与1b的有条件的(有进位发生)比特异或来实现。该运算记为xtime()。与x的高次幂相乘可通过与x多次相乘得到。通过中间结果的相加，我们可以用xtime()实现任意常数乘法。例如：计算57*13=FEGF(28)域上的多项式一个(4字节)字可以看作是GF(28)域上的多项式，每个字对应于一个次数小于4的(四项) 多项式。对相应的系数简单相加就可以实现多项式的相加。由于GF(28)中的加法为比特异或，因此，两个向量的加法是一个简单的异或。乘法则比较复杂。假设我们有GF(28)上的两个多项式：a(x)= a3 x3+ a2 x2+ a1 x+ a0 和 b(x)=b3 x3+ b2 x2+ b1 x+ b0它们的乘积c(x)a(x)*b(x)由下面给出： 显然，c(x)不能再被表示为4字节向量。我们通过一个4次多项式取模来对c(x)进行化简，这样，乘法的结果可以化简为一个次数小于4次的多项式。在AES中，使用的模数多项式取为M(x)x4+1。由于xi mod x4+1=xi mod 4记 a(x),b(x)相乘的结果为d(x)=a(x)b(x)，因此一个固定的多项式a(x)和b(x)相乘所构成的运算可以写成矩阵乘法：其中的矩阵是一个循环矩阵。由于x4十1不是GF(28)上的不可约多项式，所以被一个固定多项式相乘不一定是可逆的。AES选择了一个有逆元的固定多项式。乘x考虑用多项式x乘b(x)显然结果为：b3 x4+ b2 x3 + b1 x2 + b0 x使用x4+1取模得到：b2 x3 + b1 x2 + b0 x+ b3 用矩阵乘法形式表示为因此，用x或x的方幂乘GF(28)上的多项式等价于一个4字节字的左循环移位4.3.2. AES的输入输出及中间状态AES的分组长度为128位对于128位的输入，经AES加密或解密处理后得到的输出也为128位。在AES中，各种运算是以字节为单位来进行处理的。AES加密和解密过程中的中间各步的结果称为一个状态。每个状态也是128位表示为一个44的字节矩阵。对于128bit的明文x，包含16个字节：x0，x15，则x对应的state为:x0x4x8x12x1x5x9x13x2x6x10x14x3x7x11x15在AES中有三种可选的密钥长度，分别为128bit、192bit和256bit。密钥的长度常以4字节字为单位来表示密钥长度记为Nk，Nk4，6或8这就是说密钥的长度为4个字、6个字或8个字AES的分组长度记为Nb，Nb4这就是说AES的分组长度为4个字，即128位在AES中，加密或解密过程中的轮变换的数目记为Nr轮变换的数日Nr与密钥的长度Nk有关，如表4-1所示表4-1 轮变换的数目Nr与密钥的长度Nk的关系4.3.3 AES加密过程Cipher(byte in4*Nb, byte out4*Nb, word wNb*(Nr+1)Beginbytestate4, Nbstate = inAddRoundKey(state, w0, Nb-1)for round=1 step 1 to Nr-1subBytes(state)ShiftRows(state)MixColumns(state)AddRoundKey(state, wround*Nb, (round+1)*Nb-1)endforsubBytes(state)ShiftRows(state)AddRoundKey(state, wNr*Nb, (Nr+1)*Nb-1)Out=stateendAES密码的每一轮中，都要进行轮密钥的混合，代换和置换。该算法的轮函数如下：Round(State,RoundKey)SubBytes (State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey);算法的最后一轮有所不同：FinalRound(State, RoundKey)SubBytes (State);ShiftRow(State);AddRoundKey(State, RoundKey);接下来介绍轮函数中出现的几个变换。1字节置换SubBytes操作使用一个S盒，对state中的每一个字节进行独立的变换。这里S盒相当于一个0255的一个置换。SubBytes是可逆的，它由两个可逆变换复合而成：(1)首先，将一个字节变换为有限域GF(28)中的乘法逆元素规定00h变换为其自身00h(2)其次进行如下运算：通过SubBytes变换状态x为y。将字节代替变换SubByte的各种可能的变换结果排成一个表，如表4-2所示。表4-2称为AES的字节置换表或s盒。我们可以通过查表得到SubBytes()的输出。如果状态中的一个字节为xy，则S盒中第x行第y列的字节就是SubBytes()的输出例如：假设hl53，则SubBytes()的输出为s盒中第5行第3列的字节ed表4-2 AES的字节置换表 2行移位变换ShiftRows() 行移位变换ShiftRows ()对一个状态的每一行循环左移不同的位移量。其中第0行不移位保持不变，第一行循环左移1个字节，第二行循环左移2个字节，第三行循环左移3个字节。对State的ShiftRow操作如图4-3所示：图4-3. ShiftRow对状态的后三行循环移位 3列混合变换MixColumns()列混合变换MixColumns()对一个状态逐列进行变换，变换中列内每个元素的变换结果只与同列元素相关。它将一个状态的每一列视为有限域GF(28)上的一个多项式将每一列变换为新的列。令：a(x)=03x3+01x2+01x+02则对于状态矩阵中的第c列s(x)，列混合变换为（其中代表模x4+1乘法）：即： 4轮密钥加法变换AddRoundKey() 轮密钥加法变换AddRoundKey()简单地将一个轮密钥按位异或到一个状态上。轮密钥的长度为t个字(128位)。一个字为4个字节(32位)。轮密钥按顺序取自扩展密钥，扩展密钥是由原始密钥经过扩展后得到的，扩展密钥为Nk(Nr十1)个字。其中wround*Nb+c表示本轮使用扩展密钥。4.3.4. 密钥扩展 密钥扩展过程产生Nk(Nr十1)个字，最初的Nk个字为原始密钥，后面的字由前面的字递归定义。KeyExpansion(byte key4*Nk, word wNb*(Nr+1), Nk)beginword tempi = 0while (i Nk)wi = word(key4*i, key4*i+1, key4*i+2, key4*i+3)i = i+1end whilei = Nkwhile (i 6 and i mod Nk = 4)temp = SubWord(temp)end ifwi = wi-Nk xor tempi = i + 1end whileendSubWord()的输入为一个4字节的字，对字中的每个字节做s盒变换，变换后的4个字节所组成的字为SubWord()的输出。 RotWord()的返回值为一个4字节的字，它是输入的4字节字的一个循环置换。假设RotWord()的输入为字(a0,a1,a2,a3)，则Rotword()的返回值为字(a1,a2,a3,a0)。 Rcon是一个常量字的数组每轮使用的常量为： Rconj(xjl，00，00，00)， j1xjl表示有限域GF(28)中的多项式x的j-1次方所对应的字节。注意到有限域GF(28)中的多项式x所对应的字节为02，我们有： Rconj(cj，00，00，00)， j1， c001， cj02cjl， j1这里表示有限域GF(28)中的乘法 在AES的加密过程中，第r次调用AddRoundKey()所用到的轮密钥由扩展密钥的第4r，4r十1，4r十2，4r十3个字组成，0rNr。4.3.5. AES解密过程 AES的解密过程描述如下:InvCipher(byte in4*Nb, byte out4*Nb, word wNb*(Nr+1)beginbyte state4,Nbstate = inAddRoundKey(state, wNr*Nb, (Nr+1)*Nb-1) for round = Nr-1 step -1 downto 1InvShiftRows(state)InvSubBytes(state) AddRoundKey(state, wround*Nb, (round+1)*Nb-1)InvMixColumns(state) end forInvShiftRows(state)InvSubBytes(state)AddRoundKey(state, w0, Nb-1)out = stateend4.3.5.1 逆行移位变换InvShiftRows()InvShiftRows()是ShiftRows()的逆变换InvShiftRows()对一个状态的每一行循环右移不同的位移量。第0行不移位保持不变，第1行循环右移1个字节，第2行循环右移2个字节，第3行循环右移3个字节。如图4-4所示。图4-4 InvShiftRow对状态的后三行循环移位4.3.5.2 逆字节置换变换InvSubByts() InvSubBytes()是SubBytes()的逆变换。它将状态中的每一个字节非线性地变换为另一个字节。InvSubBytes()首先对一个字节在GF(2)上做式(4，2)中的仿射变换的逆变换，对应的置换表如4-3所示：表4-3 逆字节置换表4.3.5.3 逆列混合变换InvMixColumns()InvMixColumns()是MixColumns()的逆变换InvMixColumns()对一个状态逐列进行变换，它将状态的每一列视为有限域GF(28)上的一个多项式。InvMixCo1umns()将状态的每一列所对应的GF(28)上的多项式模x4十1乘以多项式:a-1(x)=0bx3+0dx2+09x+0ea-1(x)是式(43)中的多项式a(x)模x4+1的乘法逆多项式。令：则：4.3.5.4 逆AddRoundKey()变换异或操作的逆就是自身，因此AddRoundKey()的逆变换就是它自身。4.3.6 AES的安全性及实现AES算法的安全性仍然在讨论当中，从目前的进展来看，对AES尚无已知的安全性方面的攻击，算法似乎具有良好的安全性。目前对AES的批评主要集中于AES似乎有些简单，除s盒外，Rijdael算法几乎是线性的(其余的变换全部是线性的)，它的数学结构可能会受到攻击，但是，也正是由于它的简单性，才能够在AES选拔期间被进行详尽的安全性分析。另外，AES的密钥长度为可变的，当进行穷举密钥攻击时，穷举密钥的期望尝试次数与密码密钥的长度有关：对于128比特的密钥，期望尝试执行次数为执行2127(约为1.71038)次算法；对于192比特的密钥，期望尝试执行次数为执行2191(约为3.1l057)次算法；对于256比特的密钥，期望尝试执行次数为执行2255(约为5.81076)次算法。相比而下，AES算法比DES算法加密强度高。 AES在设计时已经考虑到差分攻击与线性攻击，可以很好地抵抗差分攻击与线性攻击。NIST将继续对AES算法的安全性进行监测，并将在以后的时间内对可能产生的安全问题作出相应处理；同时，NIST仍将关注对AES密码分析的进展，一旦AES成为正式的标准，此标准将会每隔五年重新评估一次。 关于AES算法的安全性问题，感兴趣的读者可以查看AES的主页及相关的一些资料以得到更多的信息。 关于效率问题，无论在有无反馈模式的计算环境下，AES的硬件、软件实现都表现出了良好的性能。AES可以在包括8位和64位平台在内的各种平台及DSP上进行加密和解密。AES算法的轮变换与S盒是完全并行的，它这种固有的高并行性便于有效使用处理器资源，即使不以并行的方法实现该算法，它的软件效能也非常地好，它的密钥建立速度很快。另外，AES对RAM和ROM的需求量低，非常适合在空间有限的环境单独进行加密或解密(但由于其加密、解密过程的不完全对称性，加密与解密时使用了不同的代码和S盒，如果同时实现加密和解密，将会增加ROM需求量。) 另外，AES也非常适合于硬件实现。但是，由于加密、解密过程使用了不同的代码和S盒，加密与解密过程只能共用部分电路。4.4 分组密钥算法的加密模式分组加密算法定义为加密固定长度的数据块，为了加密任意长度的数据，可以使用不同的加密模式。这里我们介绍四种常用的工作模式： ECB模式 电子密码本模式(Electronic Code Book)。在使用分组加密算法加密任意长度的数据时，先将数据块分成多个小块，每块的长度与算法定义的块长度相同，对于最后一块，将其按一定协议添充为块长度。然后分别将各小分组加密。 ECB模式的加密强度同加密算法本身相同，但存在不安全性。攻击者可在不知道密钥的情况下对密文块用置换法进行篡改，ECB模式本身却不能发现。而且相同的明文总是加密出相同的密文，因此攻击者破译密文的机会大大增加了。 CBC模式 密文链方式(Cipher Block Chain)。 在CBC 模式中每一个明文块被加密前先与前一个密文块异或( XOR )，然后再加密。第一块与用户指定的初始向量异或；其加密和解密过程如图4-5所示:图4-5 CBC加密模式 ECB模式的加密强度同加密算法本身相同，而且CBC模式使得相同明文在不同的位置加密出密文不同，每个密文都与前边所有密文相关。这样就无法用置换法篡改，而且增加了密码分析的难度。加密速度同原算法相同。CBC方式的缺点是不能实现流式加密，只有明文长度达到固定长度，加密才能进行。 CFB模式 密文反馈模式(Cipher Feed Back)。 在 CFB 方式中，上次的密文被加密，明文与加密结果异或生成本次密文。同CBC模式一样CFB模式也需要一个初始向量。其加密和解密过程如图4-6所示:图4-6 CFB加密模式 CFB模式同CBC模式一样使相同明文在不同的位置加密的密文不同，但CFB模式不需要明文达到块长度就可输出密文，因此实现了流式加密。 OFB模式输出反馈模式(Output Feedback Mode)。OFB 模式与CFB模式类似，不同的是与明文异或的数据是独立产生的，通过对一个初始向量迭代加密形成。OFB 模式与CFB模式相比有一个优点是在 CFB 模式中一旦密文在传输中出现任何错误，错误之后的密文都将作废，而 OFB 模式则不会受此影响。但 OFB 模式的安全性不如CFB模式。4.5 分组加密算法的高效实现技术加密算法的两个重要指标是加密强度和速度。加密强度是算法的基本性质，是算法抵抗各种攻击的能力。在大多数应用中,在保证一定加密强度的前提下,加密/解密的速度是最重要的性质,尤其是对于要求较高速度的应用。 加密强度在算法的设计阶段已经确定,算法的不同实现一般不会对加密强度产生影响。而同一加密算法的加/解密速度在不同的实现中则可能有很大不同。加密速度在根本上由算法本身的设计决定，但在实现中可以使用各种优化技术最大限度地发挥算法速度的潜力。本节研究在算法确定情况下提高算法速度的实现方法，不涉及新算法设计问题。本节的内容给出了优化分组加密算法的一些有效方法，并给出了对几种加密算法的实现进行优化的实例和测量结果。在不同机器和不同操作系统上实现的加密算法性能差别很大。提高加密算法实现的性能，首先需要对算法本身及其实现环境的特性有较好了解。下面我们考察加密算法的计算特征： 加密算法的一般计算特征 对称密钥加密算法包括两个部分: 密钥扩展和加解密。密钥扩展是将原始密钥扩展为加密函数使用的子密钥。在一般的应用中基本操作是加密循环，加密循环中的操作都是整数运算，包括加减乘除、移位、异或、查表等，很多加密算法还使用S-box和P-box等内部表。有些算法执行时间与明文、密钥长度相关，有些算法与之无关。 当代CPU的特征 在以Intel Pentium为代表的当代CPU中采用了许多巨型计算机的先进技术，包括指令流水线、超标量等。在算法的软件实现中应该充分利用这些特性提高速度。对于Pentium系列CPU，它拥有两条整数运算流水线,能在同一时钟周期内同时执行两条整数运算指令，如果程序设计得当，使得相邻的指令不相关，就能提高速度。编译器会作一些优化工作，但很有限。如果在程序设计时，针对加密算法和CPU的特征进行一些手工优化，则会产生更好的效果。 语言的选择 与其他高级语言相比，C语言编译生成的可执行码常常具有较高的执行效率，而且在可移植性方面具有极大的优势，在几乎所有的平台上都有ANSI C编译器，并且技术成熟，相互间的兼容性也很好。对于不同的机器只需在很少的某些程序段分别编写，大部分程序不必重写即可实现跨平台使用。著名的SSLeay就是用C语言编写的。汇编语言具有适合编写高速度程序的特点，但对不同的机器需重新编写程序。JAVA语言的跨平台能力使得它非常适合某些应用场合。尤其是在瘦客户机系统的安全通信中，JAVA加密包是一个有效的解决方案。4.5.1提高算法速度的原则 通过对加密算法的特点以及机器的特性的分析和实验归纳，可总结出以下提高算法速度的实现原则： 1 展开加密循环和函数 加密算法的大部分运行时间是执行加密循环。展开加密循环实际上是将加密循环变为多个循环体中的程序模块，同时将加密循环中调用的函数展开。这样减少了很多条件跳转指令和计算指令,并且将许多变量变为常量。而且由于Pentium CPU采用了指令流水线、超标量等技术，循环和变量操作数会造成指令流水线的阻断和指令预取的作废，展开加密循环能减少流水线的阻断和指令预取的作废，而且变量变为常量使得相应的指令变为速度更快的指令，大大提高速度。这种方法的缺点是增大了程序的长度。 2 在内部循环中避免使用条件跳转指令 在INTEL Pentium系列CPU中分枝预测的成功率对程序的执行效率有重要的影响。条件跳转指令会产生不可预见的指令流，容易分枝预测的失败，从而浪费大量指令周期。在C语言中for 和if/then/else/等语句都会产生条件跳转指令。在加密算法内部循环中应避免使用条件跳转指令。 3 变量长度与CPU内部寄存器长度相同 对于Pentium等32位CPU，程序中的数组和变量，如密钥和中间结果等，无论在算法描述中是16位或8位，在实现中都应定义为32位。因为数据类型与CPU内部长度不同，将使得变量的存取都需要附加其他的指令，增加了程序长度和指令