密码学原理技术-第四章-The Advanced Encryption Standard (AES)

基础信息

预览

轮数和选择的key长度有关

AES具体实现

伽罗瓦域（Galois Fields，简称 GF

Byte Substitution Layer

AES S-box

输入字节的高 4 位表示行 X，低 4 位表示列 Y

Diffusion Layer

ShiftRows Sublayer

MixColumn Sublayer

Key Addition Layer

Key Schedule

Decryption

Inv MixColumn layer:

Inv ShiftRows layer

Inv Byte Substitution layer+Decryption key schedule

Practical issues

---

直接实现适合 8 位处理器

为什么适合 8 位处理器？

• 8 位处理器一次只能处理 8 位（1 字节） 的数据。AES 的核心算法（如 S-Box、行移位、列混合等操作）是基于矩阵的运算，在这种情况下只能逐步处理每一个字节。
• 因为 8 位处理器本身性能较低，资源也有限，使用直接实现的方法更简单、更易用。

举例：

AES 的一个数据块大小是 128 位（16 字节）。如果处理器一次只能处理 8 位（1 字节），那么它必须逐个处理每个字节。比如：

1. AES 要加密一块 128 位的数据。
2. 每次只能处理 8 位（1 字节），所以需要 128 ÷ 8 = 16 步。
3. 每步又包含多个计算（例如字节替代、行移位、列混合等），因此整个过程可能需要上百个指令周期。

这种逐字节操作的方式虽然简单，但在 32 位或 64 位处理器 上就显得效率低了，因为它们可以一次性处理更多数据（例如 32 位处理器能同时处理 4 个字节，64 位处理器能处理 8 个字节）。

---

优化的表查找方法

为什么需要优化？

• 在现代的 32 位或 64 位处理器中，逐字节处理显得太慢。优化的思路是：用查找表（Lookup Table）代替复杂计算。
• 查找表是提前计算好的结果集合，直接通过索引（比如一个字节的值）找到对应的结果，而不需要实时计算。

优化方法：

1. S-Box 优化：

   • S-Box 是 AES 中用来替代字节的表（每个字节都用一个特定的字节替换），可以提前生成一个包含 256 个条目的查找表。
   • 每次需要替代一个字节时，直接查表即可。

2. 合并运算：

   • 不仅是 S-Box，AES 的其他操作（如行移位、列混合）也可以合并到一个查找表中。
   • 这样每个字节的所有计算都可以通过查表一次性完成。

3. 最终优化：

   • 生成 4 个表，每个表包含 256 个条目，每个条目是 32 位宽。
   • 每轮 AES 运算只需要查表 16 次，就能完成所有的字节处理。（16个字节，表中有该字节对应的各个操作的结果）

举例：

假设 AES 要处理一个 128 位的数据块：

• 原始方式： 逐字节处理，需要上百个指令周期（比如每个字节进行 S-Box 替代 + 行移位 + 列混合）。
• 优化方式： 每个字节只需要查表 1 次，整个数据块需要查表 16 次，大幅减少了指令数和计算时间。

这种优化方式非常适合现代处理器，因为现代处理器擅长高效的表查找操作。

---

现代 64 位处理器速度

为什么速度更快？

现代 64 位处理器可以并行处理多个数据：

1. 查找表可以放在处理器的缓存中，查表的速度非常快。
2. 64 位处理器可以同时处理 8 个字节的数据，因此计算的并行度大幅提升。

举例：

• 假设 AES 要加密一个文件：
  • 文件大小为 2 GB（约 16 亿位）。
  • 在优化后的实现中，AES 的处理速度是 1.6 Gbit/s。
  • 处理 2 GB 的文件只需要 2 × 8 ÷ 1.6 = 10 秒。

优化后的表查找方法使得 AES 加密在现代硬件上变得非常快。

---

安全性

1. 暴力破解攻击（Brute-force attack）

翻译：
由于 AES 的密钥长度为 128 位、192 位或 256 位，暴力破解攻击是不可能实现的。

解释：

• 什么是暴力破解？
  暴力破解指的是尝试所有可能的密钥组合，直到找到正确密钥。对于 AES，加密的安全性取决于密钥长度。

• 为什么不可行？

  • AES 使用的密钥长度非常大：
    • 128 位密钥：可能的密钥总数是 (2^{128})，大约 (3.4 \times 10^{38})。
    • 192 位密钥：可能的密钥总数是 (2^{192})，大约 (6.3 \times 10^{57})。
    • 256 位密钥：可能的密钥总数是 (2^{256})，大约 (1.1 \times 10^{77})。
  • 即使使用当前最快的超级计算机，穷举这些密钥所需的时间也远远超过了宇宙的寿命，因此暴力破解是不可能的。

---

2. 分析性攻击（Analytical attacks）

翻译：
目前没有已知的分析性攻击比暴力破解更有效。

解释：

• 什么是分析性攻击？
  分析性攻击指的是通过数学或算法的弱点直接破解加密，而不需要尝试所有密钥。例如，攻击者可能试图找到 AES 算法中的漏洞，缩短破解时间。

• AES 的情况：

  • AES 是经过严格数学验证的，设计上没有已知的弱点。
  • 目前，所有针对 AES 的已知攻击都需要的计算量与暴力破解相当，甚至更高。
  • 因此，AES 在设计上仍然是安全的，没有已知的分析性攻击能击败它。

---

3. 侧信道攻击（Side-channel attacks）

翻译：

• 已经有多种侧信道攻击被公开。
• 需要注意的是，侧信道攻击并不是针对算法本身的，而是针对算法的具体实现。

解释：

• 什么是侧信道攻击？
  侧信道攻击不直接破解加密算法，而是利用加密操作过程中泄漏的物理信息（如时间、功耗、电磁辐射）来推断密钥或加密数据。

• 示例：

  1. 时间攻击（Timing attack）：
     通过测量加密操作的执行时间，推测密钥的某些部分。
  2. 功耗攻击（Power analysis）：
     通过观察加密过程中设备的功耗波动，分析内部的操作细节。
  3. 电磁辐射攻击（Electromagnetic attack）：
     通过分析设备在加密时产生的电磁信号，提取关键信息。

• 为什么不影响算法本身？
  侧信道攻击并不是针对 AES 算法本身的弱点，而是利用了设备实现中的漏洞。
  例如：

  • 如果加密操作的某些步骤在时间上存在不一致，攻击者可以利用这些时间差来推断密钥。
  • 如果硬件设计不合理，可能会泄漏更多的电磁信息，使攻击者更容易获取加密信息。

---

Attacks on the implementation