第三节 关于对称加密算法

一、对称加密的基本原理

对称加密算法一般以“块”或“流”的方式对输入信息进行处理。块加密算法的常用算法包括DES、3DES、CAST和Blowfish等，它们一般每次对一个数据块进行处理。至于块的大小，则取决于算法本身（目前多数使用系统均采用64位的块长度），对一个块的处理称为加密算法的“处理单位”。另一方面，流加密算法每次处理的是数据的一个位（或者一个字节），用一个键值适当地进行种子化处理，便能生成一个位（这里的“位”指二进制的位）流。

无论是块加密还是流加密，它们都适用于批量信息的加密处理。块加密算法可采用不同的模式工作，一种模式是每次都用同一个密钥；另一种模式是将上一次操作的结果“喂”给当前操作，从而将数据块连接到一起。综合运用这些模式，便可使一种加密算法变得更为“健壮”，对特定的攻击产生更强的免疫力。例如，块加密算法的基本应用就是“电子密码本（Electronic Code Book, ECB）”模式。每个明文块都加密成一个密文块，由于使用相同的密钥，相同的明文块会加密成相同的密文块，所以对一段已知的明文来说，完全能构建出一个密码本，其中包含所有的密文组合。如果我们知道一个IP数据包已进行了加密处理，那么由于密文的头20个字节代表的是IP头，因此可利用一个密码本推断出真实的密钥。

在块加密算法的具体应用中，由于不能保证输入数据的长度正好为一个密码块长度的整数倍，所以根据具体的模式，需要对输入进行适当的填充。假如块的长度是64位，而最后一个输入块的大小仅为48位，那么就有必要增添16位的填充数据，然后才能执行加密（或解密）运算。

加密块链接（CBC）模式可取得前一个密文块，并在对下一个明文块进行加密之前，先对两者执行一次XOR运算，如图1.3所示。假如是第一个块，那么与它进行XOR运算的是一个初始化矢量（Initialization Vector, IV）。IV必须具有“健壮”的伪随机特性，以确保完全一致的明文不会产生完全一致的密文。解密过程与加密相反：每个块都会进行解密，并在对前一个块进行解密之前，对两者进行一次XOR运算。解密到第一个块时，它同样会与IV进行XOR运算。目前使用的所有加密算法都属于块加密算法，采用CBC模式运行。

其他流行的模式包括加密回馈模式（Cipher Feedback Mode, CFB）和输出回馈模式（Output Feedback Mode, OFB），前者的前一个密文块会被加密，并与当前的明文块进行XOR运算（第一个明文块只与IV进行XOR运算）；后者会维持一种加密状态，不断地加密，并与明文块进行XOR运算，以生成密文（IV代表初始的加密状态）。

二、DES算法实现

数据加密标准（Data Encryption Standard, DES）是使用最为普遍的对称密钥算法。DES算法于1975年由IBM发明并公开发表，并于1976年批准成为美国政府标准。DES算法在POS、ATM、磁卡及智能卡（IC卡）、加油站、高速公路收费站等领域被广泛应用，以此来实现关键数据的保密，如信用卡持卡人的PIN的加密传输，IC卡与POS间的双向认证、金融交易数据包的MAC校验等，均用到DES算法。

DES算法的处理速度比较快。根据RSA实验室提供的数据，当DES完全由软件实现时，它至少比RSA算法快100倍。如果由硬件实现，DES比RSA快1000甚至10000倍。因为DES使用S盒（或称选择盒，是一组高度非线性函数。在DES中S盒像一组表，是DES真正执行加密，解密运算的函数部分）运算，只使用简单的表查找功能，而RSA却则建立在非常大的整数运算上。

DES使用相同的加密、解密算法，密钥是任意一个64位的自然数。算法的工作方式决定了只有56位有效（8位用作校验）。NIST授权DES成为美国政府的加密标准，但只适用于加密“绝密级以下信息”，尽管DES被认为十分安全，但确实存在方法可以攻破它。

通过穷尽搜索密钥空间，提供总共256（大约7.2×1016）个可能的密钥。如果每秒能检测一百万个密钥，则需2000年。但有一组Internet用户，花费了4个多月时间分工合作解决了RSA DES挑战并最终攻破了这一算法。

该小组在检验了大约18×1015个密钥后找到了正确的密钥，并恢复了如下明文。

strong cryptography makes the world a safer place.

该小组采用“强行攻击（Brute-Force）”的技术，即所有参加这一挑战的计算机搜索所有可能的密钥，一共有超过72057594037927936个密钥。当把这一正确密钥报告给RSA Data Security公司时，该小组已经搜索了大约所有可能密钥的25%。强行攻击是破译DES密码的通用方法，通过不同的加密分析，可以将密钥数量降至247个，但这仍是一个很大的工程。如果DES使用长度超过56位的密钥，那么破译它的可能性几乎为零。

下面我们详细分析一下DES的处理过程。DES数据加密算法的基本流程如图1.4所示。该算法输入的是64位的明文，在64位的密钥控制下，通过初始换位IP变成T0=IP(T)，再对T0经过16层的加密变换，最后再通过逆初始变换得到64位的密文。密文的每一位都由明文的每一位和密钥的每一位联合确定。DES的加密过程可分为加密处理、加密变换和子密钥生成几个部分。下面分别进行分析。

1．加密处理过程

（1）初始变换

加密处理首先要对64位的明文按表1.1所示的初始换位表IP进行变换。表中的数值表示输入位被置换后的新位的位置。例如，输入的第58位，在输出时被置换到第1位；输入的第7位，在输出时被置换到第64位。

（2）加密处理

上述换位处理的输出，中间要经过16层复杂的加密变换。初始换位的64位的输出成为下一步的输入，此64位分成左、右两个32位，分别记为L0和R0，从L0、R0到L16、R16共进行16轮加密变换。换完之后，若经过第n轮处理后的左右32位分别为Ln和Rn，则Ln和Rn可做如下的定义。

Ln=Rn-1

Rn=Ln-1⊕f（Rn-1, Kn）

这里，Kn是向第n轮输入的48位的子密钥；Ln-1和Rn-1分别是第n-1轮加密的输出；f是Mangler函数。过程如图1.5和图1.6所示。

（3）最后换位

进行16轮的加密变换之后，将L16和R16合成64位的数据，再按表1.2所示的最后换位表进行IP-1的换位，得到64位的密文，这就是DES加密的结果。

2．加密变换

计算f(R, K)的方式如图1.7所示。在DES算法中，其他部分都是线性的，而f(R, K)变换是非线性的，因此可以产生强度很高的密码。

32位的R先按表1.3所示的扩展换位表E进行扩展换位处理，得到48位的R'。将这48位的R’和48位的密钥K进行异或运算，并分成6位的8个分组，输入S1～S8的8个S盒中，S1～S8称为选择函数，这些S盒输入6位，输出4位。S盒如表1.4所示。

一个S盒中具有四种替换表（用行号0、1、2、3表示），究竟采用哪一行，要通过输入的六位的开头和末尾两位选定，然后按选定的替换表将输入的六位的中间四位进行代替，下面举例说明。当向S1输入“011011”时，因开头和结尾的组合是“01”，所以选中编号为“1”的替代表；又根据中间四位“1101”，选定第13列，查表第1行第13列所指的值为5，即输出为“0101”，这四位就是经过替代后的值。按此进行，输出32位。再用表1.5所示的单纯换位表P进行变换，这样就完成了f(R, K)的变换。

3．子密钥的生成

下面说明子密钥K1～K16的16个子密钥的生成（Mangler函数）过程，在64位的密钥中包含了8位的奇偶校验位，所以密钥的实际长度为56位，而每轮要生成48位的子密钥。

输入的64位密钥，首先通过压缩换位（PC-1）去掉校验位，输出56位的密钥，每层分成两部分，上部分28位为C0，下部分为D0。C0和D0依次进行循环左移操作生成了C1和D1，将C1和D1合成为56位，再通过压缩换位（PC-2）输出48位的子密钥K1，再将C1和D1进行循环左移操作和PC-2压缩换位，得到子密钥K2……，以此类推，就可以得到16个子密钥。密钥压缩换位如表1.6所示。要注意的是，在产生子密钥的过程中，L1、L2、L9、L16是循环左移1位，其余都左移2位，左移次数如表1.7所示。

4．解密处理

从密文到明文的解密处理过程可采用与加密完成相同的算法。不过，解密要用加密的逆变换，也就是把上面的最后换位表和初始换位表完全倒过来变换，即第1次用第16个子密钥K16，第2次用K15……，依此类推。另外，在16轮的变换处理中，由于Rn-1=Ln和Ln-1=Rn⊕f（Ln, Kn），因此要求出Rn-1和Ln-1，只要知道Ln、Rn和Kn，并使用函数f所表示的变换即可实现。从而在各层的变换中，如果采用与加密时相同的Kn来处理就可实现解密。具体来说，输入DES算法中的密文，经过初始换位得到L16和R16，第1层处理时的密钥是逆序的，用K16求出L15和R15，然后用K15求出L14和R14，依此类推即可完成解密处理。

三、其他对称加密算法

1．国际数据加密算法

国际数据加密算法（IDEA）是加密算法中最好、最安全的一种。由瑞士联邦科学技术学院（SFT）的Xuejia Lai和James Massey提出。IDEA使用三个64位的块，以进一步防范加密分析过程。IDEA使用了密码反馈操作，使得算法强度更高。在这种模式下，密文输出也被用来作为加密运算的输入。

IDEA的另一个重要特点是它的密钥长度为128位。正如DES，密钥越长，其保密性越好。当试图破译IDEA时，它和DES一样没有泄露任何明文组成的信息。IDEA能够将一位的明文扩散到多位的密文中，以达到完全隐藏明文的统计结构。

2．CAST算法

CAST算法由Carlisle Adams及Stafford Tavares开发。该算法使用64位的块长及64位的密钥，它使用六个八位输入、32位输出的S盒，这些S盒的结构太复杂，已经超出了本书的范围。想得到更多关于此方面的信息，可参考相关书籍。

CAST加密过程是将明文块分为两个子块：左子块和右子块。该算法有八圈，每圈一半明文经过f函数运算与某一密钥组合，然后将结果与另半部分异或，左子块形成新的右子块，原来的右子块变为左子块。经过八次这样的运算之后，这两部分的输出就是密文，可见这种运算十分简单。表1.8给出了一些函数。

3．Skipjack算法

Skipjack算法是NSA为Clipper芯片开发的加密算法。它被确定为美国政府机密，没有太多关于该算法的描述。但有一点已经清楚：它是一个对称密钥算法，使用80位的密钥，且加、解密需要进行32轮运算。

Clipper芯片是一种使用Skipjack算法的加密芯片，是一种由NSA设计的商用加密芯片。AT&T用它加密语音电话线路，NSA采用Skipjack算法加密自己的信息系统。因此，可以认为算法本身是安全的。Skipjack算法使用长为80位的密钥，也就是说有280（大约1024）或更多可能的密钥可供使用。这意味着要用4000亿年才能穷尽该算法的密钥空间。

Clipper芯片使用带两个密钥的Skipjack算法。无论是谁，只要知道了“主密钥”就可以解密所有用该芯片加密的信息。因此，在必要情况下，NSA至少在理论上可以利用它的“主密钥”破译一切用Clipper芯片加密的信息。这种在算法中留有后门的方法被称为第三方密钥（Key Escrow）。

每块Clipper芯片内有一个独一无二的80位单元密钥（KU）。拥有KU可以解开所有经由这块芯片产生的密文。KU分两个子密钥KU1和KU2，满足KU1⊕KU2=KU，这两个子密钥分别交由两个独立的可信任的机构保存。此外，每块芯片内还有一个80位的族密钥（KF）和一个序列号（UID）。

在进行秘密通信之前，双方先商定一个80位的会话密码（Session Key, KS）。双方的通信内容用KS来加密，这里用EKS[M]来表示密文。除传输密文外，每次通信时，另有一段所谓的“执法访问区”（Law Enforcement Access Field, LEAF）也会传到对方。LEAF的构成是将会话密钥KS用单元密钥KU加密之后，再会同芯片的序列号UID及一串认证码（Authentication Code）P，以族密钥KF将其全部加密，即

LEAF = EKF(UIDA||KKUA(KS)||PA)

密文接收者首先对LEAF解密，验证其中的认证码以鉴别密文的真伪，其次用共同会话密钥解开密文。执法机关要解开此密文时，先用KF解开LEAF，得到芯片的序列号UID的两个子密钥KU1和KU2，这样就能解开密文。

通过对上面几种对称加密算法的讨论，基本的结论是：在短时间内DES不会受到致命攻击。IDEA的设计者是民间学者，不像DES和Skipjack那样受到NSA的影响，因此人们比较接受IDEA算法没有后门的说法。此外，IDEA采用128位的密钥，较DES和Skipjack的56位和80位都长，因此其抗攻击能力也比较强。

冷战结束后，密码学的研究几乎完全从军事目的转成商业应用。密码学与其他科学的不同之处在于，其研究和发展必须是“本土性”的科学，不能像其他科学一样能依赖引进，这里归纳几个设计密码算法的基本原则。

1）安全性：使用密钥的长度应在100位左右，同时还要考虑运算轮转的次数。

2）简易性：尽量使用简单的数学及逻辑运算以加快速度。

3）混淆性：DES使用S盒，IDEA使用三种函数的混合，其目的就是使密文、明文和密钥的关系复杂到没法分析。

4）扩散性：目的在于改变明文中的一位，对密文中的所有位都影响。

5）规律性：目的在于方便用软件和硬件实现，规律性一般体现在操作的重复上。

6）相同性：加密与解密结构应相同，其差别只在于子密钥产生的不同而已。