第3章〓对称密码体系








本章先介绍对称密码体系的概念、结构和特点，之后详细阐述对称密码体系的两类算法： 流密码和分组密码。流密码部分重点说明其构造算法和工作原理； 分组密码部分主要介绍Feistel密码结构。然后通过介绍一些有代表性的加密算法，如DES、AES和IDEA，强化读者对对称加密算法的理解。最后介绍分组密码的常用工作模式。


3.1
3.1〓对称密码体系概述

对称密码算法(Symmetric Algorithm)也称传统密码算法、单钥密码算法，它包括许多数据加密方法。公钥密码技术出现之前，对称密码系统已被使用了多年。对称密码体系的基本模型如图31所示，其基本特征是： 数据加密和解密使用同一个密钥。在算法公开的前提下所有秘密都在密钥中，因此密钥本身应该通过另外的秘密信道传递。对称密码体系的安全性依赖于两个因素： 其一，加密算法强度至少应该满足当敌手已知算法时通过截获密文不能导出明文或者发现密钥，更高的要求是敌手即使拥有部分密文以及相应明文段落也不能导出明文或者发现密钥系统； 其二，发送方和接收方必须以安全的方式传递和保存密钥副本，对称加密的安全性取决于密钥的保密性而不是算法的机密性。



图31对称密码体系的基本模型


对称加密算法可以分成两类： 一类为流算法，是一次只对明文中单个位(有时为字节)加密或解密的运算； 另一类为分组算法，是一次只对明文的一组固定长度的字节加密或解密的运算。现代计算机密码算法一般采用的都是分组算法，一般分组的长度为64位，这是由于这个长度大到足以防止分析破译，但又小到足以方便使用。

对称算法的加密和解密表示为


Ek(M)=C
Dk(C)=M




常用的对称加密体系有五个组成部分。 


（1） 明文M： 原始数据信息。

（2） 加密算法Ek： 以密钥k为参数，对明文M进行多种置换和转换的规则和步骤，结果即为密文。

（3） 密钥k： 加密与解密算法的参数，直接影响对明文进行变换的结果。

（4） 密文C： 对明文进行变换的结果。

（5） 解密算法Dk： 加密算法的逆变换，以密文C为输入、密钥k为参数，变换结果为明文。

对称密码体系的优点是算法实现的效率高、速度快，缺点是密钥的管理过于复杂。如果按照上述方法，任何一对发送方和接收方都有他们各自商议的密钥，那么很明显，假设有N个用户进行对称加密通信，则需要产生N(N-1)把密钥，每个用户要记住或保留N-1把密钥，当N很大时，记住是不可能的，而保留起来又会引起密钥泄露可能性的增加。常用的对称加密算法有DES、AES和IDEA等。



3.2
3.2〓流密码

3.2.1流密码简介

香农证明了“一次一密”密码体制在理论上是不可破译的，促使人们长期以来一直寻求某种能仿效“一次一密”密码的密码体制，流密码就是所寻求的方法之一。流密码也称序列密码(Stream Cipher)，具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点。因此在实际应用中，特别是在专用或机密机构中保持着优势，典型的应用领域包括世界军事、无线通信、外交通信。

流密码加密时先将文本、声音、图像等原始明文转换成01串，然后将它与密钥流逐位异或生成密文流传送给接收者，接收者将密文流与相同的密钥流逐位异或恢复出明文。在流密码中，将明文分成一定长度的分组，分别对各个分组用同一密钥流序列的不同部分进行加密产生相应的密文。相同的明文分组因为处于明文序列中的不同位置，所对应的密钥流位也不同，因此会加密成不同的密文组。


流密码系统可以用一个六元组(M,C,K,Z,Ek,Dk)来描述。其中，M表示明文空间，C表示密文空间，K表示密钥空间，Z表示密钥流生成算法，Ek和Dk表示密钥流与明文(密文)的加密和解密规则，通常为异或运算。对密钥k∈K，由Z确定一个密钥流。流密码系统加解密的原理如图32所示。



图32流密码系统加解密的原理


流密码的加密是用一个密钥流序列(伪随机)和明文序列相异或来产生密文，解密过程相同，即用同一密钥流序列和密文序列相异或来获得明文。

设二进制序列M=M1M2…Mi…Mn是明文序列，Mi∈GF(2),i≥1； 二进制序列C1C2…Ci…Cn作为密文比特流，Ci∈GF(2),i≥1； 序列k=k1k2…ki…kn作为密钥流序列，同样ki∈GF(2),i≥1。加密过程可表示为Ci=Miki，解密操作表示为Mi=Ciki，i≥1。表示按位异或运算。

密钥流序列的伪随机性决定了流密码的安全性。当密钥流序列是由无记忆离散的二进制均匀分布信源产生的随机序列时，产生该序列的密码就是“一次一密”密码，在理论上它已经被证明是安全的。但是，用产生真正随机序列的方法来产生完全相同的随机序列几乎是不可能的。实际使用“一次一密”密码时要求信息的收发双方必须持有加解密信息所用的密钥流副本。已经证明仅当密钥数目与明文数目至少一样多时，“一次一密”才是完全保密的，即密钥必须至少和明文一样长且不重复使用。而很长的密钥序列不便于存储和分配，流密码的设计就是研究如何用一个短的密钥生成一个周期长且安全的密钥流。利用这种方法能够重复产生相同的密钥序列，但产生的序列不是真正的随机序列，而是伪随机的，这就要求伪随机序列满足真随机序列的一些随机特性。要实现保密通信，只需要在信息的发送方和接收方之间传送一个短的密钥。

3.2.2流密码的结构

根据明文和密文的消息流与密钥流序列的关系，可将流密码分为同步流密码和自同步流密码两类。

1. 同步流密码

在同步流密码中，密钥流的产生独立于明文和密文。发送方和接收方只要有相同的密钥和初始内部状态，就能产生相同的密钥流。同步流密码加密结构如图33所示。



图33同步流密码加密结构


由于密钥流与明文串无关，所以同步流密码中的每个密文字符ci不依赖于之前的明文mi-1，…,m1。所以同步流密码的一个重要特点就是无错误传播： 在传输期间一个密文字符被改变只影响该符号的恢复，不会对后继的符号产生影响。但是，在同步流密码中发送方和接收方必须是同步的，用同样的密钥且该密钥操作在同样的位置时才能保证正确解密。如果在传输过程中密文字符有插入或删除导致同步丢失，密文与密钥流将不能对齐，导致无法正确解密。要正确还原明文，密钥流必须再次同步。与同步流密码相反，自同步流密码有错误传播现象，但可以自行实现同步。

2. 自同步流密码

在自同步流密码中，密钥流的产生与之前已经产生的若干密文有关，其加密结构如图34所示。
其中，密钥流ki的生成过程如图35所示。



图34自同步流密码加密结构




图35同步流密码的密钥流生成过程



用函数表示为


σi=F(σi-1,ci-1,…,ci-k)
ki=G(σi,k)
ci=E(ki,mi)




其中，k是种子密钥； σi是密钥流生成器的内部状态(初始状态记为σ0)； F是状态转移函数； G是生成密钥流的函数； E是自同步流密码的加密变换，它是ki与mi的函数。

由此可见，如果自同步流密码中某一符号出现传输错误，则将影响到它之后k个符号的解密运算，亦即，自同步流密码有错误传播现象。等到该错误移出寄存器后寄存器才能恢复同步，因而一个错误至多影响k个符号。在k个密文字符之后，这种影响将消除，密钥流自行实现同步。由于密文流参与了密钥流的生成，使得密钥流的理论分析复杂化，目前的流密码研究结果大部分都是关于同步流密码的，因为这些流密码的密钥流的生成独立于消息流，从而使它们的理论分析成为可能。

3.2.3反馈移位寄存器与线性反馈移位寄存器

如前所述，序列密码的安全强度取决于密钥流生成器生成的密钥流的安全性(如周期、游程分布、线性复杂度等)。有多种产生同步密钥流生成器的方法，最普遍的是使用一种称为线性反馈移位寄存器(Linear Feedback Shift Register，LFSR)的设备。

采用LFSR作为基本部件的主要原因如下： 

（1） LFSR的结构非常适合硬件实现；

（2） LFSR的结构便于使用代数方法进行理论分析；

（3） 产生的序列的周期可以很大；

（4） 产生的序列具有良好的统计特性。

1. 反馈移位寄存器

图36所示为一个反馈移位寄存器的流程图，信号从左到右。a表示存储单元，取值为0或1，ai的个数n称为反馈移位寄存器的级。在某一时刻，这些级的内容构成该反馈移位寄存器的一个状态，共有2n个可能的状态，每一个状态对应于F上的一个n维向量，用(a1,a2,…,an)表示。函数f是一个n元布尔函数，称之为反馈函数。




图36反馈移位寄存器流程图


在主时钟确定的周期区间上，每一级存储器ai都将其存储内容向下一级ai-1传递，最右一级存储器的内容作为该时刻的输出，根据该时刻寄存器的状态计算f(a1,a2,…,an)作为最左一级寄存器在下一时刻的内容。显然，一个反馈移位寄存器的逻辑功能完全由该移位寄存器的反馈函数所标志。

2. 线性反馈移位寄存器

如果反馈函数形如f(a1,a2,…,an)=cna1cn-1a2…c1an，其中，系数ci=0,1，这里的加法运算为模2加，乘法运算为普通乘法，则称该反馈函数是a1,a2,…,an的线性函数，对应的反馈移位寄存器称为线性反馈移位寄存器，用LFSR表示。否则，称为非线性反馈移位寄存器(NonLinear Feedback Shift Register，NLFSR)。LFSR的示意图如图37所示。




图37线性反馈移位寄存器流程图


显然，根据LFSR中反馈函数的系数ci(i=1,…,n)取值的不同，这样的反馈函数有2n种。令ai(t)表示t时刻第i级寄存器的内容，则第t+1时刻寄存器的内容为： 


ai(t+1)=ai+1(t),i=1,2,…,n-1
an(t+1)=cna1(t)cn-1a2(t)…c1an(t)




通常称多项式cnxn+cn-1xn-1+…+c1x1+1为上述LFSR的特征多项式。



图384级线性反馈移位寄存器示例

LFSR的特征多项式与它的反馈函数是一一对应的，如果知道了LFSR的特征多项式，便立即可以求得该移位寄存器的反馈函数，反之亦然。

例31图38为一个4级线性反馈移位寄存器，状态转移关系为


ai(t+1)=ai+1(t),i=1,2,3
a4(t+1)=a1(t)a4(t)



假设初始状态为(a1,a2,a3,a4)=(0,1,1,0)，则可根据反馈函数计算出该线性反馈移位寄存器在各时刻的所有状态，如表31所示。


表31各时刻的所有状态



t
a4
a3
a2
a1
t
a4
a3
a2
a1
0011081110
1001191111
21001100111
30100111011
40010120101
50001131010
61000141101
71100150110


由计算过程可见，在t=15时刻该寄存器的状态恢复至t=0时刻的状态，因此之后的状态将开始重复。这个移位寄存器输出的序列就是011001000111101011001000111101……，序列的周期为15，也称该移位寄存器的周期为15(=24-1)。

为了从直观上描述这一LFSR的状态转移情况，可以使用一些方框以及连接这些方框的箭头组成的图形，即为状态转移图，如图39所示。



图39状态转移图



例32图310所示是一个特征多项式为x3+x+1的线性反馈移位寄存器。



图3103级线性反馈移位寄存器示例


根据特征多项式可知，该LFSR的反馈函数为f(a1,a2,a3)=a1a3。假设初始状态为(a1,a2,a3)=(1,1,1)，其状态转移图如图311所示。




图3113级LFSR的状态转移图


在状态转移图中，从初始状态开始，沿着箭头所指示的路径依次取出最右边的分量便得到该LFSR的输出序列： 1110100 1110100……，周期为7(=23-1)。3级移位寄存器的所有可能状态数为23=8 (含状态(0,0,0))，而本例中从初始状态(1,1,1)开始可以得到所有非(0,0,0)的状态。

若以状态转移图中任一状态作为初始状态，沿箭头所指示的路径依次取出最右边的分量还可得到另外6个序列： 1101001 1101001……； 1010011 1010011……； 0100111 0100111……； 1001110 1001110……； 0011101 0011101……； 0111010 0111010……。全部7个序列取自同一个状态转移图，将这7个序列之一经过适当的移位可以得到其余任一序列，称这7个序列是移位等价的。

例33图312所示为一个4级LFSR，其特征多项式为x4+x3+x2+x+1。

① 如取初始状态为(a1,a2,a3,a4)=(1,1,1,1)，则其状态转移图如图313所示。



图3124级LFSR




图313初始状态转移图一



对应的输出序列为11110 11110……，周期为5。

② 如取初始状态为(a1,a2,a3,a4)=(0,0,0,1)，则其状态转移图如图314所示。

对应的输出序列为00011 00011……，周期为5。

③ 如取初始状态为(a1,a2,a3,a4)=(1,0,1,0)，则其状态转移图如图315所示。



图314初始状态转移图二



图315初始状态转移图三


对应的输出序列为10100 10100……，周期为5。

以上15个状态连同状态(0,0,0,0)即为4级移位寄存器所有可能的24=16个状态。

3.2.4m序列及其伪随机性
1. m序列与最长线性移位寄存器

根据LFSR的状态转移图可以看出，一个n级LFSR序列的周期最大只能为2n-1： 有的LFSR序列周期可能远小于这个值，但也有的LFSR序列的周期可以达到这个值。如果以GF(2)上n次多项式cnxn+cn-1xn-1+…+c1x+1为连接多项式的n级LFSR所产生的非零序列的周期为2n-1，则称这个序列为n级最大周期线性移位寄存器序列，简称m序列。显然，如果一个n级LFSR产生了m序列，则该LFSR的状态转移图仅由两个圈构成，其中一个是由全零状态构成的长度为1的圈，另一个是由全部其余2n-1个状态构成的长度为2n-1的圈。换句话说，如果一个n级LFSR输出的非零序列是m序列，则其余2n-2个非零序列也是m序列，它们一起构成了一个移位等价类。这里把产生周期为2n-1的m序列的n级LFSR称为最长线性移位寄存器。

显而易见，一个序列是否是m序列应当与产生这一序列的LFSR的连接多项式有密切的关系。事实上，已证明下面的结论是正确的： 如果以GF(2)上n次多项式cnxn+cn-1xn-1+…+c1x+1为连接多项式的n级LFSR所产生的非零序列是m序列，则cnxn+cn-1xn-1+…+c1x+1必为GF(2)上的不可约多项式。这一结果表明一个LFSR为最长移位寄存器的必要条件是它的连接多项式为不可约多项式。

但是，连接多项式为不可约的假设尚不足以保证该LFSR输出的非零序列是m序列。例如，对于GF(2)上4次不可约多项式x4+x3+x2+x+1，对应的LFSR的非零序列周期为5，而非24-1。关于m序列的充分必要条件是： 
以GF(2)上n次多项式cnxn+cn-1xn-1+…+c1x+1为连接多项式的n级LFSR所产生的非零序列是m序列cnxn+cn-1xn-1+…+c1x+1为GF(2)上的n次本原多项式。

因此，一个n级LFSR为最长移位寄存器的充要条件是它的连接多项式为GF(2)上的n次本原多项式。例如，多项式x3+x+1是GF(2)上的3次本原多项式，可以验证以此为连接多项式的LFSR的输出序列均为m序列。在实践中，经常使用GF(2)上的本原三项式，这是因为它只需要一个抽头，所以电路设计最简单。

由以上的讨论可知，本原多项式的概念不论是在理论上还是实践上均起重要作用。由代数学的知识知道，当2n-1为素数时，GF(2)上的每一个n次不可约多项式均为n次本原多项式。形如2n-1的素数称为梅森(Mersenne)数，如n=2,3,5,7,13等。

2. m序列的安全性

LFSR的输出序列就是流密码的密钥流。一个LFSR可以输出足够长的二进制位以匹配明文的二进制位。要解密密文，只需要运行具有相同初始状态的LFSR即可。对于给定的整数n，由于m序列是周期最长的，是否可以用m序列直接作为密钥流实现流密码?或者说将LFSR作为密码序列产生器，安全吗?下面通过一个简单的例子来描述m序列直接在流密码中使用时可能遇到的问题。

例34m序列的破译。假设在某个流密码体制中，其密钥流生成器是一个5级LFSR，如图316所示。设攻击者得到密文串10110 10111和相应的明文串01100 11111，并知道该流密码体制中的LFSR是5级的。因此，攻击者可计算出相应使用的密钥流为11010 01000。



图3165级LFSR


由于 


a6=c5a1+c4a2+c3a3+c2a4+c1a5
a7=c5a2+c4a3+c3a4+c2a5+c1a6
a8=c5a3+c4a4+c3a5+c2a6+c1a7
a9=c5a4+c4a5+c3a6+c2a7+c1a8
a10=c5a5+c4a6+c3a7+c2a8+c1a9




攻击者可根据密钥流建立如下方程组： 


0=c51+c41+c30+c21+c10(1)
1=c51+c40+c31+c20+c10(2)
0=c50+c41+c30+c20+c11(3)
0=c51+c40+c30+c21+c10(4)
0=c50+c40+c31+c20+c10(5)




由(5)知c3=0； 从而由(2)知c5=1； 从而由(4)知c2=1； 从而由(1)知c4=0； 从而由(3)知c1=0。这样，攻击者就知道了该LFSR的具体结构。

攻击者利用这一结构和已经掌握的部分密钥流，就可以计算出之后所有的密钥序列。因此，相应的流密码毫无安全性可言。

上述分析可以推广到一般情况： 对于一个n级的LFSR，如果攻击者可以得到2n个明文密文对，就可以获得该LFSR的具体代数结构。

3. Golomb随机性假设

流密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段密钥流时不会泄露更多信息，这样的序列称为伪随机序列。之所以把这种序列称为伪随机序列，是因为产生这种序列是按照完全确定的方式进行的，而不像随机序列那样元素的出现是随机的。

下面先说明游程的概念： 设{ai}=(a1a2a3…)为0、1序列，例如00110111，其前两个数字是00，称为0的2游程； 接着是11，是1的2游程； 再下来是0的1游程和1的3游程。

Golomb提出了度量伪随机序列随机性的三条规则，称为Golomb随机性假设。简单起见，假设所述伪随机序列为二元序列a1,a2,…,ai,…,an,…(ai∈{0,1})，其周期为n。

（1） 在每一周期内，0的个数与1的个数近似相等。

（2） 在每一周期内，长度为i的游程数占游程总数的1/2i。

（3） 定义自相关函数为C(τ)=∑ni=1(-1)ai+ai+τ，这是一个二值函数： 

C(τ)=n,τ≡0 mod n
c,其他

其中，c为一个常数。

例如，在周期为7的序列1110010……中，每一周期内有4个1，3个0,4个游程，且有2个长度为1的游程、1个长度为2的游程、1个长度为3的游程。自相关函数为：


C(τ)=7,τ≡0 mod n
-1,其他 




m序列是满足Golomb随机性假设的典型代表。

4. m序列的伪随机性

m序列之所以在电子工程的许多领域获得广泛的应用，主要是由于它具有与随机序列类似的性质，满足Golomb的三个随机性假设。下面不加证明地给出其相应的结论，感兴趣的读者可以自己尝试给出其正确性证明。

（1） 在n级m序列的一个周期段内，1出现的次数恰为2n-1，0出现的次数恰为2n-1-1。

（2） 在n级m序列的一个周期段内，游程总数为2n-1； 长为k(1≤k≤n-2)的0游程(或1游程)数为2n-2-k； 长为n-1的游程只有1个，为0游程； 长为n的游程也只有1个，为1游程。

（3） 自相关函数是二值的，且为

C(τ)=2n-1,τ≡0 mod （2n-1）-1,其他

需要说明的是，对于密钥流序列而言，Golomb随机性假设只是判别二元周期序列的随机性标准的必要条件，并不是充分的。这是因为，由其中很小一部分就可简单地确定出整个密钥序列。

5. 线性复杂度

除了要求伪随机序列具有长周期、满足Golomb的三个随机性假设外，还要求适用于流密码的伪随机序列满足高的线性复杂度(Linear Complexity)。给定二元序列a1,a2,…,ai,…,an,…(ai∈{0,1})，其线性复杂度定义为能够输出该序列的最短线性移位寄存器的级数。

例如，给定序列011 011……，连接多项式为x2+x+1的LFSR可以生成该序列，连接多项式为x3+1的LFSR也可以生成该序列。但连接多项式为x+1的LFSR则无法做到这一点，所以，该序列的线性复杂度为2。序列线性复杂度的概念在密码学中的重要意义是通过以下结论体现出来的： 如果序列的线性复杂度为l(l≥1)，则只要知道序列中任意相继的2l位，就可确定整个序列。由此可见，序列线性复杂度是流密码安全性的重要指标，作为密钥流序列，其线性复杂度很小是不安全的。通常认为一个安全的密钥流应该满足以下三个基本条件： 周期充分长； 随机统计特性好(即基本满足Golomb的随机性假设)； 线性复杂度大。这里长周期一般指不少于1016，而线性复杂度为序列长度的一半是比较合适的。

3.2.5线性移位寄存器的非线性组合

由于直接使用LFSR的m序列是不安全的，因此线性移位寄存器序列不能直接作为密钥流使用。如果在LFSR的基础上加入非线性化的手段，便可产生适合于流密码应用的密钥序列。

为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列。这样LFSR作为驱动源以其输出推动了一个非线性组合函数所决定的电路产生出非线性序列。实际上，这就是所谓的非线性前馈序列生成器。线性移位寄存器用来保证密钥流的周期长度，非线性组合函数用来保证密钥流的各种密码性能，以抗击各种可能的攻击。许多专用流密码算法都是用这种方法构成，通常可将这种方法分为三类： 滤波生成器、组合生成器和钟控生成器。

1. 滤波生成器

滤波生成器(Filter  Generator)是一种常见的密钥流生成器，由一个n级线性移位寄存器和一个m(m<n)元非线性滤波函数组成，滤波函数的输出为密钥流序列，工作模式如图317所示。

这里g为一个m元布尔函数，其输入由LFSR中的一部分抽头构成，其输出构成整个生成器的输出。

2. 组合生成器

在序列密码设计和分析中，组合生成器(Combinatorial Generator)也有着广泛的应用，它由若干线性移位寄存器LFSRi(i=1,…,n)和一个非线性组合函数组成，组合函数的输出构成密钥流序列。组合生成器工作模式如图318所示。



图317滤波生成器工作模式




图318组合生成器工作模式



其中，LFSRi(i=1,…,n)为n个级数分别为r1,r2,…,rn的线性移位寄存器，相应的移位寄存器序列为{aij}(i=1,…,n)。函数f(x1,x2,…,xn)是n元布尔函数。令kj=f(a1j,a2j,…,anj)，则{kj}即为该组合生成器的输出。

使用组合生成器可以极大地提高序列的周期。事实上，如果r1,r2,…,rn两两互素，函数f(x1,x2,…,xn)与各变元均有关，则{kj}的周期为∏ni=1(2ri-1)。


3. 钟控生成器

钟控方法设计密钥流生成器的基本思想是： 用一个或多个移位寄存器来控制另一个或多个移位寄存器的时钟，这样的序列生成器称为钟控生成器(ClockControlled Generator)。最终的输出称为钟控序列，基本模型如图319所示。



图319钟控序列生成器基本模型



假设LFSR1和LFSR2分别输出序列{ak}和{bk}。当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR，因此LFSR重复输出前一位。

例如，假设LFSR1输出周期序列10101 10101……，LFSR2输出周期为3的序列a0,a1,a2,a0,a1,a2,…,则上述钟控生成器输出的钟控序列为a0,a0,a1,a1,a2,a0,a0,a1,a1,a2,…，周期为5。

交错停走式生成器也是一种钟控生成器。这个生成器使用了3个不同级数的移位寄存器，如图320所示。



图320交错停走式生成器


当LFSR1的输出是1时，LFSR2被时钟驱动； 当LFSR1的输出是0时，LFSR3被时钟驱动。最后，LFSR2的输出与LFSR3的输出做异或运算即为这个交错停走式生成器的输出，输出的序列具有长周期和大的线性复杂度。

除利用LFSR的良好结构设计伪随机序列生成器之外，还有其他一些基于数论或有限域的知识构造的伪随机序列。这些生成器所依赖的数学工具可对它们的周期、随机统计特性、线性复杂度等进行理论分析。


3.3
3.3〓分组密码

3.3.1分组密码概述

在许多密码系统中，分组密码是系统安全的一个重要组成部分。分组密码易于构造伪随机数生成器、流密码、消息认证码(MAC)和散列函数等，还可进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。



分组密码是将明文消息编码表示后的数字序列x0,x1,…,xi,…划分成长为n的组x=(x0,x1,…,xn-1)，各组(长为n的量)分别在k=(k0,k1,…,kt-1)控制下变换成等长的输出数字序列y=(y0,y1,…,ym-1)(长为m的量)，其加密函数E:Vn×K→Vm，Vn为n维明文空间，Vm为m维密文空间，K为密钥空间，如图321所示。



图321分组密码框图


 分组密码与流密码的不同之处在于： 输出的每一位数字不是只与相应时刻输入的明文数字有关，而是与一组长为n的明文数字有关。在相同密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为n的数字序列的代换密码。通常取m＝n。若m＞n，则为有数据扩展的分组密码； 若m＜n，则为有数据压缩的分组密码。下面介绍设计分组密码时的一些常用方法。

1. 代换

设明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值。为使加密运算可逆，明文的每一个分组都应产生唯一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数有2n!个。

图322表示n＝4的代换密码的一般结构，4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个比特表示。加密映射和解密映射可由代换表来定义，如表32所示。这种方法是定义分组密码最简单的常用形式。



图322n=4的代换结构




表32n=4对应的代换表



明文
密文
明文
密文
0000
1110
1000
0011
0001
0100
1001
1010
0010
1101
1010
0110
0011
0001
1011
1100
0100
0010
1100
0101
0101
1111
1101
1001
0110
1011
1110
0000
0111
1000
1111
0111


2. 扩散和混淆

扩散和混淆是由信息论创始人香农提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析。如果敌手知道明文的某些统计特性，如消息中不同字母出现的频率、可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，那么敌手就有可能得出加密密钥或其一部分，或者得出包含加密密钥的一个可能的密钥集合。在香农称之为理想密码的密码系统中，密文的所有统计特性都与所使用的密钥独立。



所谓扩散，就是将明文的统计特性散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，即密文中每一位均受明文中多位影响。例如，对英文消息M=m1m2m3…，对字符cn的加密操作为： 


cn=mn26mn+126mn+2…26mn+k




上式表示密文字母cn由明文中连续k个字母进行模26相加所得。这样使密文中各字母出现的频率特征较为平均，敌手无从猜测其中的关键短语或者词汇。单纯的扩散较容易被敌手攻破。混淆试图使密文的统计特征与密钥取值的关系尽量复杂，实现混淆的常用方法是代换。要注意的是线性变换起不到有效的混淆效果。

流密码通过反馈设计加入了一些扩散，但它主要依赖于混淆。分组密码算法既用到了扩散，也用到了混淆。E.Schaefer(1996)为教学目的提出了一个简化的DES(SDES)加密算法，这个算法非常具体地说明了分组密码中如何实施扩散和混淆。

SDES加密算法以10位密钥和8位明文分组为输入，产生8位分组密文输出。其解密算法用同一密钥对8位密文分组产生原来的明文分组。图323给出了SDES算法流程。



图323SDES算法流程



SDES加密算法步骤如下。 

（1） 对输入的8位明文分组m执行初始置换IP(m)。

（2） 执行一个包含置换、替代操作且依赖于密钥的变换fk1。

（3） 将数据进行左右4位两半部分交换SW。

（4） 结果再执行fk2。

（5） 最后执行IP-1产生逆密文输出c，并且


c=IP-1(fk2(SW(fk1(IP(m)))))




解密是加密的逆变换，即


m=IP-1(fk1(SW(fk2(IP(c)))))




其中，密钥k1、k2都是8位子密钥，由10位输入密钥产生。



图324SDES密钥生成


1) SDES密钥的生成

SDES密钥是一个10位码，由发送、接收双方共享。两个8位子密钥由10位输入密钥按照图324所示的流程生成。子密钥k1、k2生成过程如下。 

（1） 对10位码m中进行10阶置换P10。置换P10定义为


P10=1,2,3,4,5,6,7,8,9,103,5,2,7,4,10,1,9,8,6




即对m=(b1,b2,b3,b4,b5,b6,b7,b8,b9,b10)，m1=P10(m)=(b3,b5,b2,b7,b4,b10,b1,b9,b8,b6)。

例如，P10(1010000010)=(1000001100)。

（2） 将m1看作左右两个5位码m1L和m1R，即m1=m1L‖m1R，分别循环左移一次（LS-1,LS表示左移循环），输出m2仍为10位码。如上例，m2=LS-1(m1L)‖LS-1(m1R)=(0000111000)。

（3） 10位转8位置换。P8(b1,b2,b3,b4,b5,b6,b7,b8,b9,b10)=(b6,b3,b7,b4,b8,b5,b10,b9)得子密钥k1。如上例，k1=P8(m2)=P8(0000111000)=(10100100)。

（4） 将m2看作左右两个5位码m2L和m2R，即m2=m2L‖m2R，分别循环左移二次（LS-2），输出m3仍为10位码。如上例，m3=LS-2(m2L)‖LS-2(m2R)=(0010000011)。

（5） 对m3做10位转8位置换P8，得子密钥k2=P8(m3)。如上例，k2=P8(m3)=P8(0010000011)=(01000011)。


2) SDES加密操作

SDES加密操作首先执行一个8位的置换IP： 


IP=1,2,3,4,5,6,7,82,6,3,1,4,8,5,7




即IP(b1,b2,b3,b4,b5,b6,b7,b8)=(b2,b6,b3,b1,b4,b8,b5,b7)。将IP上下两行互换，即得IP的逆置换IP-1，IP-1(IP(x))=x。加密操作中最复杂的是fk,fk是若干置换和代换的组合。如图325所示，fk(L,R)=(LP4((S0‖S1)(E/P(R)Key)))‖R，其中： 



图325变换fk的细节


① L、R分别为输入字节的左半4位和右半4位。

② E/P为一个4位到8位的扩展变换： E/P(b1,b2,b3,b4)=(b4,b1,b2,b3,b2,b3,b4,b1)。

③ 是按位异或运算。

④ S0、S1分别为4位到2位的变换盒，S0作用于8位字节的左4位，S1作用于8位字节的右4位。S0、S1定义如下： 


S0=1032321002133132S1=0123201330102103




变换盒S的操作过程是将4位输入码的第0、3位作为2位数值i，第1、2位作为2位数值j，则S盒中元素Sij即为输出。例如，S0(1110)=3=(11)。

① P4是一个4位置换： P4(b1,b2,b3,b4)=(b2,b4,b3,b1)。

② ‖表示两个位串的拼接。

SDES是一个对称分组加密的简化模型，它揭示了设计分组密码算法的基本模式和框架。但是，SDES没有实际应用价值。由于算法是公开的，所有秘密都在密钥中。即假设攻击者掌握SDES算法细节(包括IP、E/P、S0、S1、P4的值)，已知明文m=(b1,b2,b3,b4,b5,b6,b7,b8)和对应密文c=(p1,p2,p3,p4,p5,p6,p7,p8)，则通过穷举攻击，遍历210=1024个可能密钥，一定可以找出正确的加密密钥。

现代分组密码算法应满足以下要求。 

(1) 分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。DES、IDEA分组长度n＝64，AES的分组长度n=128。

(2) 密钥空间要足够大，尽可能消除弱密钥并使所有密钥的加密强度相同，但是为便于密钥管理，密钥又不能过长。DES的密钥长度为56位，但被认为太短。AES的密钥长度为128位，目前被认为是安全的。

(3) 由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，能抗击各种已知的密码分析攻击。使得敌手除穷举攻击外没有其他捷径可循。

(4) 加密和解密运算简单，易于软件和硬件高速实现。通常的考虑是分组长度应该是2的幂，如取32、64、128、256等，密码运算的基本操作是加、与、或、异或、移位和矩阵变换等。

(5) 通常不考虑数据位扩展或者压缩，即输入明文和输出密文具有相同长度。

(6) 差错传播尽可能小。

扩散和混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。

3.3.2Feistel密码结构
1. Feistel加密结构

由图323，SDES算法对8位明文的加密过程分为两个阶段： 第一阶段对明文作置换IP，然后施以具有扩散和混淆效果的代换处理fk1； 第二阶段对上阶段输出交换左、右半部，然后再次施以fk2，最后实施IP-1。其中每个阶段的模式基本一致。将实施一次fki称为一轮，则下一轮的输入和上一轮输出的关系是： 


L2=R1
R2=L1F(R1,k2)




这种交换左、右半部，其中下一轮右半部为上一轮左半部和依赖于上轮右半部与子密钥的变换值，下一轮左半部为上一轮右半部的框架模式称为Feistel加密结构。

SDES仅实施了两轮具有Feistel结构特征的处理，一般的Feistel加密过程需要实施n轮迭代，其中第i轮迭代关系如下： 


Li=Ri-1
Ri=Li-1F(Ri-1,ki)




其中，ki是第i轮用的子密钥，由加密密钥k得到。

Feistel网络中每轮结构都相同，总是依赖于上轮右半部数据与子密钥经过变换函数F(Ri-1,ki)处理后，其结果与上轮左半部数据进行异或运算，这就是前面介绍的代换操作。代换过程完成后，再交换左、右两半数据，这一过程称为置换。这种结构是香农提出的代换置换网络SPN(SubstitutionPermutation Network)的特有形式。

SDES中增加了开始的置换IP和最后结束的逆置换IP-1。在完整的DES中也是这样处理的。

Feistel网络的实现与以下参数和特性有关。 

(1) 分组大小。分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是64比特或者128比特。

(2) 密钥大小。密钥越长则安全性越高，但加密速度就越慢，现在普遍认为64比特或更短的密钥长度是不安全的，通常使用128比特的密钥长度。

(3) 轮数。单轮结构远不足以保证安全性，多轮结构有足够的安全性。典型的轮数取为16。

(4) 子密钥产生算法。该算法的复杂性越大，则密码分析的困难性就越大。

(5) 轮函数F。轮函数F的复杂性越大，密码分析的困难性也越大。

(6) 算法分析难度。算法结构清晰，解释没有二义性，则容易分析算法的复杂性和抗攻击能力。

2. Feistel解密结构

Feistel解密过程本质上和加密过程一样，算法使用密文作为输入，但使用子密钥ki的次序与加密过程相反，即第1轮使用kn，第2轮使用kn-1，…，最后一轮使用k1。这一特性保证了解密和加密可采用同一算法。

图326的左、右图分别表示16轮Feistel结构的加、解密过程，加密过程由上而下，解密过程由下而上。为清楚起见，加密算法每轮的左右两半用LEi和REi表示，解密算法每轮的左右两半用LDi和RDi表示。图中右边标出了解密过程中每一轮的中间值与左边加密过程中间值的对应关系，即加密过程第i轮的输出是LEi‖REi(‖表示连接)，解密过程第16i轮相应的输入是LDi‖RDi。




图326Feistel加、解密过程


加密过程的最后一轮执行完后，左右两半输出再经交换，因此密文是RE16‖LE16。解密过程取以上密文作为同一算法的输入，即第1轮输入是RE16‖LE16。下面证明解密过程第1轮的输出等于加密过程第16轮输入左右两半的交换值。

在加密过程中： 


LE16=RE15
RE16=LE15F(RE15,k16)




在解密过程中： 


LD1=RD0=LE16=RE15
RD1=LD0F(RD0,k16)=RE16F(RE15,k16)
=［LE15F(RE15,k16)］F(RE15,k16)=LE15




所以解密过程第1轮的输出为LE15‖RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。

通常有LDi=RE16-i，RDi=LE16-i，i=1,2,…,16。明文m=(LE0‖RE0)。这里并不要求F是可逆函数，事实上F的构造任意，以上过程仍然成立，但是从密码强度考虑，函数F的构造是关键。


3.4
3.4〓DES

3.4.1DES算法简介

DES(Data Encryption Standard，数据加密标准)是IBM的研究成果，是数据加密算法(Data Encryption Algorithm，DEA)的规范描述，在1997年被美国政府正式采纳。值得注意的是，IBM在美国国家标准局(NBS)第二次发布征集公告后，所提交的候选算法是在其早先开发的Lucifer算法基础上修改和发展而来的，密钥长度为112，但是公布的DES算法的密钥长度为56。无论如何，DES算法成为使用最广泛的密钥系统之一，在各个领域特别是在金融领域数据安全保护中广泛应用，与此同时，对DES安全性的研究也在不断继续。

1997年一个研究小组经过4个月努力，在Internet上搜索了3×1016个密钥，找出了DES的密钥。同年美国国家标准与技术研究所(NIST)宣布1998年12月以后美国政府不再使用DES，并且发出征集AES(高级加密标准)的通知。1998年5月美国研究机构EFF(Electronic Frontier Foundation)宣布用一台价值20万美元的计算机改装的专用解密系统，花费56h破译了56位密钥的DES。2000年10月2日，NIST公布了新的AES，DES作为标准正式结束。尽管如此，学习DES，对于掌握分组密码的基本理论和设计思想仍然有重要参考价值。同时在非机密级的许多应用中，DES仍在广泛使用。

3.4.2DES算法设计思想

DES算法对明文以64位为分组单位进行分组，最后一组若不足64位，以0补齐。之后对每组64位的数据进行加密。DES中密钥长度为56位，输出64位密文分组，其加密算法框图如图327所示。图的左边是明文的加密处理过程，该过程分三个阶段。 



图327DES加密算法框图


第一阶段： 64位明文进行初始置换IP，用于重排明文分组的64比特数据。



第二阶段： 顺序经过16轮功能相同的变换，每一轮变换的输入是上轮变换的输出和右部56位初始密钥生成的48位子密钥ki。对加密过程中每一轮，子密钥分发前都需进行左循环移位。因此k1，…，k16各不相同。

第三阶段： 将第16轮变换输出的64位码进行左右32位变换，然后对其进行逆初始置换。所得结果即为64位密文分组。

除初始置换和逆初始置换外，DES的结构和Feistel图的密码结构完全相同。

DES算法中每轮处理细节如图328所示。结合图327可知，DES的16轮循环处理流程具有严格的Feistel密码结构。由图328的左部，第i轮处理过程为： F函数的输入为前一轮输出的右半部分Ri-1和当前轮密钥ki。F函数的输出将与加密左半部分输入位Li-1进行XOR操作产生Ri。和Feistel网络一样，每轮变换可由以下公式表示： 


Li=Ri-1
Ri=Li-1F(Ri-1,ki)





图328DES算法单轮处理过程



3.4.3DES算法内部结构

DES的基本构造元件为初始置换与逆初始置换、F函数以及密钥生成，其中F函数涉及E盒扩展置换、S盒置换和P盒置换。

1. 初始置换与逆初始置换

1) 初始置换IP

初始置换IP的功能是把输入的64位明文数据，通过一个8×8的置换矩阵按位进行重新组合，如表33所示。初始置换是线性变换，它使明文发生位置上的变换。


表33初始置换IP



IP

58
50
42
34
26
18
10
2
60
52
44
36
28
20
12
4
62
54
46
38
30
22
14
6
64
56
48
40
32
24
16
8
57
49
41
33
25
17
9
1
59
51
43
35
27
19
11
3
61
53
45
37
29
21
13
5
63
55
47
39
31
23
15
7


设x是分块后的64位明文数据块，置换后x0=IP(x)=L0R0，这里L0和R0都是32位。初始置换后效果如图329所示。



图329初始置换中位交换的示例


2) 逆初始置换IP-1

在加密中，经过16次迭代运算后得到L16和R16，将此作为输入进行逆初始置换，即得到密文输出。逆置换正好是初始置换的逆运算。其逆置换的规则如表34所示。


表34逆初始置换IP-1



IP-1

40
8
48
16
56
24
64
32
39
7
47
15
55
23
63
31
38
6
46
14
54
22
62
30
37
5
45
13
53
21
61
29
36
4
44
12
52
20
60
28
35
3
43
11
51
19
59
27
34
2
42
10
50
18
58
26
33
1
41
9
49
17
57
25


逆初始置换后效果如图330所示。

值得注意的是，初始置换和逆初始置换都没有增加DES的安全性。尽管人们不是很清楚这两种置换存在的真正原理，但看上去他们的初衷是以字节形式排列明文和密文，以方便8位数据总线的数据读取。8位数据总线是20世纪70年代初期最新的寄存器大小。



图330逆初始置换中位置换的示例


2. 函数计算F(Ri1,ki)



正如前文所述，F函数在DES的安全性中发挥着重要作用，F函数实现原理如图331所示。



图331F函数实现原理


1) E盒扩展置换

首先将输入分成8个4位的分组，然后将每个分组扩展为6位，从而将32位的输入扩展为48位。这个过程在E盒中进行，E盒是一种特殊的置换。第一个分组包含的位为(1，2，3，4)，第二个分组包含的位为(5，6，7，8)，以此类推。

图332显示了将4位扩展为6位的过程。



图332E盒扩展置换的置换示例


从表35可知，32个输入位中正好有16个输入位在输出中出现了两次。但是任意一个输入位都不会在同一个6位的输出分组出现两次。扩展盒增加了DES的扩散行为，因为某些输入位会影响两个不同的输出位置。


表35E盒扩展置换表



E

32
1
2
3
4
5
4
5
6
7
8
9
8
9
10
11
12
13
12
13
14
15
16
17
16
17
18
19
20
21
20
21
22
23
24
25
24
25
26
27
28
29
28
29
30
31
32
1


2) S盒置换

将E盒扩展得到的48位结果与当前轮密钥ki进行XOR操作，并将8个6位长的分组送入8个不同的替换盒中，这个替换盒也称S盒，如表36所示，每个S盒都是一个查找表，它将6位的输入映射为4位的输出。



图333使用S盒1对输入1001012
进行解码的示例


每个S盒包含26=64项，可以表示为一个4行16列的表格。每项是一个4位的值。图333列出了表格的读取方式： 每个6位输入中最重要的位(MSB)和最不重要的位(LSB)将选择表行，而4个内部位则选择列。该表中每个项的整数0，1，…，15表示的是4位值对应的十进制的值。

从密码学强度来讲，S盒是DES的核心，因为S盒在密码中引用了非线性，即 


S(a)S(b)≠S(ab)




S盒中的非线性构造元件也是DES算法中唯一的非线性元素，并提供了混淆。有了这些特征，DES算法可以抵御各种高级的数学攻击，尤其是差分密码分析的攻击。

例35S盒的输入b=(100101)2表示行112=3(即第4行)，以及列00102=2(即第3列)。如果将输入b送入S盒1，则输出为S1(37=1001012)=8=10002。

例36求出用DES的8个S盒(见表36)将48比特串70a990f5fc36压缩置换输出的32比特串(用十六进制写出每个S盒的输出)。

解： 比特串70a990f5fc36用二进制表示为011100 001010 100110 010000 111101 011111 110000 110110，每6比特一组共8组，分别用8个S盒变换如下： 


S1（011100）=S1（00,1110）=S1（0,14）=0=0000=0
S2（001010）=S2（00,0101）=S2（0,5）=11=1011=b
S3（100110）=S3（10,0011）=S3（2,3）=9=1001=9
S4（010000）=S4（00,1000）=S4（0,8）=1=0001=1
S5（11101）=S5（11,1110）=S5（3,14）=5=0101=5
S5（11101）=S5（11,1110）=S5（3,14）=5=0101=5
S7（110000）=S7（10,1000）=S7（2,8）=10=1010=a
S8（110110）=S8（10,1011）=S8（2,11）=13=1101=d




故8个S盒的输出为00001011 10010001 01011000 10101101，即0b9158ad。


表36S盒置换表



S1
14
4
13
1
2
15
11
8
3
10
6
12
5
9
0
7
0
15
7
4
14
2
13
1
10
6
12
11
9
5
3
8
4
1
14
8
13
6
2
11
15
12
9
7
3
10
5
0
15
12
8
2
4
9
1
7
5
11
3
14
10
0
6
13
S2
1518146113497213120510
3134715281412011069115
0147111041315812693215
1381013154211671205149
S3
1009146315511312711428
1370934610285141311151
1364981530111212510147
1101306987415143115212
续表


S4
7131430691012851112415
1381156150347212110149
1069012117131513145284
3150610113894511127214
S5
2124171011685315130149
1411212471315015103986
4211110137815912563014
1181271142136150910453
S6
1211015926801334147511
1015427129561131401138
9141552812370410113116
4321295151011141760813
S7
4112141508133129751061
1301174911014351221586
1411131237141015680592
6111281410795015142312
S8
1328461511110931450127
1151381037412561101492
7114191214206101315358
2114741081315129035611




3) P盒置换

S盒置换后产生32位输出，该输出再经过表37定义的P盒置换进行按位置换，产生的结果即为函数F(Ri,ki)的输出。


表37P盒置换表



P

16
7
20
21
29
12
28
17
1
15
23
26
5
18
31
10
2
8
24
14
32
27
3
9
19
13
30
6
22
11
4
25


与初始置换IP及其逆初始置换IP-1不同，P盒置换将扩散引入DES中，因为每个S盒的4位输出都会进行置换，使得每位在下一轮中会影响多个不同的S盒。由扩充带来的扩散、S盒与P盒置换可以保证，在第5轮结束时每个位都是每个明文位与每个密钥位的函数。这种行为也称雪崩效应。

3. 子密钥ki的产生

图334显示了实际密钥生成过程。DES的输入密钥通常是64位，由于DES算法规定，其中每第8个位都作为前面7位的一个奇偶校验位，不参与DES运算。



图334DES加密的密钥生成过程


故经过表38所示的初始PC1(置换选择1)置换后密钥的实际可用位数由64位压缩为56位，可以说DES是一个56位的密码，而不是64位的。


表38初始密钥置换PC1



PC1

57
49
41
33
25
17
9
1
58
50
42
34
26
18
10
2
59
51
43
35
27
19
11
3
60
52
44
36
63
55
47
39
31
23
15
7
62
54
46
38
30
22
14
6
61
53
45
37
29
21
13
5
28
20
12
4


长度均为28位的左右两部分将周期性地向左移动1位或2位(即循环移位)，而移动的具体位数则取决于轮数i，如表39所示，其规则如下： 


表39循环左移位数



轮
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
位数
1
1
2
2
2
2
2
2
1
2
2
2
2
2
2
1


（1） 在i=1，2，9，16轮中，左右两部分向左移动1位。

（2） 在i≠1，2，9，16的其他轮中，左右两部分向左移动2位。

这里需要注意的是，循环移动位置的总数为4×1+12×2=28，这样会使得C0=C16和D0=D16，此结果对解密密钥的生成非常有用。

移位后的结果作为求下一轮子密钥的输入，同时也作为表310的PC2(置换选择2)的输入，即密钥的左右两部分需要再次根据PC2进行按位置换。Ci和Di总共有56位，而PC2忽略了其中的8位，得到48位的本轮子密钥ki，作为函数F(Ri-1，ki)的输入。


表310PC2的轮密钥置换



PC2

14
17
11
24
1
5
3
28
15
6
21
10
23
19
12
4
26
8
16
7
27
20
13
2
41
52
31
37
47
55
30
40
51
45
33
48
44
49
39
56
34
53
46
42
50
36
29
32


4. DES算法解密过程

DES算法的优势之一是其解密过程与加密过程在本质上是完全相同的。这主要是因为DES基于Feistel网络。与加密相比，解密过程中只有密钥生成顺序逆转了，即解密的第一轮需要子密钥k16，第二轮需要子密钥k15，……，最后一轮用k1，算法本身并没有任何变化。

3.4.4DES算法的安全性
1. DES算法的安全强度

在DES算法被提出后不久，针对DES密码强度的批评主要围绕以下两个方面。 

（1） DES的密钥空间太小，该算法很脆弱，易受蛮力攻击。

IBM提议的原始密码的密钥长度为128位，而将它减少为56位的做法很令人怀疑。此外，DES算法所使用的密钥ki是各次迭代中递推产生的，这种相关性也必然降低了密码体制的安全性。

DES蛮力攻击也为硬件开销的不断下降提供了很好的学习案例。EFF(Electronic Frontier Foundation)于1998年构建的硬件机器Deep Crack，使用蛮力攻击可以在56小时内破解DES，其平均搜索时间为15天。在2006年，来自德国波鸿大学和基尔大学一个研究小组基于商业集成电路构建的COPACOBANA机器破解DES的官方平均搜索时间不到7天。

总之，56位的密钥大小已经不足以保证当今机密数据的安全性。因此，对大多数应用程序而言，单重DES只能用于要求短期安全性(比如几小时)的应用或被加密数据价值较低的情况。不过，多重DES仍然很安全，尤其是三重DES。

（2） DES算法中S盒的设计准则是保密的，所以有可能已经存在利用S盒数学属性的分析攻击，只是此攻击只有DES的设计者知道。

尽管DES算法自公布之日起就经历了许多很强的分析攻击，但至今还没发现能高效破解它的攻击方式。1990年，Eli Biham和Adi Shamir发现了差分密码分析(DC)，这是一种非常强大的攻击方式，理论上它可以破解任何分组密码。1993年，Mitsuru Matsui公布了一种与DC相关但又不同的分析攻击，即线性分析攻击(LC)。与差分密码分析类似，这种攻击的有效性很大程度上取决于S盒的结构。

然而事实证明，DES的S盒可以很好地抵抗住了这些攻击。

2. DES算法的安全管理

1) 避开DES算法漏洞

在DES密钥ki的使用、管理及密钥更换的过程中，应绝对避开DES算法的应用误区，即绝对不能把ki的第8、16、24、64位作为有效数据位，来对ki进行管理。从上述DES算法的描述中知道，每个字节的第8位作为奇偶校验位以确保密钥不发生错误，这8位不参与DES运算。因此，如果采用定期更换DES密钥ki的办法来进一步提高系统的安全性和可靠性，忽略了上述应用误区，那么，更换新密钥将是徒劳的。所以更换密钥一定要保证新ki与旧ki真正的不同，即除了第8、16、24、64位以外其他位数据发生了变化，这样才能保证DES算法安全可靠地发挥作用。

2) DES算法存在弱密钥

在DES算法中存在12个半弱密钥和4个弱密钥。由于在子密钥的产生过程中，密钥被分成了两个部分，如果这两个部分密钥是全0或全1，那么每轮产生的子密钥都是相同的，当密钥是全0或全1，或者一半是1或0时，就会产生弱密钥或半弱密钥，DES算法的安全性就会变差。因此，在设定密钥时应避免弱密钥或半弱密钥的出现。

3.4.5多重DES
1. 二重DES

为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用。二重DES是多重使用DES最简单的形式，如图335所示。其中明文为P，密文为C，两个加密密钥为k1和k2。



图335二重DES




加密过程为C=Ek2［Ek1［P］］。解密时，以相反顺序使用两个密钥P=Ek1［Ek2［C］］。

对于任意56位密钥k1、k2，是否能够找出56位密钥k3，使得Ek3［P］=Ek2［Ek1［P］］?换言之，是否存在等价于二重DES的单重DES算法?研究表明，这是不可能的。但是由于DES本身的安全性有限，对二重DES有以下一种称为中途相遇攻击的攻击方案，这种攻击不依赖于DES的任何特性，因而可用于攻击任何分组密码。其基本思想如下： 

设C=Ek2［Ek1［P］］，则令X=Ek1［P］=Dk2［C］。如果知道明文密文对(M,C)，可以用如下方法进行攻击(找出密钥)： 

(1) 用256个所有可能密钥k1对P加密，将结果按照递增序存入一个表T中。

(2) 用256个所有可能的k2对C解密，在表T中查找与C解密结果相匹配的项。

(3) 如果找到匹配项，则记下相应的k1和k2。

(4) 最后再用一新的明文密文对(P′,C′)检验上面找到的k1和k2，即C′是否等于Ek2［Ek1［P′］］，如果相等则攻击有效。

对已知的明文P，二重DES能产生264个可能的密文，而可能的密钥个数为2112个。因此就平均情况而言，对一个已知的明文，有2112/264=248个密钥可产生已知的密文。而再经过另外一对明文密文的检验，误报率将下降到248-64=2-16。所以在实施中途相遇攻击时，如果已知两个明文密文对，则找到正确密钥的概率为1-2-16。

2. 三重DES

为了抵抗中途相遇攻击，又提出图336所示的三重DES(TDES)： C=Ek3［Dk2［Ek1［M］］］。其中第二步的解密操作的目的就是阻断中途相遇攻击。其使用了三个不同的密钥，TDES密钥的有效长度为168，它以DES为基础，但安全性大大增加。1999年，三重DES被合并到数据加密标准中(FIPS PUB 463)。许多基于Internet的应用采用了三重DES，其中包括PGP和S/MIME。考虑到实现效率和开销，实际应用中使用的是两个密钥的三重DES，即在三重DES中令k1=k3。



图336三重DES



3.5
3.5〓AES

3.5.1AES算法简介

随着未来计算机能力的提高，DES加密技术已经难以满足长期高安全性的加密要求。NIST于1997年公开征集新一代加密算法，希望能找到一种新的加密算法，选定的算法最终会形成AES(Advanced Encryption Standard，高级加密标准)。新的加密算法要求满足四个基本条件： 运算速度要比三重DES更快； 安全强度不低于三重DES； 数据分组长度采用128位； 密钥可支持128/192/256位等多种长度。

1998年8月，在首届AES会议上公布了15个候选算法。1999年8月，最终确定了五个算法作为候选方案进一步提交讨论，候选算法包括RC6、Rijndael、Twofish、MARS、Serpent。最后在2000年10月，选定由比利时的Joan Daemen和Vincent Rijmen提出的Rijndael算法作为AES的标准算法。Rijndael算法是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变，分组长度可以支持128位、192位、256位的明文分组长度。NIST对算法进行了一定的修改以简化其复杂度，修改后的算法只提供128位的明文分组长度，能符合当时的各种主流应用环境。

最终形成的AES算法是一个对称密钥的分组密码，是一个采用迭代的反复重排方式来实现加解密的演算法，以128位(16字节)分组大小加密和解密数据。算法采用的密钥长度有128、192、256位三种，分别形成AES128、AES192、AES256系统。AES标准已成为NIST用于加密电子数据的规范，由于采用了新的加密算法，这样可更好地保护金融、电信和政府数字信息的安全。

3.5.2AES算法设计思想

Rijndael算法分组大小和密钥大小都可以为128、192或256位。根据AES标准要求，只有分组长度为128位的Rijndael才称为AES算法。本节只讨论分组长度为128位的Rijndael的标准版本。图337显示了AES输入/输出参数。



图337AES输入/输出参数



AES算法同时支持三种密钥长度。一般而言，加密轮数Nr取决于密钥长度lk，两者之间关系为Nr=6+lk/32。表311给出了两者的关系。


表311AES轮函数与密钥关系



参数
轮函数

AES128
AES192
AES256

密钥长度Nr
128
192
256
轮数lk
10
12
14


与DES不同，AES未采用Feistel结构。Feistel网络在每轮迭代中并没有加密整个分组，例如单轮DES只加密了64/2=32位。而AES在一次迭代中就加密了所有128位。这也是为什么AES的轮数比DES少的原因。

AES加密框图如图338所示。其中明文用x表示，密文用y表示，轮数用Nr表示。其轮函数是由三个不同的可逆变换组成的。每个变换的设计遵循“宽轨迹策略”。所谓宽轨迹策略，是指抗线性分析和差分分析的一种策略，其实现思想体现在轮函数中的三种功能层。



图338AES加密框图


1) 非线性层(字节代换层)

将具有最优的“最坏情况非线性特性”的S盒并行使用，即状态中的每个元素都使用具有特殊数学属性的查找表进行非线性变换。这种方法将混淆引入数据中，即它可以保证对单个状态位的修改，可以迅速传播到整个数据路径中。这就导致线性逼近和差分分布表中的各项趋近于均匀分布，为抵御差分和线性攻击提供了安全性。

2) 线性混合层(扩散层)

为所有状态位提供扩散。它由两个子层组成，每个子层都执行线性操作。 

（1） 行移位变换(ShiftRows)层： 在位级别进行数据置换。

（2） 列混合变换(MixColumns)层： 是一个混淆操作，它合并(混合)了长度为4个字节的分组。

3) 密钥加法层

128位轮密钥(或子密钥)来自于密钥生成中的主密钥，它将与状态进行相加(异或)操作。

与DES类似，AES密钥的生成也从原始AES密钥中计算出轮密钥或子密钥(k0,k1,…,kn)。在AES算法中，除第一轮外，其他每轮都是由三种功能层组成。此外，最后一轮Nr并没有使用列混合变换，而这种方式使得加密方案和解密方案正好对称。


3.5.3AES算法相关知识

在进一步描述各层的内部功能前，首先定义一系列基本概念。

1. AES算法的基本概念

1) 字节



AES算法中的基本运算单位是字节(byte)，即作为一个整体的8位二进制序列。算法的输入数据、输出数据和密钥都以字节为单位，明文、密钥和密文数据串被分隔成一系列8个连续比特的分组，并形成字节数组。假设一个8字节的分组b是由字节序列{b7,b6,b5,b4,b3,b2,b1,b0}所组成的，则可将bi看作一个7次多项式b(x)的系数，即


b(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0




式中，bi∈{0,1}。

例如，{01010111}表示成多项式为x6+x4+x2+x+1。

也可以使用十六进制符号来表示字节值，将每4比特表示成一个符号便于记忆。例如，{01010111}={57}。

2) 字节数组

输入序列按字节划分，表示形式如下： 


{a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15}




假设将128位输入串{i0,i1,i2,i3,i4,…,i127}划分成字节，字节和字节内的比特按照如下方式排序： 

a0={i0,i1,i2,i3,i4,i5,i6,i7}
a1={i8,i9,i10,i11,i12,i13,i14,i15} 
…
a15={i120,i121,i122,i123,i124,i125,i126,i127}

一般式表示： an={i8n,i8n+1,i8n+2,i8n+3,i8n+4,i8n+5,i8n+6,i8n+7}，其中0≤n≤15。

3) 状态

AES算法的运算都是在一个二维字节数组上完成的，这个数组称为状态(State)。当输入的明文序列转换成字节数组后，进一步将一维的字节数组内容转换为二维排列，就形成了状态矩阵。一个状态矩阵由4行组成，每一行包括Nb个字节，Nb的值等于分组长度除以32。状态矩阵用s表示，每一个字节的位置由行号r(范围是0≤r<4)和列号c(范围是0≤c<Nb)唯一确定，记为sr,c或s［r,c］。在AES标准中状态矩阵参数Nb=4，即0≤r<4。

算法在加密和解密的初始阶段将输入字节数组{in0in1in2in3in4…in15}复制到如图339所示的状态矩阵中。加密或解密的运算都在该状态矩阵上进行，最后的计算结果输出并复制到输出字节数组{out0out1out2out3out4…out15}中。




图339AES加解密状态矩阵运算


在加密和解密的初始阶段，输入数组in转化成状态矩阵的公式如下： 


s［r,c］=in［r+4c］




式中，0≤r<4，0≤c<Nb。

在加密和解密的完成阶段，状态矩阵将按照下述规则转换，结果存储在输出数组out中： 


out［r+4c］=s［r,c］




式中，0≤r<4，0≤c<Nb。

4) 状态矩阵列数组

状态矩阵中每一列的4个字节是一个32位长的字，行号r是这个字中每个字节的索引，因此状态矩阵可以看作32位(列)长的一维数组，列号c是该数组的列索引。由此上例中的状态可以看作4个字组成的数组，表示如下： 


ω0=［s0,0,s1,0,s2,0,s3,0］
ω1=［s0,1,s1,1,s2,1,s3,1］
ω2=［s0,2,s1,2,s2,2,s3,2］
ω3=［s0,3,s1,3,s2,3,s3,3］



2. 有限域基本数学运算

AES算法的基本思想是基于置换和代替变换的演算方法。其中，置换是对数据的重新排列，而代替则是用数据替换另一个。AES算法中的所有字节按照每4位表示成有限域GF(28)中的一个元素。这个有限域元素可以进行加减法和乘法运算，但是这些运算不同于代数中使用的运算。下面介绍有限域相关算法的基本数学概念。

1) 加减法

在有限域中，多项式的加法运算定义为两个元素对应多项式相同位置指数项相应系数的“加法”。简单地说，有限域GF(28)的加法是按位进行异或XOR运算(记为)，即模2加。多项式减法与多项式加法的规则相同。例如： 


{57}+{83}=(01010111)2(10000011)2=(11010100)2={D4}




以多项式表示加法的计算过程如下： 


(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2




2) 乘法

有限域GF(28)的乘法运算也可以用多项式表示。乘法运算很容易造成溢出问题，解决的方法是多项式相乘后再模一个不可分解的多项式。因此AES算法在有限域GF(28)上的乘法(记为·)定义为多项式的乘积再模一个幂次数为8的不可约多项式m(x)，模m(x)确保了所得结果是次数小于8的二元多项式，因此可以用一字节表示。m(x)的内容为


m(x)=x8+x4+x3+x+1



或用十六进制表示该多项式为{01}{1B}。

例如，{57}·{83}=(x6+x4+x2+x+1)·(x7+x+1)

=(x13+x11+x9+x8+x6+x5+x4+x3+x+1)mod

(x8+x4+x3+x+1)

=x7+x6+1=(11000001)2={C1}

3) x乘法

用多项式x乘以b(x)，即x·b(x)，其结果可以表示为


b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x




将上述结果模m(x)即可求得结果。如果得到的结果序列中： 

（1） b7=0，则不会出现结果溢出问题，该结果即是模运算后的正确形式； 

（2）  b7=1，则会出现结果溢出问题，该乘积结果需要减去m(x)，即求此乘积结果与m(x)的异或。

由此得出，x(即{00000010}2或{02}16)乘以b(x)可先对b(x)在字节内左移一位(最后一位补0)，若b7=1，则再与{1B}16(其二进制为00011011)做逐比特异或来实现，该操作记为b=xtime(a)。x的幂乘运算可以通过重复应用xtime()实现。而任意常数乘法可以通过对中间结果相加实现。

例如，{57}·{13}={FE}，因为


{57}·{02}=xtime（{57}）={AE}
{57}·{04}=xtime（{AE}）={47}
{57}·{08}=xtime（{47}）={8E}
{57}·{10}=xtime（{8E}）={07}


所以{57}·{13}={57}·（{01}{02}{10})={57}{AE}{07}={FE}。

4) 系数在有限域GF(28)的特殊多项式运算

给定字符向量转换为系数在有限域GF(28)中的多项式a(x)=a3x3+a2x2+a1x+a0，它可以用［a0,a1,a2,a3］形式表示。该多项式与有限域元素定义中使用的多项式操作不同，此处的系数本身就是有限域元素，即是字节(byte)而不是比特(bit)，系数本身可以用另一个有限域多项式表示。特殊的4项多项式的乘法可使用不同的模多项式M(x)=x4+1。系数在有限域GF(28)中的多项式运算主要有乘法和乘以x两种。

（1） 给定多项式b(x)=b3x3+b2x2+b1x+b0，计算a(x)与b(x)相乘。令d(x)=a(x)b(x)=d3x3+d2x2+d1x+d0，即


d0=a0·b0a3·b1a2·b2a1·b3
d1=a1·b0a0·b1a3·b2a2·b3
d2=a2·b0a1·b1a0·b2a3·b3
d3=a3·b0a2·b1a1·b2a0·b3


其向量表示为


d0d1d2d3=a0a3a2a1a1a0a3a2a2a1a0a3a3a2a1a0b0b1b2b3




由于多项式M(x)=x4+1在GF(28)下可能不是可约多项式，因此如果任意给定一个4项多项式，在模M(x)下不一定存在一个对应的乘法反多项式。

在AES算法中，对多项式b(x)，这种乘法运算只限于乘一个固定的有逆元的多项式a(x)=a3x3+a2x2+a1x+a0，即存在a(x)a-1(x)=1 mod (x4+1)关系。

（2） 计算b(x)乘以x。c(x)=xb(x)定义为x与b(x)的模M(x)乘法，即c(x)=xb(x)=b2x3+b1x2+b0x+b3。其矩阵表示中，除a1=01外，其他所有ai=00，即



c0c1c2c3=00000001010000000001000000000100b0b1b2b3


因此，x(或x的幂)模乘多项式相当于对字节构成的向量进行字节循环移位。

3.5.4AES算法内部结构

为了理解数据在AES内部的传递方式，首先假设状态A(即128位的数据路径)是由16个字节A0,A1，…,A15按照4×4(字节)的矩阵方式组成。






A0
A4
A8
A12
A1
A5
A9
A13
A2
A6
A10
A14
A3
A7
A11
A15


从下面的内容可知，AES操作的元素是当前状态矩阵的行或列。同样，密钥字节也是以矩阵方式排列，其行数为4，列数可以为4(128位的密钥)、6(192位的密钥)或8(256位的密钥)。

1. 字节代换

字节代换是一个非线性可逆变换，针对状态矩阵中的每个字节，利用替代表(S盒)进行运算，表示为SubBytes(State)，也称仿射变换，其计算过程主要由两个变换复合而成。两个变换的内容如下： 

（1） 选取有限域GF(28)上的乘法逆运算，其中元素{00}映射到它自身。

（2） 应用如下算法完成一有限域GF(28)上的仿射变换


b′=bib(i+4)mod 8b(i+5)mod 8b(i+6)mod 8b(i+7)mod 8b(i+8)mod 8ci




算法中当0≤i<8时，bi是字节的第i个比特，ci是值为{63}(即{01100011})的字节c数组的第i个比特。算法描述中以b′表示该变量将用右侧的值更新。

首先，将字节数据看成GF(28)上的元素，进行模M(x)运算映射到自己的乘法逆，0映射到自身； 其次，作GF(28)的仿射变换，该变换过程可逆。预先将GF(28)上的每个元素通过查表作SubBytes变换，形成S盒。与DES算法中S盒不同的是，AES算法中的S盒具有一定的代数结构，而DES算法中是人为指定构造的。

以矩阵的形式，S盒的仿射变换可表示为


b0b1b2b3b4b5b6b7=1000111111000111111000111111000111111000011111000011111000011111b0b1b2b3b4b5b6b7+11000110




S盒的仿射变换在状态矩阵上的变换功能如图340所示。



图340S盒的仿射变换


实际运算时，此函数可以通过查表快速获得对应变换值，字节变换的变换值如表312所示。例如，b1,1={53}，查字节变换值表，找到第5列第3行，对应数值为{ed}，表示经过字节替代变换后b′1,1={ed}。


表312S盒中字节x，y的替代值(十六进制格式)



x
y

0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
0
63
7c
77
7b
f2
6b
6f
c5
30
01
67
2b
fe
d7
ab
76
1
ca
82
c9
7d
fa
59
47
f0
ad
d4
a2
af
9c
a4
72
c0
2
b7
fd
93
26
36
3f
f7
cc
34
a5
e5
f1
71
d8
31
15
3
04
c7
23
c3
18
96
05
9a
07
12
80
e2
eb
27
b2
75
4
09
83
2c
1a
1b
6e
5a
a0
52
3b
d6
b3
29
e3
2f
84
5
53
d1
00
ed
20
fc
b1
5b
6a
cb
be
39
4a
4c
58
cf
6
d0
ef
aa
fb
43
4d
33
85
45
f9
02
7f
50
3c
9f
a8
7
51
a3
40
8f
92
9d
38
f5
bc
b6
da
21
10
ff
f3
d2
8
cd
0c
13
ec
5f
97
44
17
c4
a7
7e
3d
64
5d
19
73
9
60
81
4f
dc
22
2a
90
88
46
ee
b8
14
de
5e
0b
db
a
e0
32
3a
0a
49
06
24
5c
c2
d3
ac
62
91
95
e4
79
b
e7
c8
37
6d
8d
d5
4e
a9
6c
56
f4
ea
65
7a
ae
08
c
ba
78
25
2e
1c
a6
b4
c6
e8
dd
74
1f
4b
bd
8b
8a
d
70
3e
b5
66
48
03
f6
0e
61
35
57
b9
86
c1
1d
9e
e
e1
f8
98
11
69
d9
8e
94
9b
1e
87
e9
ce
55
28
df
f
8c
a1
89
0d
bf
e6
42
68
41
99
2d
0f
b0
54
bb
16


2. 行移位变换

行移位变换是在状态矩阵的行上进行的。状态阵列的后3行分别以ci为移位大小循环移位。其中，第0行c0=0，即保持不变； 第1行循环移位c1字节； 第2行循环移位c2字节； 第3行循环移位c3字节。运算结果是将行中的字节移向较低位，最低位的字节循环移动至行的最高位。128位状态矩阵的行移位变换操作如图341所示。



图341128位状态矩阵的行移位变换操作


偏移量ci与分组长度Nb有关，不同分组长度的行移位变换偏移量如表313所示。


表313不同分组长度的行移位变换偏移量



Nb
c1
c2
c3
4
1
2
3
6
1
2
3
8
1
3
4



行移位变换实现了字节在每一行的扩散，很自然地想到字节在列中也需要扩散。

3. 列混合变换



列混合变换在状态矩阵上，按照每一列分别进行运算，并将每一列看作有限域4次多项式，即将状态的列看作GF(28)上的多项式a(x)与多项式c(x)相乘，计算结果对固定多项式M(x)=x4+1取模。多项式c(x)表示为


c(x)={03}x3+{01}x2+{01}x+{02}




其中，系数是用十六进制表示的，并且c(x)与x4+1互素。

令b(x)=c(x)a(x) mod (x4+1)，由于x1 mod (x4+1)=x1 mod 4，故有


b0=c0·a0c3·a1c2·a2c1·a3
b1=c1·a0c0·a1c3·a2c2·a3
b2=c2·a0c1·a1c0·a2c3·a3
b3=c3·a0c2·a1c1·a2c0·a3




写成矩阵表示形式为


b0b1b2b3=02030101010103010101020303010102a0a1a2a3



列混合变换的过程如图342所示。



图342列混合变换的过程


例37在AES列混合变换中，模多项式M(x)=x8+x4+x3+x+1，请根据下面的状态矩阵，填写下面表格空格的值，并写出计算过程。


02030101010203010101020303010102s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33=s′00s′01s′02s′03s′10s′11s′12s′13s′20s′21s′22s′23s′30s′31s′32s′33







解： 

s′00=02·8703·6E01·4601·A6

=000011100001101111011100011011100100011010100110

=0100011=47

s′11=01·F202·4C03·E701·8C

=111100101001100011001110000110111110011110001100

=11010100=D4

s′22=01·4D01·9002·4A03·D8

=0100110110010000100101001011000000001101111011000

=00111010=3A

s′33=03·9701·EC01·C302·95

=0010111000011011100101111110110011000011

0010101000011011

=10111100=BC

故空格处分别填47，D4，3A，BC。

4. 轮密钥加变换

在轮密钥加变换中，用轮密钥与状态矩阵按比特进行异或(XOR)操作。轮密钥是通过主密钥生成的子密钥，为了便于计算，轮密钥的长度等于分组长度，每一个轮密钥由Nb个字节组成。轮密钥加变换的过程如图343所示。



图343轮密钥加变换的过程





例38设AES算法分组长度为128，输入的明文M=32 6C A8 F6 42 31 8C D6 43 72 64 E0 98 89 07 C3，密钥k=A3 61 89 B5 54 12 D8 90 F4 14 FC AB 81 70 AE 3F。求AES的第一轮输出。

解： 考虑到扩展密钥的前Nk个字是由密码密钥填充的，即初始轮密钥为k。明文与初始轮密钥加得： 91 0D 21 43 16 23 54 46 B7 66 98 4B 19 F9 A9 FC

经过字节代换为： D0 B1 F4 8A 21 EB 4F AA 0E F6 3B F7 BD 84 C5 DF

行位移变换得： D0 B1 F4 8A EB 4F AA 21 3B F7 0E F6 DF BD 84 C5

列混合变换得： 79 E2 9C 43 8F D0 2D 0C 17 D7 D5 08 1E 18 B0 C1

轮密钥加变换得： A3 54 F4 81 61 12 14 70 89 D8 FC AE B5 90 AB 3F

即得第一轮输出： DA B6 68 C2 EE C2 39 7C 9E 0F 29 A6 AB 88 1B FE

5. 密钥扩展算法

下面以128位的密钥长度介绍密钥扩展算法，其他192位和256位的密钥长度所对应的密钥编排存在一定的相似性。AES的密钥扩展算法是面向字的，其中1个字=32位。对长度为128位的密钥而言，它对应的轮数Nr=10，并得到11个子密钥，且每个密钥的长度均为128位。AES轮密钥(子密钥)ki的计算是递归的，即为了得到子密钥ki，子密钥ki-1必须是已知的，以此类推。



11个子密钥存储在元素为W［0］,…,W［43］的密钥扩展数组W［i］中。子密钥的计算方式如图344所示。元素k0,…,k15表示原始AES密钥对应的字节。



图344128位密钥大小的AES密钥编排


首先，需要注意的是，第一个子密钥k0为原始AES密钥，即原始密钥直接被复制到扩展密钥数组W［i］的前4个元素中。从图中可知，子密钥W［4i］(i=1,…,10)最左边字的计算方式为： 


W［4i］=W［4(i-1)］+g(W［4i-1］)




这里的g表示的是一个输入和输出均为4字节的非线性函数。子密钥其余的三个字是通过递归计算得到的： 


W［4i+j］=W［4i+j-1］+W［4(i-1)+j］




其中，i=1,…,10； j=1,2,3。函数g首先将4个输入字节翻转，并执行一个按字节的S盒代换，最后与轮系数RC相加。轮系数是GF(28)域中的一个元素，即为一个8位的值。轮系数只与函数g最左边的字节相加。而且轮系数每轮都会改变，其变换规则为： 


RC［1］=x0=(00000001)2
RC［2］=x1=(00000010)2
RC［3］=x2=(00000100)2
︙
RC［10］=x9=(00110110)2





函数g的目的有两个： 第一，增加密钥编排中的非线性； 第二，消除AES中的对称性。这两种属性都是抵抗某些分组密码攻击所必要的。




6. AES解密

AES的解密过程是加密过程的逆运算。解密算法中各个变换的操作顺序与加密算法不同，但是加密和解密算法中的密钥生成形式是一致的。AES算法的若干性质保证了可以构造一个等价的解密算法，解密时各个变换的操作顺序与加密时相反(由逆变换取代原来的变换)。解密算法中使用的变换依次为逆列混合变换、逆行位移变换、逆字节变换和轮密钥加变换，变换作用在密文序列对应的状态矩阵上。具体的解密过程如图345所示。



图345AES解密过程


3.5.5AES算法的安全性

对于Rijndael算法的安全性讨论，通过对以下已知的攻击方法来进行分析。 

（1） 穷举攻击法： Rijndael算法中最短的密钥长度是128比特，如果用穷举法则需要2128次，计算量是非常大的，故使用目前技术的穷举法是无效的。

（2） 差分攻击法： 这种攻击法是利用大量已知的明文/密文对之间的差异来推测出密钥。对于Rijndael算法，当轮数超过三轮，若存在1/2n-1(n位分组块的)长度可预测性的差异，这种攻击法就可以推测出密钥的位元值，在Rijndael算法中已经证明Rijndael经过四轮运算后，存在不超过2－150的可预测性差异，5轮运算后不超过2－300的可预测差异，因此可以说这种攻击法对Rijndael算法是无效的。

（3） 线性攻击法： 这种攻击法利用大量收集到的明文/密文对，根据其中可预测的相对关系推导出一个代数展开式，只要能找出相对关系数超过2n/2的线性轨迹，就可以找出密钥值。Rijndael算法已经被证明执行4轮运算后不存在相关系数大于2－75的线性轨迹； 在执行8轮后，其相关系数大于2－150的相关系数也不存在，因此可以说这种攻击法对Rijndael算法是无效的。

（4） 平方攻击法： 这种攻击是一种明文攻击，攻击强度不依赖于S盒列混合矩阵和密钥扩散准则的选取，但迄今为止这种攻击法只能够对经过不超过6次轮运算的Rijndael算法有效，计算量为273+264，因此可以说这种攻击法对Rijndael算法是无效的。

（5） 内插攻击法： 这种攻击法是攻击者利用加密的输入与输出配对，建立一些多项式。如果加密的元件有一个乘法的代数展开式，并且与管理的复杂度结合在一起时，这种攻击便是可行的。攻击的方式是如果攻击者建立的代数展开式的阶度很小，只需要一些加密法的输入和输出配对就可以得到代数展开式的各项系数。但是，Rijndael算法中的GF(28)域是非常复杂的，因此可以说这种攻击法对Rijndael算法是无效的。

从以上分析可以看出，Rijndael算法对已知的攻击具有较好的免疫性，安全性比较高。


3.6
3.6〓IDEA

3.6.1IDEA算法简介

1990年，瑞士联邦技术学院的Xuejia Lai和James Massey提出一个取代DES的对称密码算法，称为PES(Proposed Encryption Standard，建议的加密标准)。为提高对差分密码攻击的抵抗能力，设计者对PES经过两次修改，于1992年将修改后的PES改名为IDEA(International Data Encryption Algorithm，国际数据加密算法)。类似于DES，IDEA算法也是一种数据块加密算法，它设计了一系列加密轮次，每轮加密都使用从完整的加密密钥中生成的一个子密钥。与DES的不同处在于： 它采用软件实现和采用硬件实现同样快速。由于IDEA是在美国之外提出并发展起来的，避开了美国法律上对加密技术的诸多限制，因此，有关IDEA算法和实现技术的文献都可以自由出版和交流，极大地促进了IDEA的发展和完善。

IDEA的分组长度是64位，密钥长度是128位，是已公开的可用算法中速度快且安全性强的分组加密算法，不但具有极强的抗攻击能力，而且具有良好的应用前景。目前，PGP使用IDEA作为其分组加密算法； 安全套接字层SSL也将IDEA包含在其加密算法库SSLRef中； IDEA算法专利的所有者Ascom公司也推出了一系列基于IDEA算法的安全产品，包括基于IDEA的Exchange安全插件、IDEA加密芯片、IDEA加密软件包等。IDEA算法的应用和研究正在不断走向成熟。

3.6.2IDEA算法设计思想

分组密码的强度，主要是通过混淆和扩散来实现的，IDEA算法所依据的设计思想是“混合使用来自不同代数群中的运算”。

1. 混淆

算法的“混淆”性由连续使用作用于一对16比特子块的三种“不相容”的群运算获得，这三种16位的基本运算如下。

（1） 异或运算，即按位做不进位加法运算，规则为


10=01=1，00=11=0




（2） 模216加运算 ，即16位无符号整数做加法运算，规则为： 


X Y≡(X+Y) mod (216)




（3） 模(216+1)乘运算⊙，即16位整数做乘法运算，规则为： 


X⊙Y≡(X×Y) mod (216+1)


注意： 
模(216+1)整数乘法a⊙b的实现公式为

(ab) mod (2n+1)=((ab) mod 2n)-((ab) div 2n)…((ab) mod 2n)≥((ab) div 2n)
((ab) mod 2n)-((ab) div 2n)+2n+1…((ab) mod 2n)≤((ab) div 2n)


例如，(04A5)(B605)≡(B2A0)

(74A5) (B60B)≡(2AB0)

(0000)⊙(8000)≡(216×215) mod (216+1)≡（215+1）≡(8001)


在三种不同的群运算中，要特别注意216+1整数乘法运算⊙，这里除了将16位的全零子块处理为216外，其余16位的子块均按通常处理成一个整数的二进制形式。

三种运算结合起来使用可对算法的输入提供复杂的变换，从而使得对IDEA的密码分析比对仅使用异或运算的DES更为困难。

2. 扩散

IDEA加密算法中的“扩散”性是由称为乘加(Multiplication/Addition，MA)结构的基本单元实现的，如图346所示。该结构的输入是两个16位的子段和两个16位的子密钥，输出也为两个16位的子段。这一结构在算法中重复使用8次，除获得了非常有效的扩散效果之外，还保证了加解密过程的相似性。



图346MA运算结构


MA结构定义： 设A、B、k1、k2是4个16位输入码，‖表示位串的拼接，则32位输出码MA(A,B,k1,k2)可表示为： 


MA(A,B,k1,k2)=((A⊙k1) (((A⊙k1) B)⊙k2))‖(((A⊙k1) B)⊙k2)




以上表达式中的括号不能省略，因为三种运算中的任何两个都相互不可分配，也不可结合。

这里MA运算结构作为IDEA的主要模块，相当于分组加密算法中的S盒作用。

3.6.3IDEA算法内部结构

整个算法包括数据加密过程、子密钥产生、数据解密过程三部分。

1. IDEA迭代过程


IDEA加密算法的总体结构如图347所示。这里加密函数有两类输入： 待加密明文和密钥。其中输入的64位明文数据块x被分成4个16位子块x1，x2，x3，x4，即x=x1x2x3x4。这4个分组作为算法的第1轮输入，整个加密过程总共进行8轮循环，每轮循环由64位码Wi1，Wi2，Wi3，Wi4和6个16位子密钥Z(i-1)*6+1，Z(i-1)*6+2，Z(i-1)*6+3，Z(i-1)*6+4，Z(i-1)*6+5，Z(i-1)*6+6作为输入，产生64位输出W(i+1)1，W(i+1)2，W(i+1)3，W(i+1)4，这里i=1,2,…,8。最后再经过一次输出变换得到4个16位子分组密文y1，y2，y3，y4，将4个子分组重新连接起来就可生成密文y，即y=y1y2y3y4。输入的密钥Z长度为128位，通过子密钥生成器产生52个16位子密钥。



图347IDEA加密算法的总体结构


IDEA加密算法详细迭代过程如图348所示，其中每轮迭代运算分为以下两部分。



图348IDEA加密算法详细迭代过程



第一部分是变换运算，其方法是采用加法及乘法运算将4个16位的子明文分组与4个子密钥混合，产生4个16位的输出。

第二部分是用于产生扩散性的乘加(MA)运算。MA运算生成2个16位的输出。MA的输出再与变换运算的输出采用XOR运算产生4个16位的最后输出，这4个16位的最后输出即成为下一轮运算的原始输入。在这4个最后结果中的第2、3个输出是经位置互换而得到的，这样处理的目的是对抗差分分析攻击。

下面是IDEA算法具体的变换过程。

① x1和第1个子密钥Z(1)1做乘法运算。

② x2和第2个子密钥Z(1)2做加法运算。

③ x3和第3个子密钥Z(1)3做加法运算。

④ x4和第4个子密钥Z(1)4做乘法运算。

⑤ 将①和③的结果相异或。

⑥ 将②和④的结果相异或。

⑦ 将⑤的结果与Z(1)5相乘。

⑧ 将⑥和⑦的结果相加。

⑨ 将⑧的结果与Z(1)6相乘。

⑩ 将⑦和⑨的结果相加。

 将①和⑨的结果相异或。

 将③和⑨的结果相异或。

 将②和⑩的结果相异或。

 将④和⑩的结果相异或。

第一轮的输出是4个子块，即、、和的结果。将中间两个块交换(最后一轮除外)后，就是下一轮的输入。

在经过8轮运算之后，IDEA使用一个输出变换对8轮迭代的结果进行运算，输出变换在进行运算前将第2个输入与第3个输入进行互换，这实际上是将第8轮迭代运算最后所做的互换抵消了，这种特殊安排的目的在于可以使用与加密算法相同结构的解密算法进行解密，从而简化了设计及使用IDEA算法的复杂性。输出变换的过程如下： 

① x1和Z(9)1相乘。

② x2和Z(9)2相加。

③ x3和Z(9)3相加。

④ x4和Z(9)4相乘。

将这4步运算的结果连到一起就是最后产生的正式密文。



2. IDEA密钥生成过程

在加密之前，IDEA需要通过密钥扩展(Key Expansion)将128位的密钥扩展为52个子密钥。加密算法进行迭代操作时，每轮需要6个子密钥，另外还需要4个额外子密钥用于输出变换。

整个密钥的扩展的过程如表314所示，为了能够看清楚8轮迭代的关系，在表中用粗线条将每轮进行了区别。将128位密钥按位编号为（0,1,2,…,127），表314中单元格的内容表示128位密钥子段的范围。例如，16~31表示（16,17,18,…,31），121~8表示（121,122,…,127,1,2,…,8）。



表314IDEA的密钥扩展过程




r
k1
k2
k3
k4
k5
k6
1
0~15
16~31
32~47
48~63
64~79
80~95
2
96~111
112~127
25~40
41~56
57~72
73~88
3
89~104
105~120
121~8
9~24
50~65
66~81
4
82~97
98~113
114~1
2~17
18~33
34~49
5
75~90
91~106
107~122
123~10
11~26
27~42
6
43~58
59~74
100~115
116~3
4~19
20~35
7
36~51
52~67
68~83
84~99
125~12
13~28
8
29~44
45~60
61~76
77~92
93~108
109~124
9
22~37
38~53
54~69
70~85
—
—




下面详细说明密钥扩展过程。首先，将128位密钥k表述为k=b0b1…b127。

第1轮： 将此128位密钥分成8段，依次得8个子密钥： 

Z(1)1=b0b1…b15，Z(1)2=b16b17…b31，…，Z(1)6=b80b81…b95，Z(2)1=b96b97…b111，Z(2)2=b112b113…b127，即将8段中的前6段密钥用于第1轮加密，后2段用于第2轮。

第2轮： 将k循环左移25位，得b25b26…b127b0b1…b24。


将此左移后的128位密钥再分成8段，前4段用于第2轮的子密钥： Z(2)3，Z(2)4，Z(2)5，Z(2)6； 后4段用于构成第3轮子密钥的前半部分： Z(3)1，Z(3)2，Z(3)3，Z(3)4。

第3轮： 再次把第2轮的k循环左移25位，同样分成8段，前2段用于构造第3轮子密钥； 后6段用于下一轮。

以此继续操作，当循环左移了5次之后，已经生成了48个子密钥，还有4个额外的子密钥需要生成，再次把k循环左移25位，选取划分出来的8个16位子密钥的前4个作为那4个额外加密密钥。至此，供加密使用的52个子密钥生成完毕。

3. IDEA的解密过程

IDEA的解密过程本质上与加密过程相同，所不同的是参与迭代运算的解密子密钥的生成方式。解密密钥和加密密钥有一个对应关系，其子密钥k(r)i是从加密密钥Z(r)i导出的。导出关系如下： 


(k(r)1,k(r)2,k(r)3,k(r)4)=(z(10-r)-11,-z(10-r)3,-z(10-r)2,z(10-r)-14),r=2,…,8
(k(r)1,k(r)2,k(r)3,k(r)4)=(z(10-r)-11,-z(10-r)2,-z(10-r)3,z(10-r)-14),r=1,9
(k(r)5,k(r)6)=(z(9-r)5,z(9-r)6),r=1,…,8




这里Z-1表示Z mod (216+1)乘法的逆，即Z⊙Z-1≡1 mod (216+1)； -Z表示Z mod 216加法的逆，即Z⊙-Z≡0 mod 216。

以上解密密钥导出的公式描述如下。 

（1） 第r(r=1,2,…,9)轮解密的前4个子密钥是由加密过程第(10-r)轮的前4个子密钥导出的，其中变换阶段被记为循环9。解密密钥的第1个和第4个子密钥取为相应的第1个和第4个加密子密钥模216+1乘法逆元。第2个和第3个解密子密钥取法为： 当轮数r=2,…,8时，取为相应的第3个和第2个加密子密钥的模216加法逆元； 当r=1和9时，取为相应的第2个和第3个加密子密钥的模216加法逆元。

（2） 第r(r=1,2,…,8)轮解密的后两个子密钥等于加密过程的第(9-r)轮的后两个子密钥。



3.6.4IDEA算法的安全性

IDEA算法的密钥长度为128位。自1991年提出至今，设计者尽最大努力使该算法不受差分密码分析的影响，数学家已证明IDEA算法在其8轮迭代的第4轮之后便不受差分密码分析的影响。假定穷举法攻击有效，那么即使设计一种每秒可以试验10亿个密钥的专用芯片，并将10亿片这样的芯片用于此项工作，仍需1013年才能解决问题； 若用1024片这样的芯片，有可能在一天内找到密钥，不过人们还无法找到足够的硅原子来制造这样一台机器。目前，尚无公开发表的试图对IDEA进行密码分析的文章。因此，目前看IDEA是非常安全的，并且IDEA数据比较RSA算法加、解决速度快得多，又比DES算法要相对安全得多。


3.7
3.7〓中国商用密码算法SM4

3.7.1SM4算法简介

2012年3月，中国国家密码管理局（National Cryptographic Administration）正式公布了包含SM4分组密码算法在内的6项密码行业标准，SM4的正式名称是“基于SM1算法的分组密码算法”（Block Cipher Algorithm Based on SM1）。SM1算法是中国自主研发的分组密码算法，SM4算法在其基础上进行了改进和优化。

3.7.2SM4算法设计思想

与DES和AES算法类似，SM4算法是一种分组密码算法。其分组长度为128bit，密钥长度也为128bit。加密算法与密钥扩展算法均采用32轮非线性迭代结构，以字（32位）为单位进行加密运算，每次迭代运算均为一轮变换函数F。SM4算法加/解密算法的结构相同，只是使用轮密钥相反，其中解密轮密钥是加密轮密钥的逆序。

SM4密码算法的基本运算有模2加和循环移位。

（1） 模2加：记为，为32位逐比特异或运算。

（2） 循环移位： <<<i，把32位字循环左移i位。

3.7.3SM4算法内部结构
1． SM4算法基本构件

1） S盒

S盒是以字节为单位的非线性替换，其密码学作用是混淆，它的输入和输出都是8位的字节。设输入字节为a，输出字节为b，则S盒的运算可表示为

b=S(a)


S盒的替换规则如表315所示。


表315SM4密码算法的S盒


0123456789ABCDEF

0D690E9FECCE13DB716B614C228FB2C05
12B679A762ABE04C3AA44132649860699
29C4250F491EF987A33540B43EDCFAC62
3E4B31CA9C908E89580DF94FA758F3FA6
44707A7FCF37317BA83593C19E6854FA8
5686B81B27164DA8BF8EB0F4B70569D35
61E240E5E6358D1A225227C3B01217887
7D40046579FD327524C3602E7A0C4C89E
8EABF8AD240C738B5A3F7F2CEF96115Al
9E0AE5DA49B341A55AD933230F58CBlE3
A1DF6E22E8266CA60C02923AB0D534E6F
BD5DB3745DEFD8E2F03FF6A726D6C5B51
C8D1BAF92BBDDBC7F11D95C411F105AD8
D0AC13188A5CD7BBD2D74D012B8E5B4B0
E8969974A0C96777E65B9F109C56EC684
F18F07DEC3ADC4D2079EE5F3ED7CB3948



2） 非线性变换τ

非线性变换τ是以字为单位的非线性替换，它由4个S盒并置构成。设输入为A=(a0,a1,a2,a3)(4个32位的字)，输出为B=(b0,b1,b2,b3)(4个32位的字)，则

B=(b0,b1,b2,b3)=τ(A)=(S(a0),S(a1),S(a2),S(a3))（31）


3） 线性变换L

线性变换L以字为处理单位，其输入输出都是32位的字，它的密码学作用是扩散。

设L的输入为字B，输出为字C，则

C=L(B)=B(B<<<2)(B<<<10)(B<<<18)(B<<<24)（32）


4） 合成变换T

合成变换T由非线性变换τ和线性变换L复合而成，数据处理的单位是字。设输入为字X，则先对X进行非线性τ变换，再进行线性L变换，记为

T(X)=L(τ(X))（33）


由于合成变换T是非线性变换τ和线性变换L的复合，所以它综合起到混淆和扩散的作用，从而可提高密码的安全性。

2． 轮函数

轮函数由上述基本构件组成。设轮函数F的输入为4个32位字（X0,X1,X2,X3），共128位，轮密钥为一个32位的字rk，输出也是一个32位的字，由下式给出：

F(X0,X1,X2,X3,rk)=X0T(X1X2X3rk)


根据式（33），有

F(X0,X1,X2,X3,rk)=X0L(τ(X1X2X3rk))


记B=(X1X2X3rk),根据式（31）和式（32），有

F(X0,X1,X2,X3,rk)=X0［S(B)］［S(B)<<<2］［S(B)<<<10］
［S(B)<<<18］［S(B)<<<24］


轮函数的结构如图349所示。

3. 加密算法

加密算法采用32轮迭代结构，每轮使用一个轮密钥。

设输入的明文为4个字（X0, X1, X2, X3）（128比特长），输入的轮密钥为rki（i=0,1,…,31）,共32个字。输出的密文为4个字（Y0,Y1,Y2,Y3）（128比特长），加密算法可描述如下：

Xi+4=F(Xi,Xi+1,Xi+2,Xi+3,rki) 
= XiT(Xi+1Xi+2Xi+3rki)(i=0,1,…,31)


为了与解密算法需要的顺序一致，同时也与人们的习惯顺序一致，在加密算法之后还需要一个反序处理R：

(Y0, Y1, Y2, Y3)=(X35,X34,X33,X32)=R(X32,X33,X34,X35)


加密算法的框图如图349所示。



图349SM4加密算法和轮函数结构图


4. 解密算法

解密算法与加密算法相同，只是轮密钥的使用顺序相反，解密轮密钥是加密轮密钥的逆序。

算法的输入为密文(Y0, Y1, Y2, Y3)和轮密钥rki (i=31,30,…,1,0)，输出为明文(X0,X1,X2,X3)。为了便于与加密算法对照，解密算法中仍然用Xi表示密文，于是可得到如下的解密算法。

Xi=F(Xi+4,Xi+3,Xi+2,Xi+1,rki) 
=Xi+4T(Xi+3Xi+2Xi+1rki)(i = 31,30,…,1,0)


与加密算法之后需要一个反序处理同样的道理，在解密算法之后也需要一个反序处理R：

(X0,X1,X2,X3)=R(X3,X2,X1,X0)

5. 密钥扩展算法

SM4算法采用32轮的迭代加密结构，拥有128位加密密钥，一共使用32轮密钥，每一轮的加密使用32位的一个轮密钥。SM4算法的特点使得它需要使用一个密钥扩展算法，在加密密钥当中产生32个轮密钥。在这个密钥的扩展算法当中有常数FK、固定参数CK这两个数值，利用这两个数值便可完成它的这一个扩展算法。

1） 常数FK

FK为系统参数，其中每一项都为32位的字，表示为： FK=(FK0,FK1,FK2,FK3)，在密钥扩展中使用的常数设置如下：

FK0=(A3B1BAC6),FK1=(56AA3350)

FK2=(677D9197),FK3=(B27022DC)

2） 固定参数CK

CK用于密钥扩展算法，一共使用有32个固定参数CKi，其中每一项CKi都为32位的字，其产生规则如下：

设cki,j为CKi的第j字节(i=0,1,…,31;  j=0,1,2,3)，即CKi=(cki,0,cki,1,cki,2,cki,3)，则cki,j=(4i+j)×7(mod 256)。

这32个固定参数如下（十六进制）：

00070e15,1c232a31,383f464d,545b6269,

70777e85,8c939aa1,a8afb6bd,c4cbd2d9,

e0e7eef5,fc030a11,181f262d,343b4249,

50575e65,6c737a81,888f969d,a4abb2b9,

c0c7ced5,dce3eaf1,f8ff060d,141b2229,

30373e45,4c535a61,686f767d,848b9299,

a0a7aeb5,bcc3cad1,d8dfe6ed,f4fb0209,

10171e25,2c333a41,484f565d，646b7279。

3） 密钥扩展算法

加密密钥：SM4算法的加密密钥长度为128比特，将其分为四项，其中每项都为32位的字，可设输入的加密密钥为MK=(MK0,MK1,MK2,MK3)。

轮密钥：由加密密钥通过密钥扩展算法生成，其中每项都为32位的字，可设输出的轮密钥为rki(i=0,1,…,30,31)。

密钥扩展算法可描述如下，其中Ki(i=0,1,…,34,35)为中间数据：

（1） (K0,K1,K2,K3)=(MK0FK0,MK1FK1,MK2FK2,MK3FK3)

（2） For i=0,1,…,31 Do

rki=Ki+4=KiT′(Ki+1Ki+2Ki+3CKi)

说明： 其中的T′变换与加密算法轮函数中的T基本相同，只将其中的线性变换L修改为以下的L′：

L′(B)=B(B<<<13)(B<<<23)

从密钥扩展算法中可以发现，密钥扩展算法与加密算法在算法结构方面类似，同样都采用了32轮类似的迭代处理。

3.7.4SM4算法的安全性

SM4算法的设计目标是提供高安全性、高效率和易于实现的分组密码方案。它采用128位密钥和128位分组大小，通过32轮的迭代结构和一系列的置换、代换和异或等基本运算来实现加密和解密操作，已通过了多种密码学安全性分析和评估，被广泛认可和接受。

SM4算法的主体运算是非平衡Feistel网络，有很高的灵活性，所采用的S盒可以根据需要进行替换，以应对突发性的安全威胁。算法的32轮迭代采用串行处理，这与AES中每轮使用代换和混淆并行地处理整个分组有很大不同。此外，需要特别注意的是，密钥扩展算法采用了非线性变换T，这个措施将极大地增强密钥扩展的安全性，SM4算法的这个特点与AES加密算法类似，而DES的密钥生产算法并没有采用这种类似措施。

SM4算法的发布标志着中国在商用密码算法领域的自主研发和国际化进程。它已成为中国政府和企事业单位的标准加密算法，并在各个领域得到广泛应用，包括金融、电子支付、电子政务、物联网等。SM4算法的发布也体现了中国在信息安全领域的重视和发展。作为一种自主可控的密码算法，SM4在保护国家信息资产、提升信息安全能力方面发挥着重要作用。同时，SM4算法也向国际密码学界展示了中国在密码学研究和应用方面的贡献和实力。总的来说，SM4密码算法是中国自主研发的分组密码算法，具有高安全性、高效率和易于实现的特点，被广泛应用于各个领域并成为中国的标准加密算法。


3.8
3.8〓分组密码的工作模式

分组密码是最基本的密码技术之一，其处理消息的长度是固定的，如DES为64位，AES为128位，但是在实际中需要处理的消息通常是任意长的，且要求密文尽量不确定，同时需要采用适当的方式来隐蔽明文的统计特性、数据的格式等，以提高整体的安全性。这些要求分组密码自身不能做到，因此，引出了如何利用分组密码处理任意长度消息的问题，解决这个问题的技术就是分组密码的工作模式。1980年12月，FIPS 81标准化了为DES开发的五种工作模式。这些工作模式适合任何分组密码。本节以DES为例介绍分组密码主要的五种工作模式。

3.8.1电码本模式

对给定的随机密钥k，每一块明文对应固定的密文块，即相同的明文组蕴含着相同的密文组，类似电码本中的码字，因此又称电码本(Electronic Code Book，ECB)模式，如图350所示。电码本(ECB)模式是分组密码最简单的工作模式。加密算法和解密算法定义如下。 

加密算法： Ci=Ek(Mi)(i=1,2,…,m)

解密算法： Mi=Dk(Ci)(i=1,2,…,m)




图350ECB工作模式



上述算法中，M=M1M2…Mm表示明文； C=C1C2…Cm表示相应的密文。每个分组块Mi长度为64位，如果最后一个分组不够64位，则需要填充0或1。

ECB模式的优点是可并行运算、速度快和易于标准化。缺点是分组加密不能隐蔽数据格式； 不能抵抗组的重放、嵌入、删除等攻击； 加密长度只能是分组的倍数。因此，ECB模式仅适用于短数据加密，如果需要安全地传递DES密钥，ECB是最合适的模式。

3.8.2密码分组链接模式

为了解决ECB的安全缺陷，可以让重复的明文分组产生不同的密文分组，密码分组链接(Cipher Block Chaining，CBC)模式就可满足这一要求。CBC模式主要基于两种思想。第一，所有分组的加密都链接在一起，其中各分组所用的密钥相同。加密时输入的是当前的明文分组和上一个密文分组的异或，这样使得密文分组不仅依赖当前明文分组，而且还依赖前面所有的明文分组。因此，加密算法的输入不会显示出与这次的明文分组之间的固定关系，所以重复的明文分组不会在密文中暴露出这种重复关系。第二，加密过程使用初始量(IV)进行了随机化。图351是CBC工作模式示意图。



图351CBC工作模式示意图



加密算法和解密算法定义如下。 

加密算法： 

Ci=Ek(Ci-1Mi)(i=1,2,…,m)

C0=IV 

解密算法： 

Mi=Dk(Ci)Ci-1(i=1,2,…,m)

C0=IV

CBC模式的优点是引入了收发双方相互可公开的随机初始量C0=IV，为使安全性最高，IV应像密钥一样被保护，可使用ECB加密模式来发送IV。保护IV的原因： 如果敌手篡改IV中的某些比特，则接收方收到的M1中相应的比特也发生了变化。

如果加密算法E是伪随机的，则输出具有一定的随机性，避免了ECB模式的缺点，隐蔽了明文的数据格式，在一定程度上能防止数据窜改。缺点是会出现错误传播，密文Ci在传输中发生错误不仅影响Ci的正确译文，还会影响其后Ci+1的正确解密。CBC模式不能纠正传输中的同步差错，即传输中增加或丢失一个或多个比特所引起的密文组边缘的错乱。CBC模式是应用最广、影响也最大的一个工作模式，适合加密长度大于64位的消息，但消息长度只能是分组长度的倍数，不能是任意长度的消息； 此外，CBC模式还可以用来实现报文的完整性认证和用户的身份认证。

3.8.3密码反馈模式

上述的CBC模式非常适用于大量信息的加密，然而在实时(RealTime)通信的应用中，如果接收方收到发送方传送的密文后，想立即解密时，就不适用了，此时效率就变成非常重要的问题，这种情况下密码反馈(Cipher Feedback，CFB)模式加密就派上用场了。

利用CFB模式思想是： 把分组密码当作流密码使用，即CFB模式可将DES分组密码置换成流密码。流密码具有密文和明文长度一致、运行实时的性质，这样数据可以在比分组小得多的单元里进行加密。如果需要发送的每个字符长为8比特，就应使用8比特密钥来加密每个字符。如果长度超过8比特，则造成浪费。但是要注意，由于CFB模式中分组密码是以流密码方式使用，所以加密和解密操作完全相同，因此无法适用于公钥密码系统，只能适用于对称密钥密码系统。

加密算法和解密算法定义如下： 


设原分组密码长度为l，以流密码方式传送的单元长度为s，一般取s＝8且1<s<l。如图352所示，明文M被划分成明文组M1M2…Mi…Mm，其中Mi(1≤i<m)都为s比特。



图352CFB工作模式


MSBs(X)： 表示从自变量X中选择最左侧(最高有效位)s比特输出。

LSBl-s(X)： 表示把自变量X的内容向左移位s比特(最左边的s比特丢失了)。

‖： 表示串联。

加密算法： C1=M1MSBs(Ek(IV)) 

Ci=MiMSBs(Ek(LSBl-s(Ii-1)‖Ci-1))(i=2,3,…,m)

解密算法： M1=C1MSBs(Ek(IV)) 

Mi=CiMSBs(Ek(LSBl-s(Ii-1)‖Ci-1))(i=2,3,…,m)


加密时，加密算法的输入是64比特移位寄存器，其初值为某个初始量IV。加密算法输出的最左(最高有效位)s比特与明文的第一个单元M1进行异或，产生出密文的第一个单元C1，并传送该单元。然后将移位寄存器的内容左移s位，并将C1送入移位寄存器最右边(最低有效位)s位。这一过程继续到明文的所有单元都被加密为止。

解密时，将收到的密文单元与加密函数的输出进行异或。注意这时仍然使用加密算法而不是解密算法，原因如下： C1=M1MSBs(Ek(IV))； M1=C1MSBs(Ek(IV))。可证明以后各步也有类似的这种关系。


CFB模式也需要一个初始量IV，无须保密，但对每条消息必须有一个不同的IV。

CFB模式的缺点： 

（1） 对信道错误较敏感，且会造成错误传播。

（2） 数据加密的速率被降低。

CFB模式的优点： 

（1） 可以处理任意长度的消息，能适应用户不同数据格式的需要。

（2） 可实现自同步功能。

（3） 具有有限步的错误传播，除能获得保密性外，还可用于认证。

（4） 具备CBC模式的优点。

该模式适应于数据库加密、无线通信加密等对数据格式有特殊要求或密文信号容易丢失或出错的应用环境。

3.8.4输出反馈模式

输出反馈(Output Feedback，OFB)模式的结构类似于CFB模式，也把分组密码置换成流密码的形式进行加密处理，如图353所示。不同之处在于OFB模式将加密算法的输出反馈到移位寄存器，而CFB模式是将密文单元反馈到移位寄存器，即OFB模式加密后的初始量没有与明文进行异或操作。事实上对于第一组明文，初始量加密以后作为第二组明文的输入并且再与第一组明文进行异或操作。后续的加密操作都发生在异或之前。



图353OFB工作模式


加密算法和解密算法定义如下。



加密算法： 

O0=IV 

Oi=Ek(Oi-1)Ci=MiOi(i=1,2,…,m-1) 

Om=Ek(Om-1)Cm=MmMSBs(Ek(Om)) 

解密算法： 

O0=C0 

Oi=Ek(Oi-1)Mi=CiOi(i=1,2,…,m-1) 

Om=Ek(Om-1)Mm=CmMSBs(Ek(Om)) 

OFB模式的初始量IV的要求同CFB模式相同，也无须保密，对每条消息也必须选择不同的IV。

OFB模式的优点： 

（1） 错误传播小，如C1中的1比特错误只导致M1中的1比特错误，后面各明文单元则不受影响； 而在CFB中，C1也作为移位寄存器的输入，因此它的1比特错误会影响解密结果中各明文单元的值。

（2） 消息长度是任意的，可以预处理，并且可在线处理(随时处理明文)等。


OFB模式的引入是为了克服CBC和CFB这两种模式中存在的错误传播问题。OFB模式虽然不存在错误传播问题，但对密文是否被篡改难以进行检测，因此比CFB模式更易遭受攻击，好在OFB模式多在同步信道中运行，对手难以知道消息的起止点而使篡改攻击不易奏效。OFB模式不具有自同步能力，系统必须保持严格的同步，否则难以解密。在实际应用中，比其他模式更适用于不太稳定的信道(噪声通道)上加密，如人造卫星通信中的加密。

3.8.5计数器模式

CBC模式和CFB模式都存在这样一个问题： 不能以随机顺序来访问加密的数据，因为当前密文数据块的解密依赖于前面的密文块。而这个问题对于很多应用来说，特别是数据库的应用，是很难接受的。为此，又出现了另一种工作模式，即计数器(Counter，CTR)模式。

CTR模式本质上和OFB模式很类似，都是将分组密码变为流密码，如图354所示。两者的区别在于： CTR模式通过递增一个加密计数器来产生连续的密钥流，密钥流的产生之间是没有关联的，而是由计数器来提供； 而OFB模式中的密钥流是逐级反馈的。CTR模式中计数器可以是任意保证不产生长时间重复输出的函数，但使用一个普通的计数器是最简单和最常见的做法。



图354CTR工作模式


加密算法和解密算法如下定义。 

加密算法： 


Ci=MiEk(Ti)(i=1,2,…,m-1)
Cm=MmMSB|Mm|(Ek(Tm))




解密算法： 


Mi=CiEk(Ti)(i=1,2,…,m-1)
Mm=CmMSB|Mm|(Ek(Tm)) 




CTR模式需要计数器序列T1，…，Ti,…，Tm，通过对计数器序列调用分组加密算法得到密钥流，然后和明文异或得到密文。对计数器序列的要求是两两不同，而且不仅是在一个消息的操作中，而且是在同一密钥的所有操作中均要求所用计数器序列两两不同。

也许有人会问，为什么需要这么多模式?CTR模式最吸引人的一个特点就是可以并行化，因为CTR模式不需要任何反馈，这与OFB或CFB模式完全不同。所以可以让两个分组密码引擎同时并行工作，即让两个引擎同时使用第一个分组密码加密计数器值CTR1和CTR2。等这两个分组密码引擎完成后，一个引擎将继续加密值CTR3，而另一个引擎则继续加密CTR4，如此循环。这种方案的加密速率是单个实现方式的两倍。当然，也可以同时运行多个分组密码引擎，这也会使加密速率按比例增加。对吞吐率要求严格的应用，并行化的加密模式非常合适。CTR模式被广泛用于ATM网络安全和IPSec应用中。




〓〓习题3


1. 分别画出并说明流密码流程和分组密码流程。


2. 三级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。

3. 设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2,…,an-1,an)=(1,0,1)，证明输出序列的周期等于p(x)的阶。

4. 设n＝4，f(a1,a2,a3,a4)=a1a4a2a3，初始状态为(a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。

5. 已知流密码的密文串1010110110和相应的明文串0100 010001，而且已知密钥流是使用三级线性反馈移位寄存器产生的，试破译该密码系统。

6. 给定密钥k=(0111111101)，按照SDES密码处理过程以手工方式对明文字节(01000001)进行加密和解密。要求写出每个函数处理后的中间结果。


7. 说明DES中每个子密钥的第一个24位来自初始密钥的同一个28位子集，而其后的第二个24位来自初始密钥的不相交的28位子集。

8. 画出DES解密算法的流程图(注意： 输入是密文，输出是明文)。

9. 在IDEA算法中，已知明文M和密钥k分别为


M=10101010 11100110 01010101 00001111 11001100 00110011 10011001 01100110
k=00000000 11111111 00000000 11111111 11111111 00001111 11110000 11111111
00001111 11110000 11111111 00000000 00001111 11111111 11110000 00001111




求第一轮的输出和第二轮的输入。

10. 为什么IDEA算法中的乘法操作是模(216+1)，而不是简单的模216?

11. 以F5为例说明S盒的替代操作（不通过查表，而通过代数运算）。

12. 在8比特CFB模式中，如果在密文字符中出现1比特的错误，那么该错误能传播多远?

13. 比较CBC模式和CFB模式的异同。

14. 请设计一种一次加密一个明文字节(例如加密来自远程的击键)的OFB模式方案。使用的分组密码为AES，对每个新的明文字节都执行一个分组密码操作。请绘出你的方案框图，请特别留意你给出的框图中使用的位长度。