对称密码技术

2.3.1　对称密码技术

对称密钥密码系统使用的加密密钥和解密密钥是相同的，或者可以简单地相互推导出来。典型的对称密钥密码系统是数据加密标准（DES－data encryption standard），此外还有IDEA（international data encryption algorithm）、AES（advanced encryption standard）等。

1.数据加密标准（DES）

DES加密算法的数据流程如图2-2所示。该算法输入的是64比特的明文，在64比特的密钥控制下，通过初始换位IP变成T₀＝IP（T），再对T0经过16层的加密变换，最后通过逆初始变换（也称最后变换）得到64比特的密文。密文的每一比特都是由明文的每一比特和密钥的每一比特联合确定的。DE5的加密过程可分为加密处理、加密变换及子密钥的生成几个部分，如图2-3所示。下面，分别说明加密处理、加密变换、子密钥生成和解密几个过程。

图2-2　DES加密的数据流程

图2-3　DES算法的框图

（1）加密处理

①初始换位：加密处理首先要对64比特的明文按表2-3所示的初始换位表进行IP换位。

表2-3　初始换位表lP

表中的数值表示输入比特被置换后的新比特位置。例如，输入的第58比特，在输出时被置换到第1比特的位置；输入的第2比特，在输出时被置换到第8比特的位置；输入的第1比特，在输出时被置换到第40比特的位置；输入的第7比特，在输出时被置换到第64比特的位置上。

②加密处理：上述换位处理的输出，中间要经过16层复杂的加密变换。经过初始换位的64比特的输出变为下一步的输入，此64比特分成左、右两个32比特，左为L₀，右为R₀，从L₀和R₀到L₁₆和R₁₆共进行了如图2-4所示的16层加密变换。换完之后，若经过第n层处理后的左、右32比特分别为L_n和R_n，则L_n和R_n可作如下的定义：

L_n＝R_n－1　　　　　　　　

R_n＝L_n－1⊕f（R_n－1，K_n）

图2-4　第n层的加密变换

这里，K_n是向第n层输入的48比特的密钥；L_n－1和R_n－1分别是第n－1层的输出；f是以R_n－1和K_n为变量的输出32比特的函数。

③最后换位：进行完16次的加密变换之后，将L₁₆和R₁₆合成64位数据，再按表2-4所示的最后换位表IP^－1进行换位，得到64比特的密文，这就是DES加密的结果。

表2-4　最后换位表IP^－1

由图2-5可以看出，表2-4和表2-3是完全的逆变换。

图2-5　初始换位和最后换位

（2）加密变换

计算f（R，K）的方式如图2-6所示。在DES算法中，其他部分都是线性的，而这个f（R，K）变换是非线性的。因此可以产生强度很高的密码。

图2-6　f（R，K）的计算

32比特的R首先按表2-5所示的扩展型换位表E进行换位，同时把一部分比特重复使用，便可扩大成48比特。这样得到了48比特的R′。按照从头算起，每4比特再加上后面的2比特，便形成每6比特一组的8个分组，即

R₃₂R₁R₂R₃R₄R₅，R₄R₅R₆R₇R₈R₉，…，…R₂₈R₂₉，R₂₈R₂₉R₃₀R₃₁R₃₂R₁

表2-5　扩展型换位表E

这48比特的R′和48比特的密钥K进行异或运算，并分成每组6比特的8个分组，输入到S₁～S₈的8个S盒中去，S₁～S₈称为选择函数（Selection Function）。这些S盒输入是6比特，输出是4比特。

表2-6列举的是一个S盒中S₁的代替表。一个S盒中备有四种代替表（行号为0，1，2，3），究竟采用哪一种代替表，要通过输入的6比特的开头和末尾两个比特选定，然后按选定的代替表将输入的6比特的中间4比特进行代替。

表2-6　S盒的代替表（S₁）

下面举一个例子予以说明。当向S₁输入一个二进制状态01 1011时，因开头的0和末尾的1合起来为01（即十进制数1），所以选中了编号为1的代替表；又因中间4个比特状态为1101（十进制数13），表示选第13列。第1行第13列所指示的值为5，即输出状态为0101，这4个比特就是经过代替之后的状态。表2-7给出了S₁～S₈的S盒代替表，其中的每一行代表一种代替表。接着，从8个S盒输出的32比特，根据表2-8所示的单纯换位表P进行换位，这样便实现了f（R，K）的变换。

表2-7　S盒代替表

表2-8　单纯换位表P

（3）子密钥的生成

下面，说明子密钥K₁～K₁₆的16层子密钥的生成过程。在64比特的密钥里包含了8位的奇偶校验位，所以实际密钥长度是56比特，而每层要生成48比特的子密钥。

输入64比特的密钥，首先通过压缩型换位PC-1（Permutation Choice）去掉奇偶校验位，再将不含奇偶校验位的56比特进行输出，而每层要分成两部分，上部分的28比特为C₀，下部分的28比特为D₀，如表2-9所示。C₀和D₀依次进行循环左移位，这样就生成了C₁和D₁，然后将C₁和D₁合成56位，再通过压缩型换位PC-2（表2-10），输出的结果即为48位的子密钥K₁。再将C₁和D₁进行循环左移位和PC-2的转换，即得子密钥K₂…依次类推，就可以得出16级的子密钥K₁，K₂，…，K16。16层子密钥的生成过程如图2-3右半部所示。值得注意的是，在产生16级子密钥的过程中，L₁、L₂、L₉、L₁₆是循环左移1位的变换，而其余的L_n都是循环左移2位的变换。16层变换中的循环左移位次数如表2-11所示。

表2-9　密钥的压缩型变换PC-1

表2-10　密钥的压缩型变换PC-2

表2-11　密钥生成中的循环左移位次数

（4）解密处理

从密文到明文的解密处理可采用与加密算法完全相同的算法。不过，解密要用加密的逆变换，也就是把上述的最后换位表IP^－1和初始换位表IP完全倒过来变换。另外，在16层的变换处理中，由于R_n－1＝L_n和L_n－1＝R_n⊕f〔L_n，K_n〕，因此要求出R_n－1和L_n－1只要知道L_n、R_n和K_n，并使用同一个函数f所表示的变换便可以实现，从而在各层变换中，如果采用与加密时相同的K_n来处理，就能实现解密。具体地说，输入DES算法中的密文，经过初始换位可得到L₁₆和R₁₆，第1层处理时的密钥是逆序的，用K₁₆可以求出L₁₅和R₁₅，其中f（R，K）即使不可逆也没有关系；然后用K₁₅进行变换求出L₁₄和R₁₄。依次类推，经过16层的变换即可得到L₀和R₀。

（5）DES加密的评价

DES加密法的保密性到底如何？早在DES被正式公布为数据加密标准之前，就展开了热烈的讨论。由于目前尚无一个评价加密系统性能的统一标准和严格的理论，因此人们只能从一个密码系统抵抗现有解密手段的能力来评价它的好坏。自1975年以来，美国的许多机构、公司和学者，包括国家保密局（NSA）、NBS、IBM公司、DELL实验室和一大批著名的密码学专家都对DES进行了大量的研究，但迄今尚未找到破译DES的一种行之有效的方法。因此，认为DES具有良好的保密性能和抗分析破译性能，并已广泛地应用于金融业，不仅在美国，而且日本和西欧也使用DES，并且还将继续下去。目前，已有DES的软、硬件产品，它们在各种算法的加密产品中占有很大的比重，最具有代表性，影响最大，应用最广。20世纪80年代中期，人们看到DES算法迭代次数少，密钥长度短，其代替函数Si中可能有不安全因素，因而曾经有过不少批评，有人甚至还想取消它，但是DES以它顽强的生命力至今仍占据着加密技术的霸主地位。目前，DES的研究和应用还在不断发展，出现了一些增强DES的设想，如增长密钥长度和改进代替函数Si等，对DES的分析和研究还在继续深入。虽然1984年美国国家安全局决定研制新的数据加密标准CCEP，但从发展趋势上看，CCEP是按封闭的原则管理的，应用范围很有限，它不再具有技术上的开放性和使用上的灵活性，因此受到金融界的强烈反对。由于反对的呼声很高，美国政府不得不于1987年初废除了1984年签署的用CCEP取代DES加密标准的命令，所以它很难取代DES的广泛应用。DES作为密码学史上影响最大、应用最广的数据加密算法，其成功是当之无愧的。

（6）二重DES

为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用。图2-7为二重DES。

图2-7　二重DES

但上式对DES并不成立。将DES加密过程64比特分组到64比特分组的映射看作一个置换，如果考虑2⁶⁴个所有可能的输入分组，则密钥给定后，DES的加密将把每个输入分组映射到一个唯一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实施。对2⁶⁴个输入分组，总映射个数为（2⁶⁴）！＞（₁₀10²⁰）。

另一方面，对每个不同的密钥，DES都定义了一个映射，总映射数为2⁵⁶＜10¹⁷。

因此，可假定用两个不同的密钥两次使用DES，可得一个新映射，而且这一新映射不出现在单重DES定义的映射中，这一假定已于1992年被证明。所以使用二重DES产生的映射不会等价于单重DES加密。但对二重DES有以下一种称为中途相遇攻击的攻击方案，这种攻击不依赖于DES的任何特性，因而可用于攻击任何分组密码。其基本思想如下：

如果已知一个明—密文对（P，C），攻击的实施可如下进行：首先，用2⁵⁶个所有可能的K₁对P加密，将加密结果存入一表并对表按X排序，然后用2⁵⁶个所有可能的K₂对C解密，在上述表中查找与C解密结果相匹配的项，如果找到，则记下相应的K₁和K₂。最后再用一新的明—密文对（P′，C′）检验上面找到的K₁和K₂，用K₁和K₂对P′两次加密，若结果等于C′，就可确定K₁和K₂是所要找的密钥。

对已知的明文P，二重DES能产生2⁶⁴个可能的密文。而可能的密钥个数为2¹¹²，所以平均来说，对一个已知的明文，有2¹¹²/2⁶⁴＝2⁴⁸个密钥可产生已知的密文。而再经过另外一对明—密文的检验，误报率将下降到2^48－64＝2^－16。所以在实施中途相遇攻击时，如果已知两对明—密文，则找到正确密钥的概率为1～2^－16。

（7）两个密钥的三重DES

抵抗中途相遇攻击的一种方法是使用三个不同的密钥做三次加密，从而可使已知明文攻击的代价增加到2¹¹²。然而又会使密钥长度增加到56×3＝168比特，因而过于笨重。一种实用的方法是仅使用两个密钥做三次加密，实现方式为加密—解密—加密，简记为EDE（Encrypt—Decrypt—Encrypt），见图2-8。

图2-8　两个密钥的三重DES

第二步解密的目的仅在于使得用户可对一重DES加密的数据解密。此方案已在密钥管理标准ANS X.917和ISO 8732中被采用。

（8）三个密钥的三重DES

三个密钥的三重DES密钥长度为168比特，加密方式为

令K₃＝K₂或K₁＝K₂，则变为一重DES。

三个密钥的三重DES已在因特网的许多应用（如PGF和S/MIME）中被采用。

2.国际数据加密算法（IDEA）

国际数据加密算法IDEA是瑞士的著名学者提出的。1990年XueJia Lai和Massey开发出IDEA加密算法雏形，称为PES，即“建议的加密标准”。第二年，根据有关专家对这一密码算法的分析结果，设计者对该算法进行了强化并称之为IPES，即“改进的建议加密标准”。该算法于1992年更名为IDEA，即“国际加密标准”。这种算法是在DES算法的基础上发展出来的，类似于三重DES。发展IDEA也是因为感到DES具有密钥太短等缺点。

IDEA算法的密钥长度为128位，针对64位的数据进行加密或解密操作。XueJia Lai已证明IDEA算法在其8轮迭代的第4圈之后便不受差分密码分析的影响了。假定穷举法攻击有效的话，那么即使设计一种每秒钟可以试验10亿个密钥的专用芯片，并将10亿片这样的芯片用于此项工作，仍需1 013年才能解决问题；另一方面，若用1 024片这样的芯片，有可能在一天内找到密钥，不过人们还无法找到足够的硅原子来制造这样一台机器。目前，尚无公开发表的试图对IDEA进行密码分析的文章。因此，就现在来看，应当说IDEA是非常安全的。

IDEA有大量的弱密钥，这些弱密钥是否会威胁它的安全性还是一个谜。IDEA密码能够抵抗差分分析和线性分析。设计者Lai认为IDEA不是一个群，但目前仍未得到证实。Eurocrypt’97会议上给出了两种新的攻击低圈IDEA的方法，第一种攻击方法可破译大约3.5-圈的IDEA；第二种攻击方法可破译大约3-圈的IDEA。但从分析结果来看，这两种攻击方法并未对IDEA的安全性构成威胁。

类似于DES，IDEA算法也是一种数据块加密算法，它设计了一系列加密轮次，每轮加密都使用从完整的加密密钥中生成的一个子密钥。与DES的不同处在于，它采用软件实现和采用硬件实现同样快速。

由于IDEA是在美国之外提出并发展起来的，避开了美国法律上对加密技术的诸多限制，因此，有关IDEA算法和实现技术的书籍都可以自由出版和交流，可极大地促进IDEA的发展和完善。但由于该算法出现的时间不长，针对它的攻击也还不多，还未经过较长时间的考验。因此，尚不能判断出它的优势和缺陷。

有关IDEA算法的详细过程，请参考：［美］William Stallings.密码编码学与网络安全：原理与实践（2版）.杨明等译.北京：电子工业出版社，2001。

3.高级加密标准（AES）

数据加密标准（DES）作为20世纪70年代的加密标准，其加密强度越来越不能满足人们的要求。DES的密钥长度只有56比特，随着计算能力的不断提高，利用穷举搜索的方法攻击DES是完全可能的。特别是在政府或者其他组织的支持下，设计专门的硬件来攻击DES已经是轻而易举的事情。在这种情况下，美国国家标准技术局（NIST）在1997年开始倡导制定高级加密标准（AES）替代DES以满足21世纪的信息加密需求。经过几年的招标、筛选，NIST于2000年底最终确定了AES（RIJNDAEL）。AES是由比利时密码专家Joan Daemen和Vincent Rijmen共同设计的。下面简单地介绍AES。

RIJNDAEL的信息块长度和加密密钥长度都是可变的，它们都可以是128比特、192比特和256比特。为了方便数据的计算和算法的描述，我们首先把信息块做如下的处理。以192比特的信息块为例，假设信息块是m₀m₁…m₁₉₁，写成字节形式就是a₀₀a₀₁…a₀₅a₁₀a₁₁…a₁₅…a₃₀a₃₁…a₃₅或者写成字的形式就是w₀w₁…w₅，如图2-9所示。

图2-9　192比特信息的字表示

我们也可以对加密密钥做类似的处理。设N_b为信息块经过上述处理后得到的字的个数，N_k为加密密钥经过上述处理后得到的字的个数。那么根据信息块的长度，N_b＝4，6，8，根据加密密钥的长度，N_k＝4，6，8，加密的轮数N_r根据表2-12由N_b和N_k控制。

表2-12　N_r的取值

整个算法包括加密过程与轮密钥生成两个独立的部分。

（1）加密过程

设信息块是M，轮密钥分别是K₀，K₁，…，Kn_r－1，加密过程如图2-10所示。解密过程把加密过程完全反过来即可。

图2-10　AES的加密过程

①ByteSub函数

把每个8比特的字节看成有限域GF（2⁸）中的一个元素，那么函数ByteSub是作用在每个字节上的非线性变换，它定义为：ByteSub：GF（2⁸）→GF（2⁸）

如右图：

图2-11描述了信息块长度是192比特时，函数ByteSub的作用情况。

图2-11　函数ByteSub

②ShiftRow函数

把信息块记为4行、N_b列的矩阵形式，函数ShiftRow就是对每行实行不同的左移位，每行的左移位数C₁，C₂，C₃分别由N_b按照表2-13决定。

表2-13　左移位函数的确定

函数ShiftRow的作用可表示成图2-12。

图2-12　函数ShiftRow

③MixColumn函数

MixColumn函数是GF（2⁸）⁴上的一个线性变换，变换矩阵C定义为：

其中的运算均为在GF（2⁸）中进行。图2-13描述了信息块长度是192比特时，MixColumn函数的作用情况。此处矩阵C中的元素xy理解为两个4比特长的二进制数的串接，比如02理解为0000 0010。

图2-13　函数MixColumn

（2）轮密钥的生成

轮密钥的生成过程包括加密密钥的扩张和轮密钥的选取两个部分。

①加密密钥的扩张

当N_r≤6时，对于N_k≤i＜N_b（N_r＋1），如图2-14（a）所示。

当N_r＞6时，对于N_k≤i＜N_b（N_r＋1），如图2-14（b）所示。

其中，RotByte把（a，b，c，d）变为（b，c，d，a），a，b，c，d是8比特字节；

Rcont［i］＝（RC［i］，00，00，00）；RC［1］＝1，RC［i］＝xRC［i－1］＝x^i－1，即RC［i］表示有限域GF（2⁸）中值为x^i－1的元素。

图2-14　密钥扩张

②轮密钥的选取

加密密钥经过扩张产生了N_b（N_r＋1）个32比特字，把它们均等地分成N_r＋1块，每块包含N_b个32比特字，那么第一个轮密钥就是第一个块，第二个轮密钥就是第二个块，依此类推得到所有的轮密钥。

（3）关于AES的讨论

AES的原型是Square算法，它的设计策略是宽轨迹策略（Wide Trail Strategy）。这种策略是针对差分分析和线性分析提出来的，是一个分组迭代密码，具有可变的分组长度和密钥长度。Rijndael汇聚了安全、性能好、效率高、可实现性和灵活性等优点，尤其是在无论有无反馈模式的计算环境下的软硬件中。Rijndael对内存的需求非常低，也使它很适合用于受限制的环境中，Rijndael的操作简单并可抵御强大和实时的攻击。此外，它还有许多未被特别强调的防御性。

与其他分组码相比，AES具有如下特点：①可变的密钥长度；②混合的运算；③数据相关的圈数；④密钥相关的圈数；⑤密钥相关的S盒；⑥长密钥调度算法；⑦可变长明文/密文块长度；⑧可变圈数；⑨每圈操作作用于全部数据。