密码学系列之三：DES、AES、IDEA —— 一文搞懂分组密码_idea密码

1. 基本概念

分组密码（block cipher）是现代密码学广泛应用的重要体制之一，主要提供数据保密性，也可用于构造伪随机数生成器、流密码、认证码和哈希函数等方面。分组密码分为对称分组密码和非对称分组密码（公钥密码），分组密码在很多场合一般指是对称分组密码。由于分组密码加解密速度较快、安全性好，得到许多密码芯片的广泛支持与应用。

1.1 定义

分组密码本质是一个从明文空间$P$（$m$长的比特串集合）到密文空间$C$（$n$长的比特串集合）的一一映射（一般$m=n=t$）。

将明文消息经编码表示后的二进制序列$p0,p1,\dots ,pi,\dots$划分成若干固定长度的组（或块）$p=(p_0,p_1,\dots ,p_{m-1})$，各组分别在密钥$k=(k_0,k_1,\dots ,k_{t-1})$的控制下转换成长度为$n$的密文分组$c=(c_0,c_1,\dots ,c_{n-1})$。

1.2 分组密码原理

1.2.1 扩散与混乱

（1）扩散 指算法使每一比特明文的变化尽可能多地影响到输出密文序列的变化，以便隐蔽明文的统计特性；并且每一位密钥的影响也尽可能迅速地扩展到较多的输出密文比特中去。即扩散的目的是希望密文中的任一比特都要尽可能与明文、密钥相关联，或者说，明文和密钥中任何一比特值得改变，都会在某种程度上影响到密文值的变化（又称雪崩效应），以防止将密钥分解成若干个孤立的小部分，然后各个击破。

（2）混乱 指在加密变换过程中是明文、密钥以及密文之间的关系尽可能地复杂化，以防密码破译者采用统计分析法进行破译攻击。混乱可以用“搅拌”来形象地解释，将一组明文和一组密文输入到算法中，经过充分混合，最后变成密文。同时要求，执行这种“混乱”作业的每一步都必须是可逆的，即明文混乱以后能得到密文，反之，密文经过逆向混乱操作后能恢复出明文。

1.2.2 乘积密码

乘积密码就是以某种方式连续执行两个或多个密码，使得最后结果或乘积从密码编码的角度比其任意一个组成密码都更强。

设$S_1=\left(M_1,C_1,K_1,E_1,D_1\right)$ 和 $S_2=\left(M_2,C_2,K_2,E_2,D_2\right)$ 是两个密码体制, $S_1\times S_2$定义了乘积密码体制:$$\left(M_1\times M_2,C_1\times C_2,K_1\times K_2,E_1\times E_2,D_1\times D_2\right)$$实际应用中,明文空间和密文空间往往相同, 即$M_1=M_2=C_1=C_2$ , 则乘积密码体制 $S_1\times S_2$ 可简化为 $$\left(M,M,K_1\times K_2,E,D\right)$$ 其中，$E=E_1\times E_2,D=D_1\times D_2$

对任意明文$x\in M$和密钥$k=\left(k_1,k_2\right)\in K_1\times K_2$, 加密变换为: $$E_k(x)=E_{k2}\left(E_{k1}(x)\right)$$ 对任意密文$y\in M$和密钥$k=\left(k_1,k_2\right)\in K_1\times K_2$, 解密变换为: $$D_k(x)=D_{k1}\left(D_{k2}(y)\right)$$ 设$S$是一个明文空间和密文空间相同的密码体制$$S^n\stackrel{\text{ def }}{=}\underset{n}{\underbrace{S\times S\times \cdots \times S}}$$则$S^n$称为迭代密码体制。

如果$S^2=S$, 则称$S$是等幂的密码体制。置换密码、仿射密码、Vigenere 密码以及 Hill 密码等许多传统密码体制都是幂等的密码体制。对于幂等的密码体制, 则没有必要使用迭代密码体制$S^2$, 因为$S^2$需要更多的密钥但其安全强度与$S$一样。

如果$S$不是幂等的密码体制, 则对$n>1$ ,迭代密码体制$S^n$的安全强度会比$S$高, 这种通过对一个密码体制进行迭代来提高其安全强度的思想被广泛应用于对称密码体制的设计中, 通常称之为密码体制的迭代结构。具体地, 就是在密钥控制下扩散和混乱两种基本密码操作的多次迭代,每次迭代中的各种基本密码操作总体,称之为轮函数。

1.2.3 分组密码的迭代结构

（1） SP网络

代换-置换网络（Subsituation Permutation Network） 简称SP网络，是由多重**S变换（S盒，混乱）和P变换（P盒，扩散）**组合成的变换网络，是乘积密码的一种常见表现形式。

SP网络中的S盒是许多密码算法唯一的非线性部件，其密码强度决定了整个密码算法的强度。

SP网络具有雪崩效应，即输入（明文或密钥）即使只有很小的变化，也会导致输出（密文）产生巨大变化。

（2）Feistel网络

Feistel网络由Feistel提出，保证了算法可逆性，即加密和解密可以采用同一算法实施。

长度为$n$bit（$n$为偶数）的明文分组分为左右各长为$n/2$的两部分：$L$和$R$。定义迭代算法如下：$$L_i=R_{i-1}$$$$R_i=L_{i-1}\oplus f(R_{i-1}，K_i)$$其中，$K_i$是第$i$轮使用的子密钥，$f$是任意轮函数。

1.3 算法要求

（1）算法要求

• 分组长度足够大：分组长度较小时，攻击者可有效穷举明文空间，得到密码变换规律（难以抵抗选择明文攻击）
• 密钥量足够大：如果密钥量小，攻击者可有效地通过穷举密钥，对密文进行解密，得到有意义的明文（难以抵抗唯密文攻击）
• 密码变换足够复杂：使攻击者除了穷举法攻击以外，找不到其他简洁的数学破译方法
• 加解密简单：易于软硬件快速实现。

（2）设计准则

• 分组长度：确保抵抗选择明文攻击，一般为128位
• 密钥长度：确保抵抗唯密文攻击，一般128位以上
• 轮函数：轮函数$F$要遵循雪崩效应和位独立准则（要求输入中某一位的变化，引起输出中其他位的变化是彼此无关的）
• 迭代轮数：使密码分析难度大于简单穷举攻击的难度，一般采用$8、10、12、16、20$的居多
• 子密钥生成方法：不存在简单关系（简单关系指给定两个有某种关系的种子密钥，能预测他们子密钥间的关系）；种子密钥的所有比特对每个子密钥比特的影响大致相同；没有弱密钥或可避开弱密钥

2. DES

2.1 简介

美国国家标准局（NBS，National Bureau of Standards）于1973年开始征集联邦数据加密标准，许多公司提交了算法，IBM公司的Lucifer加密系统最终胜出。经过两年多的公开讨论，1977年1月15日NBS决定利用这个算法，并将其更名为数据加密标准（DES，Data Encryption Standards）。

DES是第一个广泛应用于商用数据保密的密码算法，当时确定有效期为5年，随后在1983年、1988年、1993年三次再度授权该算法续用五年，直到1997年开始征集高级加密标准，2000年选定比利时人设计的Rijndael算法作为新标准。

2.2 DES基本结构

DES加密主要分为三个阶段：

• 64位明文经初始置换（$IP$）被重新排列，并将其分为左右两个分组$L_0$和$R_0$，各32位
• 在密钥参与下，对左右两个分组进行16轮相同轮函数的迭代，每轮迭代都有置换和代换。最后一轮迭代输出为64位，是左半部分和右半部分互换产生的预输出
• 最后的预输出再通过逆初始置换（$I{P}^{-1}$）产生64位密文

形式化描述如下：

$i$：迭代次数
$\oplus$：逐位模2求和
$f$：加密函数

2.2.1 $IP$和$I{P}^{-1}$

初始置换$IP$及逆初始置换$I{P}^{-1}$按照置换表进行换位，无密码意义。

2.2.2 DES的一轮迭代

DES的轮函数$F$由三部分组成：扩展置换（E盒）、非线性代换（S盒）、线性置换（P盒）。

(1)扩展置换

扩展置换（E盒）将32位输入扩展为48位输出。扩展方法为:将48位输出按8行6列的次序排列,排列时,将输入位序号按32、1、2、…、31的次序依次排列,但上一行的后两位依次在下一行的起始位置重用。

E盒产生与子密钥相同长度的数据使得能进行异或运算，同时，扩展后的数据在S盒的作用下能进行压缩，实现了非线性变换。此外，由于E盒输入的1位影响2个S盒的输入，所以输出对输入的依赖性将传播更快，从而快速实现雪崩效应。

(2)压缩代换

代换盒（S盒）的功能是进行非线性代换，它是DES中唯一的非线性部分，DES的安全强度主要取决于S盒的安全强度。S盒是一个查表运算，8个S盒分别对应8个非线性的代换表。输入的48位数据分成8组,每组6位作为分别进入8个S盒进行运算。每个S盒的输入均为6位，输出为4位。这样,经过S盒代换之后,E盒扩展生成的48位数据又重新被压缩成32位数据。


S盒的查表方法：假设S盒的6位输人为$b_1{b}_2{b}_3{b}_4{b}_5{b}_6$，则将$b_1$$b_6$组合,形成1个两位数,这两位数可以转换成十进制的$0-3$的某个数,它对应表的行号,其余4位$b_2{b}_3{b}_4{b}_5$构成了1个4位数,可转化为$0-15$的某个数，对应表的号，通过6位输人确定的行号和列号所对应位置的值作为输出。

S盒的设计特点:

• 具有良好的非线性,即输出的每一个比特与全部输入比特有关;
• 每一行包括所有16种4位二进制;
• 两个输入相差1bit比特时,输出相差2bit;
• 如果两个输入刚好在中间2个比特上不同,则输出至少有2个比特不同;
• 如果两个输入前2位不同而最后2位相同,则输出一定不同;
• 相差6bit的输入共有32对,在这32对中有不超过8对的输出相同。

此外，S盒的设计标准被列入官方机密，并未公开，因此无法确信DES内部结构没有陷门，美国国家安全局有可能利用这些陷门在没有密钥的情况下解密。

（3）置换运算
置换运算（P盒）按照列表进行简单位置置换。

2.2.3 DES子密钥生成

初始密钥64位通过置换选择PC-1得到有效的56位密钥，然后分为2个28位数据$C_0$和$D_0$。每轮迭代中，$C_{i-1}$和$D_{i-1}$分别循环左移1位或2位，移位后的值作为下一轮输入，同时也作为置换选择PC-2的输入，通过置换选择PC-2产生48位的输出，即为一个子密钥。

2.3 DES的安全性

（1）互补性
对明文$m$逐位取补，记为$\bar{m}$，密钥$k$逐位取补，记为$\bar{k}$，若$c=E_k(m)$，则$\bar{c}=E_{\bar{k}}(\bar{m})$。其中$\bar{m}、\bar{k}、\bar{c}$分别表示对$m、k、c$按位取反。

则该特性被称为算法的互补性，互补性表明，如果用某个密钥加密一个明文分组得到一个密文分组，那么用该密钥的补密钥加密该明文分组的补得到的是该密文分组的补。

由于DES算法中的两次异或运算（1次在S盒之前，1次在P盒之后）使其具有互补性，因此DES在选择明文攻击下所需工作量减半，仅需测试$2^{55}$个密钥（$2^{56}$个密钥的一半）。

（2）弱密钥

给定初始密钥$K$，若子密钥生成器得到各个子密钥都相同，即$$K_1=K_2=...K_{16}$$则称初始密钥$K$为弱密钥（Weak Key）。

若$K$为弱密钥，则对任意64位数据$M$，有$$E_K(E_K(M))=M，D_K(D_K(M))=M$$即加密和解密没有区别。

弱密钥的产生是由于密钥生成器中的C和D的存数载循环移位时没有发生变化，DES的弱密钥共4个。

给定初始密钥$K$，若子密钥生成器得到子密钥只有2种，且每种都出现8次，则称$K$为半弱密钥（Semi-weak Key）。半弱密钥是成对出现的，且是互补的。此外还有$1/4$弱密钥和$1/8$弱密钥。

DES共有256个安全性较差的密钥，包括所有的弱密钥、半弱密钥、$1/4$弱密钥和$1/8$弱密钥，这相对于密钥空间$2^{256}$是一个很小的数，且是能够识别的。

2.4 多重DES

为了提高DES的安全性能，并充分利用有关DES的现有软件和硬件资源，可以使用多重DES。多重DES就是使用多个密钥利用DES对明文进行多次加密。使用多重DES可以增加密钥量，从而大大提高抵抗对密钥的穷举搜索攻击的能力。已经证明多重DES并不等价于使用一个56位密钥的单重DES，常用的为三重DES。

3. AES

3.1 简介

为确定一个安全性能更好的分组密码算法以取代DES，1997年美国国家标准与技术研究院(NIST,National Institute of Standards and Technology)公开征集高级加密标准(AES，Advanced Encryption Standard)。AES的基本要求是安全性能不低于三重DES,性能比三重DES快。NIST特别提出了高级加密标准必须是分组长度为128位的对称分组密码，且支持长度为128位、192位、256位的密钥。此外，如果算法被选中,在世界范围内须是可免费获得的。

2000年10月2日，NIST宣布最终评选结果，根据安全性（稳定的数学基础、无算法弱点、可抗密码分析）、性能（速度快）、大小（内存与存储空间占用小）、易实现（良好的软硬件适应性）等标准，比利时密码学家Joan Daemen和Vincent Rijmen提出的“Rijndael数据加密算法”最终获胜。修改的Rijndael算法成为高级加密标准AES，2001年11月26日，NIST正式公布高级加密标准AES，并于2002年5月26日正式生效。

3.2 AES基本结构

AES分组长度只能是128位，密钥的长度可以使用128位、192位或256位三者中的任意一种。密钥长度不同，则加密轮数不同，如表所示。

AES处理单位是字节，128位输入明文分组$P$和输入密钥$K$都被分成16个字节（$4\times 4$）。明文分组用以字节为单位的正方形矩阵描述，称为状态（State）矩阵。

AES由四个的阶段组成:字节代换、行位移、列混淆、轮密钥加，未使用Feistel结构，解密过程与加密过程并不一致。

3.2.1 AES的一轮操作

（1）字节代换

AES的字节代换可以简化成一个简单的查表操作，定义了一个S盒用于加密查表，一个逆S盒用于解密查表，都是由$16\times 16$字节组成的矩阵，即矩阵共有$256$元素，每元素的内容是一个1个字节(8bit)的值，且每元素各不相同。

状态矩阵中的元素按照以下方式映射为一个新的字节：该字节的高4位作为行值，低4位作为列值，取出S盒（或逆S盒）中对应列的元素作为输出。

（2）行移位

行移位操作用于S盒的输出，将列的4个行螺旋地左移，即第0行左移0字节，第1行左移1字节，第2行左移2字节，第3行左移3字节，如下图所示。

行移位使得列完全进行了重排，即在移位后的每列中，都包含有未移位前每个列的一个字节。接下来就可以进行列内混合了。(逆向行移位变换将中间态数据的后三行执行相反方向的移位操作)

（3）列混合

列混合变换由经移位后的状态矩阵与固定的矩阵相乘，得到混淆后的状态矩阵。

列混淆变换的矩阵系数是基于在码字间有最大距离的线性编码，这使得在每列的所有字节中有良好的混淆性。列混淆变换和行移位变换使得在经过几轮变换后，所有的输出位均与所有的输入位相关。

（4）轮密钥加

轮密钥加是将128位轮密钥$K_i$同状态中的数据进行逐位异或操作，密钥$K_i$中每个字$w[4i],w[4i+1],w[4i+2],w[4i+3]$为32bit,包含4个字节（$w[4i],i=\mathrm{0.1.}\dots ,10$)的生成过程。该过程可以看成字逐位异或的结果,也可以看成字节级别或者位级别的操作。

3.2.2 密钥扩展

AES将初始密钥输入到$4\times 4$的矩阵中，矩阵每一列的4个自己组成一个字，一次命名为$w[0]w[1]w[2]w[3]$，构成一个以字为单位的数组$w$。

然后以递归的反噬产生40的新列，对$w$数组进行扩充：

• 如果$i$不是4的倍数，第$i$列如下：$$w[i]=w[i-4]\oplus w[i-1]$$
• 如果$i$是4的倍数，第$i$列如下：$$w[i]=w[i-4]\oplus T(w[i-1])$$

其中，$T$是一个复杂函数，有3部分组成：字循环、字节代换和轮常量异或

• 字循环：将1个字节中的4个字节循环左移1个字节，$[b_0,b_1,b_2,b_3]$变换为$b_1,b_2,b_3,b_0$
• 字节代换： 对字循环的结果使用S盒进行字节代换
• 轮常量异或：将前两步的结果同轮常量$Rcon[j]$进行异或，$j$表示论数。轮常量$Rcon[j]$是一个字，主要是防止不同轮产生的轮密钥的对称性或相似性

密钥扩展的设计标准：

• 已知密钥或轮密钥的部分位无法计算出轮密钥的其它位。
• 可逆的变换，即知道扩展密钥中任何连续的$N_k$个字能够重新产生整个扩展密钥（$N_k$是构成密钥所需的字节数）
• 使用轮常量来排除对称性
• 密钥的每一位能影响到轮密钥的一些位
• 足够的非线性以防止轮密钥的差异完全由密钥的差异所决定

3.3 AES的安全性

• AES加密和解密过程不一致，避免了弱密钥的存在
• AES具有较好的抗击差分分析和线性分析的能力，目前没有已知攻击方法能够攻击AES（Rijndael）
• 密钥穷举攻击，平均需要$2^{127}$次AES运算，计算量非常大

3.4 AES与DES对比

（1）相似之处

• 两者的圈(轮)函数都是由三层构成：非线性层、线性混合层、子密钥异或，只是顺序不同
• AES的子密钥异或对应于DES中S盒之前的子密钥异或
• AES的列混合运算的目的是让不同的字节相互影响，而 DES中F函数的输出与左边一半数据相加也有类似的效果
• AES的非线性运算是字节代替(ByteSub)，对应于DES中惟一的非线性运算S盒
• 行移位运算保证了每一行的字节不仅仅影响其它行对应的字节，而且影响其它行所有的字节，这与DES中置换P相似

（2）不同之处

• AES不是Feistel结构，加密运算和解密运算不一致，因而加密器不能同时用作解密器，DES则无此限制
• AES的密钥长度(128位、192位、256位)是可变的，而DES的密钥长度固定为56位
• DES是面向比特的运算，AES是面向字节的运算

4.1 IDEA

4.1 概述

国际数据加密算法(IDEA, International Data Encryption Algorithm)由瑞士的来学嘉(Xuejia Lai)和 James Massey于1990年公布,当时称为推荐加密标准(PES, Proposed Encryption Standard)。1991年,为抗击差分密攻击,他们对算法进行了改进,称为改进推荐加密标准(IPES,Im proved PES),并于1992年改名为国际数据加密算法IDEA。

IDEA受专利保护,要先获得许可证之后才能在商业应用程序中使用，著名的电子邮件隐私技术PGP就是基于IDEA的。

4.1.2 IDEA基本结构

IDEA的明文分组也是64位，密钥为128位，其加解密也是相似的，即可以用相同算法加密和解密。

64位输人明文块分成4个部分,各16位,$P_1,P_2,P_3,P_4$为算法第1轮的输人。每一轮从原先的128密钥产生6个子密钥，各为16位。这6个子密钥作用于4个状态块。第8轮之后是输出变换,用4个子密钥$K_{49},K_{50},K_{51},K_{52}$，产生的最后输出，即密文块$C_1,C_2,C_3,C_4$(各16位)构成64位密文块。

IDEA共有8轮，每一轮输入为6个子密钥$K_1-K_6$和4个状态数据块$P_1,P_2,P_3,P_4$。

$⊞$:表示模$2^{16}$加

$⨀$:表示模$2^{16}+1$乘

$⨁$:表示异或

IDEA使用128位密钥，没有DES意义下的弱密钥，能够抗差分分析和相关分析。

5. 分组密码工作模式

实际消息长度一般大于分组密码的分组长度，分组密码将消息分为固定长度的数据块来逐块处理。人们设计了许多不同的块处理方式，称为分组密码的工作模式，通常是基本密码模块、反馈和一些简单运算的组合。这些工作模式同时为密文分组提供了一些其他性质，如隐藏明文的统计特性、错误传播控制、流密码的密钥流生成等。

NIST在FIPS 81中定义了4种工作模式,由于新的应用和要求的出现，在800-38A中将推荐模式扩展为5个，可用于包括三重DES和AES在内的任何分组密码。

5.1 电子密码本（ECB）

电子密码本(ECB, Electronic Code Book)模式一次处理一个明文分组，各个明文分组被独立加密成相应的密文分组，主要用于**内容较短且随机的报文（如密钥）**的加密传递。

• 相同明文(在相同密钥下)得出相同的密文，易受实现统计分析攻击、分组重放攻击和代换攻击
• 链接依赖性：各组的加密都独立于其它分组，可实现并行处理
• 错误传播：单个密文分组中有一个或多个比特错误只会影响该分组的解密结果
  

5.2 密码分组链接（CBC）

密码分组链接（CBC, Cipher Block Chaining）模式应用了反馈机制，明文在加密之前需要与前面的密文进行异或，即每个密文分组不仅依赖于产生它的明文分组，还依赖于它前面的所有分组。CBC适合文件加密，是软件加密的最佳选择。

• 相同的明文，即使相同的密钥下也会得到不同的密文分组，隐藏了明文的统计特性
• 链接依赖性:对于一个正确密文分组的正确解密要求它之前的那个密文分组也正确，不能实现并行处理
• 错误传播:密文分组中的一个单比特错误会影响到本组和其后分组的解密，错误传播为两组

5.3 密码反馈（CFB）

密码反馈（CFB, Cipher Feedback Block）将消息看作比特流，无需接受完整个数据分组后才能进行加解密，是自同步序列密码算法的典型例子，通常用于加密字符序列。

• 可用于同步序列密码，具有CBC模式的优点
• 对信道错误较敏感且会造成错误传播
• 数据加解密的速率降低，其数据率不会太高

5.4 输出反馈（OFB）

输出反馈(OFB, Output Feedback Block)是基于分组密码的同步序列密码算法的一种例子。

• CFB模式的一种改进，克服由错误传播带来的问题，但对密文被篡改难于进行检测
• OFB模式不具有自同步能力，要求系统保持严格的同步，否则难于解密