1、2.1 分组密码的设计准则 2.2 数据加密标准DES 2.3 高级数据加密标准AES 2.4 国际数据加密标准IDEA*2.5 RC5算法 2.6 分组密码的安全性及工作模式 习题 分组密码是指对固定长度的一组明文进行加密的一种加密算法，这一固定长度称之为分组长度。分组长度是分组密码的一个参数，其值取决于实际应用的环境。对于通过计算机来实现的分组密码算法，通常选取的分组长度为64位。这是一个折中的选择，考虑到分组算法的安全性，分组长度不能太短，应该保证加密算法能够应付密码分析；考虑到分组密码的实用性，分组程度又不能太长，要便于操作和运算。近年来，随着计算机计算能力的不断提高，分组长度为64位
2、的分组密码的安全性越来越不能满足实际需要，为了提高加密的安全性，很多的分组密码开始选择128位作为算法的分组长度。2.1 分组密码的设计准则分组密码的设计准则分组密码的加密过程是对一个分组长度为n位的明文分组进行加密操作，相应地产生一个n位的密文分组，由此可见，不同的n位明文分组共有2n个。考虑到加密算法的可逆性(即保证解密过程的可行性)，每一个不同的n位明文分组都应该产生一个惟一的密文分组，加密过程对应的变换被称为可逆变换或非奇异变换。所以，分组密码算法从本质上来说是定义了一种从分组的明文到相应的密文的可逆变换。分组密码是现代密码学的重要组成部分，当前被广泛使用的分组加密算法几乎都是基于Fe
3、istel分组密码的结构而设计的。为了对具有代表性的分组密码DES(Data Encryption Standard)算法、AES(Advanced Encryption Standard)算法和IDEA(International Data Encryption Algorithm)算法进行深入研究和分析，我们首先介绍Feistel分组密码的基本结构和设计准则。2.1.1 Feistel分组密码的基本结构分组密码的基本结构Feistel分组密码结构是基于1949年Shannon提出的交替使用代换和置换方式构造密码体制的设想提出的。在设计密码体制的过程中，Shannon提出了能够破坏对密码系统
4、进行各种统计分析攻击的两个基本操作：扩散(Diffusion)和混淆(Confusion)。扩散的目的是使明文和密文之间的统计关系变得尽可能复杂；混淆的目的是使密文和密钥之间的统计关系变得尽可能复杂。为了使攻击者无法得到密钥，在扩散过程中，明文的统计信息被扩散到密文的更长的统计信息中，使得每一个密文数字与许多明文数字相关，从而使密文的统计信息与明文之间的统计关系尽量复杂，以至于密文的统计信息对于攻击者来说是无法利用的；在混淆过程中，密文的统计信息与加密密钥的取值之间的关系会尽量复杂，以至于攻击者很难从中推测出加密密钥。扩散和混淆给出了分组密码应具有的本质特性，成为分组密码设计的基础。Feist
5、el分组密码的基本结构如图2-1所示。加密算法的初始输入是一个长度为2L位的明文分组序列和一个初始密钥K，在加密之前先将分组的明文序列等分成长度均为L的L0和R0两部分。加密过程分为n轮进行，其中第i轮以第i-1轮输出的Li-1和Ri-1作为输入，此外第i轮加密过程的输入还包括从初始密钥K产生的子密钥Ki。第i轮的加密过程由两步操作实现：第一步先对Ri-1使用轮函数F和子密钥Ki进行变换，将变换结果与Li-1再进行异或运算，运算结果作为Ri；第二步将Ri-1直接作为Li得到第i轮的输出值。最终将加密过程的输出序列Ln和Rn组合起来产生相应的长度是2L位的密文。图2-1 Feistel分组密码的
6、基本结构在每一轮加密过程中，第一步操作是一个代换过程，第二步操作是一个置换过程，通过“代换置换”这两步操作实现了Shannon提出的扩散和混淆的目的。根据图2-1所示的Feistel分组密码的基本结构可知，Feistel型分组密码的安全性取决于以下几个方面：(1)明文消息和密文消息的分组大小：在其他条件相同的情况下，每一轮加密的分组长度越大，加密算法的安全性就越高，而相应的加密速度也越慢，效率越低。目前常用的分组加密算法的分组长度取64位。(2)子密钥的大小：算法的安全性随着子密钥长度的增加而提高，但是相应的加密速度会降低，所以设计分组密码时需要在安全性和加密效率之间进行平衡。在实际应用中，一
7、般认为，要保证分组加密算法满足计算安全性，子密钥的长度至少要大于128位。(3)循环次数：循环越多安全性越高，相应的加密效率也就越低。(4)子密钥产生算法：在初始密钥给定的情况下，产生子密钥的算法越复杂，加密算法的安全性越高。(5)轮函数F：对于轮函数的讨论相对较复杂，一般认为，轮函数F越复杂，对应的加密算法的安全性越高。Feistel分组密码的解密过程与加密过程是相同的。解密过程将密文作为算法的输入，同时按照与加密过程相反的次序使用子密钥对密文序列进行“加密”，即第1轮使用Kn，第2轮使用Kn-1，依此类推，最后一轮使用K1，进行相同次数“加密”，“加密”的结果就得到相应的明文序列。2.1.
8、2 F函数的设计准则函数的设计准则Feistel分组密码的核心是轮函数F。轮函数F在Feistel分组密码算法中的作用是对消息序列进行混淆操作。为了保证这样的混淆操作的安全性，设计轮函数F的一个基本准则是要求F是非线性的。F的非线性程度越强，则算法的安全性能越高，相应的攻击难度也就越大。S盒是F函数的重要组成部分，S盒的设计问题一直是人们关注的重点。对于S盒的设计，基本要求是希望S盒输入序列的任何变动都使得输出序列产生看似随机的变动，并且这两种变动之间的关系应该是非线性的。考虑到加密算法应该具有良好的“雪崩效应”，也就是说，输入消息序列一个位的值发生改变，相应的输出序列应该产生多个位的值变化。
9、设计的F函数应该满足严格雪崩准则(Strict Avalanche Criterion，SAC)，这个准则的具体内容是：对于任意的i、j，当任何一个输入位i发生改变时，S盒的任何输出位j的值发生改变的概率为1/2。虽然以上准则是对S盒的设计提出的，但是由于S盒是F函数的重要组成部分，因此该准则的要求也可以作为F函数的设计要求。设计F函数还应满足的一个准则是位独立准则(Bit Independence Criterion，BIG)，这个准则的具体内容是：对于任意的i、j、k，当任何一个输入位i发生改变时，输出位j和k的值应该独立地发生改变。S盒的设计除了要满足以上讨论的SAC和BIC准则外，还应
10、该满足的一个条件是保证雪崩准则(Guaranteed Avalanche Criterion，GAC)，这个准则的具体内容是：一个好的S盒应该满足阶的GA(Guaranteed Avalanche)，也就是说对于输入序列中1位的值发生改变，输出序列中至少有位的值发生改变。一般要求的值介于25之间。当然除了以上要求，关于F函数和S盒的设计还有其他很多的建议和要求。这些要求和建议都是为了改进F函数和S盒的非线性和随机性，从而增强分组密码算法的安全性。DES(Data Encryption Standard)算法是最为广泛使用的一种分组密码算法。DES对推动密码理论的发展和应用起了重大的作用。学习D
11、ES算法对于掌握分组密码的基本理论、设计思想和实际应用都有重要的参考价值。1972年美国商业部所属的美国国家标准局(National Bureau of Standards，NBS)开始实施计算机数据保护标准的开发计划。1973年5月13日，美国国家标准局发布文告征集在传输和存储数据中保护计算机数据的密码算法。1975年3月17日，首次公布DES算法描述，并认真地进行公开讨论。2.2 数据加密标准数据加密标准DES1977年1月15日，正式批准DES为无密级应用的加密标准(FIPS46)。以后每隔5年美国国家安全局对其安全性进行一次评估，以便确定是否继续使用它作为加密标准。在1994年1月的评
12、估后决定1998年12月以后不再将DES作为加密标准。2.2.1 DES的描述的描述DES是一个分组加密算法，它以64位为分组对数据进行加密。64位的分组明文序列作为加密算法的输入，经过16轮加密得到64位的密文序列。加密密钥的长度为56位(注：密钥通常表示为64位的数，但每个第8位都用作奇偶校验位，可以忽略)，密钥可以是任意的56位的数，其中极少量的56位数被认为是弱密钥。为了保证加密的安全性，在加密过程中应该尽量避开使用这些弱密钥。DES对64位的明文分组进行操作。首先通过一个初始置换IP，将64位的明文分成各32位长的左半部分和右半部分，该初始置换只在16轮加密过程进行之前进行一次，在接
13、下来的轮加密过程中不再进行该置换操作。在经过初始置换操作后，对得到的64位序列进行16轮加密运算，这些运算被称为函数f，在运算过程中，输入数据与密钥结合。经过16轮加密后，左、右半部分合在一起得到一个64位的输出序列，该序列再经过一个末尾置换IP-1(初始置换的逆置换)获得最终的密文(具体加密流程见图2-2)。图2-2 DES加密流程图在每一轮加密过程中，函数f的运算包括以下四个部分：首先进行密钥序列移位，从移位后的56位密钥序列中选出48位(该部分采用一个压缩置换实现)；其次通过一个扩展置换将输入序列32位的右半部分扩展成48位后与48位的轮密钥进行异或运算；第三部分通过8个S盒将异或运算后
14、获得的48位序列替代成一个32位的序列；最后对32位的序列应用P盒进行置换变换得到f的32位输出序列。将函数 f 的输出与输入序列的左半部分进行异或运算后的结果作为新一轮加密过程输入序列的右半部分，当前输入序列的右半部分作为新一轮加密过程输入序列的左半部分。上述过程重复操作16次，便实现了DES的16轮加密运算。假设Bi是第i轮计算的结果，则Bi为一个64位的序列，Li和Ri分别是Bi的左半部分和右半部分，Ki是第i轮的48位密钥，且 f 是实现代换、置换及密钥异或等运算的函数，那么每一轮加密的具体过程为 以上操作的详细过程如图2-3所示。),(111iiiiiiKRfLRRL图2-3 一轮D
15、ES加密过程下面对DES加密过程中包含的基本操作进行详细说明。(1)初始置换(Initial Permutation，IP置换)。初始置换在第一轮运算之前执行，对输入分组实施如表2-1所示的IP置换。例如：表2-1表示该IP置换把输入序列的第58位置换到输出序列的第1位，把输入序列的第50位置换到输出序列的第2位，依此类推。(2)密钥置换。DES加密算法输入的初始密钥大小为8个字节，由于每个字节的第8位用来作为初始密钥的校验位，因此加密算法的初始密钥不考虑每个字节的第8位，DES的初始密钥实际对应一个56位的序列，每个字节的第8位作为奇偶校验以确保密钥不发生错误。首先对初始密钥进行如表2-2所
16、示的置换操作。DES的每一轮加密过程从56位密钥中产生出不同的48位子密钥(Subkey)，这些子密钥Ki通过以下方法产生。首先将56位密钥等分成两部分，每部分的长度为28位。然后根据加密轮数，这两部分密钥分别循环左移1位或2位。表2-3给出了对应不同轮数产生子密钥时具体循环左移的位数。对两个28位的密钥循环左移以后，通过如表2-4所示的压缩置换(Compression Permutation，也称为置换选择)从56位密钥中选出48位作为当前加密的轮密钥。表2-4给出的压缩置换不仅置换了56位密钥序列的顺序，同时也选择出了一个48位的子密钥，因为该运算提供了一组48位的数字集。例如，56位的密
17、钥中位于第33位密钥数字对应输出到48位轮密钥的第35位，而56位的密钥中位于第18位的密钥数字在输出的48位轮密钥中将不会出现。以上产生轮密钥的过程中，由于每一次进行压缩置换之前都包含一个循环移位操作，因此产生每一个子密钥时，使用了不同的初始密钥子集。虽然初始密钥的所有位在子密钥中使用的次数并不完全相同，但在产生的16个48位的子密钥中，初始密钥的每一位大约会被14个子密钥使用。(3)扩展变换(Expansion Permutation，也称为E盒)。扩展变换将64位输入序列的右半部分Ri从32位扩展到48位。扩展变换不仅改变了Ri中32位输入序列的次序，而且重复了某些位。这个操作有以下三个
18、基本的目的：一方面，经过扩展变换可以应用32位的输入序列产生一个与轮密钥长度相同的48位的序列，从而实现与轮密钥的异或运算；另一方面，扩展变换针对32位的输入序列提供了一个48位的结果，使得在接下来的替代运算中能进行压缩，从而达到更好的安全性；同时，由于输入序列的每一位将影响到两个替换，因此输出序列对输入序列的依赖性将传播得更快，体现出良好的“雪崩效应”。所以，该操作有助于设计的DES算法尽可能快地使密文的每一位依赖于明文和密钥的每一位。表2-5给出了扩展变换中输出位与输入位的对应关系。例如，处于输入分组中第3位的数据对应输出序列的第4位，而输入分组中第21位的数据则分别对应输出序列的第30位
19、和第32位。在扩展变换过程中，每一个输出分组的长度都大于输入分组，而且该过程对于不同的输入分组都会产生惟一的输出分组。(4)S盒替代(Sboxes Substitution)。每一轮加密的48位的轮密钥与扩展后的分组序列进行异或运算以后，得到一个48位的结果序列，接下来应用S盒对该序列进行替代运算。替代由8个代替盒(Substitution boxes，S盒)，每一个S盒对应6位的输入序列，得到相应的4位输出序列。在DES算法中，这8个S盒是不同的(DES的这8个S盒占的存储空间为256字节)。48位的输入被分为8个6位的分组，每一分组对应一个S盒替代操作：分组1由S盒1操作，分组2由S盒2操
20、作，依此类推(见图2-4)。图2-4 S盒替代DES算法中，每个S盒对应一个4行、16列的表，表中的每一项都是一个十六进制的数，相应的对应一个4位的序列。表2-6列出了所有8个S盒。输入序列以一种非常特殊的方式对应S盒中的某一项，通过S盒的6个位输入确定了其对应的输出序列所在的行和列的值。假定将S盒的6位的输入标记为b1、b2、b3、b4、b5、b6。则b1和b6组合构成了一个2位的序列，该2位的序列对应一个介于03的十进制数字，该数字即表示输出序列在对应的S盒中所处的行；输入序列中b2到b5构成了一个4位的序列，该4位的序列对应一个介于015的十进制数字，该数字即表示输出序列在对应的S盒中所
21、处的列，根据行和列的值可以确定相应的输出序列。例例2.1 假设对应第6个S盒的输入序列为110011。第1位和最后一位组合构成的序列为11，对应的十进制数字为3，说明对应的输出序列位于S盒的第3行；中间的4位组合构成的序列为1001，对应的十进制数字为9，说明对应的输出序列位于S盒的第9列。第6个S盒的第3行第9列处的数是14(注意：行、列的记数均从0开始，而不是从1开始)，14对应的二进制为1110，对应输入序列110011的输出序列为1110。S盒的设计是DES分组加密算法的关键步骤，因为在DES算法中，所有其他的运算都是线性的，易于分析，而S盒是非线性运算，它比DES的其他任何操作能提供
22、更好的安全性。运用S盒的替代过程的结果为8个4位的分组序列，它们重新合在一起形成了一个32位的分组。对这个分组进行下一步操作：P盒置换。(5)P盒置换(P-boxes Permutation)。经S盒代替运算后的32位输出依照P盒(Permutation boxes)进行置换。该置换对32位的输入序列进行一次置换操作，把每个输入位映射到相应的输出位，任一位不能被映射两次，也不能被略去。表2-7给出了P盒置换的具体操作。例如，输入序列的第21位置换到输出序列的第4位，而输入序列的第4位被置换到输出序列的第31位。将P盒置换的结果与该轮输入的64位分组的左半部分进行异或运算后，得到本轮加密输出序列
23、的右半部分，本轮加密输入序列的右半部分直接输出，作为本轮加密输出序列的左半部分，相应得到64位的输出序列。(6)逆初始置换(Inverse Initial Permutation)。逆初始置换是初始置换的逆过程，也称为末尾置换，表2-8列出了逆初始置换IP-1的具体操作。需要说明的是，DES在16轮加密过程中，左半部分和右半部分并没有进行交换位置的操作，而是将R16与L16并在一起形成一个分组作为逆初始置换的输入。这样做保证了DES算法加密和解密过程的一致性。初始置换IP和对应的逆初始置换IP-1操作并不会增强DES算法的安全性，它们的主要目的是为了更容易地将明文和密文数据以字节大小放入DES
24、芯片中。(7)DES解密。DES算法的加密过程经过了多次的替代、置换、异或和循环移动操作，整个加密过程似乎非常复杂。实际上，DES算法经过精心选择各种操作而获得了一个非常好的性质：加密和解密可使用相同的算法，即解密过程是将密文作为输入序列进行相应的DES加密，与加密过程惟一不同之处是解密过程使用的轮密钥与加密过程使用的次序相反。如果加密过程中各轮的子密钥分别是K1，K2，K3，K16，那么解密过程中相应的解密子密钥分别是K16，K15，K14，K1。因此解密过程产生各轮子密钥的算法与加密过程生成轮密钥的算法相同，与加密过程不同的是解密过程产生子密钥时，初始密钥进行循环右移操作，每产生一个子密钥
25、，对应的初始密钥移动位数分别为0，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1。这样就可以根据初始密钥生成加密和解密过程所需的各轮子密钥。例例2.2 已知明文m=computer，密钥k=program，相应的ASCII码表示为m=01100011 01101111 01101101 01110000 01110101 01110100 01100101 01110010k=01110000 01110010 01101111 01100111 01110010 01100001 01101101其中k只有56位，必须加入第8，16，24，32，40，48，56，64位的奇偶校验
26、位构成64位。其实加入的8位奇偶校验位对加密过程不会产生影响。令m=m1m2m63m64，k=k1k2k63k64，其中m1=0，m2=1，m63=1，m64=0，k1=0，k2=1，k63=1，k64=0。m经过IP置换后得到L0=11111111 10111000 01110110 01010111R0=00000000 11111111 00000110 10000011密钥k经过置换后得到C0=11101100 10011001 00011011 1011D0=10110100 01011000 10001110 0110循环左移一位后得到48位的子密钥k1：k1=00111101 1
27、0001111 11001101 00110111 00111111 01001000R0经过扩展变换得到的48位序列为10000000 00010111 1111111010000000 11010100 00000110结果再和k1进行异或运算，得到的结果为10111101 10011000 0011001110110111 11101011 01001110将得到的结果分成8组：101111 011001 100000 110011101101 111110 101101 001110通过8个S盒得到32位的序列为01110110 00110100 00100110 10100001对S
28、盒的输出序列进行P置换，得到01000100 00100000 10011110 10011111经过以上操作，得到经过第1轮加密的结果序列为00000000 11111111 00000110 1000001110111011 10011000 11101000 11001000以上加密过程进行16轮，最终得到加密的密文为01011000 10101000 01000001 1011100001101001 11111110 10101110 00110011 需要说明的是，DES的加密结果可以看做是明文m和密钥k之间的一种复杂函数，所以对应明文或密钥的微小改变，产生的密文序列都将会发生很大
29、的变化。2.2.2 DES的分析的分析自从被采用作为联邦数据加密标准以来，DES遭到了猛烈的批评和怀疑。首先是DES的密钥长度是56位，很多人担心这样的密钥长度不足以抵御穷举式搜索攻击；其次是DES的内部结构即S盒的设计标准是保密的，这样使用者无法确信DES的内部结构不存在任何潜在的弱点。事实上，后来的实践表明DES的S盒被精心设计成能够防止诸如差分分析方法类型的攻击。另外，DES的初始方案IBM的Lucifer密码体制具有128位的密钥长度，DES的最初方案也有64位的密钥长度，但是后来公布的DES算法将其减少到56位。IBM声称减少的原因是必须在密钥中包含8位奇偶校验位，这意味着64位的存
30、储只能包含一个56位的密钥。许多密码体制都存在着弱密钥，DES也存在这样的弱密钥和半弱密钥。如果DES的密钥k产生的子密钥满足k1=k2=k16则有这样的密钥k称为DES算法的弱密钥。DES的弱密钥有以下四种：k=01 01 01 01 01 01 01 01k=1F 1F 1F 1F 0E 0E 0E 0Ek=E0 E0 E0 E0 F1 F1 F1 F1k=FE FE FE FE FE FE FE FE)(DES)(DES1mmkk如果DES的密钥k和k满足则称密钥k和k是DES算法的一对半弱密钥。DES的半弱密钥有以下六对：)(DES)(DES1mmkk01 FE 01 FE 01 FE
31、 01 FEFE 01 FE 01 FE 01 FE 01 kk 1FE0 1FE00EF1 0EF1E0 1FE0 1FF1 0EF1 0E kk 01E001E0E0F1 01F1E001E001F1 01F1 01 kk 1FFE1FFE0EFE0EFEFE1FFE1FFE0EFE0E kk 01 1F01 1F01 0E01 0E1F011F01 0E01 0E 01 kk E0FEE0FEF1FEF1FEFEE0FEE0FEF1FEF1 kk 以上0表示二值序列0000，1表示二值序列0001，E表示二值序列1110，F表示二值序列1111。对于DES的攻击，最有意义的方法是差分分析
32、方法。差分分析方法最初是由IBM的设计小组在1974年提出的，所以IBM在设计DES算法的S盒和换位变换时有意识地避免差分分析攻击，使得DES能够抵抗差分分析攻击。1991年，Biham和Shamir提出了针对选择明文攻击的差分分析方法，可以攻击很多分组密码。差分分析方法需要带有某种特性的明文和相应的密文之间的比较，攻击者寻找明文对应的某种差分的密文对，这些差分中的一部分会有较高的重现概率。差分分析方法用这种特征来计算可能的密钥概率，最后可以确定出最可能的密钥。但是由于DES的S盒在设计阶段就进行了优化，因此它能够有效抵御差分分析攻击。DES加密的轮数对安全性也有较大的影响。如果DES只进行8
33、轮加密过程，则在普通的个人电脑上只需要几分钟就可以破译密码。如果DES加密过程进行16轮，应用差分分析攻击比穷举式搜索攻击稍微有效一些。然而如果DES加密过程进行18轮，则差分分析攻击和穷举式搜索攻击的效率基本一样。如果DES加密过程进行19轮，则穷举式搜索攻击的效率还要优于差分分析攻击的效率。随着计算机硬件技术的飞速发展，DES的安全性越来越受到人们的怀疑。为了提高DES加密算法的安全性，人们一直在研究改进DES算法安全性能的方法，下面介绍较为基本的几种针对DES算法的改进方法。改进方法一改进方法一设明文消息x长度比较大，将其分为64位一组的结果表示如下x=x1x2x3xn相应的密文序列y表
34、示为y=y1y2y3yn其中，yi=DESk(xi)，i=1，2，n。在以上加密过程中，当明文序列的结构有一定的固定格式时，相应的密文序列也会表现出一定的规律性，从而导致加密算法不安全。对该问题可以采用分组反馈的方法进行改进。对明文分组xi，i=2，3，n进行加密前，先将明文分组消息和前一组加密的密文分组序列yi-1进行异或运算，然后对运算的结果序列再进行加密操作，即相应的解密过程为niyxi,xyiikiki,3,2 ),(DES1 )(DES1niyyi,yxiikiki,3,2 ,)(DES1 )(DES111以上改进方法由于采用了密文反馈的方式进行加密，当明文序列的结构有一定的固定格式
35、时，相应的密文序列表现出的规律性会被隐藏，从而能有效改进加密算法的安全性。改进方法二改进方法二由于DES算法的密钥长度只有56位，因此安全性较差。最简单的改进算法安全性的方法是应用不同的密钥对同一个分组消息进行多次加密，由此产生了多重DES加密算法。2.2.3 多重多重DES1.双重双重DES 最简单的双重DES加密过程是采用两个不同的密钥分两步对明文分组消息进行加密。给定一个明文分组x和两个加密密钥K1和K2，相应的密文消息y由下式得到：相应的解密过程为相比于传统的DES算法，以上改进方案的密钥长度变为128位，因此算法的安全性有一定的改进。下面对双重DES加密方法进行安全性分析。)(DES
36、DES12xyKK)(DESDES1121yxKK假设对DES以及所有的56位的密钥值，给定任意的两个密钥K1和K2，如果都可以得到一个密钥K3使得成立，那么双重DES的两次加密甚至包括任意多次加密对于算法的安全性来说都没有实质性的意义，因为得到的加密结果都等于DES算法使用一个56位的密钥进行一次加密的结果。)(DES)(DESDES312xxKKK可将DES加密算法看做是从64位的分组消息序列到另一个64位消息序列的一个映射，考虑到加密/解密结果的惟一性，这个映射应是一个置换。对于所有可能的264个明文消息分组序列，用一个特定的密钥进行DES加密就是把每个分组映射为另一个惟一的64位的消息
37、序列。那么对于264个明文消息分组序列，产生一个置换的不同映射的个数为264!=10347380000000000000000另一方面，DES的每一个密钥都可以定义一个映射，因此由56位的密钥可以定义的映射个数为 256264!通过以上分析可知，如果使用DES算法对消息序列进行两次加密，每次使用不同的密钥，那么产生的映射不是单次使用DES算法定义的一种映射。这说明双重DES加密算法的密钥空间要大于DES算法，所以其安全性优于DES算法。2.三重三重DES在众多的多重DES算法中，由Tuchman提出的三重DES算法是一种被广泛接受的改进方法。在该加密算法中，加密过程用两个不同的密钥K1和K2对
38、一个分组消息进行3次DES加密。首先使用第一个密钥进行DES加密，然后使用第二个密钥对第一次的结果进行DES解密，最后再使用第一个密钥对第二次的结果进行DES加密。解密过程首先使用第一个密钥进行DES解密，然后使用第二个密钥对第一次的结果进行DES加密，最后再使用第一个密钥对第二次的结果进行DES解密。以上这种加密模式称为加密解密加密(EDE)模式。DES算法的密钥长度是56位，所以三重DES算法的密钥长度是112位。使用两个密钥的三重DES是一种较受欢迎的改进算法，目前已经被用于密钥管理标准ANS X9.17和ISO 87322中。)(DESDESDES111121yxKKK)(DESDES
39、DES1211xyKKK随着密码破译技术和计算机硬件技术的飞速发展，虽然到目前为止还没有一种非常有效的攻击算法能够完全破译DES加密算法，但是考虑到人们对加密算法安全性的担忧，对于DES算法的改进工作从1997年就开始公开进行了。2.3 高级数据加密标准高级数据加密标准AES1997年4月15日，美国国家标准技术研究所(NIST)发起了征集DES的替代算法AES(Advanced Encryption Standard)算法的活动。1997年9月12日，NIST发布了征集算法的正式公告和具体细节，要求AES比三重DES快，至少与三重DES一样安全，具有128位的分组长度，能够支持128、192
40、和256位的密钥长度，同时要求AES要能够在全世界范围内免费使用。1998年8月20日，NIST在“第一次AES候选大会”上公布了满足条件的15个AES的候选算法。1998年8月，NIST从这15个候选算法中选出了5个AES的候选算法，分别是MARS、RC6、Rijndael、Serpent、Twofish。到2000年10月2日，NIST正式宣布Rijndael被选择为高级数据加密标准，该算法是由两位比利时人Daemen 和Rijmen提出的。2.3.1 AES的描述的描述AES也是一个典型的迭代型分组密码，而且其分组长度和密钥长度都可变，分组长度和密钥长度可以独立地指定为128位、192位
41、和256位。现在被采用的AES算法的加密轮数依赖于所选择的子密钥长度。对于选择128位的密钥长度，加密的轮数为10；对于选择192位的密钥长度，加密的轮数为12；对于选择256位的密钥长度，加密的轮数为14。对于128位的消息分组，AES加密算法的执行过程描述如下：(1)输入长度为128位的分组明文x，将其按照一定的规则赋值给消息矩阵State，然后将对应的轮密钥矩阵Roundkey与消息矩阵State进行异或运算AddRoundkey(State，Roundkey)。(2)在加密算法的前N-1轮中，每一轮加密先对消息x应用S盒进行一次字节代换操作，称为ByteSubs(State)；对消息矩
42、阵State做行移位操作，称为ShiftRows(State)；然后对消息矩阵State进行列混合操作，称为MixColumns(State)；最后再与轮密钥Roundkey进行密钥异或运算AddRoundkey(State，Roundkey)。(3)对前N-1轮加密的结果消息矩阵State再依次进行ByteSubs(State)、ShiftRows(State)和AddRoundkey(State，Roundkey)操作。(4)将输出的结果消息矩阵State定义为密文y。其中AddRoundkey(State，Roundkey)、ByteSubs(State)、ShiftRows(State
43、)和MixColumns(State)也被称为AES算法的内部函数。AES中的操作都是以字节为对象的，操作所用到的变量是由一定数量的字节构成的。输入的明文消息x长度是128位，将其表示为16个字节x0，x1，x15，初始化消息矩阵State如下：函数ByteSubs(State)对State的每一个字节进行一个非线性代换，任一个非零字节x被下面的变换所代替：y=Ax1+b (2-1)82F其中 01100011,1111100001111100001111100001111110001111110001111110001111110001bA上述变换的非线性性质来自于逆x-1，如果将该变换直接
44、作用于变量x，那么该变换就是一个线性变换。另外，由于常数矩阵A是一个可逆矩阵，因此函数ByteSubs(State)是可逆的。上面给出的AES算法中ByteSubs(State)操作相当于DES算法中S盒的作用。该代换矩阵也可以看做是AES算法的“S盒”。实际上，函数ByteSubs(State)对State中每一个字节进行的非线性代换与下表给出的AES算法的“S盒”对x进行代换的结果是等价的。下面对表2-9给出的对应关系的有效性进行简单的验证。设x-1=00001001，将其转换成两个十六进制的数字形式为x-1=09，通过表2-9给出的对应关系可知，与x对应的y=01。这个对应关系如果按照公
45、式(2-1)进行计算，相应的过程为1010010000000100010010101yAxbA 将其转换成两个十六进制的数字形式为y=01。可以发现两种方法的结果是一致的。函数ShiftRows(State)在消息矩阵State的每行上进行操作。对于128位的分组长度，它进行以下变换：这个函数的运算结果实际上是对State进行一个简单的换位操作，它重排了元素的位置而不改变元素本身的值。所以函数ShiftRows(State)也是可逆的。函数MixColumns(State)对State的每一列进行操作。以下只描述该函数对一列进行操作的详细过程。首先取当前的消息矩阵State中的一列，定义为32
46、10SSSS把这一列表示成一个三次多项式S(x)=S3x3+S2x2+S1x+S0其中S(x)的系数是字节，所以多项式定义在上。列S(x)上的运算定义为：将多项式S(x)乘以一个固定的3次多项式C(x)，然后和多项式x4+1进行取模运算。具体如下：S(x)C(x)mod(x4+1)(2-2)其中C(x)=C3x3+C2x2+C1x+C0C(x)的系数也是中的元素。82F82F公式(2-2)中的乘法和一个4次多项式进行取模运算的目的是为了使运算结果输出一个3次多项式，从而保证获得一个从一列(对应一个3次多项式)到一列(对应另一个3次多项式)的变换，这个变换在本质上是一个使用已知密钥的代换密码。同
47、时，由于上的多项式C(x)与x4+1是互素的，因此C(x)在中关于x4+1的逆C-1(x)mod(x4+1)存在，所以公式(2-2)的乘法运算是可逆的。2xF2xF函数AddRoundkey(State，Roundkey)将Roundkey和State中的元素逐字节、逐位地进行异或运算。其中Roundkey使用一个固定的密钥编排方案产生，每一轮的Roundkey是不同的。接下来讨论AES的密钥编排方案。对于需要进行N轮加密的AES算法，共需要N+1 个子密钥。下面以128位的种子密钥为例，给出产生11个轮密钥的方法。由于密钥编排算法是以字为基础(每个字包含32位)，因此每一个轮密钥由4个字组成
48、，11个轮密钥共包含44个字，在此表示为w0，w1，w43。具体算法步骤如下：(1)初始化：RCon1=01000000RCon2=02000000RCon3=04000000RCon4=08000000RCon5=10000000RCon6=20000000RCon7=40000000RCon8=80000000RCon9=1B000000RCon10=36000000(2)当0i3时，wi=(key4i，key4i+1，key4i+2，key4i+3)(3)当4i43且i=0 mod 4时，wi=wi-4wi-1(4)当4i43且i0 mod 4时，wi=wi-4(SubWord(RotW
49、ord(wi-1)RConi/4)其中，步骤4中操作RotWord(B0，B1，B2，B3)对四个字节(B0，B1，B2，B3)进行循环移位操作：RotWord(B0，B1，B2，B3)=(B1，B2，B3，B0)操作SubWord(B0，B1，B2，B3)对四个字节(B0，B1，B2，B3)进行置换操作：其中，),(),(SubWord32103210BBBBBBBB3,2,1,0),(SubBytesiBBii以上是AES算法的整个加密过程。与DES算法相同的是，AES算法的解密也是加密的逆过程，由于AES算法的内部函数都是可逆的，因此解密过程仅仅是将密文作为初始输入，按照轮子密钥相反的方
50、向对输入的密文再进行加密的过程，该过程加密的最终结果就可以恢复出相应的明文。2.3.2 AES的分析的分析在AES算法中，每一轮加密常数的不同可以消除可能产生的轮密钥的对称性，同时，轮密钥生成算法的非线性性质消除了产生相同轮密钥的可能性。加/解密过程中使用不同的变换可以避免出现类似DES算法中出现的弱密钥和半弱密钥的可能。经过验证，目前采用的AES加/解密算法能够有效抵御已知的针对DES的所有攻击方法，如部分差分攻击、相关密钥攻击等。到目前为止，公开报道中对于AES算法所能采取的最有效的攻击方法只能是穷举式搜索攻击，所以AES算法是安全的。2.4 国际数据加密标准国际数据加密标准IDEAIDE
