对称加密之分组加密【四】

1、分组密码概述

分组密码和流密码的区别。

1.分组密码和流密码的概念与区别：

所谓流密码，就是把明文的所有字符作为一个整体，然后一位一位地对明文字符进行加密。如维吉尼亚密码和Vernam密码，都属于流密码。一位明文被一位密钥加密为一位密文是流密码的特点。

分组密码：需要先对明文进行分组，然后**对分组后的明文一组一组地进行加密。它与流密码的区别是，分组密码一次用一个密钥k加密一组明文，而不是一位一位加密。如下图明文分组长度为 n, 密文分组长度为 m, 加密函数 E : V n × K → V m E : V_n \times K \rightarrow V_m E:Vn​×K→Vm​ 。通常取n=m , 密文分组与明文分组相等。若 n < m ，则为有数据扩展的分组密码，若 n>m ，则为有数据压缩的分组密码。

• 分组密码是许多系统安全的一个重要组成部分。可用于构造
  • 伪随机数生成器、流密码、消息认证码(MAC)和哈希 (hash) 函数
  • 消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制 的核心组成部分。

2.理想的分组密码：

（1）分组密码的可逆映射： 一个明文分组一定对应着唯一一个密文分组。反之亦然（否则加解密不互逆）。这样的明文分组与密文分组之间的一一映射称为可逆映射 (称为代换)。而所有可能的明文分组集到对应的密文分组集的映射组成的表称为一个可逆映射表。

（2）分组密码变换的总数: 在长度为 n 的分组中，一个可能的可逆映射表中含有的映射对有 2 n 2^n 2n 个（因为长为n位的明文组可以有 2 n 2^n 2n 种，如2位的明文分组有 00,01,10,11 四种）。而第一种明文（如00）也可以对应其他4种密文（如00,01,10,11），第二种明文（如01）可以对应剩下的3种密文，以此类推，总数为 2 2 ! = 24 2^2 ! = 24 22!=24 种，当长度 n 为位分组，其明密文可逆映射表有 2 n ! 2^n ! 2n! 种。

（3）理想分组密码的密钥：对于一个长度为 n 位的分组，其明文组和密文组对应的映射本身就是加密函数，而加密函数又与密钥相对应。从本质上来说，明文对应的某一特定的密文就是从所有可能映射中决定某一特定映射的密钥。因此，对于一个分组长度为 n 的明文，其密钥长度为 n × 2 n n \times 2^n n×2n。

（4）理想分组密码遇到的困难和改进：因为对于一个理想的分组密码，其密钥长度为 n × 2 n n \times 2^n n×2n 。而分组密码的分组长度还不能太小，否则容易被攻破。但太大时，密钥会非常长：当n=64时， 64 × 2 6 4 ≈ 1 0 21 64 \times 2 ^64 \approx 10^{21} 64×264≈1021 。这造成了密钥共享的困难。考虑到这些困难，Feistel 提出，我们只是需要使用一种不太理想的分组密码，用来逼近理想分组密码即可（实际场景）。

2、SP 网络和 Feistel 密码体制

分组密码设计的两种主要结构类型便是：SP 网络和 Feistel 密码体制。

2.1 SP 网络

在 Shannon 1949 的文章中，介绍了替代( Substitution )-置换( Permutation )网络的思想，即SP网络。这种思想形成了现代密码的基础，SP网络是替代-置换乘积密码的现代形式。

SP网络是基于下列两种最基本的密码运算: 替代( Substitution )、置换( Permutation )

• 代换盒 (S 盒)

在密码设计中，可选 n = r ⋅ n 0 n=r·n_0 n=r⋅n0​，其中 r 和 n 0 n_0 n0​ 都为正整数，将设计 n 个变量的代换网络化为设计 r 个较小的子代换网络，而每个子代换网络只有 n 0 n_0 n0​ 个输入变量。称每个子代换网络为代换盒(Substitution Box)。如下图中 DES 算法中的代换 S 盒。

• S 盒的设计准则
• 迄今为止，有关方面未曾完全公开有关DES的S盒的设计准则。Branstead 等曾披露过下述准则:
  • P1 S盒的输出都不是其输入的线性或仿射函数。
  • P2 改变S盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生 变化。
  • P3 当S盒的任一输入位保持不变，其它5位输入变化时(共有25 =32种情况)， 输出数字中的0和1的总数近于相等。

这三点使DES的S盒能够实现较好的混淆。

2.2 Feistel密码体制

1.分组密码的设计原则： 既然理想分组密码不太实用，那么我们可以从密码设计的本源进行探索，一个足够安全且实用的密码系统具有什么特征？

香农引进了混淆和扩散两个概念。

（1）扩散：

所谓扩散，就是使明文和密文之间的关系尽可能复杂，使明文中原有的统计规律在密文中消失。即无法通过密文来获知有关明文的任何信息。可以通过让明文中的多个位对密文的一位造成影响，从而造成扩散（这也是命名为扩散的原因）。实际中，可以对明文进行置换，然后使用多个函数多次对其作用，就能产生这样的效果。（如下面的 Feistel 密码机制）

（2）混淆

混淆是指使密文和密钥之间的关系尽可能复杂，即无法通过密文来推断出密钥。

扩散和混淆简明扼要地抓住了现代分组密码设计的最核心的本质。

2.乘积密码体制：

所谓乘积密码体制，就是指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果，达到扩散和混淆的效果。Feistel 建议多次使用古典密码中的两个重要方法：代替和置换。这种密码体制本质上密钥长度为 k k k 位，每一种密钥可以产生一个唯一的可逆映射表，因此可以产生的可逆映射表数量为 2 k 2^k 2k ，小于理想分组密码的可逆映射表数 2 n ! 2^n ! 2n! 。这种密码体制是向理想分组密码体制的一种逼近。

3.Feistel密码体制的描述：

一个 Feistel 密码体制包含 16 轮迭代和一次左右置换。如下图所示：

• Feistel 网络分组密码实现的参数

  1、分组大小: 分组越大则安全性越高，但加密速度就越慢。

  2、密钥大小:密钥越长则安全性越高，但加密速度就越慢。

  3轮数:单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。 典型地，轮数取为16。

  4、子密钥产生算法:该算法的复杂性越大，则密码分析的困难性就越大。 5 轮函数:轮函数的复杂性越大，密码分析的困难性也越大。

4、Feistel 加密结构

输入是分组长为 2 w 2w 2w的明文和一个密钥 K K K。将每组明文分成左右两半 L 0 L_0 L0​和 R 0 R_0 R0​，在进行完 n n n轮迭代后，左右两半再合并到一起以产生密文分组。第 i i i 轮迭代的输入为前一轮输出的函数:

{ L i = R i − 1 R i = L i − 1 ⊕ F ( R i − 1 , K i ) \left\{\begin{matrix} L_i = R_{i-1} \\ R_i = L_{i-1} \oplus F(R_{i-1}, K_i) \end{matrix}\right. {Li​=Ri−1​Ri​=Li−1​⊕F(Ri−1​,Ki​)​

• 其中 K i K_i Ki​是第 i 轮用的子密钥，由加密密钥 K 得到。一般地，各轮子密钥彼此不同而且与 K K K也不同, 在其他明确的分组加密算法中，有专门的密钥编排算法用于生成每轮加密秘钥。

5、Feistel解密结构

• Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入
• 但使用子密钥 K i K_i Ki​ 的次序与加密过程相反，即第 1 轮使用 K n K_n Kn​，第2轮使用 K n − 1 ， . . . . . . ， K_{n-1}，......， Kn−1​，......，最后一轮使用 K 1 K_1 K1​。这一特性保证了解密和加密可采用同一算法。

6、Feistel密码解密的正确性

一般地，加密过程中的第 i 轮有
L E i = R E i − 1 R E i = L E i − 1 ⊕ F ( R E i − 1 , K i ) \begin{array}{l} L E_{i}=R E_{i-1} \\ R E_{i}=L E_{i-1} \oplus F\left(R E_{i-1}, K_{i}\right) \end{array} LEi​=REi−1​REi​=LEi−1​⊕F(REi−1​,Ki​)​
因此可得解密过程：
R E i − 1 = L E i L E i − 1 = R E i ⊕ F ( R E i − 1 , K i ) = R E i ⊕ F ( L E i , K i ) \begin{array}{l} R E_{i-1}=L E_{i} \\ L E_{i-1}=R E_{i} \oplus F\left(R E_{i-1}, K_{i}\right)=R E_{i} \oplus F\left(L E_{i}, K_{i}\right) \end{array} REi−1​=LEi​LEi−1​=REi​⊕F(REi−1​,Ki​)=REi​⊕F(LEi​,Ki​)​
注意：这里并没有要求轮函数 F 可逆，轮函数 F 是否可逆不会影响整个轮变换的可逆性。由于每个轮迭代都是可逆的，所以整个 16 轮迭代的输入输出都是可逆的。在解密时，只需将加密得到的密文输入，然后倒着使用加密过程的16轮轮迭代即可。

3、数据加密标准（DES）

DES（Data Encryption Standard）是 1977 年美国国家标准局颁布的信息处理标准，多年来，DES是主流的对称加密算法。但现在DES已经不太安全了。DES主要采用了Feistel加密体制，是一种分组密码加密体制。

DES有两个输入，分别是分组长度为64位的明文，和长度为56位的密钥（实际为64位，剩下的8位可以作为奇偶校验码或随意设置）。

其加密过程如下，首先对64位明文进行初始置换，然后进行16轮的轮迭代（与Feistel密码体制完全相同），最后再进行一次逆初始置换，得到密文。每轮的密钥由一个专门的算法产生。

DES 加密过程简图如下：

• 从上图我们可以看出，DES 算法主要包括两部分：
  • (左边) 迭代加解密 和 (右边) 密钥编排算法

1.初始置换和逆初始置换：

初始置换（Initial Permutation, IP）和逆初始置换（ I P − 1 IP^{-1} IP−1 ）是位于DES开始和结尾的两个置换。输入两个置换表的输入都是64位，输出的结果也是64位，具体置换规则是，将64位输入从1到64编号，然后按照表中的数字，将对应的编号位置上的数据位放到当前的位置上，即完成置换。初始置换表和逆初始置换表是互逆的，即满足 p = I P − 1 ( I P ( p ) ) p = IP^{-1}(IP(p)) p=IP−1(IP(p)) 。关于初始置换和逆置换表在此省略，关于算法细节推荐看后面推荐文章。

2.轮变换（轮迭代）的细节过程：

明文经过初始置换后，就进入了16轮轮迭代的过程。每轮迭代如上图左侧所示。（右侧为轮密钥产生方法）。与前面所讲的Feistel密码体制一样，经过初始置换的64位明文，被分成了左右32位： L i L_i Li​ 和 R i R_i Ri​，然后经历下面的变换：

{ L i = R i − 1 R i = L i − 1 ⊕ F ( R i − 1 , K i ) \left\{\begin{matrix} L_i = R_{i-1} \\ R_i = L_{i-1} \oplus F(R_{i-1}, K_i) \end{matrix}\right. {Li​=Ri−1​Ri​=Li−1​⊕F(Ri−1​,Ki​)​

其中 R R R 为 32 位，参与轮函数 F 的密钥 k 为48位（之后会讲密钥产生方法）。即输入为 （x , y) ，则 DES 的轮函数输出为： ( y , x ⊕ f k ( y ) ) (y, x \oplus f_k(y)) (y,x⊕fk​(y))，它等价于两个对合变换的复合 (对合变换指经过两次变换后，回到初始本身状态信息)：

( x , y ) → ( x ⊕ f ( k , y ) , y ) → ( y , x ⊕ f ( k , y ) ) (x,y) \rightarrow (x \oplus f(k,y),y) \rightarrow (y,x \oplus f(k,y)) (x,y)→(x⊕f(k,y),y)→(y,x⊕f(k,y)) , 外层复合的对合函数为 （ a , b ） →   ( b , a ) （a, b）\rightarrow \ (b, a) （a,b）→ (b,a)

• 无论 f f f 函数如何选取，DES 的轮函数都是一个对合变换。 F ( x , y ) = ( x ⊕ f ( k , y ) ,   y ) F(x, y ) = (x \oplus f(k,y),\ y) F(x,y)=(x⊕f(k,y), y)

• 即 F ( F ( x , y ) ) = F ( x ⊕ f ( k , y ) , y ) = ( ( x ⊕ f ( k , y ) ) ⊕ f ( k , y ) , y ) = ( x , y ) F(F(x, y))=F(x \oplus f(k, y), y)=((x \oplus f(k, y)) \oplus f(k, y), y)=(x, y) F(F(x,y))=F(x⊕f(k,y),y)=((x⊕f(k,y))⊕f(k,y),y)=(x,y)

其中轮函数包含这么几个过程：进入轮函数中的32位的 R i − 1 R_{i-1} Ri−1​ 首先要经过一个扩展置换 E ，被扩展为48位，置换规则与初始置换相同。其后，被扩展出的48位与密钥 $ k_i $ 进行按位异或，得出 48 位的结果。之后，这48位将进入一个代替函数，产生出32位的输出。这个代替函数由8个S盒组成。查表规则如下图所示，每个 S 盒都对应着一个代换表格。

• 8个S盒的代换表格略。经过S盒后，我们获得了32位的输出。最后还需让这32位经过一个置换 P ，再次得到32位的输出。这个32位输出就是整个轮函数的输出。经过整个轮函数后，我们最终得到了32位的输出。整个轮函数总结如下：

3.密钥产生算法，DES密钥编排

DES的密钥实际有64位，在输入密钥后，对其1-64位按顺序编号，

• DES中的子密钥的生成

• DES算法密钥编排中使用的表

• 关于 DES 算法的细节，推荐：DES 算法详细图示

4、多重 DES

• 如果一个分组密码易受到穷举密钥搜索攻击，那么对同一消息加密多次就 有可能增强安全性.

• 多重DES就是使用多个密钥利用DES对明文进行多次加密。使用多重DES可以 增加密钥量，从而大大提高抵抗穷举密钥搜索攻击的能力

• 多重加密类似于一个有着多个相同密码的级联，但各级密码无需独立，且 每级密码既可以是一个分组密码加密函数，也可是相应的解密函数

• 双重DES

简单的对消息xi利用两个不同的密钥进行两次加密，目的是为了抵抗穷搜索攻击，期望密钥长度扩展为112比特。

• 三重DES算法

三重DES中三个密码组件既可以是一个加密函数，也可以是一个 解密函数。当k1=k3时，则称为双密钥三重DES 。

• 破译它的穷举密钥搜索量为 2 112 ≈ 5 × 1 0 35 2^{112} \approx 5 \times 10^{35} 2112≈5×1035 量级
• 差分分析破译也要超过 1 0 52 10^{52} 1052量级
• 此方案仍有足够的安全性

4、分组密码的工作模式

• 因为分组密码加密时分组长度是固定的，而实际中待加密的消息可能是不确定的，数据格式是多种多样的。根据不同的数据格式和安全性要求, 以一个具体的分组密码算法为基础构造一个分组密码系统的方法称为分组密码的工作模式。分组密码的工作模式应当力求简单, 有效和易于实现。
• 需要采用适当的工作模式来隐蔽明文的统计特性、数据的格式等。降低删除、重放、插入和伪造成功的机会。
• 常见的分组密码工作模式有：
  • 电码本(ECB)模式。Electronic Code Book
  • 密码分组链接(CBC)模式
  • 密码反馈(CFB)模式
  • 输出反馈(OFB)模式
  • 计数器模式（Counter, CTR）。推荐 AES 使用此运行模式。
• 电码本 ECB

• 优点：

  • 将长消息分块,若最后一个分块不足分组长度，则需要填充;
  • 加密过程和解密过程分别调用加密算法和 解密算法;
  • 密文块分别独立解密，无顺序要求;各密文块独立传播，不会相互影响; 实现简单;
  • 不同明文分组的加密可并行实施，尤其是硬件实现时速度很快

• 缺点:

  (1)相同明文分组对应相同密文分组

  (2) 不能隐蔽明文分组的统计规律和结构规律,不能抵抗替换攻击

• 应用:

  (1) 用于随机数的加密保护

  (2) 用于单分组明文的加密。一个分组长度的短数据加密。

• 密码分组链接CBC (Cipher Block Chaining)模式

  • 这种模式先将明文分组与上一次的密文块进行按比特异或，然后再进行加 密处理。这种模式必须选择一个初始向量 c 0 = I V c_0= IV c0​=IV，用于加密第一块明文。
  • 加密过程为 c i = E k ( m i ⊕ c i − 1 ) c_i = E_k(m_i \oplus c_{i-1}) ci​=Ek​(mi​⊕ci−1​)
  • 解密过程为 m i = D k ( c i ) ⊕ c i − 1 m_i = D_k(c_i) \oplus c_{i-1} mi​=Dk​(ci​)⊕ci−1​

• CBC模式的特点

  • 明文块的统计特性得到了隐蔽。由于在CBC模式中，各密文块不仅与当前明文块有关，而且还与以前的 明文块及初始化向量有关，从而使明文的统计规律在密文中得到了较好的隐藏。
  • 具有有限的(两步)错误传播特性。一个密文块的错误将导致两个密文块不能正确解密
  • 具有自同步功能。密文出现丢块和错块不影响后续密文块的解密.若从第t块起密文块正确, 则第 t+1个明文块就能正确求出。

• 利用CBC模式实现报文的完整性认证

  • 目的: 检查文件在(直接或加密)传输和存储中是否遭到有意或无意的篡改。
  • 此外，还可以采用 merkel 树的方式校验数据报文的完整性。对于 CBC 模式如何实现完整性认证，感兴趣的朋友可自行搜索学习。

• 密码反馈 CFB(Cipher Feedback)模式

  • 若待加密消息需按字符、字节或比特处理时，可采用CFB模式。 并称待加密消息按 r 比特处理的CFB模式为 r 比特CFB模式。
  • 适用范围:
    • 适用于每次处理 r 比特明文块的特定需求的加密情形,能灵活适应数据各格式的需要。
    • 例如, 数据库加密要求加密时不能改变明文的字节长度,这时就要以明文 字节为单位进行加密。
  • CFB的加密解密示意图：

• CFB 模式的特点

  • 相同明文: 和按CBC模式加密一样，改变 IV 同样会导致相同的明文输入得到不同的加密输出。IV无需保密(虽在某些应用中 IV 须是不可预测的)。
  • 链接依赖性: 类似CBC加密，链接机制致使密文组依赖于当前明文组和其前面的明文组; 因此，重排密文组会影响解密。
  • 错误的传播: 一个或多个比特错误出现在任一个 r 比特的密文组中会影响这个组和后继 ⌈ n / r ⌉ \left \lceil n/r \right \rceil ⌈n/r⌉ 个密文组的解密。
  • 错误恢复: CFB和CBC相似，也是自同步的，但它需有 ⌈ n / r ⌉ \left \lceil n/r \right \rceil ⌈n/r⌉ 个密文组才能还原

• 输出反馈 OFB (Output Feedback)模式

  • OFB 模式在结构上类似于CFB模式，但反馈的内容是DES的输出而不是密文 !

• OFB 工作模式的特点

  • 相同明文: 和CBC及CFB一样，改变IV同样会导致相同的明文输入得到不同的加密输出。
  • 链接依赖性:密钥流是独立于明文的。
  • 错误传播:有一个或多个比特错误的任一密文字符仅会影响该字符 的解密， 密文字符的某比特位置出错将致使还原明文的相应位置 也出错。
  • 错误恢复:OFB模式能从密文比特错误中得以恢复，但在丢失密文 比特后就无法实现自同步了，这是因为丢失密文比特会破坏密钥流的编排。

• 四类工作模式比较和选用： ECB，CBC，CFB，OFB

  • (1)ECB模式简单、高速，但最弱，易受重放和替换攻击， 一般用于加密长度小于等于分组长度的消息。
  • (2) CBC，CFB，OFB模式的选用取决于实际的特殊需求。

    • 1、明文不易丢信号，对明文的格式没有特殊要求的环境可选用CBC模式。需要完整性认证功能时也可选用该模式。

    • 2、容易丢信号的环境，或对明文格式有特殊要求的环境，可选用CFB模式。

    • 3 不易丢信号，但信号特别容易错，且明文冗余特别多，可选用OFB模式。

• 计数器模式 CTR

  • 利用固定密钥 k 对自然数序列 $ 1,2,3,…,n, …$ 加密，将得到的密文分组序列看作密钥流序列，按加法密码的方式与明文分组逐位异或的一种方式。
  • 利用这种方式可以产生伪随机数序列,其伪随机特性远比计算机产生的随机数的性质好。

• CTR的优点

  • 效率
    • 可并行加密
    • 预处理
    • 吞吐量仅受可使用并行数量的限制
  • 加密数据块的随机访问
  • 可证明安全
  • 简单性 (只要求实现加密算法)

5、AES 高级加密标准（Advanced Encryption Standard）

因为 AES 中的相关操作都定义在 G F ( 2 8 ) GF(2^8) GF(28) 有限域上，故在了解学习 AES 之前，先了解一下有限域的相关操作。

1、什么是域

F 是一个非空集合，定义了加法、乘法两个二元运算，对这两个运算封闭

• 加法满足: 对于任意 a , b , c ∈ F a,b,c∈F a,b,c∈Fa

  • +b=b+a; 交换律
  • (a+b)+c=a+(b+c); 结合律
  • 存在 0 ∈ F 0∈F 0∈F，使得 a+0=a; 有零元
  • 存在 − a ∈ F -a∈F −a∈F，使得 a+(-a)=0; 有负元

• 乘法满足:对于任意 a , b , c ∈ F a,b,c∈F a,b,c∈Fa

  • ·b=b·a;交换律
  • (a·b)·c=a·(b·c);结合律
  • 存在$ e∈F $，使得 a·e=a ;有单位元
  • 存在 a − 1 ∈ F a-1∈F a−1∈F，使得 a ⋅ a − 1 = e ; a·a^{-1}=e; a⋅a−1=e; 有逆元。不一定每个元素都有逆元。

• 乘法对加法满足分配率

  • a ⋅ ( b + c ) = a ⋅ b + a ⋅ c a·(b+c)=a·b+a·c a⋅(b+c)=a⋅b+a⋅c

2、域的例子

1、数域

• Z n = 0 , 1 , 2 , . . . ， n − 1   m o d   n Z_n= {0,1,2,...，n-1}\ mod\ n Zn​=0,1,2,...，n−1 mod n，加法和乘法都是模 n 的运算，运算封闭
  • 加法满足结合律和交换律，有零元0，有负元
  • 乘法满足结合律和交换律，有单位元 1，不一定有逆元.
  • Z n Z_n Zn​中的数什么时候才有乘法逆元呢?
• 引理: 整数 a 在模 n 乘法下有逆元，当且仅当a与n互素。
• 所有与 n 互素的元素在模 n 乘法下构成乘法交换群。
  • 1…n-1都与n互素，则n为素数
  • 对于任一素数 p ， Z p p，Z_p p，Zp​为域，其元素个数为 p 个

2、多项式

• F(x) 是域上的多项式环，f(x) 是一个 n 次多项式。定义 F[x] 商去 f(x) 的理想: F [ x ] / ( f ( x ) ) = { r ( x ) = r n − 1 x n − 1 + r n − 2 x n − 2 + . . . + r 1 x + r 0 ∣ r i ∈ F , 0 ≤ i ≤ n − 1 } F[x]/(f(x))=\left\{r(x)=r_{n-1}x^{n-1}+r_{n-2}x^{n-2}+...+r_1x+r_0|r_i \in F, 0≤i≤n-1 \right\} F[x]/(f(x))={r(x)=rn−1​xn−1+rn−2​xn−2+...+r1​x+r0​∣ri​∈F,0≤i≤n−1}，加法和乘法都是 模f(x)的运算，运算封闭。
  • 加法满足结合律和交换律，有零元0，有负元
  • 乘法满足结合律和交换律，有单位元 1，不一定有逆元
  • F [ x ] / ( f ( x ) ) F[x]/(f(x)) F[x]/(f(x)) 中的多项式什么时候才有乘法逆元呢? 类似数域的情况。我们有下列引理。
• 引理: r(x) 在模 f(x) 乘法下有逆元，当且仅当 r(x) 与 f(x) 互素。
  • 所有与f(x)互素的元素在模f(x)乘法下构成乘法交换群
  • 次数比f(x)的次数低的多项式都与f(x)互素，则f(x)为不可约多项式
  • 对于任一首项系数为 1 的不可约多项式， F [ x ] / ( f ( x ) ) F[x]/(f(x)) F[x]/(f(x))为域
  • 若 F = Z p F=Z_p F=Zp​，则 F [ x ] / ( f ( x ) ) F[x]/(f(x)) F[x]/(f(x))中元素个数为 p n p^n pn个
• 于是我们可以总结得出：
  • p n p^n pn 域的构造方法: 首先选取 Z p Z_p Zp​中的一个 n 次不可约多项式，然后构造集合 F [ x ] / ( f ( x ) ) = { r ( x ) = r n − 1 x n − 1 + r n − 2 x n − 2 + . . . + r 1 x + r 0 ∣ r i ∈ F , 0 ≤ i ≤ n − 1 } F[x]/(f(x))=\left\{r(x)=r_{n-1}x^{n-1}+r_{n-2}x^{n-2}+...+r_1x+r_0|r_i \in F, 0≤i≤n-1 \right\} F[x]/(f(x))={r(x)=rn−1​xn−1+rn−2​xn−2+...+r1​x+r0​∣ri​∈F,0≤i≤n−1} 集合中的加法和乘法运算为模多项式 f(x) 的运算。

3、AES 中的处理单元表示以及运算

• AES 加密标准算法中是以字节为处理单元。AES 中的字节表示方法：可以将每一字节看作是有限域 G F ( 2 8 ) GF(2^8) GF(28) 上的一个元素，分别对应于一个次数不超过 7 的多项式。如 b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 b_7b_6b_5b_4b_3b_2b_1b_0 b7​b6​b5​b4​b3​b2​b1​b0​ 可表示为多项式 b 7 x 7 + b 6 x 6 + b 5 x 5 + b 4 x 4 + b 3 x 3 + b 2 x 2 + b 1 x 1 + b 0 b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0 b7​x7+b6​x6+b5​x5+b4​x4+b3​x3+b2​x2+b1​x1+b0​ ，还可以将每个字节表示为一个十六进制数，即每 4 比特表示为一个十六进制 数，代表较高位的4比特的符号仍在左边。例如，01101011 可表示为 6B

• 它们之间的运算为$GF(2^8) $中的运算.

• 在定义了 AES 中字节的表示方法后，我们来定义在 G F ( 2 8 ) GF(2^8) GF(28) 中的运算。

  • 定义: 在 G F ( 2 8 ) GF(2^8) GF(28) 上的加法定义为二进制多项式的加法，且其系数模 2, 使其系数在 {0, 1} 之间。
  • 定义: 在 G F ( 2 8 ) GF(2^8) GF(28) 上的乘法(用符号·表示)定义为二进制多项式的乘积模一个次数为8 的不可约二进制多项式。 m ( x ) = x 8 + x 4 + x 3 + x + 1 m(x)= x^8+x^4+x^3+x+1 m(x)=x8+x4+x3+x+1 , 它的十六进制表示为‘11B’。

• G F ( 2 8 ) GF(2^8) GF(28) 中的逆元和 x 乘法

  • 定义: 对任何次数小于 8 的多项式 b(x)，可用推广的欧几里得算法得 b ( x ) a ( x ) + m ( x ) c ( x ) = 1 b(x)a(x)+m(x)c(x)=1 b(x)a(x)+m(x)c(x)=1

    即 a ( x ) ⋅ b ( x ) = 1 m o d m ( x ) a(x)·b(x)=1 mod m(x) a(x)⋅b(x)=1modm(x)。因此 a(x) 是 b(x) 的乘法逆元。

• 定义: 函数 x t i m e ( x ) xtime(x) xtime(x) 定义为 G F ( 2 ) GF(2) GF(2) 上的 x ⋅ b ( x ) x·b(x) x⋅b(x)。其运算如下: 若 b 7 = 0 b_7 =0 b7​=0，则 x ⋅ b ( x ) x·b(x) x⋅b(x) 的结果就是把字节 b 左移一位，且在最右边补上上0; 若b7 =1，则先对 b(x) 在字节内左移一位(最后一位补0)，则再与 ‘ 1 B ’ ( 00011011 ) ‘1B’(00011011) ‘1B’(00011011) 做逐比 特异或。

• 定义 xtime 函数的原因就是它比多项式乘法更加高效，是 G F ( 2 8 ) GF(2^8) GF(28) 上的快速乘法。

• x t i m e ( x ) xtime(x) xtime(x) 例子

  • 例如，‘57’·‘13’可按如下方式实现:
  • ‘57’·‘02’=xtime(57)=‘AE’;
  • ‘57’·‘04’=xtime(AE)=‘47’;
  • ‘57’·‘08’=xtime(47)=‘8E’;
  • ‘57’·‘10’=xtime(8E)=‘07’;
  • ‘57’·‘13’=‘57’·(‘01’ ⊕ \oplus ⊕‘02’ ⊕ \oplus ⊕ ‘10’)=‘57’ ⊕ \oplus ⊕‘AE’ ⊕ \oplus ⊕ ‘07’=‘FE’

• G F ( 2 8 ) GF(2^8) GF(28) 上的模多项式运算

  • 4 个字节构成的向量可以表示为系数在 G F ( 2 8 ) GF(2^8) GF(28)上的次数小于 4 的多项式。
  • 多项式的加法就是对应系数相加;换句话说，多项式的加法就是4字节向量的逐比特异或。
  • 规定多项式的乘法运算必须要取模 M ( x ) = x 4 + 1 M(x)=x^4+1 M(x)=x4+1，这样使得次数小于 4 的多项式的。乘积仍然是一个次数小于 4 的多项式，将多项式的模乘运算记为 ⊗ \otimes ⊗，设 a ( x ) = a 3 x 3 + a 2 x 2 + a 1 x + a 0 ， b ( x ) = b 3 x 3 + b 2 x 2 + b 1 x + b 0 ， c ( x ) = a ( x ) ⊗ b ( x ) = c 3 x 3 + c 2 x 2 + c 1 x + c 0 a(x)= a_3x^3+a_2x^2+a_1x+a_0，b(x)= b_3x^3+b_2x^2+b_1x+b_0，c(x)= a(x) \otimes b(x)=c_3x^3+c_2x^2+c_1x+c_0 a(x)=a3​x3+a2​x2+a1​x+a0​，b(x)=b3​x3+b2​x2+b1​x+b0​，c(x)=a(x)⊗b(x)=c3​x3+c2​x2+c1​x+c0​。由于 x j m o d ( x 4 + 1 ) = x j   m o d   4 x^j mod (x^4+1)= x ^{j\ mod\ 4} xjmod(x4+1)=xj mod 4，所以

• 模 x 4 + 1 x^4+1 x4+1逆元
• 定理: 系数在 G F ( 2 8 ) GF(2^8) GF(28)上的多项式 a 3 x 3 + a 2 x 2 + a 1 x + a 0 a_3x^3+a_2x^2+a_1x+a_0 a3​x3+a2​x2+a1​x+a0​是模 x 4 + 1 x^4+1 x4+1可逆的，当且仅当上述循环矩阵在 G F ( 2 8 ) GF(2^8) GF(28) 上可逆。

4、AES 提出的背景及其框架参数说明

1、AES 提出的背景

• DES算法由于其密钥较短，难以抵抗现有的攻击，因此不再作为加密标准，1997年1月，美国NIST向全世界密码学界发出征集21世纪高级 加密标准(AES——Advanced Encryption Standard) 算法。初选了 15 个方案，都比 3-DES 的算法强度强，实现速度也快于 3-DES。最终 2000年10月2日，NIST宣布 Rijndael （J. Daemen,比利时）作为新的 AES 。
• AES算法征集的要求
  • AES是公开的;
  • AES为对称密钥分组密码体制;
  • AES的密钥长度可变，可按需要增大;
  • AES适于用软件和硬件实现;
  • AES可以自由地使用，或按符合美国国家标准(ANST)策 略的条件使用。

2、AES 框架参数及其说明简述

• AES算法设计思想
  • 设计简单，在多个平台上速度快，编码紧凑
  • 抵抗所有已知的攻击
  • Rijndael 没有采用 Feistel 结构，轮函数由 3 个不同的可逆均匀变换构成的，称为3个层。均匀变换是指状态的每个 bit 都用类似的方法处理。
• 轮函数的3层
  • 线性混合层: 确保多轮之上的高度扩散;
  • 非线性层: 将具有最优的“最坏情况非线性特性”的 S 盒并行使用;
  • 密钥加层: 单轮子密钥简单的异或到中间状态上，实现一次性掩盖。
• 算法简要说明
  • 明文分组可变，128、192、256比特。
  • 密钥长度可变，各自可独立指定为128、192、256比特。
  • 状态：算法中间的结果也需要分组，称之为状态，状态可以用以字节为元素的矩阵阵列表示，该阵列有 4 行，列数 N b N_b Nb​ 为分组长度除 32
  • 种子密钥: 以字节为元素的矩阵阵列描述，阵列为 4 行，列数 N 为密钥长度除 32
  • 算法的输入、输出和种子密钥可看成字节组成的一维数组。下标范围
    • 输入输出: 0 ∼ 4 N b − 1 0 \sim 4N_b-1 0∼4Nb​−1
    • 种子密钥: 0 ∼ 4 N b − 1 0 \sim 4N_b -1 0∼4Nb​−1
  • 由于输入是一位数组，故需要将输入和秘钥分组都进行重新放置排列。如下是 N b = 6 N_b=6 Nb​=6 和 N k = 4 N_k=4 Nk​=4 的状态密钥阵列。

• 分组和阵列中元素对应关系、以及轮函数索引关系
  • 分组下标 n
  • 阵列位置 (i, j)
    • i = n   m o d   4 , j = [ n / 4 ] ;   n = i + 4 j i=n\ mod\ 4, j=[n/4];\ n=i+4j i=n mod 4,j=[n/4]; n=i+4j
    • 轮数 N r N_r Nr​与 N b N_b Nb​和 N k N_k Nk​对应关系如下：如当列数 N b = 4 N_b = 4 Nb​=4 及分组长度 32 * 4 = 128 位，秘钥长度也为 128 位时，其轮函数执行 10 轮。

• 如下是秘钥长度和数据分组都为 128 位时的 AES 加密过程流程图示：注意最后一轮为了加密使用同一套算法，最后一轮函数少了列混淆步骤。

3、 AES 的轮函数

• AES 轮函数主要包括四个过程：字节代换、行移位、列混淆、轮密钥加

字节代换

• 非线性代换，独立地对状态的每个字节进行，并且代换表(S盒) 可逆，记为ByteSub(State),分两步

  • (1) 将字节作为 G F ( 2 8 ) GF(2^8) GF(28)上的元素映射到自己的逆元
  • (2) 将字节做 G F ( 2 ) GF(2) GF(2)上的仿射变换。即 y = A x − 1 + B y = Ax^{-1} +B y=Ax−1+B ，其中A是一个GF(2)上 8☓8的可逆矩阵，B 是 GF(2) 上一个 8 位列向量
  • 字节代换相当于做了如下这样的矩阵变换。是非线性的 S 替换盒。

• AES 也给出了 S 盒的替换表，有了它就不用在自己去进行矩阵计算了，可以直接查表，其结果是等价的。例如：如下例子，输入 8a, 输出 7e, 即 7 e = S ( 8 a ) 7e = S(8a) 7e=S(8a)

• 逆字节代换 InvSubBytes( )
  • 逆字节替代变换是字节替代变换的逆变换，在状态的每个字节上 应用逆S盒
  • 这是通过应用字节替代变换中的仿射变换的逆变换，再对所得结果应用有限域的乘法逆运算得到的。即 $ y = A^{-1}(x - B) $ 其逆 S 盒表，略 (可自行搜索查看)
  • 上述 S-盒 对状态的所有字节所做的变换记为 ByteSub (State)

行移位

• 将状态阵列的各行进行循环移位，不同行的移位量不同
• 0行: 不动，1行:循环左移 C1字节， 2行: 循环左移 C2 字节，3行: 循环左移C3字节
• 记为:ShiftRow(State) ，表格如下：
• 逆行移位变换是行移位变换的逆变换，即右移相应字节即可。

列混淆

• 将每列视为 G F ( 2 8 ) GF(2^8) GF(28)上多项式，与固定的多项式 c ( x ) c(x) c(x) 进行模 x 4 + 1 x^4+1 x4+1 乘法，记为 ⊗ \otimes ⊗, 要求 c(x) 模 x 4 + 1 x^4+1 x4+1 可逆。
• 表示为 MixColumn(State), 其运算表达式如下所示：

• 逆列混淆 InvMixColumns()
  • 逆列混淆变换是列混淆变换的逆
  • 它将状态矩阵中的每一列视为系数在 上的次数小于 4 的 G F ( 2 8 ) GF(2^8) GF(28) 多项式与同一个固定的多项式 d ( x ) d(x) d(x) 相乘。 d ( x ) d(x) d(x) 满足: ( ‘ 03 ’ x 3 + ‘ 01 ’ x 2 + ‘ 01 ’ x + ‘ 02 ’ ) ⊗ d ( x ) = ‘ 01 ’ (‘03’x^3+‘01’x^2+‘01’x+‘02’) \otimes d(x)=‘01’ (‘03’x3+‘01’x2+‘01’x+‘02’)⊗d(x)=‘01’ 由此可得： d ( x ) = ‘ 0 B ’ x 3 + ‘ 0 D ’ x 2 + ‘ 09 ’ x + ‘ 0 E ’ d(x)=‘0B’x^3+‘0D’x^2+‘09’x+‘0E’ d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’
  • 同样，逆列混淆可以写成矩阵乘法形式。

轮密钥加

• 轮密钥与状态进行逐比特异或。
• 轮密钥由种子密钥通过密钥编排算法得到
• 轮密钥长度与分组长度相同
• 表示为 AddRoundKey(State,RoundKey)

4、AES的密钥编排及伪代码

秘钥编排

• 密钥编排指从种子密钥得到轮密钥的过程，它由密钥扩展和轮密钥选取两部分组成。其基本原则如下:
  • (1) 轮密钥的比特数等于分组长度乘以轮数加1; 例如要将128 比特的明文经过10轮的加密，则总共需要 ( 10 + 1 ) ∗ 128 = 1408 (10+1)*128=1408 (10+1)∗128=1408 比特的密钥。
  • (2) 种子密钥被扩展成为扩展密钥;
  • (3) 轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前 N b N_b Nb​个字，第 2 轮轮密钥取接下来的 N b N_b Nb​个字，如此下去。

秘钥扩展

• 扩展密钥是以 4 字节字为元素的一维阵列，表示为 W [ N b ∗ ( N r + 1 ) ] W[Nb* (N_r+1)] W[Nb∗(Nr​+1)]，其中前 N k N_k Nk​个字取为种子密钥，以后每个字按递归方式定义。扩展算法根据 N k ≤ 6 N_k≤6 Nk​≤6和 N k > 6 N_k>6 Nk​>6有所不同。

• 当 （ N k > 6 ） （N_k > 6） （Nk​>6） 时的秘钥扩展算法

轮常数

•以上两个算法中， R c o n [ i / N k ] Rcon[i/Nk] Rcon[i/Nk] 为轮常数，其值与Nk无关，定义 为(字节用十六进制表示，同时理解为 G F ( 2 8 ) GF(2^8) GF(28)上的元素):

R c o n [ i ] = ( R C [ i ] , ‘ 00 ’ , ‘ 00 ’ , ‘ 00 ’ ) Rcon [i]=(RC[i], ‘00’, ‘00’, ‘00’) Rcon[i]=(RC[i],‘00’,‘00’,‘00’) 其中 R C [ i ] RC[i] RC[i] 是 G F ( 2 8 ) GF(2^8) GF(28) 中值为$x^{i-1} 的元素，因此

R C [ 1 ] = 1 ( 即 ‘ 01 ’ ) 、 R C [ i ] = x ( 即 ‘ 02 ’ ) ⋅ R C [ i − 1 ] = x i − 1 RC[1] =1(即‘01’)、 RC[i] = x(即‘02’)·RC[i-1]= x^{i-1} RC[1]=1(即‘01’)、RC[i]=x(即‘02’)⋅RC[i−1]=xi−1

轮密钥选取

轮密钥i (即第i 个轮密钥) 由轮密钥缓冲字 W[Nb* i] 到 W[Nb*(i+1)]给出，如图所示，更详细的不走可参见 here

• AES加密过程的伪代码

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*Nr+1]) 
  begin
      byte state[4,Nb]
      state = in
      AddRoundKey(state, w[0, Nb-1]) 
      for round = 1 step 1 to Nr-1
          SubBytes(state) 
          ShiftRows(state) 
          MixColumns(state)
          AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) 
      end for
      SubBytes(state)
      ShiftRows(state)
      AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) 
      Out = state
  end

• AES解密过程的伪代码

InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*Nr+1]) 
  	begin
        byte state[4,Nb]
        state = in
        AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) 
  			for round = Nr-1 step -1 downto 1
            InvShiftRows(state) 
            InvSubBytes(state)
            AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) 	                     InvMixColumns(state)
        end for
        SubBytes(state)
        ShiftRows(state) 
         AddRoundKey(state, w[0, Nb-1]) 
         Out = state
  	end

• AES 密钥编排算法的伪代码

KeyExpansion (byte key[4*Nk] , word w[Nb*(Nr+1)], Nk) 
  begin
      word temp i=0
      while (i<Nk)
        w[i]=word(Key[4* i], Key[4* i +1], Key[4* i +2], Key[4* i +3] )
        i=i+1 
      end while
      i=Nk 
      while(i<Nb*(Nr+1))
          temp=W[i-1]
          if (I mod Nk= =0)
          		temp=SubByte (RotByte (temp)) xor Rcon[i /Nk] 
          else if (Nk>6 and i mod Nk = 4)
          		temp=SubWord(temp) 
          end if
          		w[i]=w[i-Nk ] xor temp 
      end while
  end

4、SM4 (商密)

SM4概况

• SM4 分组密码算法是国家密码管理局于 2006年1月6日公布的无线局域网产品使用的密码算法，是国内官方公布的第一个商用密码算法。
• SM4 是一个分组密码算法，分组长度和密钥长度均为 128 比特。加密算法与密钥扩展算法都采用32轮非线性迭代结构。
• 它的解密算法与加密算法的结构相同，只是轮密钥的使用顺序相反，解密 轮密钥是加密轮密钥的逆序。

SM4 算法的术语说明

• Z 2 e Z_2^e Z2e​ 表示 e-比特的向量集， Z 2 8 Z_2^8 Z28​ 中的元素称为字节， Z 2 32 Z_2^{32} Z232​ 中的元素为字

• S 盒是一个固定的 8 比特输入 8 比特输出的置换，记为Sbox(.)

• SM4 中的采用了两个基本运算: ⊕ \oplus ⊕，32 比特异或; < < < i <<< i <<<i，32 比特循环左移 i 位。

• SM4 算法的加密密钥长度为 128 比特，表示为 M K = ( M K 0 , M K 1 , M K 2 , M K 3 ) MK = (MK_0, MK_1, MK_2, MK_3) MK=(MK0​,MK1​,MK2​,MK3​)

  其中， M K i   i = 0 , 1 , 2 , 3 MK_i\ i= 0,1,2,3 MKi​ i=0,1,2,3 为字。

  • 轮密钥为 ( r k 0 , r k 1 , ⋅ ⋅ ⋅ , r k 31 ) , r k i (rk_0,rk_1,···,rk_{31}), rk_i (rk0​,rk1​,⋅⋅⋅,rk31​),rki​ 为字。轮密钥由加密密钥通过密钥扩展算法生成。

  • F K = ( F K 0 , F K 1 , F K 2 , F K 3 ) FK = (FK_0,FK_1,FK_2,FK_3) FK=(FK0​,FK1​,FK2​,FK3​)为系统参数，

  • C K = ( C K 0 , C K 1 , ⋅ ⋅ ⋅ , C K 31 ) CK = (CK_0 ,CK_1, ··· , CK_{31}) CK=(CK0​,CK1​,⋅⋅⋅,CK31​) 为固定参数，用于密钥扩展算法。

SM4 加密算法整体结构

SM4 的轮函数

• 设输入为 ( X i , X i + 1 , X i + 2 , X i + 3 ) / i n ( Z 2 32 ) 4 (X_i ,X_{i+1}, X_{i+2}, X_{i+3} ) /in (Z_2^{32})^4 (Xi​,Xi+1​,Xi+2​,Xi+3​)/in(Z232​)4 ，轮密钥为 r k i ∈ Z 2 32 rk_i \in Z_2^{32} rki​∈Z232​，则轮函数为:

X i + 4 = F ( X i , X i + 1 , X i + 2 , X i + 3 , r k i ) = X i ⊕ T ( X i + 1 ⊕ X i + 2 ⊕ X i + 3 ⊕ r k i ) , i = 0 , 1 , ⋯   , 31 X_{i+4}=F\left(X_{i}, X_{i+1}, X_{i+2}, X_{i+3}, r k_{i}\right)=X_{i} \oplus T\left(X_{i+1} \oplus X_{i+2} \oplus X_{i+3} \oplus r k_{i}\right), \quad i=0,1, \cdots, 31 Xi+4​=F(Xi​,Xi+1​,Xi+2​,Xi+3​,rki​)=Xi​⊕T(Xi+1​⊕Xi+2​⊕Xi+3​⊕rki​),i=0,1,⋯,31

其中 T : Z 2 32 → Z 2 32 T : Z_2^{32} \rightarrow Z_2^{32} T:Z232​→Z232​ 称为合成置换，是一个由非线性变换和一个线性变换复合而成的可逆变换，即 T ( . ) = L ( τ ( . ) ) T (.) = L(\tau (.)) T(.)=L(τ(.))

• SM4 的S盒与 AES 类似，在此不列举了。
• SM4的S盒说明
  • 非线性变换τ中所使用的S盒是一个具有很好密码学特性的、由 8 比特输入产生 8 比特输出的置换。
  • 在设计原理上，SMS4比AES的S盒设计多了一个仿射变换
    • 即 y = A ( A x + B ) − 1 + B y = A(Ax + B)^{-1} + B y=A(Ax+B)−1+B
  • SMS4 有很高的灵活性，所采用的S盒可以灵活地被替换，以应对突发性的安 全威胁。算法的32轮迭代采用串行处理，这与AES中每轮使用代换和混淆并 行地处理整个分组有很大不同。

如下是 SM4 的加密算法和解密算法以及秘钥扩展算法示意图