隐私计算与密码学应用实践最新章节_成方金融科技有限公司著

2.2 分组密码

分组密码（Block Cipher，简写为BC）指的是，将待加密的明文消息划分为 n 个等长的组，每组明文消息片段分别在密钥的作用下映射为等长的一组密文序列。许多隐私计算相关密码原语与协议都可以基于分组密码构建。例如，隐私计算服务需求方使用分组密码构建不经意伪随机函数（Oblivious Pseudo Random Function，简写为OPRF），进而实现隐私集合求交（Private Set Intersection，简写为PSI）。本节首先介绍分组密码的定义和属性，然后给出分组密码的两个常用算法，即国际常用分组密码的高级加密标准（Advanced Encryption Standard，简写为AES） ^［52-53］和中国自主设计的分组密码标准SM4。

2.2.1 定义与属性

分组密码是一个确定性的加密体制，可以记为 ε =（Enc，Dec）。其中，Enc表示加密置换，Dec表示解密置换，Dec是Enc的逆置换。 ε 的消息空间和密文空间同为有限集合 X 。如果 ε 的密钥空间是 K ，则称 ε 是一个定义在（ K ， X ）上的分组密码，称元素 x ∈ X 为数据块， X 为数据块空间。对于每一个固定密钥 k ∈ K ，可以定义函数 f k ：=Enc（ k ，·），即使用 f k ：= X X ，将 x ∈ X 映射到Enc（ k ， x ）∈ X 。一个正确的 ε 意味着，每个固定的密钥 k 与函数 f k 是一一对应的，由于 X 是有限的， f k 也必须是有限的。因此， f k 是 X 上的一个置换，而Dec（ k ，·）是其逆置换。下面介绍两个常用的分组密码——AES算法和SM4算法。

2.2.2 AES算法

1997年，美国国家标准与技术研究院（National Institute of Standards and Technology，简写为NIST）提出了一项新的分组密码标准建议，即高级加密标准（Advanced Encryption Standard，简写为AES）。AES必须在128比特（bit，位）分组上操作，并支持3种密钥大小：128比特、192比特和256比特。1997年9月，NIST收到了15项提案，其中许多是由非美国国籍的候选人提出的。在举行了两次公开会议来讨论这些提案后，NIST于1999年将名单缩小到5名候选人。在接下来的一轮激烈讨论中，与各自密码标准的优劣相关的议题被广泛探讨。这场讨论在2000年4月的AES3会议上达到了高潮，最后5个团队的代表都进行了演讲，阐述为何他们的标准应该成为AES的选择。2000年10月，NIST宣布，比利时学者提出的Rijndael分组密码被选为AES。AES在2001年11月成为官方标准，并在FIPS 197中发布，成为为期五年的标准化DES替代程序。Rijndael ^［54］是由比利时密码学家Joan Daemen和Vincent Rijmen设计的。不过，AES与原始的Rijndael密码略有不同。例如，Rijndael支持大小为128比特、192比特或256比特的分组，而AES只支持128比特的分组。

AES是一个迭代密码，它会多次迭代一个简单的循环密码。迭代的次数取决于密钥的大小：例如，AES-128分组密码示意图如图2-5所示。 f AES 是在｛0，1｝ ¹²⁸ 上的一个固定的置换（一个一对一的函数），它不依赖于密钥。然后用 f AES 的输出与当前轮密钥进行异或操作。以上过程重复9次，直到最后一轮执行置换。AES算法的逆迭代能够通过反向运行整个结构来实现。

遵循图2-5所示结构的密码被称为交替密钥密码（Alternating Key Cipher），其也被称为迭代的Even-Mansour密码。在每一轮中关于置换 f AES 的某些“理想”假设下，这种密码可以被证明是安全的。为了简化对AES的了解，只需描述置换 f AES 和AES密钥扩展伪随机生成器（Pseudorandom Generator，简写为PRG）。

图2-5 AES-128分组密码示意图

1.AES轮置换

置换 f AES 由集合｛0，1｝ ¹²⁸ 上的3个可逆操作序列组成。输入的128比特被组织成一个4×4的单元阵列，其中每个单元为8比特。然后，在这个4×4阵列上，依次执行以下3个可逆操作。

1）字节替换（ByteSub）

定义 S ：｛0，1｝ ⁸ ｛0，1｝ ⁸ 是一个固定置换。如图2-6所示， S 作用于16个单元中的每一个。 S 在AES标准中被指定为一个包含256个条目的编码表。对于 x ∈｛0，1｝ ⁸ ，要求 S （ x ）≠ x ，且 S （ x ）≠ ，其中表示 x 的按位补码。

图2-6 字节替换函数 S （ x ）

2）行移位（ShiftRow）

此步骤执行循环移动的4行：如图2-7所示，第1行不变，第2行循环左移1字节，第3行循环左移2字节，第4行循环左移3字节。

图2-7 行移位（ShiftRow）

3）列混合（MixColumn）

如图2-8中的列混合（MixColumn）所示，在这一步中，4×4阵列被视为一个矩阵，此矩阵乘以一个固定的矩阵，乘法算术发生在有限域GF（2 ⁸ ）内。GF（2 ⁸ ）中的元素表示系数为0或1，且幂小于8的多项式。其中，乘法模数为不可约多项式 x ⁸ + x ⁴ + x ³ + x +1（其中，GF（2 ⁸ ）表示伽罗瓦域，即有限集合｛0，1，2，…，255｝）。该集合中的每个元素都对应一个多项式，即GF（2 ⁸ ），可以表示成256个多项式。不可约多项式指的是无法找到两个多项式相乘来得到本多项式。多项式的介绍将在2.5.1节中给出）。

图2-8 列混合（MixColumn）

在这里，标量01、02、03使用GF（2 ⁸ ）中的元素进行表示（例如，03表示GF（2 ⁸ ）中的元素 x +1）。这个固定矩阵在GF（2 ⁸ ）上是可逆的，因此整个转换都是可逆的。

2.AES-128密钥扩展方法

回顾图2-5，我们可以看到AES-128的密钥扩展需要生成11个轮密钥 k 0 ，…， k 10 。其中，每个轮密钥是128比特。为此，128比特的AES密钥被划分为4个32比特的字 w 0，0 ， w 0，1 ， w 0，2 ， w 0，3 （在计算机中，字是用来一次性处理事务的一个固定长度的比特组），这些字形成了第1个轮密钥 k 0 ，剩下的10个轮密钥按顺序生成： k i -1 =（ w i -1，0 ， w i -1，1 ， w i -1，2 ， w i -1，3 ），其中

这里的函数 g i ：｛0，1｝ ³² ｛0，1｝ ³² 是AES标准中指定的一个固定函数。在此分3个步骤对它的4个字节输入进行操作。

步骤1：对4字节输入循环左移一个字节，例如，假设“abcd”每个字母分别代表一个字节，则循环左移一个字节后为“bcda”。

步骤2：对获得的4个字节中的每个字节应用字节替换中的 S 函数。

步骤3：用固定的轮常数 c i 异或最左边的字节。轮常数 c 1 ，…， c 10 在AES标准中指定。通常，轮常数是域（GF（2 ⁸ ））中的一个长度为8比特的元素。

AES-192和AES-256的密钥扩展程序与AES-128相似。对于AES-192，每次迭代以类似于AES-128的方式生成6个32比特字（共192比特），但只有前4个32比特字（共128比特）被用作AES轮密钥。对于AES-256，每次迭代以类似于AES-128的方式生成8个32比特字（共256比特），但只有前4个32比特字（共128比特）被用作AES轮密钥。AES密钥扩展方法被有意设计为可逆的：给定最后1个轮密钥，可以反向恢复完整的AES密钥。这样做的原因是，为了确保每个AES-128轮密钥本身与AES-128秘密密钥具有相同的熵量（信息熵是信息论中用于度量信息量的一个概念。一个系统越有序，信息熵就越低 ^［55-56］）。如果AES-128密钥扩展不可逆，那么在GF（2 ⁸ ）中，最后1个轮密钥将不一致。

可逆性确实为攻击者提供了更多的机会来尝试攻击加密算法。例如，在相关密钥攻击中，攻击者可以通过观察加密和解密过程中的密钥变化来推断出密钥的值。在对AES的侧信道攻击中，攻击者可以通过观察加密操作的功耗、电磁辐射等侧信道信息来推断出密钥的值。因此，在设计加密算法时，需要考虑可逆性带来的安全风险，并采取相应的措施来对抗攻击。

2.2.3 SM4算法

SM4算法是我国颁布的商用密码标准算法之一，它是一个迭代的分组密码算法。该算法最初为配合无线局域网标准的推广应用而设计，于2006年公开发布，并于2012年3月发布为密码行业标准，2016年8月转化为国家标准。

如图2-9所示，SM4具有以下特点 ^［57-58］：

· 分组长度和密钥长度同为128比特。

· 密钥扩展和加密具有32轮迭代结构，其中迭代结构是非线性的。

· 加密的处理单位为字（32比特串）。

· 解密算法和加密算法具有相同的结构，区别在于二者的轮密钥使用顺序相反。

图2-9 SM4流程框架

1.密钥扩展

在加密算法执行之前，需要将128比特密钥 k 扩展为32个轮密钥｛rk 0 ，…，rk 31 ｝。具体过程如下。

步骤1：首先将密钥 k 划分为4个密钥块（ k 0 ， k 1 ， k 2 ， k 3 ），选择系统参数（fk 0 ，fk 1 ，fk 2 ，fk 3 ）和固定参数（ck 0 ，…，ck 30 ，ck 31 ）。其中，fk与ck的取值如表2-2和表2-3所示。

表2-2 系统参数fk的取值

表2-3 固定参数ck的取值

续表

步骤2：计算（tk 0 ，tk 1 ，tk 2 ，tk 3 ）（ k 0 ， k 1 ， k 2 ， k 3 ）⊕（fk 0 ，fk 1 ，fk 2 ，fk 3 ）。

步骤3：执行第1轮迭代复合计算，输入（tk 0 ，tk 1 ，tk 2 ，tk 3 ，ck 0 ），输出rk 0 。首先计算得到 I 0 =tk 1 ⊕tk 2 ⊕tk 3 ⊕ck 0 ，然后计算 τ （ I 0 ），最后计算rk 0 =tk 4 =tk 0 ⊕ L '（ τ （ I 0 ））。其中， τ （·）表示一个可逆非线性转换函数，输入4个8比特串的异或值，经过4个并行的 S 盒（如表2-4所示）置换，得到新的4个32比特串。 L '（·）表示一个可逆线性转换函数，假设输入为32比特串 I ，则 L '（ I ）= I ⊕（ I ＜＜13）⊕（ I ＜＜23）， I ＜＜ i 表示 I 循环左移 i 比特。