3.2 对称密码体制

3.2.1 对称密码体制概述

密码体制可以用一个七元组来表示：（M，C，K，K′，ζ，ε，v），其中：

● M表示明文消息空间，由某个字母表上的字符串构成。

● C表示密文消息空间，即所有可能的密文消息集合。

● K为加密密钥空间，K′为解密密钥空间。

● 有效的密钥生成算法ς:N→K×K′。

● 有效的加密算法ε:M ×K→C。

● 有效的解密算法υ:C×K′→M。

对于整数1^l，ς（1^l）输出长为l的密钥对（ke,kd）∈K × K′，对于ke∈K和m∈M，将加密变换表示为c=ε_ke（m），称之为m在密钥ke下加密得到c；将解密变换表示为m=v_kd（c），称之为c在密钥kd下解密得到m。对于所有的m∈M和所有的ke∈K，一定存在kd∈K′：v_kd（ε_ke（m））=m。

在密码体制的定义中，如果kd=ke，即加密密钥与解密密钥相同，称为对称密码体制（Symmetric Cryptosystem）或单钥密码体制（One-key Cryptosystem）。如果加密和解密使用不同的密钥，即对于每一个ke∈K，存在kd∈K′，这两个密钥是不同的并且互相匹配；加密密钥ke公开，称为公钥，ke的拥有者可以使用相匹配的私钥kd来解密在ke下加密过的密文。kd≠ke的密码体制称为非对称密码体制（Asymmetric Cryptosystem）或公钥密码体制（Public Key Cryptosystem），亦称双钥密码体制（Two Key Cryptosystem）。

在单钥密码体制下，必须通过安全可靠的途径将密钥送至接收端，系统的保密性取决于密钥的安全性。因此，在单钥密码体制下，密钥的产生和密钥的管理是一个重要的研究课题，即如何产生满足保密要求的密钥以及将密钥安全可靠地分配给通信对方。密钥的产生、分配、存储、销毁等都是密钥管理的范畴。再好的密码算法，如果其密钥管理出现问题，就很难保证系统的安全性。

按照对明文消息进行加密的方式，单钥密码体制可分为两类，即流密码（Stream Cipher）和分组密码（Block Cipher）。流密码是明文消息按字符进行逐位加密，分组密码是将明文消息分组（如128位一组），分组进行加密。在无线网络安全技术中，流密码（如RC4）和分组密码（如DES和AES）都是重要的加密技术。在这里，重点介绍几种常用的分组密码算法。

1.分组密码的基本原理

分组密码及其应用的研究始于20世纪70年代中期，至今已有40多年的历史。其间，各国学者对分组密码的理论、技术和应用进行了大量的探讨和研究，提出了众多的分组密码算法，如IDEA、FEAL、RC-5、GOST等，使分组密码的理论与技术日臻完善，为分组密码的应用开辟了广阔的前景。

分组密码是将明文消息编码表示后的数字序列x₀,x₁,…,x_i,…划分成长为n的组x=（x₀,x₁,…,x_n-1），各组长为n的矢量分别在密钥k=（k₀,k₁,…,k_t-1）的控制下变换成长度为m的输出数字序列y=（y₀,y₁,…,y_m-1），如图3.5所示。

分组密码与流密码的不同之处在于输出的每一位数字不是只与相应时刻输入明文数字有关，而是与一组长为n的明文数字有关。在相同密钥下，分组密码对长为n的输入明文组所实施的变换是相同的，所以只需研究对任意一组明文数字的变换规则，这种密码实质上是对字长为n的数字序列的代换密码。

2.分组密码的安全性

在分组密码发展的几十年间，密码分析和密码设计始终是相互竞争和相互推动的，对分组密码安全性的讨论也越来越多。一些在当时被认为是安全的算法随着时间的推移以及密码攻击方法和能力的提高，已被攻破。例如已广泛使用了20多年的数据加密标准DES，在1997年6月18日，被美国科罗拉多州的一个以Rocke Verser为首的工作组破译，该破译小组成员利用美国和加拿大联网于互联网上的数万台个人计算机的空闲CPU时间，采用“穷举搜索”技术进行破译。本次破译成功证实了DES的不安全性，同时也促使NIST推出新的高级加密标准（AES）。目前对分组密码算法安全性的讨论包括差分分析、线性分析、穷举搜索等几个方面。从理论上讲，差分密码分析和线性密码分析是目前攻击分组密码的最有效的方法；而从实际上说，穷举搜索等强力攻击是攻击分组密码的最可靠方法。截止到现在，已有大量文献对分组密码的设计和测试进行研究，并归纳出许多有价值的设计和安全性准则。

目前对常见的分组密码的技术攻击方法简单介绍如下。

（1）强力攻击

在唯密文攻击中，密码分析者依次使用密钥空间中的所有密钥来解释一个或多个截获的密文，直至得到一个或多个有意义的明文块。在已知（选择）明文攻击下，密码攻击者先试用密钥空间中的所有可能的密钥对一个已知明文加密，将加密结果同该明文相应的已知密文比较，直至二者相符，然后再利用其他几个已知明密文对来验证该密钥的正确性。实际上，强力攻击适合于任何分组密码。

（2）线性攻击

线性攻击（也称线性分析）是一种已知明文攻击方法，最早由Matsui在1993年提出，该攻击主要利用了明文、密文和密钥的若干位之间的线性关系。它用于攻击DES的复杂度约为2⁴³。

（3）差分攻击

差分攻击（也称差分分析）是一种选择明文攻击方法，最早由Biham和Shamir在1990年引入，该算法主要是利用了明文对的特殊差分对相应的密文对差分的影响，通过分析某个（些）最大概率差分来确定可能密钥的概率并找出最可能的密钥。差分分析是目前用于攻击分组密码的最强有力的方法之一。它用于攻击DES的复杂度约为2⁴⁷。

（4）相关密钥攻击

类似于差分分析，相关密钥攻击（也称相关密钥密码分析）利用密钥的差分来攻击分组密码，这是因为Biham证明了许多分组密码的密钥编排算法明显保持了密钥间的关系。显然，这种攻击的方法与分组密码的迭代轮数和加密函数无关。

（5）中间相遇攻击

中间相遇攻击（Meet-in-the-middle attack）是一种适用于多重加密下的已知明文攻击。已知，遍历所有的K（K₁或K₂），密码攻击者分别计算E_K（P₁）并存储加密结果，计算D_K（C₁），在存储表中搜索与之相同的结果。此时，当前密钥很可能是K₂，而存储表中的相应密钥很可能是K₁。最后再用可能的K₁、K₂加密P₂，若加密结果为C₂，则认为K₁、K₂就是当前密钥。

3.2.2 数据加密标准（DES）

1977年1月，美国政府宣布，将IBM公司设计的方案作为非机密数据的正式数据加密标准（Data Encryption Standard，DES）。DES算法是对称的，既可用于加密又可用于解密。

DES算法可以按四种运行模式之一使用，这四种运行模式是电码本模式、密码分组链接模式、输出反馈模式及密码反馈模式。其中，电码本模式是最简单的模式，安全性也最差；密码分组链接则经常以软件方法实现；输出反馈和密码反馈往往用于硬件实现的算法中。这些内容将在本章3.2.3小节中介绍。

DES是一种分组加密算法。它由16个基本单元组成，每个基本单元都是由加密的两个基本技术—混合和扩散组合而成的。置换后被分为左、右各32位的两个子分组，通过16轮完全相同的运算之后合二为一，最后通过初始置换的逆置换获得密文。

图3.6为DES加密过程的具体描述。由图3.6可以看出，DES算法共需要16轮迭代运算。第i轮运算接受第i-1轮的输出（L_i-1，R_i-1）和K_i，产生本轮的输出（L_i，R_i）和K_i+1，而这些输出又将是下一轮运算（即第i+1轮运算）的输入。其中主要的计算工作是关于R_i。32位的R_i-1经过扩展置换后变成48位，56位的密钥K_i经过左右移位和压缩置换后也变成48位，两者经异或运算后作为S盒的输入。48位的数据经过S盒替换后变成32位，再经过P盒置换后与L_i-1异或运算即生成R_i。在这些运算当中，扩展置换、移位、压缩置换以及P盒置换都是线性的、可逆的，唯有S盒替换是非线性的、不可逆的，所以说S盒替换是DES算法的关键。下面分别介绍DES算法的各个部分。

1.初始置换IP和逆初始置换IP^-1

64位的明文分组M通过初始置换IP，首先将输入的二进制明文块M变换成M′=IP（M）。然后M′经过16次的迭代运算，最后通过逆初始置换IP^-1得到64位二进制密文输出。置换IP和IP^-1 表可分别参看表3.1和3.2。由表3.1可知，初始置换IP将M=m₀m₁…m₆₄变成M′=m₅₈m₅₀…m₇。不难看出，IP^-1是IP之逆。

2.f函数

函数f（R_i-l,K_i）的结构如图3.7所示。首先用扩展置换表E（见表3.3）将R_i-l扩展成48位二进制块E（R_i-l），然后对E（R_i-l）和K_i进行“异或运算”，并将其结果分成8个6位二进制块B₁,…,B₈。每个6位子块B_j，都是选择（替换）函数S_j（见表3.5）的输入，其输出是一个4位二进制块S_j（B_j）。把这些子块合成32位二进制块之后，用置换表P（见表3.4）将它变换成最后的输出f（R_i-l,K_i）。

3.子密钥生成函数

子密钥的生成函数如图3.8所示。密钥K是一个64位的二进制块，其中8位是奇偶校验位，分别位于第8，16，…，64位。子密钥置换函数PC-1（见表3.6）把这些奇偶校验位去掉，并把剩下的56位进行置换。置换后的结果PC-l（K）被分成两半C₀和D₀，各含28位。接下来，有如下的变换公式：

C_i=LS_i（C_i-1），D_i=LS_i（D_i-1）

其中，LS_i是循环左移位变换，LS₁、LS₂、LS₉、LS₁₆循环左移1位，其余的循环左移2位。最后，通过子密钥置换函数PC-2（见表3.7）得出K_i。

解密算法和加密算法相同，只不过第1次迭代时用密钥K₁₆，第2次迭代时用K₁₅，…，第16次迭代时用K₁。

3.2.3 高级加密标准（AES）

1997年6月18日，美国科罗拉多州以Rocke Verser为首的一个工作组宣称破译了DES加密算法。解密的明文为Strong cryptography makes the world a safer place，解密密钥为8558891AB0C851B6，RSA数据安全公司随后也证实了它的正确性。加密消息的密钥量约为7.2×10¹⁶，工作组以7.0×10¹⁰/s的速度测试了其中的四分之一，即1.8×10¹⁶。搜索到正确的密钥，前后历时四个多月。破译成功无疑宣布了DES（数据加密标准）的不安全性，使美国政府重新审视其现行的加密标准。

AES（Advanced Encryption Standard）是NIST筹划的，旨在取代DES，以保护21世纪政府敏感信息的新型加密标准。1997年4月NIST开始公开征集AES算法，要求AES是一个非保密的、公开披露加密算法的、全球免费使用的分组密码，算法必须采用对称密码体制，最少应支持128bit的分组和128bit、192bit、256bit的密钥。1998年8月，NIST召开第一次AES候选算法会议（AES1），并公布了15个候选算法。1999年3月，召开第二次AES候选算法会议（AES2），公开了15个候选算法的讨论结果。参考AES2的讨论结果，NIST从15个候选算法中选出了5个算法：MARS、RC6、Rijndael、SERPENT、Twofish，作为进一步讨论的主要对象。

2000年4月，召开第三次AES候选算法会议（AES3），对剩下的5个候选算法做进一步的分析和讨论。2000年10月2日，NIST宣布Rijndael算法当选AES，成为新一代的加密标准。AES于2001年7月正式投入使用。

当选的AES算法是由比利时人Joan Daemen和Vincent Rijmen提交的，由Joan Daemen设计的名为Rijndael的密码算法。该算法是迭代分组密码算法，其分组长度和密钥长度都可改变，该算法的扩充形式允许分组长度和密钥长度以32bit为步长，从128bit到256bit范围内进行特定的变化。该算法的主要优点是设计简单、密钥安装快、需要的内存空间少，在所有平台上运行良好，支持并行处理，抗所有已知攻击。下面分别介绍AES算法的各个部分。

1.状态、密钥种子和轮数

（1）状态

各个不同的变换都在称为状态（State）的中间结果上运算。状态可以用一个以字节为元素的矩阵阵列图表示，该阵列有4行，列数记为Nb且等于分组长度除以32。这里主要讲述了针对128bit明文的分组加密，所以Nb=4且明/密文状态图如图3.9所示。

（2）密钥种子

由加密系统提供的原始密钥称为密钥种子，与状态类似地用一个以字节为元素的矩阵阵列图表示，该阵列有4行，列数记为Nk，Nk等于分组长度除以32。如果密钥种子的长度为128bit，那么Nk=4且分布图如图3.10所示。

（3）轮数

一个明文分组按a₀₀，a₁₀，a₂₀，a₃₀、a₀₁，a₁₁，a₂₁，a₃₁等的顺序映射到状态阵列中。同理，密钥种子按k₀₀，k₁₀，k₂₀，k₃₀、k₀₁，k₁₁，k₂₁，k₃₁等的顺序映射到密钥种子阵列中。当输出密文分组时，也是按相同的顺序从状态阵列中取出各字节的。将密文分组看作4Nb （4×4）维向量，每一个分量是一个字节，记为（t₀t₁t₂…t_4Nb-1）。则密文分组的第n个分量对应于状态阵列的第（j,k）位置上的元素，其中n=j+4k，0≤j≤3。

迭代的轮数记为Nr，Nr与Nb和Nk有关，图3.11给出了Nr、Nb和Nk的关系。

2.轮函数

轮函数即每轮加密过程所完成的变换，它由四个不同的计算部件所组成，分别是字节代替（ByteSub）、行移位（ShiftRow）、列混合（MixColumn）、加密钥（AddRoundKey）。

（1）字节代替

对状态阵列的每个字节做相同的变换，该变换由以下两个子变换所合成。

1）首先，将字节看作GF（2⁸）上的元素，映射到自己的乘法逆；00字节映射到它自身。

2）其次，将字节做GF（2⁸）上的、可逆的仿射变换，如图3.12所示。

以上两个子变换合成的实现，采用一个8bit输入与8bit输出的S盒。

（2）行移位

将状态阵列的各行进行循环移位，不同的状态行的位移量不同。第0行不移动，第一行循环左移C₁个字节，第二行循环左移C₂个字节，第三行循环左移C₃个字节。位移量的选取与Nb有关。

（3）列混合

将状态阵列的每个列视为系数在GF（2⁸）上的、次数小于4的多项式，被同一个固定的多项式c（x）进行模x⁴+1乘法。当然要求c（x）是模x⁴+1可逆的多项式，否则列混合变换就是不可逆的，因而会使不同的明文分组具有相同的对应密文分组。Rijndael的设计者所给出的c（x）为（系数用十六进制数表示）

c（x）=03x³+01x²+01x+02

c（x）是与x⁴+1互素的，因此是模x⁴+1可逆的。由前面的讨论可知，列混合运算可表示为GF（2⁸）上的可逆线性变换

这个运算需要做GF（2⁸）上的乘法，但由于所乘的因子是三个固定的元素02、03、01，所以这些乘法运算仍然是比较简单的。

（4）加密钥

将单轮子密钥阵列简单地与密文阵列进行按位异或。这里要求子密钥阵列与密文阵列是同阶的。

Rijndael的AES加密算法对应的整体流程图如图3.13所示，简单说明如下：

1）Rijndael（State，CipherKey）：该算法完成Rijndael加密。其中的两个参数的意义分别是：State表示明文以“状态”的形式输入，CipherKey表示种子密钥。

2）KeyExpansion（CipherKey，ExpandedKey）：该函数主要完成密钥扩展的功能，将种子密钥（16字节，4字）扩展成11组加密密钥，每组密钥的长度等于明文状态的长度。函数中的两个参数的意义分别是：CipherKey为种子密钥，ExpandedKey为加密密钥。

3）AddRoundKey（State，ExpandedKey）：该函数主要完成初始加密钥，即对明文在进行轮变换之前，进行一次简单的密钥加变换。

4）Round（State，ExpandedKey+Nb·j）：该函数主要完成轮变换，是Rijndael加密的核心部分，输入的参数分别是算法中间的结果和对应该轮的加密密钥。

5）FinalRound（State，ExpandedKey+Nb·Nr）：该函数完成最后一轮变换，它与前面由密钥长度决定轮数的循环中的轮变换的唯一不同是少了列混合（MixColumn）。