密码学学习 - 分组密码

Question

对于分组密码的介绍，主要涵盖一些常见的分组密码构造，如 Feistel 和 SPN 结构，以及常用的分组密码算法（DES/AED/SM4）和模式（CBC/CFB/ECB/OFB/CTR）。

基本概念

分组密码定义

分组加密（英语：Block cipher），又称分块加密或块密码，是一种对称密钥算法。它将明文分成多个等长的模块（block），使用确定的算法和对称密钥对每组分别加密解密。分组加密是极其重要的加密协议组成，其中典型的如 DES 和 AES 作为美国政府核定的标准加密算法，应用领域从电子邮件加密到银行交易转帐，非常广泛。

分组密码设计原则

扩散（diffusion）和扰乱（confusion）是影响密码安全的主要因素。扩散的目的是让明文中的单个数字影响密文中的多个数字，从而使明文的统计特征在密文中消失，相当于明文的统计结构被扩散。

扰乱是指让密钥与密文的统计信息之间的关系变得复杂，从而增加通过统计方法进行攻击的难度。扰乱可以通过各种代换算法实现。

设计安全的分组加密算法，需要考虑对现有密码分析方法的抵抗，如差分分析、线性分析等，还需要考虑密码安全强度的稳定性。此外，用软件实现的分组加密要保证每个组的长度适合软件编程（如 8、16、32……），尽量避免位置换操作，以及使用加法、乘法、移位等处理器提供的标准指令；从硬件实现的角度，加密和解密要在同一个器件上都可以实现，即加密解密硬件实现的相似性。

块加密中，明文块作为一个整体被处理，并用于产生长度相等的密文块。

分组密码构造

基本操作

1. IP 置换,分为初始 IP 置换与逆置换。初始 IP 置换为将明文块的位进行换位，其置换表示固定的。初始置换表为 8*8 的表格，第一位 58 表示该位置存放明文中的第 58 位字符。第 1 位字符已经变换到 40 位的位置。如果进行初始置换，则必须进行逆初始置换，逆初始置换的实现和初始置换一样，只是置换表不同而已。

2. XOR 异或：如果 a、b 两个值不相同，则异或结果为 1。如果 a、b 两个值相同，异或结果为 0。

a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

3. 移位：

<<，有符号左移位，将运算数的二进制整体左移指定位数，低位用 0 补齐。
>>，有符号右移位，将运算数的二进制整体右移指定位数，整数高位用 0 补齐，负数高位用 1 补齐

4. P 置换：简单的位置置换，只是简单地把一位换成另一位，不进行扩展和压缩。经过 P 置换，32 位的输入得到 32 位的输出。

5. S 盒：一种非线性代换。在 DES 中，S 盒是唯一的非线性部分，DES 的安全强度主要取决于 S 盒的安全程度。S 盒运算其实是一个查表运算。在 E 盒的扩展之后得到了 48 位的数据，将其和 48 位的子密钥进行异或运算，这是密钥参与运算的步骤。将其分成 8 个组，每组 6 个，送到 8 个 S 盒中去。每一个 S 盒都是一个 6 位输入 4 位输出的结构，也就是说，48 位输入到 8 个 S 盒会得到 4*8=32 位的输出。6 位输入到 8 位输出的映射关系如下表所示，其中，第一位和最后一位作为行号，第二位到第五位最为列号。例如，101100，则行号为 10=2，列号为 0110=6。查得（2,6）=2，化成二进制位 0010。注意，8 个 S 盒的映射关系各不相同。

Feistel 结构

对于 Feistel 网络结构，其加密核心在与 F 函数的选定，不同的 F 函数就是遵循 Feistel 结构的不同的加密算法（如 DES），一个好的 F 函数对于加密效果至关重要，一般情况下，F 函数需要满足以下几点：

1. 不要求可逆：即不求 F 函数有反函数；
2. 非线性；
3. 混乱性；
4. 扩散性；
5. 雪崩性：即随着轮数增加其加密效果雪崩式增强；
6. 比特独立性：一个 bit 的加密结果不依赖于其他 bit。

Feistel 结构安全性：

如果轮函数是一个加密安全伪随机函数，以 Ki 为种子，三轮就足以使分组密码成为伪随机排列，而 4 轮足以使其成为“强”伪随机排列。

SPN 代替置换网络结构

SPN 主要依赖的基本技术为代换与置换，是一种迭代密码方案。其迭代过程的设计核心思想如下：

• 使用密钥扩展算法将输入的一个密钥扩展为多个子密钥(Subkey)
• 每轮使用一个子密钥进行加密
• 上一轮的输入作为下一轮的输出,也就是自身迭代

SPN 的安全需求主要有以下两点：

• 混乱性：密钥和明文密文间有复杂的依赖
• 扩散：单个密钥或明文的变化影响到更多的密文

SPN 网络结构的加密过程由 n 轮组成，对于每一轮需要进行分操作如下：

• 白化：子密钥和明文异或
• S 盒代换：将明文分为 m 组，每组长度为 l，按一定规则πs(z) 进行代换，代换规则称为 S 盒
• P 盒置换：代换后进行置换操作，存放置换规则的称为 P 盒
• 在多轮中，上一轮输出为下一轮输入，需要和新的子密钥进行异或操作。

分组密码算法

DES

DES 全称为 Data Encryption Standard，即数据加密标准，是一种使用密钥加密的块算法。DES 解密算法与加密算法共用相同的算法过程。两者的不同之处在于解密时的子密钥 Ki 的使用顺序与加密时的顺序相反。也就说，加密的子密钥使用顺序为 K1K2……K16，那么解密时的使用顺序就是 K16K15……K1。DES 的密钥长度为 56，块长度为 64，一共 16 轮。下面为 DES 的结构。

其中，关键在于 F 函数，其 F 函数的流程如下：

1. 将 64bit 的明文右半部分即 32bit 扩展为 48bit：采用的是 4 个 bit 一组，分为 8 组，每一组前后各加 1bit（增加的 bit 数=218=16bit）。其增加按照下表进行（虚线以外的为增加的 bit 所在位置，如：第一组前是 32，即在第一组前加一个 bit 为整个右半部分的 32bit 的第 32 位的 bit 值{0,1}）：

2. 得到的 48bit 扩充信息，和子密钥 Ki 进行异或操作，得到 48bit 的结果；
3. 将扩充信息和子密钥异或后的结果进行压缩（48bit 压缩到 32bit），压缩的方式是经过 S 盒（4*16 的矩阵）进行替换，S 盒函数是经过严格计算获得的，其 S 盒的替换表与流程如下所示：

4. 置换运算 P（经过一个 P 盒进行置换，IP 置换和 P 盒置换中，表中的数字代表新数据中此位置的数据在原数据中的位置，在 P 盒置换中，没有校验码的位置，即去除了校验码）：指的是将 32bit 压缩后的信息进行 bit 置换操作，改换位操作目的是打乱其原有排序规律（F 函数的混乱性原则）。P 盒与 S 盒的硬件设计规律如下图所示（P 盒是打乱原有 01 序列,S 盒是译码器+P 盒+编码器构成的（以 8-3 线为例））：

在 DES 的整个过程中，子密钥的生成也同样重要。DES 算法共需要 16 轮的迭代运算，每轮迭代运算使用一个子密钥，共需要 16 个子密钥。子密钥是从用户输入的 64 位初始密钥生成的。用户输入的密钥有 64 位，其中有 8 位用于奇偶校验，分别位于第 8，16，24，32，40，48，56，64 位。奇偶校验用于检查密钥 K 的产生和分配以及存储的过程中是否发生了置换的错误，所以 DES 实际的密钥长度只有 56 位。

子密钥的生成过程如下：

1. 输入的种子密钥 K（64bits）首先经过一个 PC-1 置换 j 进行重排。PC-1 置换得到一个 56 位的输出，经过置换后将不会再有奇偶校验位并且顺序也被打乱，再将这个 56 位的结果的前 28 位作为 C0，后 28 位作为 D0。下面为置换盒。

2. 在计算第 i 轮迭代所使用的子密钥时，首先对 Ci-1 和 Di-1 进行循环左移，左移的位数与迭代的轮数对应与下表，分别得到 Ci 和 Di

3. 再将得到的 CiDi 作为 PC-2 置换的输入，从 56 位中选取 48 位作为子密钥

另外，在 DES 的发展中，不断向 AED 进行过渡，从而催生了 3DES，它使用 3 条 56 位的密钥对数据进行三次加密。是 DES 的一个更安全的变形。它以 DES 为基本模块，通过组合分组方法设计出分组加密算法。比起最初的 DES，3DES 更为安全。

该方法使用两个密钥，执行三次 DES 算法，加密的过程是加密-解密-加密，解密的过程是解密-加密-解密。

• 3DES 加密过程为：C=Ek3(Dk2(Ek1§))
• 3DES 解密过程为：P=Dk1(EK2(Dk3©))

3DES 采用两个密钥进行三重加密，其主要目的和好处在于：

• 两个密钥合起来有效密钥长度有 112bit，可以满足商业应用的需要，若采用总长为 168bit 的三个密钥，会产生不必要的开销。
• 加密时采用加密-解密-加密，而不是加密-加密-加密的形式，这样有效的实现了与现有 DES 系统的向后兼容问题。因为当 K1=K2 时，三重 DES 的效果就和原来的 DES 一样，有助于逐渐推广三重 DES。
• 三重 DES 具有足够的安全性，还没有关于攻破 3DES 的报道。

AES

自 DES 算法公诸于世以来，学术界围绕它的安全性等方面进行了研究并展开了激烈的争论。在技术上，对 DES 的批评主要集中在以下几个方面：

1. 作为分组密码，DES 的加密单位仅有 64 位二进制，这对于数据传输来说太小，因为每个分组仅含 8 个字符，而且其中某些位还要用于奇偶校验或其他通讯开销。
2. DES 的密钥的位数太短，只有 56 比特，而且各次迭代中使用的密钥是递推产生的，这种相关必然降低密码体制的安全性，在现有技术下用穷举法寻找密钥已趋于可行。
3. DES 不能对抗差分和线性密码分析。
4. DES 用户实际使用的密钥长度为 56bit，理论上最大加密强度为 256。DES 算法要提高加密强度（例如增加密钥长度），则系统开销呈指数增长。除采用提高硬件功能和增加并行处理功能外，从算法本身和软件技术方面都无法提高 DES 算法的加密强度。

因此，在分组加密算法的研究中，又推出了 AES（高级加密标准）。

AES 在 1997 年提出，安全性相当于 3DES，并且比 3DES 快。明文分组的长度为 128 位即 16 字节，密钥长度可以为 16，24 或者 32 字节(128，192，256 位)。根据密钥的长度，算法被称为 AES-128，AES-192 或者 AE-256。AES 的整个加密过程大致为：对明文，先进行轮密钥加，然后进行轮运算，每轮中分别进行字节代换、行移位、列混合、轮密钥加，最后一轮为字节代换、行移位、轮密钥加。下图为其加解密流程：

其中，涉及到几个运算：

1. 字节代换：把该字节的高 4 位作为行值，低 4 位作为列值，取出 S 盒或者逆 S 盒中对应的行的元素作为输出

2. 行移位：左右循环移位操作，正行移位为左循环移位操作。当密钥长度为 128 比特时，状态矩阵的第 0 行左移 0 字节，第 1 行左移 1 字节，第 2 行左移 2 字节，第 3 行左移 3 字节，如下图所示，逆变换则相反：

3. 列混合：通过矩阵相乘来实现，经行移位后的状态矩阵与固定的矩阵相乘，得到混淆后的状态矩阵，如下图的公式所示，逆变换中，乘的矩阵和正变换中矩阵的乘积正好为单位矩阵：

SM4/SMS4

借用本科一位老师的话，一个国家密码学的发展与否，在某种程序上与核武器的发展是相当的，不管是在军事、商业还是其他用途中，如何保证信息的安全是十分重要的，而这便促使国家需要能够自己发展属于自己的密码算法，内部的一些发展咱也不懂，至少从商用密码来看，国密还是在不断发展的。而 SM4 和 SMS4，则是其中的一部分。

2012 年 3 月，国家密码管理局正式公布了包含 SM4 分组密码算法在内的《祖冲之序列密码算法》等 6 项密码行业标准。与 DES 和 AES 算法类似，SM4 算法是一种分组密码算法。SM4 采用非对称 Feistel 结构，其分组长度为 128bit，密钥长度也为 128bit。加密算法与密钥扩展算法均采用 32 轮非线性迭代结构，以字（32 位）为单位进行加密运算，每一次迭代运算均为一轮变换函数 F。SM4 算法加解密算法的结构相同，只是使用轮密钥相反，其中解密轮密钥是加密轮密钥的逆序。

SM4 基本运算：

1. 模 2 加：⊕，32 比特异或运算
2. 循环移位：<<< i ，把 32 位字循环左移 i 位

基本密码部件：

1. 非线性字节变换 S 盒：起混淆作用，8 位输入，8 位输出。本质上是 8 位的非线性置换。以输入的高半字节为行号，低半字节为列号，行列交叉点 以输入的高半字节为行号，低半字节为列号，行列交叉点处的数据即为输出。 处的数据即为输出。设输入为"ef"，则行号为 e，列号为 f，于是 S 盒的输出值为表中第 e 行和第 f 列交叉点的值，即 列交叉点的值。设输入为 a，输出为 b，S 盒运算可表示为：

b=S_Box（a）

2. 非线性字变换τ ：起混淆作用，其实是 4 个 S 盒进行并行置换，为 32 位字的非线性变换，

3. 字线性部件 L 变换：其扩散作用，32 位输入，32 位输出，输入为 B，输出为 C，其运算规则如下：

C=L(B)=B⊕(B<<<2)⊕(B<<<10)⊕(B<<<18) ⊕(B<<<24)

4. 字合成变换 T：由非线性变换τ 和线性变换 L 复合而成，先 S 盒变换，后 L 变换：

T(X)=L(τ(X))

SM4 轮函数 F

• 输入数据：（X0，X1，X2，X3），128 位，四个 32 位字。
• 输入轮密钥：rk ，32 位字。
• 输出数据：32 位字。
• 轮函数 F ：F（X0，X1，X2，X3，rk）= X0 ⊕T（ X1⊕ X2⊕ X3⊕rk)

SM4 加密与解密

SM4 的加密过程图下图所示：

其中，包含加密变换与反序变换两种：

• 输入明文:(M0 , M1 , M2 , M3)=(X0 , X1 , X2 , X3), 128 位，四个字。
• 输入轮密钥：rki ，i=0,1,…,31，共 32 个轮密钥。
• 输出密文：（Y0，Y1，Y2，Y3），128 位，四个字。
• 算法结构： 轮函数 算法结构：轮函数 32 轮迭代，每轮使用一个轮密钥。 轮迭代，每轮使用一个轮密钥。
• 加密变换：Xi+4=F（Xi，Xi+1，Xi+2，Xi+3，rki）= Xi ⊕T（ Xi+1⊕ Xi+2⊕ Xi+3⊕rki)， i = 0,1…31
• 反序变换：（Y0，Y1，Y2，Y3）=（X35，X34，X33，X32）

SM4 密码算法是对合的，因此解密与加密算法相同，只是轮密码算法是对合的，因此解密与加密算法相同，只是轮
密钥的使用顺序相反：

• 输入密文：Y0，Y1，Y2，Y3）=（X35，X34，X33，X32）
• 输入轮密钥：rki ，i=31,30,29…，1,0 共 32 个轮密钥。
• 输出明文：(X0 , X1 , X2 , X3)
• 算法结构：轮函数进行 32 轮迭代，每轮使用一个轮密钥。
• 解密变换：Xi = F（Xi+4，Xi+3，Xi+2，Xi+1，rki）= Xi+4 ⊕ T（ Xi+3 ⊕ Xi+2 ⊕ Xi+1 ⊕rki ), i=31,…1,0
• 反序变换：(X1，X2，X3，X4) =(M0 , M1 , M2 , M3)

分组加密模式

ECB 电子密码本模式

将数据按 8 个字节一段进行 DES 加密或解密后连接在一起组成密文或明文，最后不足 8 字节的补足。其有以下特点：

• 简单，有利于并行计算，误差不会被传送；
• 不能隐藏明文的模式；
• 可能对明文进行主动攻击。

CBC 密文分组链接模式

CBC 模式在 ECB 模式基础上进行了改进，将前一个密文分组与当前明文分组的内容混合起来进行加密，这样就可以避免 ECB 模式的弱点。

加密步骤如下：

1. 首先将数据按照 8 个字节一组进行分组得到 D1D2…Dn（若数据不是 8 的整数倍，用指定的 PADDING 数据补位）
2. 第一组数据 D1 与初始化向量 VI 异或后的结果进行 DES 加密得到第一组密文 C1（初始化向量 I 为全零）
3. 第二组数据 D2 与第一组的加密结果 C1 异或以后的结果进行 DES 加密，得到第二组密文 C2
4. 之后的数据以此类推，得到 Cn
5. 按顺序连为 C1C2C3…Cn 即为加密结果。

解密是加密的逆过程，步骤如下：

1. 首先将数据按照 8 个字节一组进行分组得到 C1C2C3…Cn
2. 将第一组数据进行解密后与初始化向量 VI 进行异或得到第一组明文 D1（注意：一定是先解密再异或）
3. 将第二组数据 C2 进行解密后与第一组密文数据进行异或得到第二组数据 D2
4. 之后依此类推，得到 Dn
5. 按顺序连为 D1D2D3…Dn 即为解密结果。

这里注意一点，解密的结果并不一定是我们原来的加密数据，可能还含有你补得位，一定要把补位去掉才是你的原来的数据。

CBC 模式具有以下特点：

• 不容易主动攻击,安全性好于 ECB,适合传输长度长的报文,是 SSL、IPSec 的标准。
• 每个密文块依赖于所有的信息块，明文消息中一个改变会影响所有密文块
• 发送方和接收方都需要知道初始化向量
• 加密过程是串行的，无法被并行化（在解密时，从两个邻接的密文块中即可得到一个平文块。因此，解密过程可以被并行化)。

CFB 密文反馈模式

类似于 CBC，可以将块密码变为自同步的流密码；工作过程亦非常相似，CFB 的解密过程几乎就是颠倒的 CBC 的加密过程。

在 CFB 模式中，需要使用一个与块的大小相同的移位寄存器，并用 IV 将寄存器初始化。然后，将寄存器内容使用块密码加密，然后将结果的最高 x 位与平文的 x 进行异或，以产生密文的 x 位。下一步将生成的 x 位密文移入寄存器中，并对下面的 x 位平文重复这一过程。解密过程与加密过程相似，以 IV 开始，对寄存器加密，将结果的高 x 与密文异或，产生 x 位平文，再将密文的下面 x 位移入寄存器。

另外，这种模式与 CBC 相似，平文的改变会影响接下来所有的密文，因此加密过程不能并行化；而同样的，与 CBC 类似，解密过程是可以并行化的。

OFB 输出反馈模式

输出反馈模式（Output feedback, OFB）可以将块密码变成同步的流密码。它产生密钥流的块，然后将其与明文块进行异或，得到密文。与其它流密码一样，密文中一个位的翻转会使平文中同样位置的位也产生翻转。这种特性使得许多错误校正码，例如奇偶校验位，即使在加密前计算而在加密后进行校验也可以得出正确结果。

每个使用 OFB 的输出块与其前面所有的输出块相关，因此不能并行化处理。然而，由于明文和密文只在最终的异或过程中使用，因此可以事先对 IV 进行加密，最后并行的将明文或密文进行并行的异或处理。

可以利用输入全 0 的 CBC 模式产生 OFB 模式的密钥流。这种方法十分实用，因为可以利用快速的 CBC 硬件实现来加速 OFB 模式的加密过程。

OFB 模式加密过程具体如下：

1. 将移位寄存器初始化为 IV，假设移位寄存器长度为 len 比特；
2. 移位寄存器经加密器和秘钥加密得到 Ki(i=1,2,3…)；
3. 明文长度为 m（m≤len）比特，与 K1 的高 m 比特异或，得到 m 比特密文；
4. 将移位寄存器左移 m 位，将刚刚得到的 Ki 的高 m 位填充到移位寄存器的低 m 位；
5. 重复步骤 2-4，直到所有明文被加密完成。

CTR 计数器模式

Counter mode，计数器模式。CTR 模式与 OFB 模式类似，它通过加密“计数器”的连续值来生成下一个密钥流块。计数器可以是任何保证长时间不会产生重复序列的函数。使用简单的确定性输入函数曾经是有争议的;批评者认为，“故意将密码系统暴露在已知的系统输入中是一种不必要的风险。”然而，目前 CTR 模式被广泛接受，任何问题都被认为是底层分组密码的一个弱点，无论其输入是否存在系统偏差，这种分组密码都是安全的。

CTR 模式具有类似于 OFB 的特性，但在解密期间也允许随机访问属性。CTR 模式非常适合在可以并行加密块的多处理器机器上运行。此外，它不存在影响 OFB 的短周期问题。

CTR 模式加密过程如下图所示。其中 Nonce 和前文所述的初始向量 IV 一样，由于密文需要 Nonce 和计数器 Counter 共同计算所得，故如果计数器出错，则不能得到正确的密文。

CTR 模式被广泛用于 ATM 网络安全和 IPSec 应用中，相对于其它模式而言，CTR 模式具有如下特点：

• 硬件效率：允许同时处理多块明文 / 密文。
• 软件效率：允许并行计算，可以很好地利用 CPU 流水等并行技术。
• 预处理：算法和加密盒的输出不依靠明文和密文的输入，因此如果有足够的保证安全的存储器，加密算法将仅仅是一系列异或运算，这将极大地提高吞吐量。
• 随机访问：第 i 块密文的解密不依赖于第 i-1 块密文，提供很高的随机访问能力。
• 可证明的安全性：能够证明 CTR 至少和其他模式一样安全（CBC, CFB, OFB, …）
• 简单性：与其它模式不同，CTR 模式仅要求实现加密算法，但不要求实现解密算法。对于 AES 等加/解密本质上不同的算法来说，这种简化是巨大的。
• 无填充，可以高效地作为流式加密使用。

参考

《武汉大学-密码学》