计算机和网络安全课程笔记

信息安全的基本原则

• 真实性（Authenticity）
• 保密性（Confidentiality）
• 完整性（Integrity）
• 不可否认性（Non-repudiation）
• 可用性（Availability）
• 隐蔽性（Covertness）

Hash 函数

密码学安全属性

抗第一原像性（Pre-image Resistance）

无法根据哈希函数的输出恢复其对应的输入。

抗第二原像性（Second Pre-image Resistance）

给定一个已知的输入 $x$ 难以找到另一个不同的输入 $x$ 使得：

$$ H(x) = H(x’) $$

即在已知一个具体输入 $x$ 的情况下，攻击者无法找到另一个不同的 $x’$ 使它们的哈希值相同。

抗碰撞性（Collision Resistance）

难以找到任意的两个不同的输入 $x$ 和 $x’$ 使得：

$$ H(x) = H(x’) $$

即攻击者无需指定任何一个输入，而是要找到任何一对不同的输入，它们的哈希值相同。

不同的 Hash 函数

密码哈希函数（Cryptographic Hash Functions）（满足上方 3 条性质）

主要用于安全性目的，如密码存储、数字签名等

非密码哈希函数（不满足上方 3 条性质）

主要用于数据完整性检测，不能用于安全目的

密码哈希函数的用途

密码哈希函数常被用于现代服务器后端存储密码

彩虹表攻击（Rainbow Table Attack）

彩虹表攻击是一种基于预计算哈希值的密码破解方法。攻击者提前计算并存储大量密码的哈希值，然后在攻击时快速查找匹配的哈希，从而反推出原始密码。

为了应对彩虹表攻击，现代密码哈希函数使用 Salt （盐）来解决。

Salt （盐）

Salt（盐） 是一个随机生成的额外数据，在对密码进行哈希之前，将其拼接到密码中，以防止彩虹表攻击（Rainbow Table Attack）。

具体实现步骤

1. 生成 Salt

   1. Salt 必须是随机的，否则攻击者可以提前计算哈希值表
   2. Salt 通常长度为 16 字节（128 位）或更长，以防止哈希冲突

2. 将 Salt 拼接到密码

   1. 方式 1：Salt + Password
   2. 方式 2：Password + Salt
   3. 方式 3：Salt 作为独立输入 （一些哈希算法使用这种方式来自动管理 Salt 的存储，即将密文存储为 salt$hashed_password）

3. 计算哈希值

4. 存储 Salt 和哈希（如果使用自动管理 Salt 的算法则不需要单独存储 Salt）

为什么不使用 SHA-256 这类常见哈希函数加盐来存储密码

主要是由于 SHA-256 计算速度太快，容易被暴力破解，使用 慢速哈希算法（如 bcrypt / Argon2） 增加计算成本，使暴力破解变得不可行。

加密密码场景下的哈希函数推荐

Argon2 > bcrypt > PBKDF2 > scrypt

bcrypt 仍是大多数 Web 应用的首选

密钥空间的含义

• 在密码学中，“密钥空间”是指所有可能的密钥的集合。
• 对于一个 128 位的密钥，每个密钥是一个 128 位的二进制序列。例如：
  • $ 0000\ldots0000 $（全 0）
  • $ 0000\ldots0001 $（最后一位为 1）
  • $ 1111\ldots1111 $（全 1）
  • 以及所有其他可能的组合。
• $ \{0,1\}^{128} $ 描述的就是这个集合：所有长度为 128 位的二进制字符串。

消息认证码（MACs, Message Authentication Codes）

• 定义：
  消息认证码（MAC）是一种单向哈希函数，但它有一个额外的特性：需要使用一个密钥（key）。
  具体来说，MAC 通过一个密钥 $k$ 和消息 $m$ 生成一个哈希值 $h_k(m)$。
  例如：

  • 输入：密钥 $k$ 和消息 $m$（消息可以看作一串二进制数据，比如 ${0,1}^*$）。
  • 输出：一个固定长度的哈希值 $h_k(m)$，通常表示为 ${0,1}^n$，其中 $n$ 是哈希值的长度（比如 256 位或 512 位）。

• 密钥的作用：
  这个密钥 $k$ 是保密的，只有发送者和接收者知道。密钥的存在使得 MAC 不仅仅是一个普通的哈希值，而是可以用来验证消息的真实性。
  你可以把 $h_k(m)$ 看作一种加密校验和（cryptographic checksum），用来确保消息没有被篡改。

MAC 的目标

MAC 的设计有以下几个主要目标：

• 提供消息认证（Message Authentication）：
  MAC 确保消息的真实性，即接收者可以确认消息确实是由持有密钥的发送者发出的。
  因为只有发送者和接收者知道密钥 $k$，所以如果接收者用相同的密钥计算 $h_k(m)$，并发现结果与发送者提供的 MAC 一致，就可以确认消息没有被篡改。

• 防止伪造（Eavesdropper Cannot Fake a Message）：
  如果有一个窃听者（eavesdropper）拦截了消息，他无法伪造一个有效的 MAC。
  原因是：MAC 的计算需要密钥 $k$，而窃听者不知道这个密钥。即使他修改了消息 $m$ 为 $m’$，他也无法生成正确的 $h_k(m’)$，因为他无法访问 $k$。

• 用于消息完整性（Integrity），而不是保密性（Secrecy）：
  MAC 的主要目的是确保消息的完整性（integrity），即消息在传输过程中没有被篡改。
  但 MAC 本身不提供消息的保密性（secrecy）。也就是说，消息 $m$ 本身可能是明文，任何人都可以看到，只有 MAC 值 $h_k(m)$ 是用来验证消息是否被修改的。

直观的解释

想象一个场景：

• 你（发送者）和你的朋友（接收者）共享一个秘密密码（密钥 $k$）。
• 你想给朋友发一条消息 $m$，比如“明天见”。
• 你用这个秘密密码 $k$ 和消息 $m$ 一起计算一个特殊的“校验码” $h_k(m)$，然后把消息 $m$ 和校验码 $h_k(m)$ 一起发给朋友。
• 你的朋友收到消息后，用相同的密码 $k$ 和收到的消息 $m$ 再计算一次校验码。如果计算结果和收到的 $h_k(m)$ 一样，说明消息没有被篡改，确实是你发的。
• 如果有人（比如一个坏人）在中间改了消息，比如把“明天见”改成“今天见”，但他不知道密码 $k$，他就无法生成正确的校验码。你的朋友收到后会发现校验码对不上，说明消息被篡改了。

HMAC（基于哈希的 MAC）

HMAC（Hash-based Message Authentication Code）是一种基于哈希函数的消息认证码。它结合了一个非密钥哈希函数（如 SHA-256）和一个密钥来生成 MAC，用于验证消息的完整性和真实性。

为什么需要 HMAC？

直接用哈希函数和密钥组合来构造 MAC 可能会出现安全问题。

• 尝试 1：$MAC_k(m) = h(k \mid m)$

  • 构造方式：将密钥 $k$ 和消息 $m$ 拼接（用 $\mid$ 表示拼接），然后用哈希函数 $h$ 计算哈希值。
  • 问题：不安全！
    这种方法容易受到扩展攻击（length-extension attack）。
    原因是许多哈希函数（比如 SHA-1、SHA-256）使用 Merkle-Damgård 构造。这种构造有一个特性：如果攻击者知道 $h(k \mid m)$，他们可以在消息 $m$ 后面追加数据（比如 $m’$），然后计算 $h(k \mid m \mid m’)$，而不需要知道密钥 $k$。
    因此，攻击者可以伪造一个新的消息和对应的 MAC。

• 尝试 2：$MAC_k(m) = h(m \mid k)$

  • 构造方式：将消息 $m$ 和密钥 $k$ 拼接（消息在前，密钥在后），然后计算哈希值。
  • 问题：不安全！
    这种方法容易受到生日攻击（birthday attack）。
    生日攻击利用了哈希函数的碰撞概率：如果哈希值的长度是 $n$ 位，攻击者只需要尝试大约 $2^{n/2}$ 次就可以找到两个不同的输入（比如 $m_1 \mid k$ 和 $m_2 \mid k$），它们的哈希值相同。
    对于一个 256 位的哈希函数（比如 SHA-256），攻击者只需要 $2^{128}$ 次尝试（远低于 $2^{256}$），这在密码学中被认为是不安全的。

• 尝试 3：$MAC_k(m) = h(k \mid m \mid k’)$

  • 构造方式：在消息 $m$ 的前后分别拼接密钥 $k$ 和另一个密钥 $k’$，然后计算哈希值。
  • 评价：更安全，但仍然不是最佳方案。
    这种方法通过在消息前后添加密钥，试图缓解扩展攻击和生日攻击的问题，但仍然可能存在一些理论上的弱点（比如如果 $k$ 和 $k’$ 的选择不合适，或者哈希函数本身有漏洞）。

最佳方案：HMAC

HMAC 是一种更安全的设计，公式如下：

$$ MAC_k(m) = h((k \oplus \text{opad}) \mid h((k \oplus \text{ipad}) \mid m)) $$

• 构造步骤：

  1. 首先将密钥 $k$ 与一个 内填充（ipad） 进行异或（$\oplus$）操作，得到 $k \oplus \text{ipad}$。
     • ipad 是一个固定的常量，值为 $0x36$ 重复（比如对于 512 位块，ipad 是 64 个字节的 $0x36$）。
  2. 将 $k \oplus \text{ipad}$ 与消息 $m$ 拼接，计算哈希值：$h((k \oplus \text{ipad}) \mid m)$。
  3. 然后将密钥 $k$ 与一个 外填充（opad） 进行异或操作，得到 $k \oplus \text{opad}$。
     • opad 是一个固定的常量，值为 $0x5c$ 重复（比如 64 个字节的 $0x5c$）。
  4. 将 $k \oplus \text{opad}$ 与上一步的哈希结果拼接，再次计算哈希值：$h((k \oplus \text{opad}) \mid h((k \oplus \text{ipad}) \mid m))$。
  5. 最终结果就是 HMAC。

• 为什么更安全？

  • HMAC 通过两次哈希和内外填充（ipad 和 opad）的设计，有效防止了扩展攻击和生日攻击。
  • 内外填充的异或操作引入了额外的随机性，使得攻击者难以利用哈希函数的内部结构进行攻击。
  • HMAC 的安全性已经被广泛研究和验证，得到了密码学界的认可。

对称密码（Symmetric Ciphers）

使用共享密钥（对称加密）进行加密和解密的传统方法，加密（encrypt）算法 $ E_k $ 和解密（decrypt）算法 $ D_k $ 互为逆操作，即 $ D_k(E_k(m)) = m $

密钥空间

• 密钥通常为大位数（≥128 位），如 128 位密钥的密钥空间为 $ \{0,1\}^{128} $。
• 暴力破解 128 位密钥空间需要极长时间（地球年龄内无法完成）。

$ \{0,1\}^{128} $ 的含义：

• $ \{0,1\}^{128} $ 表示由 0 和 1 组成的长度为 128 位的所有可能序列的集合。
• 上标 $ 128 $ 表示序列的长度，也就是说，每个元素是一个由 128 个二进制位（0 或 1）组成的字符串。

密钥空间的大小

因为每个位有 2 种选择（0 或 1），而总共有 128 个位，所以可能的密钥总数是：

$$ 2^{128} $$

类型

• 流密码（Stream Ciphers）: 逐位或逐字节操作。
• 块密码（Block Ciphers）: 对明文的分块（多位）进行操作。

密码分析（Cryptanalysis）

• 目标: 在不知道密钥的情况下破解加密系统，获取加密消息内容。
• 假设: 攻击者完全了解通信信道和加密系统，安全性仅依赖密钥。
• 攻击类型:
  • 仅密文攻击（Ciphertext Only Attack, COA）: 仅拥有密文，试图解出明文或密钥。
  • 已知明文攻击（Known Plaintext Attack, KPA）: 拥有明文-密文对，推导密钥或解密算法。
  • 选择明文攻击（Chosen Plaintext Attack, CPA）: 攻击者可选择明文并获取对应密文。
  • 选择密文攻击（Chosen Ciphertext Attack, CCA）: 攻击者可选择密文并获取对应明文。
• 破解程度（从最严重到最轻微）:
  • 完全破解（Total Break）：找到密钥 $k$。
  • 全局推导（Global Deduction）：找到等效解密算法。
  • 局部推导（Local Deduction）：解密单个密文。
  • 信息推导（Information Deduction）：获取部分信息。
• 攻击指标: 数据需求（Data Requirements）、处理需求（工作因子）（Processing requirements (work factor)）、内存需求（Memory requirements）、计算成本（Computational cost）。

古典密码

替换密码（Substitution Ciphers）

最古老的密码类型，通过字母替换表加密，有 26! 种不同可能的密码，因此密钥空间为 $2^{88}$。
例如，凯撒密码（移位 3）或 ROT13（移位 13）。
缺点是易被频率分析（frequency analysis）攻破（分析单字母、二字母、三字母频率从而推断替换规则）。

同音密码/改进替换密码（Homophonic Ciphers）

用多个符号替换常见字母，隐藏频率特征，增加破解难度。

置换密码（Permutation Ciphers）

置换密码是一种通过重新排列明文字符的顺序来实现加密的技术，而不是像替换密码那样替换字符。
置换密码的密钥是一个随机置换，即一个将位置重新排序的规则。

加密方式

• 输入: 给定一个消息 $ m = [m_1, m_2, m_3, \ldots, m_n] $，其中 $ m_1, m_2, \ldots, m_n $ 是明文中的各个字符或单位。
• 加密公式: 加密通过函数 $ E\pi(m) $ 实现，结果是根据置换 $ \pi $ 重新排列的字符序列，即： $$ E\pi(m) = [m_{\pi(1)}, m_{\pi(2)}, m_{\pi(3)}, \ldots, m_{\pi(n)}] $$
  • 这里 $ \pi(i) $ 表示置换 $ \pi $ 指定的新位置。例如，如果 $ \pi(1) = 4 $，那么明文中的第一个字符 $ m_1 $ 将移动到第 4 个位置。

示例

置换 $ \pi $ 的定义: 假设消息长度为 6，置换 $ \pi $ 如下：

1  2  3  4  5  6
4  3  1  5  2  6

这表示：

• 位置 1 的字符移动到位置 4
• 位置 2 的字符移动到位置 3
• 位置 3 的字符移动到位置 1
• 位置 4 的字符移动到位置 5
• 位置 5 的字符移动到位置 2
• 位置 6 的字符保持在位置 6

维吉尼亚密码（Vigenere Cipher）

多字母替换密码，使用重复密钥词，通过模 26 加法加密。

加密方式

加密通过将明文和密钥流的字母逐一对应相加（模 26）来完成。

• 字母用 0 到 25 的数字表示（A=0, B=1, …, Z=25）。
• 加密公式：$ \text{Ciphertext} = (\text{Plaintext} + \text{Key}) \mod 26 $。
• 解密公式：$ \text{Plaintext} = (\text{Ciphertext} - \text{Key}) \mod 26 $。

示例

• 明文（Plaintext）: launchmissilesatlosangeles
• 密钥流（Keystream）: cryptocryptocryptocryptocr
  • 密钥是 “crypto”，长度为 6。
  • 明文长度为 25（去掉空格和标点后），因此密钥 “crypto” 重复使用，直到匹配明文长度：crypto-crypto-crypto-crypto-cr。
• 密文（Ciphertext）: nrscvvozqhbzgjyiecurvlwzgj

加密过程详解：

• 字母编号:

  • A=0, B=1, …, Z=25（文档中特别说明 0 索引是 A）。

• 计算示例:

  1. 第一个字母：L + C
     • 明文第一个字母：L（第 11 个字母，索引从 0 开始，所以 L=11）。
     • 密钥流第一个字母：C（第 2 个字母，C=2）。
     • 加密：$ 11 + 2 = 13 \mod 26 = 13 $，第 13 个字母（从 0 开始计数）是 N（N=13）。
     • 结果：L 加密为 N。
  2. 第二个字母：A + R
     • 明文第二个字母：A（A=0）。
     • 密钥流第二个字母：R（R=17）。
     • 加密：$ 0 + 17 = 17 \mod 26 = 17 $，第 17 个字母是 R（R=17）。
     • 结果：A 加密为 R。
  3. 第三个字母：U + Y
     • 明文第三个字母：U（U=20）。
     • 密钥流第三个字母：Y（Y=24）。
     • 加密：$ 20 + 24 = 44 \mod 26 = 18 $，第 18 个字母是 S（S=18）。
     • 结果：U 加密为 S。
  4. 第四个字母：N + P
     • 明文第四个字母：N（N=13）。
     • 密钥流第四个字母：P（P=15）。
     • 加密：$ 13 + 15 = 28 \mod 26 = 2 $，第 2 个字母是 C（C=2）。
     • 结果：N 加密为 C。

• 继续计算:

  • 按此方法逐字母计算，最终明文 launchmissilesatlosangeles 加密为密文 nrscvvozqhbzgjyiecurvlwzgj。

XOR（异或）

XOR 是“Exclusive OR”（异或）的缩写，意思是“一个或另一个，但不能同时是两者”，符号表示为 $\oplus$。

数学定义

XOR 是模 2 加法，用符号 $ \oplus $ 表示。对于两个二进制位 $ a $ 和 $ b $，XOR 的计算公式为：

$$ a \oplus b = (a + b) \mod 2 $$

• 也就是说，XOR 的结果是 $ a + b $ 对 2 取模。

$ a $	$ b $	$ a \& b $ (与)	$ a | | b $ (或)	$ a \oplus b $ (异或)
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

数学验证

• $ 0 \oplus 0 = (0 + 0) \mod 2 = 0 $
• $ 0 \oplus 1 = (0 + 1) \mod 2 = 1 $
• $ 1 \oplus 0 = (1 + 0) \mod 2 = 1 $
• $ 1 \oplus 1 = (1 + 1) \mod 2 = 0 $

性质

文档列出了 XOR 的几个重要性质，这些性质在密码学中非常有用：

自反性（Something XOR’d with itself is zero）:

• $ A \oplus A = 0 $
• 解释：任何值与自身进行 XOR 操作，结果总是 0。
  • 例如：$ 0 \oplus 0 = 0 $，$ 1 \oplus 1 = 0 $。
• 意义：在加密中，这意味着如果用同一个密钥对密文再次 XOR，可以恢复明文。

结合律（Associative）:

• $ A \oplus (B \oplus C) = (A \oplus B) \oplus C $
• 解释：XOR 操作的顺序不影响结果，可以先计算 $ B \oplus C $，再与 $ A $ 进行 XOR，或者先计算 $ A \oplus B $，再与 $ C $ 进行 XOR。
• 意义：这使得 XOR 在多步操作中可以灵活分组计算。

交换律（Commutative）:

• $ A \oplus B = B \oplus A $
• 解释：XOR 操作的两个操作数可以交换位置，结果不变。
• 意义：这简化了计算，因为操作顺序不重要。

OTP

一次性密码本是一种加密方法，对明文的每个字母（或位）使用一个独立的替换密码。
在实际操作中，OTP 通常通过 XOR 操作实现，即明文 $ m $ 与一个密钥 $ k $ 按位异或，生成密文 $ c = m \oplus k $。
这里的“不同替换密码”指的是密钥的每个位都是独立的，相当于为明文的每个位提供一个独立的加密规则。

OTP 实现完美安全性的条件

OTP 被认为是理论上“完美安全”（Perfect Secrecy）的加密方法，但需要满足以下严格条件：

密钥 $ k $ 必须是真随机的（The secret key, $ k $, is truly random）:

• 密钥 $ k $ 必须是从一个真正的随机源生成的，不能有任何模式或可预测性。
• 如果密钥不是真随机的（例如使用伪随机数生成器生成），攻击者可能通过分析密钥的生成方式来推断密钥。

明文不能重复（The plaintext does not repeat）:

• 这里的“明文不重复”指的是，同一个明文不能多次使用同一个密钥加密。
• 如果明文重复（例如发送两条相同的消息），攻击者可以通过比较密文来推断信息。

密钥流不能重复（The keystream does not repeat）:

• 密钥流（即密钥 $ k $）必须与明文等长，且不能有任何重复或周期性。
• 如果密钥流重复（例如密钥长度小于明文长度，导致密钥循环使用），密文会表现出周期性模式，类似于维吉尼亚密码，可以被破解。

不满足条件的后果

• 零安全性（Failure to meet any one of these requirements results in zero security）:
  • 如果上述任一条件不满足，OTP 的安全性将完全丧失。
  • 例如：
    • 如果密钥不是真随机的，攻击者可能通过分析密钥生成方式破解。
    • 如果密钥重复使用，攻击者可以通过 $ c_1 \oplus c_2 = m_1 \oplus m_2 $ 推断明文之间的关系。
    • 如果密钥长度不足（导致重复），密文会表现出周期性，可以用重合指数等方法破解。

OTP 安全性的来源

• 真随机密钥的威力（The strength comes from the fact that a truly random key added to plaintext, produces a truly random ciphertext）:
  • 当密钥 $ k $ 是真随机的，且与明文等长时，密文 $ c = m \oplus k $ 也是完全随机的。
  • 具体来说：
    • 假设明文 $ m $ 是任意比特序列，密钥 $ k $ 是等长的真随机比特序列。
    • 对于密文的每一位 $ c_i = m_i \oplus k_i $，因为 $ k_i $ 是随机的（0 或 1 的概率各为 50%），所以 $ c_i $ 也是随机的（0 或 1 的概率各为 50%）。
    • 因此，密文 $ c $ 在统计上看起来是完全随机的，没有任何模式可供攻击者分析。

OTP 的完美安全性

• 无法破解（No amount of computing power can break a one-time pad）:

  • OTP 提供了“完美安全性”（Perfect Secrecy），即密文不泄露任何关于明文的信息。
  • 数学上，完美安全性的定义是： $$ \text{Pr}[M = m | C = c] = \text{Pr}[M = m] $$
    • 即给定密文 $ c $，明文 $ m $ 的概率分布与没有密文时的概率分布相同。
  • 原因：
    • 由于密钥是真随机的，且与明文等长，攻击者无法通过密文推断明文。
    • 对于任意密文 $ c $，每个可能的明文 $ m $ 都有一个对应的密钥 $ k = c \oplus m $，且这个密钥的概率是均等的（因为 $ k $ 是真随机的）。
    • 因此，攻击者无法确定哪个明文是正确的。

• 暴力破解的无效性（Brute force would yield each and every possible message of that length）:

  • 如果攻击者尝试暴力破解（即尝试所有可能的密钥），会发现：
    • 对于长度为 $ n $ 位的密文 $ c $，每个可能的明文 $ m $（长度也为 $ n $）都可以通过一个密钥 $ k = c \oplus m $ 解密出来。
    • 例如，密文 $ c = 1010 $，长度为 4 位：
      • 明文 $ m = 0000 $，则密钥 $ k = c \oplus m = 1010 $。
      • 明文 $ m = 1111 $，则密钥 $ k = c \oplus m = 0101 $。
      • 明文 $ m = 1010 $，则密钥 $ k = c \oplus m = 0000 $。
    • 所有 $ 2^n $ 个可能的明文（对于 $ n $ 位，有 $ 2^n $ 种可能）都会对应一个可能的密钥，且每个密钥的概率相等。
  • 因此，暴力破解无法确定哪个明文是正确的，攻击者只能得到所有可能的明文，没有任何信息增益。

OTP 破解

两用密码（Two Time Pad）

两用密码的定义

• 场景:

  • 假设有两条明文消息 $ m_1 $ 和 $ m_2 $，它们使用同一个密钥 $ k $ 进行加密。
  • 加密过程使用 OTP 的标准方法，即通过 XOR 操作： $$ c_1 = m_1 \oplus k $$ $$ c_2 = m_2 \oplus k $$
  • 其中：
    • $ c_1 $ 是第一条消息的密文，
    • $ c_2 $ 是第二条消息的密文，
    • $ k $ 是密钥（长度与明文等长，且原本应为真随机）。

• 问题:

  • OTP 的核心安全要求之一是密钥不能重复使用。
  • 如果同一个密钥 $ k $ 被用来加密两条消息（即“两用密码”），安全性将完全丧失。

破解方法：通过 XOR 密文消去密钥

• 攻击步骤:
  • 攻击者截获了两条密文 $ c_1 $ 和 $ c_2 $。
  • 将两密文进行 XOR 操作： $$ c_1 \oplus c_2 = (m_1 \oplus k) \oplus (m_2 \oplus k) $$
  • 计算过程:
    • 根据 XOR 的性质（结合律和自反性）： $$ (m_1 \oplus k) \oplus (m_2 \oplus k) = m_1 \oplus k \oplus m_2 \oplus k $$
    • 因为 $ k \oplus k = 0 $（自反性），所以： $$ m_1 \oplus k \oplus m_2 \oplus k = (m_1 \oplus m_2) \oplus (k \oplus k) = m_1 \oplus m_2 \oplus 0 = m_1 \oplus m_2 $$
  • 结果: $$ c_1 \oplus c_2 = m_1 \oplus m_2 $$
    • 密钥 $ k $ 被完全消去，攻击者得到了 $ m_1 \oplus m_2 $，即两条明文的 XOR 结果。

利用语言冗余性分离 $ m_1 $ 和 $ m_2 $

• 语言冗余性:

  • 文档提到，英语语言和 ASCII 编码具有高度冗余性。
  • 冗余性意味着明文（例如英语文本）中存在大量可预测的模式，例如：
    • 字母频率（E 出现频率高，Z 出现频率低）。
    • 单词结构（常见单词如 “the”、“and”）。
    • ASCII 编码的特性（例如，字母的第 6 位通常为 1，而大多数标点符号的第 6 位为 0）。

• 分析 $ m_1 \oplus m_2 $:

  • 攻击者得到 $ m_1 \oplus m_2 $，这是一个两条明文的 XOR 结果。
  • 由于语言的冗余性，$ m_1 \oplus m_2 $ 中会保留一些模式，攻击者可以利用这些模式推断 $ m_1 $ 和 $ m_2 $。

• 进一步推断:

  • 如果攻击者知道部分明文（例如 $ m_1 $ 包含常见单词 “the”），可以通过 $ m_1 \oplus m_2 $ 推断 $ m_2 $ 的对应部分。
  • 例如：
    • 假设 $ m_1 = \text{“the”} $，在 ASCII 中为 01110100 01101000 01100101。
    • $ m_1 \oplus m_2 $ 已知，计算 $ m_2 = (m_1 \oplus m_2) \oplus m_1 $。
    • 然后用 $ m_2 \oplus c_2 = k $ 计算密钥 $ k $，从而解密其他密文。

OTP 存在的问题

• 核心问题是密钥的分发和销毁问题
• 密钥会随着明文的长度改变导致密钥过长
• 可能遭受可塑性攻击（Malleability Attack）：攻击者可以在不解密密文的情况下，通过修改密文直接影响解密后的明文。

伪随机数生成器（Pseudorandom Number Generators， PRNGs）

为密码系统提供看似随机的密钥流，用于会话密钥、挑战码等。

来源

从外部真随机源（如热噪声、用户输入）提取随机性（熵，entropy）。

属性

• 可重复性 (Repeatability)
• 统计随机性 (Statistical randomness)
• 长周期 (Long period/cycle)
• 高计算效率 (Computational efficiency)

类型

线性同余生成器（Linear Congruential Generators, LCG）

定义和生成规则

LCG 通过一个初始种子值 $ x_0 $（seed）开始，生成一个伪随机数序列 $ x_1, x_2, \dots $。生成规则是一个递归公式：

$$ x_{n+1} = (a x_n + b) \mod c $$

• $x_{n+1}$：下一个生成的伪随机数。

• $ x_n $：当前伪随机数（从 $ x_0 $ 开始）。

• $ a, b, c $：固定的常数，分别称为乘数（multiplier）、增量（increment）和模数（modulus）。

• 参数 $ a, b, c $ 的作用：

  • $ a $ 控制序列的“跳跃”幅度。
  • $ b $ 提供额外的偏移。
  • $ c $ 决定生成数的范围（生成的数在 $ [0, c-1] $ 之间）。

• 周期性：

  • LCG 生成的伪随机数序列是周期性的，周期最大为 $ c $。也就是说，序列会在某个时刻开始重复。
  • 为了让周期尽可能长（接近 $ c $），需要仔细选择 $ a, b, c $。例如：
    • $ c $ 通常选为一个大素数或 2 的幂。
    • $ a $ 和 $ c $ 互质（两个整数 a 和 b 的最大公约数是 1）。
    • $ b $ 和 $ c $ 互质等。

• 安全性问题：

  • LCG 的伪随机数生成器（PRNG）非常不安全。如果攻击者知道连续的三个值 $x_i, x_{i+1}, x_{i+2}$，他们可以通过数学方法（例如解线性方程组）反推出参数 $ a $ 和 $ b $，从而预测整个序列。
  • 因此，LCG 不适合用于需要高安全性的场景（如密码学）。

LCG 的优点

• 简单且快速：

  • LCG 的公式非常简单，只涉及乘法、加法和取模运算，计算开销很低，适合需要快速生成随机数的场景。
  • 在早期的计算机程序中（如模拟、游戏等），LCG 是一种非常流行的选择。

• 存储需求小：

  • LCG 只需要存储当前生成的数（即 $ x_n $），不需要保存整个序列，内存占用极小。
  • 每次生成下一个数时，只需用公式计算即可。

• 可重复性：

  • LCG 的一个重要特性是：给定相同的种子 $ x_0 $ 和参数 $ a, b, c $，生成的序列是完全确定的。
  • 这在调试或比较不同系统/模型时非常有用。例如，在机器学习中，可以用相同的随机数序列来确保实验的可重复性。

线性反馈移位寄存器（Linear Feedback Shift Registers, LFSR）

线性反馈移位寄存器（LFSR）是一种用于生成伪随机序列的硬件或软件结构。它由一组寄存器（通常是二进制位，0 或 1）和一个反馈机制组成。LFSR 通过将寄存器的内容进行移位，并根据特定的反馈规则（通常是异或运算，XOR）生成新的位，然后将新位反馈到寄存器中。

流密码（Stream Chipers）

优点

• 易于实现和使用（Ease of implementation and use）
  流密码通常比块密码（block ciphers）更简单。流密码通过生成一个伪随机密钥流（keystream），然后将密钥流与明文逐位异或（XOR）来加密数据。这种操作在软件和硬件上都比较容易实现，计算开销也较低。

• 安全的伪随机数生成器（PRNG）比块密码快得多（Secure PRNGs can be a lot faster than block ciphers）
  流密码依赖于伪随机数生成器（PRNG）来生成密钥流。如果 PRNG 是安全的（即生成的序列看起来是随机的且难以预测），那么流密码的加密速度通常比块密码快。块密码（如 AES）需要将数据分成固定大小的块并进行复杂的轮次变换，而流密码可以逐位或逐字节处理数据，效率更高。

流密码的安全性依赖于伪随机数生成器

• 必须难以找到种子 $ k $ 或伪随机数序列 PRNG($ k $)（It must be computationally hard to find the seed $ k $, or the sequence PRNG($ k $)）
  流密码的安全性完全依赖于伪随机数生成器（PRNG）的质量。PRNG 会根据一个种子 $ k $（seed）生成一个伪随机序列。如果攻击者能够通过分析密文或其他方式猜出种子 $ k $，或者能够预测 PRNG 生成的序列，那么流密码就会被破解。因此，种子 $ k $ 和 PRNG 的设计必须足够安全，确保攻击者无法通过计算手段反推出 $ k $ 或序列。

• 种子 $ k $ 只能使用一次（The seed $ k $ must be used only once）
  流密码的一个关键安全原则是：同一个种子 $ k $ 不能重复使用。如果同一个种子被用来加密多条消息，攻击者可以通过分析多条密文之间的关系（例如通过异或操作）来恢复明文。这种情况类似于一次性密码本（one-time pad）的误用。一次性使用种子是流密码安全的重要保障。

• 伪随机数生成器的周期必须至少与消息长度一样长（The PRNG period must be at least as long as the message）
  PRNG 生成的伪随机序列有一个周期（period），即序列开始重复的长度。如果这个周期比消息长度短，那么密钥流会重复使用，攻击者可能通过分析密文中的重复模式来破解加密。因此，PRNG 的周期必须足够长，至少要覆盖整个消息的长度，以避免这种攻击。

流密码本身只能保证保密性

• 流密码和一次性密码本（one-time pad）类似，主要目标是保证数据的保密性（secrecy），即确保攻击者无法读取明文。然而，流密码无法防止消息在传输过程中被篡改（modification）。
  例如，攻击者可以修改密文中的某些位（因为流密码通常是逐位异或操作），这会导致解密后的明文发生变化，而接收方可能无法察觉这种篡改。为了解决这个问题，通常需要结合其他机制（如消息认证码 MAC）来保证数据的完整性（integrity）。

---

总结

流密码是一种高效的加密方式，适合需要快速加密的场景（如实时通信）。它的核心是伪随机数生成器（PRNG），安全性依赖于：

1. PRNG 的不可预测性（种子 $ k $ 和序列难以被猜出）。
2. 种子 $ k $ 的一次性使用。
3. PRNG 周期足够长。

然而，流密码只保证保密性，不能防止消息被篡改，因此在实际应用中通常需要与其他安全机制结合使用。

如果你有更具体的问题，比如某个流密码算法（如 RC4、Salsa20）的细节，可以告诉我，我可以进一步解释！

分块加密/块密码（Block Chipers）

块密码（block cipher）是一种加密算法，它将固定长度的明文块（例如 $ n $ 位）映射到相同长度的密文块（也是 $ n $ 位）。

Feistel 网络（Feistel Network）

核心思想是：给定 $ d $ 个伪随机函数 $ f_1, f_2, \dots, f_d $，每个函数 $ f_i $ 将 $ n $ 位输入映射到 $ n $ 位输出，Feistel 网络通过一种特定的结构将这些函数组合起来，构造出一个安全的可逆函数 $ F $。
这个函数 $ F $ 的输入和输出是 $ 2n $ 位（而不是 $ n $ 位），也就是说，Feistel 网络处理的是长度为 $ 2n $ 位的块。

流程

• 图中用 $ \oplus $ 表示异或操作。
• 每一轮的 $ f_i $ 是一个伪随机函数，通常由密钥 $ k $ 控制（例如 $ f_i $ 可能是某个子密钥 $ k_i $ 的函数）。
• 箭头表示数据的流动：右半部分输入到 $ f_i $，然后与左半部分异或，结果成为新的右半部分，而旧的右半部分直接成为新的左半部分。

输入和分割

• 输入是一个 $ 2n $ 位的块，被分成两半，每半部分是 $ n $ 位：
  • 左半部分：$ L_0 $
  • 右半部分：$ R_0 $

每一轮的计算

Feistel 网络由 $ d $ 轮（round）组成，每一轮使用一个伪随机函数 $ f_i $。图中展示了 $ d $ 轮的迭代过程：

• 第 $ i $ 轮（以第 1 轮为例）：

  • 右半部分 $R_{i-1}$ 作为输入，送入伪随机函数 $f_i$，得到 $f_i(R_{i-1})$。
  • 将 $f_i(R_{i-1})$ 与左半部分 $L_{i-1}$ 进行异或（XOR）操作：$L_{i-1} \oplus f_i(R_{i-1})$。
  • 这一轮的输出是：
    • 新左半部分：$L_i = R_{i-1}$
    • 新右半部分：$R_i = L_{i-1} \oplus f_i(R_{i-1})$

• 交换：注意每一轮结束后，左右两半部分会“交换”位置（实际上是通过赋值实现的：新左半部分是旧右半部分，新右半部分是计算结果）。

多轮迭代

• 上述过程重复 $ d $ 次，每一轮使用一个不同的伪随机函数 $ f_i $。
• 最后一轮（第 $ d $ 轮）结束后，得到最终的 $ L_d $ 和 $ R_d $，它们组合起来就是加密后的 $ 2n $ 位密文：$ (L_d, R_d) $。

优点

Feistel 网络之所以被广泛使用，有以下几个关键优点：

1. 可逆性：

   • Feistel 网络的结构天然保证了可逆性。解密过程几乎与加密过程相同，只需要将轮函数$f_i$按相反的顺序应用即可（不需要$f_i$本身是可逆的）。
   • 具体来说，解密时：
     • 从$(L_d, R_d)$开始。
     • 第$i$轮：$R_{i-1} = L_i$，$L_{i-1} = R_i \oplus f_i(L_i)$。
     • 这样一步步逆推回去，恢复出$(L_0, R_0)$。

2. 简单性：

   • Feistel 网络只需要设计伪随机函数$f_i$，而不需要$f_i$本身是可逆的。这大大降低了设计难度，因为伪随机函数（如哈希函数的变种）相对容易构造。

3. 安全性：

   • 如果$f_i$是密码学上安全的伪随机函数，并且轮数$d$足够多（通常需要至少 3-4 轮，实际中更多），Feistel 网络可以提供很高的安全性。
   • 这种结构在理论上可以被证明是安全的（例如通过 Luby-Rackoff 构造，证明了 3 轮 Feistel 网络在某些条件下可以构造出安全的块密码）。

为什么解密只需要按相反顺序应用$f_i$？

Feistel 网络的解密过程之所以简单，是因为它的结构天然支持可逆性。解密的目标是从密文$(L_d, R_d)$恢复出明文$(L_0, R_0)$。我们可以通过逆向推导每一轮的计算来实现这一点。

解密过程

解密时，我们从最后一轮（第$d$轮）开始，逐步逆推到第 1 轮，每一轮使用对应的$f_i$。具体来说：

• 第$i$轮（从$d$到$1$）：

  • 输入：$(L_i, R_i)$
  • 输出：$(L_{i-1}, R_{i-1})$，其中： $$ R_{i-1} = L_i $$ $$ L_{i-1} = R_i \oplus f_i(L_i) $$

• 经过$d$轮逆向计算后，从$(L_d, R_d)$恢复出$(L_0, R_0)$。

• 第二个公式可以根据加密过程得到，已知 $R_i = L_{i-1} \oplus f_i(R_{i-1}) = L_{i-1} \oplus f_i(L_i)$，则 $L_{i-1} = R_i \oplus f_i(L_i) = L_{i-1} \oplus f_i(L_i) \oplus f_i(L_i) = L_{i-1}$

DES

DES 是一种对称密钥加密算法，意味着加密和解密使用相同的密钥。它将明文（需要加密的数据）分成固定大小的块进行加密。DES 使用了 16 轮 Feistel 网络，每轮使用一个由主密钥派生的子密钥。

• 输入和密钥：
  • DES 接受一个64 位的数据块（即明文块$b$）和一个56 位密钥$k$，虽然密钥名义上是 64 位，但其中 8 位用于奇偶校验，实际有效的密钥长度是 56 位。
• 加密过程： DES 的加密过程可以分为几个主要步骤：初始置换（IP）、16 轮 Feistel 网络、最终置换（FP）。最终输出是加密后的密文$E_k(b)$。

加密步骤

1. 初始置换（IP，Initial Permutation）：

   • 输入的 64 位数据块$b$首先经过一个初始置换（IP）。
   • IP 是一个固定的位重排操作，将 64 位数据块的位重新排列，生成一个新的 64 位块。
   • 这一步的目的是打乱数据的原始顺序，增加后续加密的复杂性。

2. Feistel 网络（16 轮迭代）：

   • 经过 IP 后的 64 位块被送入一个Feistel 网络，这是 DES 的核心部分。
   • Feistel 网络将 64 位块分成左右两半（各 32 位），然后进行 16 轮迭代处理。
   • 每轮迭代使用一个轮函数$f_i(x) = F(x, k_i)$：
     • $F$是 DES 的轮函数（一个复杂的非线性函数，包含扩展、S 盒替换、P 盒置换等操作）。
     • $k_i$是第$i$轮的子密钥，长度为 48 位。
     • 子密钥$k_i$是从原始 56 位密钥$k$通过 密钥调度（key schedule） 生成的。密钥调度会从$k$派生出 16 个 48 位的子密钥${k_1, k_2, …, k_{16}}$。

3. 最终置换（FP，Final Permutation）：

   • 16 轮 Feistel 网络处理完成后，得到的 64 位块再经过一个最终置换（FP）。
   • FP 是 IP 的逆操作，将位重新排列，生成最终的密文$E_k(b)$。

轮函数（Round Function）

1. 扩展置换（E，Expansion Permutation）：

   • 输入的 32 位数据块 $x $ 首先经过扩展置换 $E $。
   • $E $ 将 32 位数据扩展到 48 位，方法是复制某些位（具体来说，某些位会被重复使用）。
   • 扩展的目的是：
     • 使数据长度与 48 位子密钥 $k_i $ 匹配，以便后续进行异或操作。
     • 增加数据的冗余，为 S 盒替换提供更多输入。
   • 图中用蓝色的“E”框表示这一步骤，输入 32 位，输出 48 位。

2. 与子密钥异或（XOR with Round Key）：

   • 扩展后的 48 位数据与当前轮的 48 位子密钥 $k_i $ 进行按位异或（XOR）操作。
   • 这一步引入了密钥的影响，使得加密过程依赖于密钥。
   • 图中用一个粉色的“⊕”符号表示异或操作。

3. S 盒替换（S-box Substitution）：

   • 异或后的 48 位数据被分成 8 组，每组 6 位（因为 $48 \div 8 = 6 $）。
   • 每组 6 位数据被送入一个 S 盒（S-box），总共有 8 个 S 盒（$S_1, S_2, …, S_8 $）。
   • 每个 S 盒是一个非线性替换表，将 6 位输入映射为 4 位输出（即“6 bits to 4 bits”）。
     • S 盒的输入 6 位中，首尾两位（第 1 位和第 6 位）决定行号（0 到 3），中间 4 位（第 2 到第 5 位）决定列号（0 到 15）。
     • 根据 S 盒的查找表，输出一个 4 位值。
   • 8 个 S 盒的输出（每个 4 位）拼接起来，生成 32 位数据（$8 \times 4 = 32 $）。
   • S 盒的作用：
     • 引入非线性变换，这是 DES 安全性的关键。
     • 提供混淆（confusion），使输入和输出之间的关系变得复杂，难以分析。
   • 图中用 8 个框（$S_1 $ 到 $S_8 $）表示 S 盒。

4. P 盒置换（P-box Permutation）：

   • S 盒输出的 32 位数据经过一个固定的置换操作 $P $。
   • $P $ 是一个位重排操作，将 32 位数据的位重新排列。
   • 这一步的作用是提供扩散（diffusion），确保 S 盒的输出位影响到更多的位，增强加密的雪崩效应（即输入的一个位变化会导致输出的多个位变化）。
   • 图中用绿色的“P”框表示这一步骤，输入和输出均为 32 位。

扩散（Diffusion）

定义

• 扩散是指将明文中的统计信息分散到密文中，使得明文的一个小变化（例如一个位的翻转）会导致密文的显著变化。
• 目标是消除明文中的统计模式（例如某些位总是 0 或 1），让密文看起来像是随机的。

具体要求

1. 明文的一个位翻转应导致密文一半的位发生变化：

   • 如果明文中的一个位从 0 变为 1（或 1 变为 0），理想情况下，密文中有大约 50%的位会发生变化。
   • 这种特性称为雪崩效应（Avalanche Effect），是扩散的一个重要指标。
   • 雪崩效应确保了明文的小变化会导致密文的大变化，从而隐藏明文的统计特性。

2. 密文的一个位翻转应导致明文一半的位发生变化：

   • 在解密过程中，如果密文的一个位被翻转，解密后的明文也应该有大约 50%的位发生变化。
   • 这确保了密文的任何篡改都会导致解密结果的显著变化，防止攻击者通过修改密文来推测明文。

混淆（Confusion）

定义

• 混淆是指使密钥和密文之间的关系尽可能复杂。
• 目标是隐藏密钥对密文的影响，使得即使攻击者知道明文和密文，也难以推测出密钥。

具体要求

1. 密文的每一位应依赖于密钥的多个位：

   • 理想情况下，密文的每一位都应该受到密钥中多个位的影响。
   • 这样，即使攻击者知道密文的一个位，也无法直接推测出密钥的某个特定位，因为该位依赖于密钥的多个位。

2. 即使攻击者收集了大量的（明文，密文）对，也无法推测出密钥：

   • 在已知明文攻击（Known-Plaintext Attack）中，攻击者可以获得许多明文和对应的密文对（使用同一密钥加密）。
   • 混淆确保即使有这些数据，攻击者也无法通过分析明文和密文之间的关系来推导出密钥。

破解

1. 给定一个明文/密文对 (m, c)，只有一个密钥 k 满足：

• 公式：$c = DES(m, k)$
• 解释：DES 是一种对称加密算法，给定一个明文 $m$ 和密钥 $k$，通过 DES 加密后得到密文 $c$。这里强调的是，对于一个特定的明文/密文对 $(m, c)$，理论上只有一个密钥 $k$ 能满足这个加密关系。

2. 将 DES 视为一个由 256 个独立排列组成的集合：

• DES 的密钥长度是 56 位，因此总共有 $2^{56}$ 个可能的密钥。
• 如果这些排列（即每个密钥对应的加密映射）是独立的，那么对于一个给定的明文/密文对 $(m, k)$，有： $$ \text{Pr}[\exists k_1 \neq k : DES(m, k_1) = DES(m, k)] = \frac{2^{-56}}{1.39 \times 10^{-17}} = 0.0000000000000000139% $$
• 解释：
  • $\text{Pr}[\exists k_1 \neq k : DES(m, k_1) = DES(m, k)]$ 表示存在一个不同于 $k$ 的密钥 $k_1$，使得它对同一个明文 $m$ 加密后得到相同的密文 $DES(m, k)$。
  • 由于 DES 的密钥空间是 $2^{56}$，而 DES 的输出是 64 位（因为 DES 是 64 位分组密码），总共有 $2^{64}$ 种可能的密文。
  • 因此，两个不同密钥产生相同密文的概率非常小，计算结果是 $2^{-56} \div 1.39 \times 10^{-17}$，即 0.0000000000000000139%，几乎可以忽略不计。
• 结论：对于一个给定的明文/密文对，密钥 $k$ 几乎是唯一的。

3. 因此，给定一个 (m, c) 对，密钥 k 是（几乎）唯一确定的，问题在于如何找到它。

• 解释：由于密钥的唯一性，理论上可以通过尝试所有可能的密钥（暴力破解）来找到正确的 $k$。但由于密钥空间巨大（$2^{56}$），需要更高效的方法。

DES 的明文暴力破解方法

• 强 n 位分组密码，j 位密钥：
  • DES 是一个强分组密码，其中分组大小 $n = 64$ 位，密钥长度 $j = 56$ 位。
  • 理论上，通过暴力破解（即尝试所有可能的密钥），平均需要 $2^{j-1}$ 次尝试来恢复密钥。
  • 条件是需要少量（小于 $(j + 4)/n$ 个）明文/密文对。
• 对于 DES，$j = 56$，$n = 64$：
  • 平均需要 $2^{55}$ 次操作来找到正确的密钥。
• 解释：
  • 暴力破解的原理是：对于一个已知的明文/密文对 $(m, c)$，尝试所有可能的密钥 $k$，直到找到一个 $k$ 使得 $DES(m, k) = c$。
  • 由于密钥长度是 56 位，总共有 $2^{56}$ 个可能的密钥，平均需要尝试一半的密钥空间，即 $2^{55}$ 次。
  • 这种方法虽然理论上可行，但计算量巨大，实际操作非常耗时。

更高效的破解方法

1. DES 是一个 Feistel 网络，因此具有补码性质：

• 公式：$DES(\sim m, \sim k) = \sim DES(m, k)$
• 解释：
  • DES 使用 Feistel 网络结构，这是一种对称的加密结构。
  • 补码性质是指：如果用明文 $m$ 的补码 $\sim m$（即对 $m$ 的每一位取反）和密钥 $k$ 的补码 $\sim k$，加密后得到的结果是密文 $DES(m, k)$ 的补码 $\sim DES(m, k)$。
  • 这一性质可以用来优化攻击。

2. 使用选择明文攻击（Chosen Plaintext Attack）来利用补码性质：

• 攻击方法：
  • 给定实际密钥 $K$ 和一个假设密钥 $k$，计算： $$ c_1 = DES(m, k) \quad \text{和} \quad c_2 = DES(\sim m, k) $$
  • 然后检查：
    • 如果 $DES(m, K) \neq c_1$ 或者 $c_2 \neq \sim DES(m, K)$，则： $$ K \neq k \quad \text{或} \quad K \neq \sim k $$
• 解释：
  • 选择明文攻击允许攻击者选择特定的明文 $m$ 并获取对应的密文。
  • 利用补码性质，攻击者可以同时测试密钥 $k$ 和它的补码 $\sim k$。
  • 如果 $DES(m, K) \neq c_1$，说明 $k$ 不是正确的密钥；如果 $c_2 \neq \sim DES(m, K)$，说明 $\sim k$ 也不是正确的密钥。
  • 这样一次测试就可以排除两个密钥（$k$ 和 $\sim k$）。

3. 因此，搜索空间减半：

• 解释：
  • 原本需要测试 $2^{56}$ 个密钥，现在利用补码性质，每次测试可以排除两个密钥（$k$ 和 $\sim k$），因此搜索空间从 $2^{56}$ 减半到 $2^{55}$。
  • 这意味着平均只需要 $2^{54}$ 次操作，而不是 $2^{55}$ 次，效率提高了一倍。

DES 的增强

2DES

• 公式：$2DES_{k_1,k_2}(m) = E_{k_1}(E_{k_2}(m))$
• 解释：
  • 2DES 是指使用两个不同的 56 位密钥 $k_1$ 和 $k_2$，对明文 $m$ 进行两次 DES 加密。
  • 首先用密钥 $k_2$ 加密明文 $m$，得到中间结果 $E_{k_2}(m)$，然后用密钥 $k_1$ 再次加密中间结果，得到最终密文 $E_{k_1}(E_{k_2}(m))$。
  • 理论上，2DES 的密钥长度是 $56 + 56 = 112$ 位，表面上看起来比单次 DES（56 位密钥）更安全。

缺陷

2DES 易受已知明文中途相遇攻击（Meet-in-the-Middle Attack）

• 解释：

  • 尽管 2DES 的密钥长度是 112 位，但它并不能提供 112 位的安全强度，因为它容易受到中途相遇攻击（Meet-in-the-Middle Attack, MITM）。
  • 中途相遇攻击利用了 2DES 的结构（两次加密），通过在“中间”寻找匹配来减少暴力破解的计算量。

攻击步骤

• 步骤 1：为固定明文 $m$，创建所有可能的密文表：
  • 计算 $E_k(m)$，其中 $k$ 是所有可能的 56 位密钥（总共 $2^{56}$ 个密钥）。
  • 将结果存储在一个表中，表的大小是 $2^{56}$。
• 步骤 2：对于给定的密文 $c = E_{k_1,k_2}(m)$，尝试解密：
  • 计算 $D_k(c)$，其中 $D_k$ 是 DES 解密操作，$k$ 也是所有可能的 56 位密钥（$2^{56}$ 个）。
• 步骤 3：寻找匹配：
  • 直到找到一个 $k$ 使得 $D_k(c)$ 出现在步骤 1 的表中。
  • 如果 $D_{k_1}(c) = E_{k_2}(m)$，则 $k_1$ 和 $k_2$ 就是正确的密钥对。
• 解释：
  • 中途相遇攻击的核心思想是：2DES 的加密过程可以分解为两部分——从明文到中间值（由 $k_2$ 加密），和从中间值到密文（由 $k_1$ 加密）。
  • 攻击者从两端（明文和密文）向中间“相遇”：
    • 从明文端：计算 $E_{k_2}(m)$，遍历所有可能的 $k_2$。
    • 从密文端：计算 $D_{k_1}(c)$，遍历所有可能的 $k_1$。
    • 当 $E_{k_2}(m) = D_{k_1}(c)$ 时，说明找到了正确的密钥对 $(k_1, k_2)$。

2DES 可以在平均 $2^{56}$ 次操作内被破解，同时需要 $2^{56}$ 个存储空间（时间-空间权衡）。

• 解释：
  • 暴力破解 2DES 理论上需要尝试 $2^{112}$ 个密钥组合（因为有两个 56 位密钥）。
  • 但中途相遇攻击将复杂度降低到 $2^{56}$ 次操作：
    • 步骤 1 需要 $2^{56}$ 次加密操作来构建表。
    • 步骤 2 需要 $2^{56}$ 次解密操作来寻找匹配。
    • 总共大约是 $2 \times 2^{56} \approx 2^{57}$ 次操作，平均复杂度为 $2^{56}$。
  • 存储需求是 $2^{56}$ 个条目，每个条目存储一个 64 位密文和对应的密钥。
• 结论：2DES 的实际安全强度只有 56 位，而不是 112 位，这使得它并不比单次 DES 安全多少。

3DES

• 公式：$3DES_{k_1,k_2}(m) = E_{k_1}(D_{k_2}(E_{k_1}(m)))$
• 解释：
  • 3DES 使用两个 56 位密钥 $k_1$ 和 $k_2$，对明文 $m$ 进行三次 DES 操作：加密-解密-加密（E-D-E）。
  • 具体步骤：
    1. 用 $k_1$ 加密 $m$，得到 $E_{k_1}(m)$。
    2. 用 $k_2$ 解密上一步的结果，得到 $D_{k_2}(E_{k_1}(m))$。
    3. 再用 $k_1$ 加密，得到最终密文 $E_{k_1}(D_{k_2}(E_{k_1}(m)))$。
  • 总密钥长度是 $56 + 56 = 112$ 位。
  • 为什么要用 E-D-E 结构？这是为了向后兼容：如果 $k_1 = k_2$，3DES 退化为单次 DES（因为 $D_{k_1}(E_{k_1}(m)) = m$，最终结果是 $E_{k_1}(m)$）。

缺陷

• 2016 年发现了 DES/3DES 的一个重大安全漏洞（CVE）。
• 解释：
  • 这里的 CVE（Common Vulnerabilities and Exposures）指的是一个已知的漏洞编号，具体可能是指 2016 年发现的“Sweet32”攻击（CVE-2016-2183）。
  • Sweet32 攻击利用了 DES 和 3DES 的 64 位分组长度（较短），通过生日攻击（Birthday Attack）可以在大量数据加密后（大约 $2^{32}$ 个分组）找到碰撞，从而恢复部分明文。
  • 虽然 3DES 的密钥长度（112 位）比 DES（56 位）更安全，但 64 位分组长度使得它容易受到这种攻击，尤其是在处理大量数据时。

Sweet32 攻击（CVE-2016-2183）

• 适用场景：3DES 使用 64 位分组长度，特别是在 CBC 模式下。
• 攻击原理：
  • Sweet32 是一种生日攻击（Birthday Attack），利用了 3DES 的 64 位分组长度。
  • 当加密大量数据（大约 $2^{32}$ 个分组，约 32GB 数据）时，由于分组长度较短，可能会出现分组碰撞（即两个不同的明文分组加密后得到相同的密文分组）。
  • 在 CBC 模式下，这种碰撞可以被攻击者利用，通过分析密文推断部分明文信息。
• 影响：
  • 攻击者可以在 $2^{32}$ 次操作内恢复部分明文，远低于暴力破解的复杂度。
  • 2016 年发现此漏洞后，3DES 被认为不适合处理大数据量场景。

DESX

• DESX 引入了额外的密钥来增强安全性：
  • $k_1 = 56$ 位（DES 密钥）
  • $k_2 = 64$ 位（白化密钥，Whitening Key）
  • $k_3 = 64$ 位（白化密钥）
• 公式：$DESX_{k_1,k_2,k_3}(m) = k_3 \oplus E_{k_1}(m \oplus k_2)$
• 解释：
  • DESX 通过在 DES 加密前后引入白化密钥（Whitening Key）来增强安全性。
  • 具体步骤：
    1. 将明文 $m$ 与白化密钥 $k_2$ 进行异或（XOR）操作：$m \oplus k_2$。
    2. 用 DES 密钥 $k_1$ 加密上一步的结果：$E_{k_1}(m \oplus k_2)$。
    3. 将加密结果与白化密钥 $k_3$ 进行异或，得到最终密文：$k_3 \oplus E_{k_1}(m \oplus k_2)$。
  • 总密钥长度是 $56 + 64 + 64 = 184$ 位，但实际安全强度取决于具体攻击。

白化密钥增强了对暴力破解的抵抗

• 解释：
  • 白化密钥 $k_2$ 和 $k_3$ 的引入增加了暴力破解的难度。
  • 在普通 DES 中，攻击者可以直接尝试所有 $2^{56}$ 个密钥来匹配明文和密文。
  • 在 DESX 中，由于明文和密文都被白化密钥异或，攻击者需要同时猜测 $k_1$、$k_2$ 和 $k_3$，这增加了攻击的复杂度。
  • 具体来说，DESX 的实际安全强度大约是 $2^{56 + 64 - \log_2(\text{number of known plaintexts})}$，因为白化密钥的效果会因已知明文的数量而减弱。
  • 如果只有少量已知明文，DESX 的安全强度接近 $2^{120}$，远高于 DES 的 $2^{56}$。

AES (Advanced Encryption Standard)

• 1997 年，美国国家标准与技术研究院（NIST）宣布举办一场竞赛，目的是选择一种新的加密算法来取代已经过时的 DES（数据加密标准）。
• 最终选定的算法被命名为高级加密标准（AES）。
• AES 处理的是 128 位（16 字节）的块。
• AES 支持可变密钥长度：
  • 128 位（16 字节）
  • 192 位（24 字节）
  • 256 位（32 字节）
• AES 是一种SP 网络（Substitution-Permutation Network，替换-置换网络），这是块密码的一种常见结构。
• SP 网络通过多轮的替换（Substitution）和置换（Permutation）操作来实现混淆（confusion）和扩散（diffusion），从而增强安全性。
• S-box（替换盒）：
  • AES 使用一个非线性的 S 盒（Substitution box），它是 AES 中唯一的非线性组件。
  • S 盒以字节（8 位）为输入，输出一个字节（8 位），本质上是一个 256 字节的查找表（lookup table）。
  • S 盒的作用是引入非线性，防止线性密码分析（Linear Cryptanalysis）等攻击。
• AES 的设计提供了很强的差分界限（differential bounds）和线性界限（linear bounds）。
• 差分界限和线性界限是指在差分密码分析（Differential Cryptanalysis）和线性密码分析中，攻击者能够利用的概率偏向性（bias）非常小，这意味着 AES 对差分和线性攻击有很强的抵抗力。
• AES 的轮数（rounds）根据密钥长度而变化，轮数越多，加密过程的混淆和扩散效果越强，安全性越高，但计算开销也越大。：
  • 10 轮：128 位密钥
  • 12 轮：192 位密钥
  • 14 轮：256 位密钥

密码分析（Cryptanalysis）

差分密码分析

1. 优于暴力破解
   差分密码分析是一种比暴力破解更高效的攻击方法，专门针对 DES（Data Encryption Standard）等分组密码。暴力破解需要尝试所有可能的密钥，而差分密码分析利用了算法的结构特性来减少密钥搜索空间。

2. 利用已知明文攻击（CPA）
   这种攻击方法需要使用已知明文攻击（Chosen Plaintext Attack, CPA），即攻击者可以选择特定的明文并获取对应的密文。攻击的核心在于分析明文和密文的 XOR（异或） 关系。

3. S-Box 函数的差分定义
   在 DES 中，S-Box（Substitution Box）是一个核心组件，用于将输入比特映射到输出比特。差分密码分析关注 S-Box 的输入和输出的差分特性：

   • 给定 S-Box 函数 $F’(x, k_i)$，其中 $x$ 是输入，$k_i$ 是轮密钥。
   • 定义两个输入 $b_1$ 和 $b_2$ 的差分： $$ \Delta = b_1 \oplus b_2 $$ 其中 $\oplus$ 表示 XOR 操作。
   • 进一步推导： $$ \Delta = (x_1 \oplus k_i) \oplus (x_2 \oplus k_i) = x_1 \oplus x_2 $$ 这里 $x_1$ 和 $x_2$ 是扩展函数（Expansion Function, E）的输出。可以看到，输入差分 $\Delta$ 不依赖于密钥 $k_i$，但输出差分 $e_1 \oplus e_2$ 仍然会受到密钥的影响。

示例

1. 定义输入差分集合 $\Delta(b)$

• 假设输入 $b_1$ 和 $b_2$ 是 6 比特的（因为 DES 的 S-Box 输入是 6 比特）。
• 因此，$b_1$ 和 $b_2$ 各有 $2^6 = 64$ 种可能取值，差分 $b_1 \oplus b_2$ 也有 64 种可能。
• 集合 $\Delta(b)$ 包含所有满足 $b_1 \oplus b_2 = b$ 的输入对 $(b_1, b_2)$，总共有 64 对。

2. 给定差分 $b_1 \oplus b_2 = 110100$

• 如果输入差分是 $110100$，则 $\Delta(b)$ 包含以下对： [ \Delta(b) = { (000000, 110100), (000001, 110101), \ldots, (111111, 001011) } ] 这些对是通过将 $b_1$ 从 $000000$ 到 $111111$ 遍历，并计算 $b_2 = b_1 \oplus 110100$ 得到的。

3. 输出差分的分布

• 对于 $\Delta(b)$ 中的所有 64 对，计算 S-Box 的输出差分 $e_1 \oplus e_2$。
• 统计结果显示：
  • 输出差分 $0000$: 0 次
  • 输出差分 $0001$: 8 次
  • 输出差分 $1111$: 6 次
  • 等等。
• 由于 $e_1 \oplus e_2$ 的值是有限的（4 比特输出，16 种可能），64 对输入对的输出差分分布并不是均匀的，而是有偏的（某些差分值出现次数更多）。

4. 利用差分特性推导密钥

• 如果 $b_1 \oplus b_2 = 110100$ 且 $e_1 \oplus e_2 = 0001$，那么 $(b_1, b_2)$ 必须是那 8 个输出差分为 $0001$ 的对之一。
• 因此，$b_1$ 只能是 16 种可能值之一（因为每对 $(b_1, b_2)$ 中 $b_1$ 是固定的）。
• 在 DES 中，$b_1 = x_1 \oplus k_i$，其中 $x_1$ 是已知的（因为明文是已知的，扩展函数 E 是固定的）。因此，$k_i$ 也有 16 种可能值。
• 通过多次使用不同的差分 $\Delta$，可以进一步缩小 $k_i$ 的可能取值范围，最终推导出密钥。

线性密码分析

线性密码分析是一种密码攻击技术，目标是找到密码算法中明文（plaintext）、密文（ciphertext）和密钥（key）之间的线性关系。

• 密文是通过明文和密钥的某些位（bits）以某种方式组合生成的。
• 如果密码算法是线性的（即密文可以通过明文和密钥的线性组合直接计算），那么它很容易被破解。
• 线性关系通常表现为异或操作（⊕），因为异或是一种线性运算。

例子

• 给出了一个具体的线性关系： $$ c[1] = p[4] \oplus p[17] \oplus k[5] \oplus k[3] $$

  • $c[1]$ 表示密文的第 1 位。
  • $p[4]$ 和 $p[17]$ 分别是明文的第 4 位和第 17 位。
  • $k[5]$ 和 $k[3]$ 分别是密钥的第 5 位和第 3 位。
  • $\oplus$ 表示异或操作（XOR）。

• 这意味着密文的第 1 位可以通过明文的第 4 位、第 17 位和密钥的第 5 位、第 3 位异或得到。

• 通过上述线性关系，可以进一步推导出密钥的某些位： [ k[3] \oplus k[5] = c[1] \oplus p[4] \oplus p[17] ]

  • 这一步是将等式中的 $k[3] \oplus k[5]$ 移到一边，得到一个关于密钥位的表达式。
  • 如果攻击者知道明文 $p[4]$、$p[17]$ 和密文 $c[1]$，就可以计算出 $k[3] \oplus k[5]$ 的值。
  • 虽然这并不能直接得到 $k[3]$ 和 $k[5]$ 的具体值，但它提供了一个关于密钥的约束条件。

填充（Padding）

将明文分成固定大小的块（例如 64 位或 128 位）进行加密。由于明文的长度不一定是块大小的整数倍，因此需要对明文进行填充以满足块密码的要求。

• ANSI X9.23
• PKCS#5 and PKCS#7

操作模式（Modes of Operation）

待加密的消息长度通常远远大于块大小，因此需要通过特定的操作模式来处理长消息。

电子密码本模式（ECB，Electronic Code Book）

ECB 模式是最简单的块密码操作模式，但由于其固有的安全缺陷，在实际应用中几乎不再使用。

• ECB 模式的工作方式：

  • ECB 模式将明文分成固定大小的块（例如，DES 的块大小为 64 位，AES 为 128 位）。
  • 每个明文块 $m_i$ 独立地使用同一密钥 $k$ 进行加密，生成对应的密文块 $c_i$： $$ c_i = E_k(m_i) $$
  • 解密时，同样独立地对每个密文块解密： $$ m_i = D_k(c_i) $$
  • 图中展示了这一过程：
    • 明文块 $m_0, m_1, …, m_8$ 分别通过加密函数 $E_k$ 转换为密文块 $c_0, c_1, …, c_8$。

• 特点：

  • 每个块的加密是独立的，不依赖于其他块。
  • 因此，ECB 模式可以看作一种替换密码（Substitution Cipher），只是替换的单位是块（block）而不是单个字母。

ECB 模式的属性

1. 相同明文块产生相同密文块（Identical plaintext blocks result in identical ciphertext blocks）
2. 密文块重排会导致明文块重排（A reordering of ciphertext blocks results in reordering of plaintext blocks）
3. 局部错误传播（Local error propagation）

密码块链接模式（CBC，Cipher Block Chaining）

CBC 模式通过引入链式依赖和初始向量（IV），解决了 ECB 模式的模式泄露问题，是块密码中较为安全且常用的操作模式之一。

CBC 模式加密

• 链式依赖：

  • CBC 模式通过异或（XOR）操作将块“链接”在一起。
  • 每个明文块在加密前与前一个密文块异或，第一个块与初始向量（IV）异或。

• 加密过程：

  • 明文被分成固定大小的块：$m_0, m_1, m_2, …, m_n$。
  • 使用一个密钥 $k$ 和一个初始向量 $IV$（IV 的大小与块大小相同，例如，AES 为 128 位）。
  • 加密公式：
    • 第一个块：$c_0 = E_k(m_0 \oplus IV)$
    • 后续块：$c_i = E_k(m_i \oplus c_{i-1})$，其中 $i \geq 1$。
  • 图中展示了这一过程：
    • 明文块 $m_0$ 与 $IV$ 异或后，通过 $E_k$ 加密生成 $c_0$。
    • 明文块 $m_1$ 与 $c_0$ 异或后，通过 $E_k$ 加密生成 $c_1$。
    • 依此类推，直到最后一个块。

• 初始向量（IV）：

  • IV 是一个随机值，与块大小相同。
  • IV 的作用是确保即使相同的明文和密钥被多次加密，生成的密文也不同（即提供随机化）。
  • IV 不需要保密，可以与密文一起公开传输，但必须是随机的且不可预测。

CBC 模式解密

• 解密过程：
  • 解密时，需要相同的密钥 $k$ 和初始向量 $IV$。
  • 解密公式：
    • 第一个块：$m_0 = D_k(c_0) \oplus IV$
    • 后续块：$m_i = D_k(c_i) \oplus c_{i-1}$，其中 $i \geq 1$。
  • 图中展示了这一过程：
    • 密文块 $c_0$ 通过 $D_k$ 解密后，与 $IV$ 异或，得到 $m_0$。
    • 密文块 $c_1$ 通过 $D_k$ 解密后，与 $c_0$ 异或，得到 $m_1$。
    • 依此类推。

CBC 模式的属性

随机化（IV 的作用）

• 相同明文和密钥不会产生相同密文：

  • 如果使用相同的密钥 $k$ 和相同的明文 $m$，但每次使用不同的随机 IV，生成的密文会不同。
  • 这是因为第一个块的加密依赖于 IV，而后续块通过链式依赖受到 IV 的影响。
  • 例如：
    • 第一次加密：$IV_1$，密文为 $c_0, c_1, …$。
    • 第二次加密：$IV_2$，密文为 $c_0’, c_1’, …$，且 $c_0 \neq c_0’$。
  • 解决的问题：
    • 避免了 ECB 模式的模式泄露问题（相同明文块产生相同密文块）。
    • 即使明文中有重复的块，密文也不会重复。

• 改变 $k$, $IV$, 或 $m_0$ 可以解决重复问题：

  • 如果需要加密相同的明文，可以通过改变密钥 $k$、初始向量 $IV$，或第一个明文块 $m_0$，确保密文不同。
  • 在实际应用中，通常通过使用随机 IV 来实现这一点（密钥 $k$ 通常固定）。

链式依赖

• 密文块依赖于所有之前的明文块：

  • 每个密文块 $c_i$ 依赖于当前明文块 $m_i$ 和前一个密文块 $c_{i-1}$。
  • 通过链式依赖，$c_i$ 间接依赖于所有之前的明文块 $m_0, m_1, …, m_{i-1}$。
  • 例如，$c_2 = E_k(m_2 \oplus c_1)$，而 $c_1 = E_k(m_1 \oplus c_0)$，$c_0 = E_k(m_0 \oplus IV)$，因此 $c_2$ 依赖于 $m_0, m_1, m_2$ 和 $IV$.

• 重排密文块会影响解密：

  • 由于链式依赖，如果攻击者重排密文块（例如，将 $c_0, c_1, c_2$ 重排为 $c_1, c_0, c_2$），解密后的明文块会完全错误。
  • 例如：
    • 原始密文：$c_0, c_1, c_2$。
    • 解密：$m_0 = D_k(c_0) \oplus IV$，$m_1 = D_k(c_1) \oplus c_0$，$m_2 = D_k(c_2) \oplus c_1$。
    • 重排后：$c_1, c_0, c_2$。
    • 解密：$m_0’ = D_k(c_1) \oplus IV$，$m_1’ = D_k(c_0) \oplus c_1$，$m_2’ = D_k(c_2) \oplus c_0$，结果完全错误。
  • 解决的问题：
    • 防止了 ECB 模式中的重排攻击（ECB 模式下重排密文块只会重排明文块）。

错误传播（Error Propagation）

• 密文错误只影响两个明文块：

  • 如果密文块 $c_j$ 发生位错误（bit error），解密时会影响两个明文块：
    1. 当前块 $m_j$：
       • $m_j = D_k(c_j) \oplus c_{j-1}$。
       • 如果 $c_j$ 有错误，$D_k(c_j)$ 会变成随机值（标记为“rnd”），导致 $m_j$ 变成乱码。
    2. 下一个块 $m_{j+1}$：
       • $m_{j+1} = D_k(c_{j+1}) \oplus c_j$。
       • $c_j$ 的错误会直接影响 $m_{j+1}$，但这种影响是可预测的（predictable）：
         • 错误的位会直接传播到 $m_{j+1}$ 的对应位。
         • 例如，如果 $c_j$ 的第 5 位翻转，$m_{j+1}$ 的第 5 位也会翻转。
  • 图中展示了这一过程：
    • 密文块 $c_1$ 发生错误（标记为“Err”）。
    • 解密后：
      • $m_1 = D_k(c_1) \oplus c_0$，由于 $c_1$ 错误，$m_1$ 变成随机值（“rnd”）。
      • $m_2 = D_k(c_2) \oplus c_1$，由于 $c_1$ 错误，$m_2$ 的某些位会发生可预测的翻转（“predictable”）。
      • 后续块 $m_3, m_4$ 不受影响。

• 自同步（Self-Synchronizing）：

  • CBC 模式具有自同步特性：
    • 如果密文块 $c_j$ 发生错误，只有 $m_j$ 和 $m_{j+1}$ 受到影响。
    • 从 $m_{j+2}$ 开始，解密恢复正常：$m_{j+2} = D_k(c_{j+2}) \oplus c_{j+1}$。
    • 例如，图中 $c_1$ 错误，影响 $m_1$ 和 $m_2$，但 $m_3, m_4$ 正确解密。
  • 意义：
    • 错误传播是有限的（只影响两个块），适合需要错误恢复的场景。

• 攻击者可以利用错误传播：

  • 由于 $c_j$ 的错误会以可预测的方式影响 $m_{j+1}$，攻击者可以故意修改 $c_j$，控制 $m_{j+1}$ 的某些位。
  • 例如，攻击者将 $c_j$ 的第 5 位翻转，$m_{j+1}$ 的第 5 位也会翻转。
  • 安全问题：
    • 这种特性可能被用于攻击（例如，填充预言机攻击，Padding Oracle Attack），需要额外的完整性保护（如 MAC）。

加密和解密的并行性

• 加密必须串行：
  • 加密时，每个密文块 $c_i$ 依赖于前一个密文块 $c_{i-1}$，因此必须按顺序计算，无法并行。
• 解密可以并行：
  • 解密时，每个明文块 $m_i$ 只需要 $c_i$ 和 $c_{i-1}$，这些值在解密开始时已知。
  • 因此，可以同时计算所有 $D_k(c_i)$，然后并行执行异或操作。

Output Feedback (OFB)

OFB 模式的核心是将块密码转化为流密码，通过生成一个密钥流（keystream），然后将明文与密钥流进行异或操作来生成密文。下面是详细步骤：

1. 初始化：

   • OFB 模式需要一个初始化向量（IV）和一个密钥 $k$。
   • IV 是一个随机值，用于确保每次加密的密钥流不同，即使明文和密钥相同。

2. 生成密钥流：

   • 首先，IV 被输入到块密码的加密函数 $E_k$ 中，生成第一个输出块（图中未直接标记为密钥流，但它是 $E_k(IV)$ 的结果）。
   • 这个输出块被再次输入到 $E_k$ 中，生成第二个输出块。
   • 这个过程不断重复，生成一个连续的密钥流。
     例如：
     • 第一次：$O_0 = E_k(IV)$
     • 第二次：$O_1 = E_k(O_0)$
     • 第三次：$O_2 = E_k(O_1)$
     • 以此类推。

3. 加密过程：

   • 密钥流 $O_0, O_1, O_2, \ldots$ 与明文块 $m_0, m_1, m_2, \ldots$ 进行按位异或操作，生成密文：
     • $C_0 = m_0 \oplus O_0$
     • $C_1 = m_1 \oplus O_1$
     • $C_2 = m_2 \oplus O_2$
     • 以此类推。

4. 解密过程：

   • 解密时，接收方使用相同的 IV 和密钥 $k$，按照同样的步骤生成相同的密钥流。
   • 然后将密文与密钥流异或，恢复明文：
     • $m_0 = C_0 \oplus O_0$
     • $m_1 = C_1 \oplus O_1$
     • 以此类推。

属性

1. 相同的明文在使用相同的密钥和 IV 加密时会产生相同的密文

• 解释：
  • 在 OFB 模式中，密钥流（keystream）的生成完全依赖于初始化向量（IV）和密钥（key），而与明文无关。
  • 如果使用相同的 IV 和密钥，生成的密钥流是固定的。因此，相同的明文与相同的密钥流进行异或操作（XOR）后，必然产生相同的密文。
  • 安全隐患：这意味着如果攻击者知道明文和对应的密文（例如通过已知明文攻击），并且 IV 和密钥被重复使用，攻击者可以推导出密钥流，进而破解其他密文。

2. 链式依赖：（与流密码相同）密钥流与明文无关

• 解释：
  • OFB 模式生成的密钥流不依赖于明文或密文，而是通过反复加密 IV（初始化向量）生成的。
  • 具体来说，密钥流是通过以下方式生成的：
    • 第一次：$O_0 = E_k(IV)$
    • 第二次：$O_1 = E_k(O_0)$
    • 第三次：$O_2 = E_k(O_1)$
    • 以此类推。
  • 由于密钥流只依赖于 IV 和密钥，与明文无关，因此 OFB 模式没有链式依赖（不像 CBC 模式那样每个密文块依赖于前一个明文块）。
  • 意义：这使得 OFB 模式更像一个流密码，加密过程可以独立于明文进行。

3. 错误传播：（与流密码相同）密文块中的位错误会导致明文中相同位置的错误

• 解释：
  • 在 OFB 模式中，密文是通过明文与密钥流异或生成的：$C_i = m_i \oplus O_i$。
  • 解密时，接收方使用相同的密钥流将密文还原为明文：$m_i = C_i \oplus O_i$。
  • 如果密文 $C_i$ 中的某一位发生错误（例如由于传输中的噪声），那么在解密时，这一错误会直接影响明文 $m_i$ 的对应位。
  • 特点：错误不会传播到后续的明文块，只会影响当前块的对应位。这与流密码的特性一致。
  • 对比：在 CBC 模式中，一个密文块的错误会影响当前块和下一个块的解密，而在 OFB 模式中，错误是局部的。

4. 错误恢复：（与流密码相同）可以从位错误中恢复，但不能从位丢失（密钥流失调）中恢复

• 解释：
  • 位错误（bit errors）：如上所述，密文中的位错误只会影响解密后明文的对应位，后续的明文块不会受到影响。因此，OFB 模式可以从位错误中“恢复”，即错误不会扩散。
  • 位丢失（bit loss）：如果密文在传输过程中丢失了一些位（例如插入或删除位，导致密文长度变化），接收方生成的密钥流与密文的对齐就会出现偏差（misalignment）。由于 OFB 模式是同步流密码，密钥流和密文的对齐是固定的，一旦失调，后续所有明文块都会解密错误，无法恢复。
  • 意义：这表明 OFB 模式对同步性要求很高，适用于可靠的传输环境（如无丢包的网络），但不适合容易发生位丢失的场景。

5. 吞吐量：密钥流可以独立计算——例如，预计算——在加密/解密之前，从而实现并行化

• 解释：
  • 在 OFB 模式中，密钥流的生成不依赖于明文或密文，只依赖于 IV 和密钥。因此，密钥流可以在加密或解密之前预先计算。
  • 例如，发送方可以在知道 IV 和密钥的情况下，提前生成整个密钥流 $O_0, O_1, O_2, \ldots$，然后在需要加密时直接将明文与密钥流异或。
  • 并行化：由于密钥流是预计算的，加密和解密过程（即异或操作）可以并行执行。例如，可以同时对多个明文块 $m_0, m_1, m_2, \ldots$ 进行异或操作，提高吞吐量。
  • 意义：这使得 OFB 模式在需要高吞吐量的场景中非常高效，例如实时通信或流媒体加密。

6. IV 必须改变。否则，它会变成一次性密码本（two time pad）

• 解释：
  • 在 OFB 模式中，密钥流是由 IV 和密钥生成的。如果在多次加密中重复使用相同的 IV 和密钥，生成的密钥流将是相同的。
  • 如果相同的密钥流被用来加密不同的明文（即“two time pad”），这会导致严重的安全问题：
    • 假设攻击者获得了两组密文 $C_1 = m_1 \oplus O$ 和 $C_2 = m_2 \oplus O$，其中 $O$ 是相同的密钥流。
    • 攻击者可以计算 $C_1 \oplus C_2 = (m_1 \oplus O) \oplus (m_2 \oplus O) = m_1 \oplus m_2$，从而得到两个明文的异或结果。
    • 通过分析 $m_1 \oplus m_2$，攻击者可能推导出明文信息（例如，如果明文是自然语言，异或结果可能暴露模式或结构）。
  • 一次性密码本（one-time pad）：理论上，流密码的安全性依赖于密钥流的一次性使用。如果密钥流被重复使用（即“two time pad”），安全性会大幅下降。
  • 解决方法：每次加密时必须使用一个新的、随机的 IV，确保生成的密钥流是唯一的，从而避免“two time pad”问题。

Counter Mode (CTR)

CTR 模式通过计数器生成不同的输入（IV + 计数器），使得每个块的加密独立，类似于流加密。

工作流程

1. 输入：

   • IV（初始化向量）：一个初始值，通常是随机的，用于确保加密的唯一性。
   • CTR（计数器）：从 $CTR_0$ 开始，依次递增为$CTR_1$, $CTR_2$, $CTR_3$, $CTR_4$等。计数器可以是简单的递增整数，也可以是伪随机数生成器（PRNG）生成的序列。
   • 明文块：明文被分成多个块，标记为$m_0$, $m_1$, $m_2$, $m_3$, $m_4$。

2. 加密过程：

   • 每个计数器值（$CTR_i$）与初始化向量（IV）结合（通常是简单的拼接或异或操作）。
   • 然后，这个组合值通过块加密算法（标记为$E_k$，表示使用密钥$k$进行加密）生成一个密钥流（key stream）。
   • 密钥流与对应的明文块（$m_i$）进行**异或（XOR）**操作，生成密文块（$c_i$）。

3. 输出：

   • 密文块：$c_0$, $c_1$, $c_2$, $c_3$, $c_4$。

属性

1. 当使用相同的密钥和 IV 加密相同的明文时，会得到相同的密文
   CTR 模式是确定性的（deterministic）。如果密钥和 IV 相同，生成的密钥流是固定的，因此相同的明文总是产生相同的密文。这是一个潜在的安全风险，因为攻击者可能通过分析密文模式发现明文的重复性。

2. 链式依赖：（与流加密相同）密钥流与明文无关
   CTR 模式中，密钥流仅由 IV、计数器和密钥生成，与明文内容无关。这意味着每个块的加密是独立的，不像 CBC（Cipher Block Chaining）模式那样依赖前一个块的密文。这种独立性使得 CTR 模式可以并行处理。

3. 错误传播：（与流加密相同）密文块中的位错误会导致明文相同位置的错误
   由于 CTR 模式使用异或操作，如果密文中的某一位发生错误（例如传输过程中翻转），解密时该位也会在明文中翻转，但不会影响其他块。这种错误传播特性与流加密相同，相比 CBC 模式（错误会传播到后续块）更可控。

4. 错误恢复：（与流加密相同）可以从位错误中恢复，但不能从位丢失（密钥流错位）中恢复
   如果只是密文中的位错误，解密后只会影响对应位。但如果密文丢失了一些位，导致密钥流和密文的对齐出错（misalignment），后续所有块的解密都会失败。

5. 吞吐量：加密和解密都可以随机访问和/或并行化，这是我们能期望的最好结果
   由于每个块的加密是独立的（不依赖前一个块），CTR 模式支持并行处理和随机访问（可以直接解密任意块）。这使得 CTR 模式在性能上非常高效，适合高吞吐量场景。

6. IV 必须改变。否则，它会变成“一次性密码本”（two time pad）
   如果在多次加密中重复使用相同的 IV 和密钥，生成的密钥流会相同。攻击者可以利用这一点，通过异或操作分析出明文（类似于一次性密码本被重用时的安全漏洞）。因此，每次加密必须使用新的 IV。

7. OFB 和 CTR 模式有相似的属性，因为它们都使块加密算法表现为流加密算法
   OFB（Output Feedback Mode）和 CTR 模式都通过生成独立的密钥流来实现流加密的效果。两者的主要区别在于密钥流的生成方式：OFB 通过反馈前一个加密输出生成密钥流，而 CTR 通过计数器生成。

Galois/Counter Mode (GCM)

• 它基于 CTR 模式（计数器模式），但增加了数据完整性验证的功能，因此不仅仅是一个加密模式

  • 传统的加密模式（如 CTR 模式）只负责将明文加密为密文，但无法检测密文在传输或存储过程中是否被篡改。
  • GCM 模式不仅加密数据，还生成一个 认证标签（authentication tag），用于验证密文和相关数据的完整性。
  • 如果密文被篡改，解密时通过认证标签的验证会失败，从而检测到篡改行为。
  • 这种特性使 GCM 成为一种 认证加密（Authenticated Encryption, AE） 模式，提供了 机密性（confidentiality） 和 完整性（integrity） 两方面的保护。

• 与 HMAC 不同，GCM 是可并行化的（你不能将两个 HMAC 组合成一个更大的 HMAC）

  • HMAC（Hash-based Message Authentication Code） 是一种基于哈希函数（如 SHA-256）的消息认证码。HMAC 的计算是串行的：你需要按顺序处理所有数据块，生成一个最终的哈希值。因此，HMAC 不支持并行计算。
  • GCM 的认证标签计算基于 Galois 域运算，这种运算可以并行化。也就是说，GCM 可以同时处理多个密文块，分别计算它们的贡献，最后将结果组合起来生成认证标签。
  • 此外，HMAC 的设计不允许将两个独立的 HMAC 值直接组合成一个更大的 HMAC（因为哈希函数的不可逆性）。而 GCM 的 Galois 域运算允许这种组合，计算效率更高。

• GCM 用于低延迟、高吞吐量的专用硬件应用（网络数据包）

  • GCM 的并行化特性（继承自 CTR 模式）和高效的认证机制使其非常适合需要快速处理的场景。
  • 低延迟（low-latency）：GCM 的加密和认证过程可以并行执行，减少了处理时间。
  • 高吞吐量（high-throughput）：GCM 可以在硬件中高效实现（例如通过 AES-NI 指令集），适合处理大量数据。
  • 专用硬件应用（dedicated hardware applications）：GCM 常用于网络通信（如 TLS/SSL 协议）中加密和验证网络数据包（network packets）。例如，HTTPS 连接中常用的 AES-GCM 就是 GCM 模式与 AES 加密算法的组合。

评估标准

为了评估一个块密码（如 DES、AES）和它的操作模式（如 ECB、CBC、CTR 等），需要从以下五个方面进行分析：

1. 密钥大小（Key Size）：

   • 定义：密钥大小是指块密码使用的密钥的位数（例如，DES 的密钥大小为 56 位，AES 可以是 128 位、192 位或 256 位）。
   • 评估要点：
     • 密钥大小决定了密码的上界安全性。更大的密钥意味着更高的安全性，因为暴力破解（Brute-Force Attack）所需的时间随着密钥大小指数级增长。
     • 例如，56 位密钥（如 DES）在现代计算能力下可以被暴力破解（大约需要 $2^{56}$ 次尝试），而 128 位密钥（如 AES-128）需要 $2^{128}$ 次尝试，远远超出现有计算能力。
   • 代价：
     • 更大的密钥会增加成本，包括：
       • 生成成本：生成更长的随机密钥需要更多的计算资源。
       • 存储成本：更大的密钥需要更多的存储空间。
       • 分发成本：在安全协议中，分发更长的密钥可能增加通信开销。
   • 与操作模式的关系：密钥大小只与块密码本身相关，与操作模式无关。

2. 块大小（Block Size）：

   • 定义：块大小是指块密码一次处理的明文/密文块的位数（例如，DES 的块大小为 64 位，AES 的块大小为 128 位）。
   • 评估要点：
     • 更大的块大小可以减少开销（overhead）：
       • 块大小小会导致需要处理更多的块，增加填充（padding）和操作模式的计算开销。
       • 例如，AES 的 128 位块（16 字节）比 DES 的 64 位块（8 字节）需要更少的块来处理相同大小的消息。
     • 更大的块大小也可能提高安全性：
       • 小块大小（如 64 位）可能导致“块碰撞”（block collision），即在大量数据中，相同的明文块可能重复出现，泄露模式信息（尤其在 ECB 模式下）。
       • 更大的块大小（如 128 位）降低了块碰撞的概率。
   • 代价：
     • 更大的块大小会增加计算成本：
       • 块密码的加密/解密算法通常与块大小相关，块越大，计算复杂度越高。
       • 例如，AES 的每一轮需要更多的操作来处理 128 位块，相比 DES 的 64 位块。
   • 与操作模式的关系：块大小只与块密码本身相关，与操作模式无关。

3. 估计的安全性水平（Estimated Security Level）：

   • 定义：安全性水平是指块密码和操作模式在面对已知攻击时的实际安全强度。
   • 评估要点：
     • 理论上的安全性（由密钥大小决定）可能高于实际安全性。
     • 实际安全性取决于块密码的结构设计和操作模式的弱点。
     • 例如：
       • DES 的理论安全性是 56 位，但由于差分密码分析（Differential Cryptanalysis）和线性密码分析（Linear Cryptanalysis）等攻击，实际安全性降低到大约 40-50 位。
       • AES-128 的理论安全性是 128 位，目前没有已知的实用攻击能显著降低其安全性。
     • 操作模式也会影响安全性：
       • ECB 模式容易泄露明文模式（如相同明文块产生相同密文块），安全性较低。
       • CBC 模式通过引入初始向量（IV）和链式依赖提高了安全性，但可能受到填充预言机攻击（Padding Oracle Attack）。
   • 与操作模式的关系：安全性水平同时受到块密码和操作模式的影响。

4. 吞吐量（Throughput）：

   • 定义：吞吐量是指块密码和操作模式在加密/解密时的速度（例如，每秒处理的字节数）。
   • 评估要点：
     • 加密/解密速度：
       • 块密码本身的算法复杂度影响速度。例如，AES 比 DES 更快，因为 AES 设计时考虑了硬件优化（如 S 盒可以用查找表实现）。
       • 操作模式也会影响速度。例如，ECB 和 CTR 模式支持并行加密（因为每个块独立），而 CBC 模式是串行的（每个块依赖前一个块的密文）。
     • 预计算：
       • 某些操作模式（如 CTR、OFB）可以预计算加密输出（例如，预先生成计数器的加密值），从而加速异或操作。
     • 例如，在 CTR 模式中，$E_k(Nonce || Counter_i)$ 可以提前计算，加密时只需异或操作。
     • 预计算可以显著提高吞吐量，尤其在高吞吐量场景（如网络加密）中。
     • 并行性：
       • 并行性是指是否可以同时加密/解密多个块。
       • ECB、CTR 模式支持并行处理，适合多核处理器。
       • CBC、CFB 模式是串行的，无法并行。
   • 与操作模式的关系：吞吐量同时受到块密码和操作模式的影响。

5. 错误传播（Error Propagation）：

   • 定义：错误传播是指在密文传输过程中，如果发生位错误（bit error）或位丢失（bit loss），对解密后明文的影响。
   • 评估要点：
     • 不同的操作模式对错误的处理方式不同：
       • ECB 模式：一个密文块的错误只会影响对应的明文块（错误不传播）。
       • CBC 模式：
         • 加密：一个明文块的错误会影响当前密文块和后续所有密文块。
         • 解密：一个密文块的错误会影响当前明文块和下一个明文块（因为解密时需要与前一个密文块异或）。
       • CFB 模式：
         • 加密：一个明文块的错误会影响当前密文块和后续所有密文块。
         • 解密：一个密文块的错误会影响当前明文块和后续若干明文块（直到错误影响的密文块被移出反馈窗口）。
       • OFB 模式：一个密文块的错误只影响当前明文块（错误不传播）。
       • CTR 模式：一个密文块的错误只影响当前明文块（错误不传播）。
     • 位丢失：
       • 如果密文丢失了一个块（例如，传输过程中丢包），某些模式（如 CBC、CFB）需要同步，可能会导致后续所有块无法正确解密。
       • CTR、OFB 模式可以通过计数器或预计算值恢复同步，影响较小。
   • 与操作模式的关系：错误传播主要由操作模式决定，与块密码本身无关。

密钥交换（Key Exchange）

Diffie-Hellman

Diffie-Hellman 密钥交换（由 Whitfield Diffie 和 Martin Hellman 在 1976 年提出，Stanford 指的是他们的研究背景）是一种非对称加密协议，但它的主要目的是让两个通信方（通常称为 Alice 和 Bob）通过不安全的信道（如互联网）建立一个共享的密钥。这个共享密钥可以用于后续的对称加密通信（比如 AES 加密）。

核心思想

1. Alice 和 Bob 同意一个公共数字 $g$

• Alice 和 Bob 首先需要公开地协商两个公共参数：
  • 一个大素数 $p$（模数，modulus）
  • 一个生成元 $g$（generator，通常是一个小于 $p$ 的整数，这个数可以很小）
• 这些参数 $p$ 和 $g$ 是公开的，任何人都可以知道，包括潜在的窃听者（eavesdropper）。

2. Alice 生成一个随机数 $a$，并发送 $g^a$ 给 Bob

• Alice 私下选择一个随机数 $a$，这个 $a$ 是她的私钥，只有她自己知道。
• 她计算 $g^a \mod p$，然后将结果发送给 Bob。
• 注意：这里发送的是 $g^a \mod p$，而不是 $a$ 本身。$g^a \mod p$ 是公开的，窃听者可以看到。

3. Bob 生成一个随机数 $b$，并发送 $g^b$ 给 Alice

• Bob 也私下选择一个随机数 $b$，这个 $b$ 是他的私钥，只有他自己知道。
• 他计算 $g^b \mod p$，然后将结果发送给 Alice。
• 同样，$g^b \mod p$ 是公开的，窃听者也可以看到。

4. Alice 和 Bob 各自计算共享密钥 $g^{ab}$

• Alice 收到 Bob 的 $g^b \mod p$，她用自己的私钥 $a$ 计算： $$ (g^b)^a \mod p = g^{ab} \mod p $$
• Bob 收到 Alice 的 $g^a \mod p$，他用自己的私钥 $b$ 计算： $$ (g^a)^b \mod p = g^{ab} \mod p $$
• 由于 $(g^b)^a = (g^a)^b = g^{ab}$，Alice 和 Bob 最终都得到了相同的共享密钥 $g^{ab} \mod p$。
• 这个共享密钥 $g^{ab} \mod p$ 可以用来加密他们后续的通信。

此处牵扯到一个问题，实际上 Alice 得到的是 $g^b \mod p$，她进行的计算是 $(g^b \mod p)^a \mod p$，为什么 $(g^b \mod p)^a \mod p = (g^b)^a \mod p$？

模运算的性质
要理解这个等式，我们需要知道模运算的一些基本性质：

1. 模运算的分配律： 对于任意整数 $x, y$ 和模数 $p$，有：

   $$ (x \mod p) \cdot (y \mod p) \mod p = (x \cdot y) \mod p $$

   也就是说，模运算可以在乘法中“提前”或“延后”进行。

2. 模运算的幂运算性质： 对于任意整数 $x, a$ 和模数 $p$，有： $$ (x \mod p)^a \mod p = x^a \mod p $$ 这意味着，在计算幂 $x^a$ 时，可以先对 $x$ 取模，然后再计算幂，最后再取模，结果与直接计算 $x^a \mod p$ 是相同的。

让我们更深入地看一下（抛开定义从数学角度）：

• 假设 $g^b = m \cdot p + k$，其中 $k = g^b \mod p$，$m$ 是某个整数（即 $g^b$ 除以 $p$ 的商）。
• 那么： $$ (g^b \mod p)^a = k^a $$
• 我们需要计算 $k^a \mod p$，并将其与 $(g^b)^a \mod p$ 比较。
• 注意到 $(g^b)^a = (m \cdot p + k)^a$。根据二项式定理展开： $$ (m \cdot p + k)^a = \sum_{i=0}^a \binom{a}{i} (m \cdot p)^{a-i} k^i $$
• 取模 $p$ 后，任何包含 $p$ 的项（即 $i < a$ 的项）都会变成 0，因为它们都包含 $p$ 的因子。所以： $$ (m \cdot p + k)^a \mod p = k^a \mod p $$
• 因此： $$ (g^b \mod p)^a \mod p = k^a \mod p = (g^b)^a \mod p $$

为什么这个方法是安全的？

1. 窃听者能看到什么？

• 窃听者（eavesdropper）可以拦截到以下信息：
  • 公共参数 $p$ 和 $g$
  • Alice 发送的 $g^a \mod p$
  • Bob 发送的 $g^b \mod p$
• 但是，窃听者无法直接看到 Alice 的私钥 $a$ 或 Bob 的私钥 $b$，也不知道最终的共享密钥 $g^{ab} \mod p$。

2. 离散对数问题的难度

• 要从 $g^a \mod p$ 反推出 $a$，或者从 $g^b \mod p$ 反推出 $b$，需要解决离散对数问题（Discrete Logarithm Problem）。
• 离散对数问题在数学上被认为是“困难的”，尤其是在 $p$ 是一个很大的素数时。即使有了 $g$、$p$、$g^a \mod p$，计算 $a$ 的过程需要非常大的计算量，现代计算机无法在合理的时间内完成。
• 因此，窃听者无法通过已知信息计算出 $a$ 或 $b$，也就无法计算出共享密钥 $g^{ab} \mod p$。

3. 共享密钥的安全性

• 由于 $a$ 和 $b$ 是 Alice 和 Bob 各自的私钥，只有他们能计算出 $g^{ab} \mod p$。
• 窃听者虽然知道 $g^a \mod p$ 和 $g^b \mod p$，但直接计算 $g^{ab} \mod p$（即所谓的 Diffie-Hellman 问题）也被认为是计算上困难的。

补充说明

1. 为什么需要模运算 $\mod p$？

   • 模运算（modulo operation）是为了确保计算结果不会变得过大，同时保持数学上的可操作性。
   • $p$ 是一个大素数，模运算在有限域中进行，这为离散对数问题提供了额外的安全性。

2. 实际应用中的改进

   • 在实际应用中，Diffie-Hellman 通常会结合其他机制（如数字签名）来防止中间人攻击（man-in-the-middle attack）。因为基本的 Diffie-Hellman 协议无法验证通信双方的身份，攻击者可能冒充 Alice 或 Bob。
   • 现代协议（如 TLS）会使用证书和公钥基础设施（PKI）来解决这个问题。

3. 为什么说是“非对称加密”？

   • Diffie-Hellman 是一种非对称加密技术，因为它依赖于公钥和私钥的概念（$g^a \mod p$ 是公钥，$a$ 是私钥）。
   • 但它的最终目标是生成一个对称密钥（$g^{ab} \mod p$），这个对称密钥可以用于更高效的对称加密算法（如 AES）。