3.2 传统加密方法（对称密码）

传统加密算法是以密钥为基础的，是一种对称加密，加密密钥与解密密钥是相同的，或者可以由其中的一个推知另一个。

在早期的密钥密码体制中，典型的有换位密码和代换密码。

换位是对明文L长字母组中的字母位置进行重新排列，而每个字母本身并不改变。它很像一种字母游戏，打乱字母的顺序，设法把打乱的字母重新组成一个单词。比如：给定明文hedeterminedtogoatonce，将明文分成长为L=6的段，m1=hedete，m2=rmined，m3=togoat，m4=oncexx，最后一段不足6，加添字母x。将各段的字母序号按下述矩阵进行换位：

得到密文如下：

etehedmenrdioaottgnxeoxc

上面的密文利用下述置换矩阵可恢复为明文：

因此，由加密矩阵可推知解密矩阵。

代换有单表代换和多表代换，此处只介绍单表代换。单表代换是对明文的所有字母用同一代换表映射成密文。比如最典型的凯撒密码是对英文的26个字母进行位移代换，即将每一字母向前推移k位，不同的k将得到不同的密文。若选择密钥k=6，则有下述变换，如表3-1所示。

表3-1 密钥为6的凯撒密码映射表

对于明文：she avoided signing the document，经k=6的凯撒密码变换后得到如下密文：MBY UPICXYX MCAHCHA NBY XIWOGYHN。当然这种映射很容易被破译。

稍复杂的单表代换可以使明文和密文的映射关系没什么规律可循，比如字母表中先排列出密钥字母，然后在密钥后面填上其他字母。若用ZHANG作为密钥，则映射关系如表3-2所示。

表3-2 密钥为ZHANG和映射关系表

但无论是上面哪一种，都相对比较简单，在今天的电子时代很容易被破译。现在最常用的对称加密方案是数据加密标准（DES），虽然它正向公钥交出半壁江山，但它依然是数据加密中所用的最重要的加密方法。

3.2.1 数据加密标准（DES）

DES是最著名的保密密钥或对称密钥加密算法，它是由IBM公司在20世纪70年代发展起来的，并经美国政府的加密标准筛选后，于1976年11月被美国政府采用。

DES可以分成初始置换、16次迭代过程和逆置换。在迭代过程中，使用56位密钥对64位的数据块进行加密，并对64位的数据块进行16轮编码。在每轮编码时，首先将待加密的右半部分由32位扩展为48位，然后与由56位密钥生成的48位某一密钥进行异或，得到的结果通过S盒压缩到32位（上述通过图3-2中的函数f完成），这32位数据经过置换再与左半部分异或，最后产生新的右半部分。它的整体框图如图3-2所示。

图3-2D ES整体框图

下面把DES框图用文字分步来进行一下详细说明。

1）DES的明文初始置换。把64位明文按初始置换表换位，如表3-3所示。表中给出的为每位二进制数据的下标。

表3-3 初始置换表

2）在初始置换后，把64位二进制明文分成左32位和右32位，进入迭代。

3）把R₀（32）赋给L₁（32）。

4）将右半部分R₀（32）进行扩展排列，由32位扩展为48位。扩展排列下标次序如表3-4所示。

表3-4 扩展排列表

5）生成第一轮的子密钥，首先把64位密钥每隔7位删除1位，即删除第8、16位等，使之成为56位的密钥。56位密钥经过置换选择1，即生成56位初始子密钥，置换选择1如表3-5所示（表中为数据下标）。

表3-5 置换选择1

6）经过置换选择1后，把56位的初始密钥分成左28位和右28位，对左右两部分分别循环移位LS_i位，各轮移位次数如表3-6所示。然后将两部分拼合起来。

表3-6 各轮移位次数表

7）拼合后，对56位密钥用置换选择2进行置换（置换选择2如表3-7所示，表中为数据下标），置换后即为本轮子密钥，本轮子密钥与经过扩展的数据的右半部分进行异或得到48位数据。

表3-7 置换选择2

8）得到的48位数据按顺序平均分成8组，这8组通过S盒（Substitution Box）变换，把每组的6位输入变成4位输出，从而得到32位数据。S盒变换数据如表3-8所示。

表3-8 S盒数据变换表

（续）

S盒的用法：对于8组中的每组S_i，6个输入端依次为b₁b₂b₃b₄b5b6，求出b1b6合在一起的十进制数并作为行，求出b₂b₃b4b5合在一起表示的十进制数并作为列，在S盒数据表中找出对应的值，即为S_i对应的4位二进制给出的十进制值。

例如：S1的输入为101110，则b₁b₆=（10）2=（2）10，b2b3b4b5=（0111）2=（7）10。

那么在S₁组中查找第2行第7列，可以得到值（11）10，所以S₁（2，7）=11，（11）10的二进制表示形式为（1011）2，得到S₁的输出就为4位二进制数1011。

9）S盒输出的32位数据还要经过Permutation置换，简称P置换（P置换如表3-9所示）。P置换后再与左32位按位异或，所得即为新的右半部分。

表3-9 P置换位置表

10）上面只是16次迭代中的一次，经过16次这样的迭代后，把得到的64位二进制数进行逆初始置换，便得到了64位可输出的密文。逆置换表如表3-10所示。

表3-10 逆初始置换表

至此才算完成了一次DES加密。

DES的解密过程和加密过程类似，不同的16轮子密钥的顺序是颠倒的，即第一轮用子密钥16，第二轮用子密钥15，最后一轮用子密钥1。这个过程用文字表示比较烦琐，但为了让读者对DES加密过程有更强的感性认识，下面用例子来说明DES加密过程的一部分。

假如给出明文为M=’FOOTBALL’，密钥为K=’OVERSEAS’，它们的ASCII码如下：

明文M=（0100011001001111010011110101010001000010010000010100110001001100）2

密钥K=（0100111101010110010001010101001001010011010001010100000101010011）2

1）明文M按表3-3初始变换后得到：

M_{初始置换后}=1111111100001010110011110010011000000000000000001100011000010111

读者可观察表3-3，会很容易发现它的规律，在练习初始变换时，画一张8×8的表格，把明文的二进制数顺序写入，然后依2、4、6、8、1、3、5、7列的次序把数据依次倒写即可。

2）把明文分成左32位和右32位后得到：

L₀（32）=11111111000010101100111100100110

R₀（32）=00000000000000001100011000010111

把R₀（32）赋给L₁（32），即L1（32）=R0（32）。

3）把R₀（32）按表3-4扩展为48位：

R₀（48）=100000000000000000000001011000001100000010101110

4）再来看密钥，把64位的密钥K删除第8、16、24、32、40、48、56、64位，变成56位的K’：

K’= 01001110101011010001001010010101001010001001000000101001

5）K’按表3-5置换选择1进行置换，得到：

K’_{置换选择1}=00000000111111110000000010011001101100100111000000011010

对于密钥的变换同样可以用8×8的表格，把密钥的64位二进制数依次写入表格，先删除最后一列，然后把表格中的数值依1、2、3、4列的次序倒着写数据，写到第36位，即第4列的中间，再从最后一列依7、6、5的次序把数据倒着往前写，最后倒着补上第4列的上面4位。读者可研究一下表3-5置换选择1中下标的次序，就会得出规律。

6）把K’_{置换选择1}分成左28位和右28位：

L₀=0000000011111111000000001001

R₀=1001101100100111000000011010

7）把L₀、R0循环左移LS₁位，通过查表3-6各轮移位次数表可知，LS₁为1，循环左移1位后即有：

L₁=0000000111111110000000010010

R₁=0011011001001110000000110101

8）L₁、R1重新拼合在一起，用置换选择2进行置换（置换见表3-7置换选择2），即可得到第一个子密钥K₁：

K₁=101100000001001001000010111100001000000110000001

9）得到R₀（48）和K₁后，把这两个48位的数值进行异或后得到：

A=001100000001001001000011100100000100000100101111

10）将上面的A值平均分成8组，再通过查表3-8的S盒数据变换表，得到：

A1=001100，S₁（0，6）=11=（1011）2

A2=000001，S₂（1，0）=3=（0011）2

A3=001001，S₃（1，4）=3=（0011）2

A4=000011，S₄（1，1）=8=（1000）2

A5=100100，S₅（2，2）=1=（0001）2

A6=000100，S₆（0，2）=10=（1010）2

A7=000100，S₇（0，2）=2=（0010）2

A8=101111，S₈（3，7）=13=（1101）2

11）依次合并S₁（0，6）到S₈（3，7），得到以下数据：

B=10110011001110000001101000101101

12）对B值进行Permutation置换，查表3-9的P置换位置表，得到：

X₀=01111100101000000100111001000110

13）L₀（32）与X₀按位异或可以得到：

R₁（32）=10000011101010101000000101100000

令L₂（32）=R₁（32），这样第一轮迭代就完成了，有了R₁（32）和L₁（32）就可以开始下一轮迭代了，以此类推就可求出R₁₆（32）和L₁₆（32），然后把R16（32）和L16（32）拼合在一起进行逆初始变换就可得到密文。

DES算法具有极高的安全性，到目前为止，除了用穷举搜索法对DES进行攻击外，还没有发现更有效的办法，即到目前为止还没有发现DES算法有什么陷门。但随着计算机速度的提高和价格下降，DES也存在密钥长度不足、不够复杂以及密钥传递困难等因素，针对DES存在的问题，人们发展了许多变形DES算法，比如多重DES、S盒可选择的DES、具有独立子密钥的DES和G-DES等。

多重DES是将DES进行级联，在不同密钥的作用下连续多次对一组明文进行加密，现在人们建议使用三重DES，并已达成共识。三重DES（TDEA）是将128位的密钥分成两个64位的组，用这两个密钥对明文进行三次加解密。假设两个密钥为K1、K2，首先用密钥K1对明文进行DES加密，然后用K2对上面加密后的结果进行DES解密，最后再用密钥K1对解密后的信息进行DES加密。据称，目前尚无人找到针对此方案的攻击方法。

S盒可选择的DES也称交换S盒的DES算法。它可使S盒的次序随密钥而变化或使S盒的内容本身可变。

3.2.2 其他对称分组密码

（1）国际数据加密算法IDEA

国际数据加密算法（International Data Encryption Algorithm，IDEA）是赖学家（Xuejia Lai）和梅西（Massey）开发的，在1990年首次成型，称为PES（建议的加密标准）。次年，设计者对该算法进行了强化并称之为IPES（改进的建议加密标准）。1992年改名为IDEA，即“国际加密标准”。

IDEA算法的密钥长度为128位，每次加密一个64位的数据块。IDEA密码中使用了3种不同的运算，即逐位异或运算、模2加运算和模2+1乘运算。

IDEA算法由8圈迭代和随后的一个输出变换组成。它将64位的数据分成4块，每个16位，令这4个子块作为迭代第一轮的输出，全部共8圈迭代。每圈迭代都是4个子块彼此间以及16位的子密钥进行异或、模2加运算、模2+1乘运算。任何一轮迭代，第三和第四子块互换。

IDEA有大量的弱密钥，这些弱密钥是否会威胁它的安全性还是一个谜。

（2）LOKI算法

LOKI算法作为DES的一种潜在替代算法于1990年在密码学界首次亮相。LOKI和DES一样以64位二进制分组加密数据，也使用64位密钥（只是其中无奇偶校验位），所有64位均为密钥。LOKI密钥公布之后，有关专家对其进行了研究破译并证明不大于14圈的LOKI算法极易受到差分密码分析等的攻击。不过，这仍然优于56位密钥的DES。