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

信息安全的基本原则

• 真实性（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）。

中间人攻击（MITM）

此时 Eve 可以通过密钥 $g^{ax} \mod p$ 和 $g^{bx} \mod p$ 与 Alice 和 Bob 进行通信。 Alice 和 Bob 无法意识到 Eve 的存在，因为 Eve 可以模拟 Alice 和 Bob 的行为。

如何解决这个问题？
一个可能的方案是将 Alice 和 Bob 要传输的公钥进行加密 $E_k(g^a \mod p)$，如果 $k$ 是临时密码，则在防止中间人攻击的同时还引入了前向安全性。 即使临时密码泄漏攻击者也无法破解之前传输的信息。

但这引入了新的问题，他们之间需要协定一个共享密钥 $k$ 来实现这一步加密。

Needham–Schroeder 协议

Needham-Schroeder 协议是一种使用可信第三方（TTP，Trent）进行密钥交换的协议，旨在让 Alice 和 Bob 建立安全的会话密钥 $k_{AB}$。

协议步骤

1. Alice 发起请求：Alice 向 Trent 发送请求，包含她的身份 $A$、Bob 的身份 $B$，以及一个随机数（nonce）$r_A$，表示她想与 Bob 通信。 $$(A, B, r_A)$$

2. Trent 分配密钥并生成票据：Trent 生成一个会话密钥 $k_{AB}$，并用 Alice 和 Bob 各自的密钥（$k_{AT}$、$k_{BT}$ ）加密相关信息，发送给 Alice：

   • $E_{k_{AT}}(r_A, B, k_{AB}, E_{k_{BT}}(k_{AB}, A))$

3. Alice 转发票据给 Bob：Alice 解密消息，获取 $k_{AB}$，并将票据 $E_{k_{BT}}(k_{AB}, A)$ 和一个用 $k_{AB}$ 加密的随机数 $s_A$ 发送给 Bob： $$(E_{k_{BT}}(k_{AB}, A), E_{k_{AB}}(s_A))$$

4. Bob 挑战 Alice：Bob 解密票据获取 $k_{AB}$，用 $k_{AB}$ 解密 $s_A$，然后发送一个挑战，用 $k_{AB}$ 加密 $s_A - 1$，并附上自己的随机数 $r_B$： $$(E_{k_{AB}}(s_A - 1, r_B))$$

5. Alice 响应挑战：Alice 解密 Bob 的消息，验证 $s_A - 1$，然后用 $k_{AB}$ 加密 $r_B - 1$ 回应 Bob： $$(E_{k_{AB}}(r_B - 1))$$

协议问题

• 问题核心：Bob 无法保证 $k_{AB}$ 是新的。旧密钥不过期，可能被重用。

  1. 如果 Eve 获取了 $k_{AT}$，她可以解密 Trent 发给 Alice 的消息，得到 $k_{AB}$。
  2. Eve 能读取 Alice 的所有消息，并冒充她与他人通信。
  3. Alice 需撤销密钥，但只有 Trent 能执行此操作。
  4. 密钥撤销是个大问题。

• Needham-Schroeder 的局限：协议假设所有用户是“好的”，目标是防止“坏人”（如 Eve）进入系统（“鸡蛋壳”模型）。但如果 $k_{AT}$ 泄露，系统安全性将崩溃。

如果 Eve 获取 $k_{AT}$ 会怎样？

Eve 能解密 Trent 发给 Alice 的消息，获取 $k_{AB}$，从而完全控制 Alice 与 Bob 的通信，读取消息并伪造身份，导致严重的安全漏洞。

总结

Needham-Schroeder 协议依赖可信第三方进行密钥分发，但存在密钥不过期和撤销困难的缺陷，容易被攻击者利用，尤其当密钥（如 $k_{AT}$）泄露时。

公钥管理与证书颁发机构（CA）

使用证书颁发机构（CA）进行公钥管理

流程：

• 步骤 1：Alice 将她的公钥发送给 CA（Trent）。
• 步骤 2：CA 为 Alice 生成证书。
• 步骤 3：Alice 将公钥和证书发送给 Bob。
• 步骤 4：Bob 使用 CA 的公钥验证证书。
• 步骤 5：Bob 使用 Alice 的公钥加密消息并发送给她。

证书内容：

• 证书格式：sign_CA[X.500: name, org, address, pub. key, expires, ...]
• 证书由 CA 签名，包含持有者的身份信息、公钥、有效期等。
• 操作系统、浏览器等需内置 CA 的公钥以验证证书。

CA 的角色：

• CA 是可信第三方，负责为用户颁发签名证书。

公钥证书生成

流程：

• 步骤 1：Alice 生成公钥/私钥对。
• 步骤 2：Alice 将公钥发送给 CA。
• 步骤 3：CA 挑战 Alice，验证她是否知道对应的私钥。
• 步骤 4：CA 生成证书并发送给 Alice。

重要说明：

• CA 不会获知 Alice 的私钥。
• 私钥保密对前向安全性（forward secrecy）至关重要。
• 如果 CA 被攻破，攻击者可能冒充 Alice。

证书撤销

可能需要撤销证书的情况：

• Alice 的私钥被窃取或以其他方式泄露。
• Alice 更换工作或信任关系发生变化。

CA 系统的撤销问题：

• 可能需要每日验证证书有效性（慢且繁琐）。
• 解决方案：
  • 使用证书中的到期日期字段。
  • 使用证书撤销列表（CRL，类似信用卡黑名单）。

挑战：

• 证书撤销是 CA 系统的主要问题，CRL 的分发和更新可能复杂。

信任模型对比

对称密钥（Symmetric Keys）：

• 结构：Alice 和 Bob 通过密钥分发中心（KDC，Carol）共享密钥。
• 特点：
  • 第三方（TTP/KDC）需始终在线（每次会话都使用）。
  • TTP 知道所有密码，且以明文形式存储，是高风险目标。
  • 无前向安全性（forward secrecy）。

非对称密钥（Asymmetric Keys）：

• 结构：Alice 和 Bob 通过 CA（Carol）验证公钥。
• 特点：
  • TTP（CA）仅在证书生成时使用，之后可离线。
  • TTP 仅知道公钥，无需存储私钥。
  • 具备前向安全性。
  • 速度较慢（如 SSL/TLS、PGP 等协议）。

RSA

• RSA 是一种非对称加密算法：非对称加密意味着使用一对密钥——公钥和私钥。公钥用于加密，私钥用于解密（反之亦可，用于数字签名）。
• 密钥生成由单方（Alice）完成：Alice 负责生成公钥和私钥，并将公钥分发给其他人（例如 Bob），而私钥则保密。

密钥生成步骤

Alice 生成 RSA 密钥的步骤如下：

1. 选择两个大素数 $p$ 和 $q$，并计算模数 $n$：
   • 选择两个大素数 $p$ 和 $q$。
   • 计算 $n = p \cdot q$。$n$ 是 RSA 模数，用于加密和解密。
2. 计算欧拉函数 $\phi(n)$：
   • $\phi(n) = (p-1)(q-1)$。这是 $\mathbb{Z}_n^\times$ 中元素的个数（即与 $n$ 互质的数的个数）。
3. 选择公钥指数 $e$：
   • 选择一个整数 $e$，满足 $1 < e < \phi(n)$，且 $e$ 与 $\phi(n)$ 互质（即 $\gcd(e, \phi(n)) = 1$ gcd: 最大公因数）。
4. 计算私钥指数 $d$：
   • 找到 $d$，满足 $e \cdot d \equiv 1 \pmod{\phi(n)}$。这可以通过扩展欧几里得算法计算。
5. 公钥和私钥：
   • 公钥是 $(n, e)$，私钥是 $(n, d)$。
   • $p, q, \phi(n)$ 在生成密钥后不再需要，可以销毁以确保安全。

加密和解密过程

假设 Bob 想向 Alice 发送消息 $m \in \mathbb{Z}_n^\times$（即 $0 \leq m < n$，且 $m$ 与 $n$ 互质）：

1. Bob 加密：
   • Bob 使用 Alice 的公钥 $(n, e)$。
   • 计算密文 $C = m^e \mod n$。
   • 将密文 $C$ 发送给 Alice。
2. Alice 解密：
   • Alice 收到密文 $C$，使用她的私钥 $(n, d)$。
   • 计算 $C^d \mod n$。
   • 根据 RSA 的数学性质，$C^d \mod n = m^{e \cdot d} \mod n$。因为 $e \cdot d \equiv 1 \pmod{\phi(n)}$，所以 $m^{e \cdot d} = m^1 = m$。
   • 因此，Alice 恢复出原始消息 $m$。

例子

这一部分通过一个具体的例子展示了 RSA 的密钥生成、加密和解密过程。

1. 密钥生成

Alice 生成一个新的 RSA 密钥：

• 选择素数 $p$ 和 $q$：
  • $p = 11$，$q = 17$。
  • 计算模数 $n = p \cdot q = 11 \cdot 17 = 187$。
• 计算 $\phi(n)$：
  • $\phi(n) = (p-1)(q-1) = (11-1)(17-1) = 10 \cdot 16 = 160$。
• 选择公钥指数 $e$：
  • 选择 $e = 7$，因为 $7$ 与 $\phi(n) = 160$ 互质（$\gcd(7, 160) = 1 $）。
• 计算私钥指数 $d$：
  • 找到 $d$，满足 $e \cdot d \equiv 1 \pmod{\phi(n)}$，即 $7 \cdot d \equiv 1 \pmod{160}$。
  • 使用扩展欧几里得算法：
    • $160 = 22 \cdot 7 + 6$
    • $7 = 1 \cdot 6 + 1$
    • $6 = 6 \cdot 1 + 0$
    • 回代：$1 = 7 - 1 \cdot 6 = 7 - 1 \cdot (160 - 22 \cdot 7) = 23 \cdot 7 - 1 \cdot 160$。
    • 因此，$7 \cdot 23 \equiv 1 \pmod{160}$，所以 $d = 23$。
• 公钥和私钥：
  • 公钥：$(n, e) = (187, 7)$。
  • 私钥：$(n, d) = (187, 23)$。

2. 加密

Bob 想向 Alice 发送消息 $m = 142$：

• Bob 使用 Alice 的公钥 $(n, e) = (187, 7)$。
• 计算密文 $C = m^e \mod n = 142^7 \mod 187 = 65$。
• Bob 将密文 $65$ 发送给 Alice。

3. 解密

Alice 收到密文 $C = 65$，使用她的私钥 $(n, d) = (187, 23)$ 解密：

• 计算 $C^d \mod n = 65^{23} \mod 187 = 142$，成功解密。

破解

因数分解攻击 （Factoring Attack）

攻击者通过分解 RSA 公钥中的大整数 $n$ 来获取私钥的过程。在 RSA 算法中，公钥由两个部分组成：模数 $n$ 和公钥指数 $e$，其中 $n$ 是两个大素数 $p$ 和 $q$ 的乘积。如果攻击者能够将 $n$ 分解为 $p$ 和 $q$，就可以计算出私钥指数 $d$，从而破解 RSA 加密或签名。

中国剩余定理（Chinese Remainder Theorem, CRT）

1. 中国剩余定理（CRT）简介
   中国剩余定理是一个数学定理，用于解决一组模线性同余方程。定理的核心是： 如果有以下同余方程组：

   $$ x \equiv a_1 \mod n_1 \ x \equiv a_2 \mod n_2 \ x \equiv a_3 \mod n_3 $$

   且 $n_1, n_2, n_3$ 两两互质（即 $\gcd(n_i, n_j) = 1$ 对于所有 $i \neq j$），那么存在一个唯一解 $x \mod (n_1 \cdot n_2 \cdot n_3)$。

2. 攻击场景
   内容中描述了一个特定的攻击场景：

   • Alice 使用相同的明文 $m$ 和相同的加密指数 $e$，但不同的模数 $n_1, n_2, n_3$（对应不同的接收者），生成了三组密文： $$ c_1 = m^e \mod n_1 \ c_2 = m^e \mod n_2 \ c_3 = m^e \mod n_3 $$
   • 假设 $n_1, n_2, n_3$ 两两互质（即 $\gcd(n_i, n_j) = 1$）。
   • 攻击者 Eve 截获了这三组密文 $c_1, c_2, c_3$，并且知道 $n_1, n_2, n_3$ 和 $e$。

3. 使用 CRT 恢复 $m^e$
   Eve 可以利用中国剩余定理来解决以下同余方程组： $$ x \equiv c_1 \mod n_1 \ x \equiv c_2 \mod n_2 \ x \equiv c_3 \mod n_3 $$ 由于 $c_1 = m^e \mod n_1$，$c_2 = m^e \mod n_2$，$c_3 = m^e \mod n_3$，并且 $n_1, n_2, n_3$ 两两互质，CRT 保证存在一个唯一解 $x \mod (n_1 \cdot n_2 \cdot n_3)$。这个解 $x$ 满足： $$ x = m^e \mod (n_1 \cdot n_2 \cdot n_3) $$

关键点在于：因为 $m < n_1, n_2, n_3$（在 RSA 中，明文 $m$ 通常小于模数 $n$），所以 $m^e < n_1, n_2, n_3$。因此，$m^e < n_1 \cdot n_2 \cdot n_3$，这意味着 $x = m^e$（不需要取模，直接就是 $m^e$）。

5. 从 $m^e$ 恢复 $m$
   一旦 Eve 得到了 $x = m^e$，并且 $e$ 是已知的（因为 $e$ 是公钥的一部分），她可以通过求 $e$ 次方根来恢复 $m$：

   $$ m = \sqrt[e]{m^e} $$

   在实际中，计算 $e$ 次方根可能需要离散对数或类似的数学方法，但如果 $e$ 较小（例如 $e = 3$），直接计算立方根是可行的。 内容中提到的“使用对数（logarithms）”可能指的是离散对数问题，但更可能是指直接计算 $e$ 次方根（例如通过数值方法）。

6. 为什么这个攻击有效？
   这个攻击利用了以下几个关键点：

   • 相同的明文和 $e$：Alice 对同一个明文 $m$ 使用了相同的 $e$ 加密，生成的密文 $c_1, c_2, c_3$ 都与 $m^e$ 相关。
   • 不同的 $n$：不同的接收者有不同的模数 $n_1, n_2, n_3$，且这些模数两两互质。
   • CRT 的应用：CRT 允许 Eve 将这些密文组合起来，直接得到 $m^e$。

   如果 $n_1, n_2, n_3$ 不两两互质，或者 Alice 使用了不同的 $e$ 或不同的明文，这个攻击就无法成功。

7. 实际意义和防御

   • 实际意义：这个攻击表明，在 RSA 中重复使用相同的明文和 $e$ 是非常危险的，尤其是在不同的模数下。攻击者可以利用数学工具（如 CRT）来恢复明文。
   • 防御方法：
     1. 填充（Padding）：在实际的 RSA 实现中，通常会对明文进行随机填充（例如使用 OAEP 填充），确保每次加密的明文都不相同，即使消息内容相同。
     2. 不同的 $e$：使用不同的 $e$ 值（虽然在实践中 $e$ 通常是固定的，例如 65537）。
     3. 避免重复加密：不要对相同的明文多次加密并发送给不同的接收者。

小加密指数攻击（Small Encryption Exponent Attack, Coppersmith Attack）

1. 小加密指数攻击的核心
   这种攻击利用了当 $e$ 较小且明文 $m$ 满足 $m^e < n$ 时的漏洞。让我们逐步分析：

   1. 条件：$m^e < n$

      • 在 RSA 加密中，密文 $c$ 是通过 $c = m^e \mod n$ 计算的。
      • 如果 $m^e < n$，那么在计算 $m^e \mod n$ 时，模运算不会生效（因为 $m^e$ 本身就小于 $n$）。这意味着： $$ c = m^e \mod n = m^e $$ 换句话说，密文 $c$ 直接等于 $m^e$，没有被模 $n$ 截断。

   2. 攻击方法：计算 $e$ 次方根

      • 如果攻击者 Eve 截获了密文 $c$，并且知道 $e$（因为 $e$ 是公钥的一部分），她可以利用 $c = m^e$ 的关系。
      • 由于 $c = m^e$，Eve 只需要计算 $c$ 的 $e$ 次方根来恢复明文 $m$： $$ m = \sqrt[e]{c} $$
      • 如果 $e$ 很小（例如 $e = 3$），计算 $e$ 次方根是相对容易的。例如，当 $e = 3$ 时，Eve 只需要计算 $c$ 的立方根： $$ m = \sqrt[3]{c} $$ 这可以通过数值方法直接计算（因为 $c$ 是一个整数，计算整数的 $e$ 次方根在 $e$ 较小时是可行的）。

2. 为什么会选择小的 $e$？
   内容中提到：

   • 小的加密指数 $e$ 通常被选择以提高 RSA 加密的速度。
     • 在 RSA 加密中，加密过程需要计算 $m^e \mod n$。如果 $e$ 较小（例如 $e = 3$ 或 $e = 17$），计算的复杂度会显著降低，因为需要进行的模幂运算次数更少。
     • 相比之下，解密过程使用私钥指数 $d$（通过 $m = c^d \mod n$ 解密），而 $d$ 通常很大，因此解密速度较慢。 选择小的 $e$（如 3 或 65537）是 RSA 实现中的常见优化手段，但如果使用不当（例如没有对明文进行适当的填充），就会导致这种攻击。

3. 攻击的局限性和适用场景

   • 适用条件：这种攻击只在 $m^e < n$ 时有效。如果 $m^e \geq n$，那么 $c = m^e \mod n$ 会使得 $c \neq m^e$，攻击者无法直接通过计算 $e$ 次方根来恢复 $m$。
   • 明文大小：如果明文 $m$ 很小，或者 $e$ 很小（例如 $e = 3$），就更容易满足 $m^e < n$。例如：
     • 假设 $n$ 是一个 2048 位的模数（大约是 $2^{2048}$ 量级）。
     • 如果 $e = 3$，而 $m$ 是一个较小的数（例如 128 位，约为 $2^{128}$），那么 $m^3 \approx (2^{128})^3 = 2^{384}$，仍然远小于 $n \approx 2^{2048}$，因此 $m^3 < n$，攻击成立。

4. 防御方法 内容中提到了一些防御措施：

   • 避免使用小的 $e$ 发送相同消息（或其变体）给多个实体：

     • 如果同一个明文 $m$ 被加密多次（即使是对不同的接收者），攻击者可能利用其他攻击（例如结合之前的“中国剩余定理攻击”）来恢复 $m$。
     • 小的 $e$ 本身并不是问题，但重复使用相同的明文会增加风险。

   • 对明文进行加盐（Salt）或填充（Padding）：

     • 加盐：在明文 $m$ 中添加随机比特（例如通过随机填充方案，如 OAEP），使得每次加密的明文都不相同，即使消息内容相同。
     • 这样可以确保 $m$ 不会太小，也不会重复，从而避免 $m^e < n$ 的情况。
     • 现代 RSA 实现通常使用 OAEP（Optimal Asymmetric Encryption Padding） 填充方案，这是一种标准的填充方法，可以有效防止这类攻击。

5. Coppersmith 攻击的扩展 内容中提到的“Coppersmith 攻击”实际上是小加密指数攻击的一个更广义的版本。Coppersmith 定理（由 Don Coppersmith 提出）是一种强大的数学工具，可以用来解决某些模方程问题。具体的 Coppersmith 攻击可以处理更复杂的情况，例如：

   • 即使 $m^e \geq n$，Coppersmith 方法仍然可以通过分析 $c = m^e \mod n$ 来恢复 $m$，只要 $m$ 足够小（例如 $m < n^{1/e}$）。
   • Coppersmith 攻击利用了模方程的多项式性质，通过格基规约（Lattice Reduction）技术（如 LLL 算法）来寻找 $m$。

   但在内容描述的简单场景中（$m^e < n$），直接计算 $e$ 次方根就足够了，不需要用到更复杂的 Coppersmith 方法。

6. 实际意义

   • 漏洞：小加密指数攻击表明，选择小的 $e$（如 $e = 3$）虽然可以提高加密速度，但如果明文 $m$ 没有经过适当的填充，可能会导致明文直接暴露。
   • 教训：RSA 的安全不仅仅依赖于大整数分解的难度，还依赖于正确的使用方式。选择小的 $e$ 本身没有问题，但必须结合适当的填充方案（如 OAEP）来确保安全。

利用同态性质攻击

RSA 具有同态性质，具体表现为：

• 如果有两个明文 $m_1$ 和 $m_2$，它们的密文分别是： $$ c_1 = m_1^e \mod n, \quad c_2 = m_2^e \mod n $$
• 那么，密文 $c_1 \times c_2 \mod n$ 对应于明文 $m_1 \times m_2$ 的加密： $$ c_1 \times c_2 = (m_1^e \mod n) \times (m_2^e \mod n) = (m_1 \times m_2)^e \mod n $$ 这意味着，密文的乘法对应于明文的乘法（在模 $n$ 的意义下）。这就是 RSA 的乘法同态性质。

攻击的目标是：Eve（攻击者）想要解密一个密文 $c$，而这个密文是 Alice（合法用户）用 Bob 的公钥 $(e, n)$ 加密的，形式为：

$$ c = m^e \mod n $$

Eve 无法直接解密 $c$，因为她没有 Bob 的私钥 $d$。但是，她可以利用 RSA 的同态性质，通过与 Alice 的交互来间接获取明文 $m$。

攻击步骤：

1. Eve 构造一个适应的密文 $c’$：

   • Eve 选择一个随机的“盲化因子” $x \in \mathbb{Z}_n^*$（即 $x$ 与 $n$ 互素）。
   • Eve 利用 RSA 的同态性质，构造一个新的密文 $c’$： $$ c’ = c \times x^e \mod n $$
   • 根据同态性质： $$ c’ = (m^e \mod n) \times (x^e \mod n) = (m \times x)^e \mod n $$ 也就是说，$c’$ 是明文 $m \times x$ 的加密结果。

2. Eve 将 $c’$ 发送给 Alice：

   • Eve 将构造的密文 $c’$ 发送给 Alice，请求 Alice 解密。
   • Alice 不知道这是 Eve 构造的密文，她会用自己的私钥 $d$（假设 Alice 有权限解密 Bob 的密文）进行解密： $$ (c’)^d = \left( (m \times x)^e \right)^d \mod n $$
   • 因为 $e \times d \equiv 1 \pmod{\phi(n)}$，所以： $$ (c’)^d = (m \times x)^{e \times d} \mod n = m \times x \mod n $$
   • 因此，Alice 解密后得到的结果是 $m \times x \mod n$。

3. Alice 将解密结果返回给 Eve：

   • Alice 将解密结果 $m \times x \mod n$ 返回给 Eve。

4. Eve“去盲化”以恢复明文 $m$：

   • Eve 已经知道自己选择的盲化因子 $x$。
   • 她可以计算 $x^{-1} \mod n$（即 $x$ 在模 $n$ 下的乘法逆元，满足 $x \times x^{-1} \equiv 1 \pmod{n}$）。
   • 然后，Eve 计算： $$ (m \times x) \times x^{-1} \mod n = m \mod n $$
   • 这样，Eve 就成功恢复了原始明文 $m$。

对称和非对称加密

对称加密

优点

• 对称加密算法可以设计为具有很高的吞吐量（throughput），即加密和解密的处理速度很快。

  • 原因：
    对称加密算法通常基于简单的数学运算（如位运算、异或、置换、替换等），这些操作在硬件和软件中都非常高效。
    例如，AES 算法使用固定大小的块（128 位）和轮函数（round function），可以在现代处理器上通过并行计算和硬件加速（如 AES-NI 指令集）实现极高的速度。
  • 应用场景：
    这种高吞吐量使得对称加密非常适合需要快速加密大量数据的场景，例如磁盘加密（BitLocker）、网络通信加密（TLS/SSL 中的数据加密部分）、或实时视频流加密。

• 对称加密的密钥长度相对较短，通常为 128 位、192 位或 256 位。

  • 原因：
    对称加密的安全性依赖于密钥的保密性，而密钥长度较短也能提供足够的安全性。
    例如，AES-128（128 位密钥）已经足以抵御暴力破解（brute-force attack），因为尝试所有可能的 128 位密钥需要 $2^{128}$ 次操作，这在当前计算能力下是不可行的。
  • 对比：
    与非对称加密（如 RSA）相比，非对称加密的密钥长度要长得多（例如 2048 位或 4096 位），因为非对称加密的安全性基于数学难题（如大整数分解），需要更大的密钥来抵御攻击。
  • 意义：
    短密钥意味着存储和传输密钥的开销较小，计算效率也更高。

• 对称加密算法可以作为基础组件（primitives）来构建其他加密工具，例如伪随机数生成器（PRNGs）。

  • 伪随机数生成器（PRNG）：
    PRNG 是一种算法，用于生成看似随机的数字序列，但实际上是确定性的（由初始种子决定）。
    对称加密算法（如 AES）可以以**计数模式（Counter Mode, CTR）**运行，将一个计数器加密后生成伪随机序列。
    例如：AES-CTR 模式中，输入一个递增的计数器和密钥，输出加密后的结果作为伪随机数。
  • 应用：
    伪随机数在密码学中非常重要，例如用于生成一次性密钥（nonce）、初始化向量（IV），或在密钥交换协议中生成临时密钥。
  • 意义：
    对称加密算法的这种灵活性使其成为密码学中的核心构建块。

• 对称加密算法可以通过简单的操作（如替换和置换）构建更强的密码系统。

  • 替换（Substitution）和置换（Permutation）：
    • 替换：将明文中的一个元素替换为另一个元素（例如，AES 中的 S-Box 将一个字节映射为另一个字节）。
    • 置换：重新排列明文的元素（例如，AES 中的 ShiftRows 和 MixColumns 操作）。
    • 这些操作通过多轮迭代（rounds）组合，增加密码的复杂性，使其更难被破解。
  • 例子：
    AES 算法通过多轮的替换和置换操作（包括 SubBytes、ShiftRows、MixColumns 和 AddRoundKey）构建了一个非常强的密码系统。
    这种设计基于 混淆（confusion） 和 扩散（diffusion） 原则：
    • 混淆：使密文和密钥之间的关系尽可能复杂（通过替换）。
    • 扩散：使明文的每个比特影响密文的多个比特（通过置换）。
  • 意义：
    这种设计使得对称加密算法能够抵御多种攻击（如差分攻击和线性攻击），从而构建更强的密码。

• 对称加密算法（如 AES）目前已知的所有攻击方式都依赖于暴力破解（exhaustive key search）。

  • 暴力破解：
    攻击者尝试所有可能的密钥，直到找到正确的密钥。
    对于一个 128 位密钥，暴力破解需要尝试 $2^{128}$ 个密钥，这在计算上是不可行的。
    例如，假设一台超级计算机每秒可以尝试 $2^{60}$ 个密钥，破解 128 位密钥仍需 $2^{128} / 2^{60} = 2^{68}$ 秒，约为 $10^{20}$ 年，远超宇宙年龄。
  • 意义：
    暴力破解的不可行性是对称加密安全性的核心保障。
    现代对称加密算法（如 AES）经过广泛的密码分析，没有发现比暴力破解更有效的攻击方法（假设没有实现漏洞或侧信道攻击）。

缺点

• 在一个两方通信网络中（例如 Alice 和 Bob），对称加密要求加密和解密的密钥在双方之间保持秘密。
  • 问题：
    • 密钥需要在通信双方之间安全地共享。如果密钥在传输过程中被拦截，攻击者就可以解密所有通信。
    • 密钥共享通常需要一个安全的信道（secure channel），但在实际中（如互联网通信），建立这样的信道可能很困难。
  • 对比非对称加密：
    非对称加密（如 RSA）使用公钥和私钥，公钥可以公开分发，私钥只需要一方持有，解决了密钥分发的难题。
  • 解决方案：
    在实际中，常用非对称加密（如 Diffie-Hellman 密钥交换或 RSA）来安全地交换对称加密的密钥。例如：
    • 在 TLS/SSL 协议中，客户端和服务器使用非对称加密协商一个对称密钥（会话密钥），然后用对称加密（如 AES）进行高效的数据传输。
• 为了安全起见，对称加密的密钥需要频繁更换，例如在每个会话（session）中使用一个新密钥。
  • 原因：
    • 如果一个密钥被长期使用，攻击者有更多时间收集密文，可能会通过密码分析（如已知明文攻击或选择明文攻击）找到密钥的弱点。
    • 频繁更换密钥可以限制攻击者的窗口期，降低密钥泄露的风险。
  • 实际操作：
    在现代协议（如 TLS）中，通常为每个会话生成一个新的对称密钥（称为会话密钥，session key），通过密钥交换协议（如 Diffie-Hellman）生成。
  • 挑战：
    频繁更换密钥增加了密钥管理的复杂性，需要确保新密钥的安全分发和存储。
• 在一个大型网络中，如果每对用户之间都需要一个唯一的对称密钥，密钥数量会急剧增加，导致密钥管理问题。
  • 计算密钥数量：
    假设网络中有 $n$ 个用户，每对用户需要一个唯一的对称密钥。
    密钥数量为组合数 $\binom{n}{2} = \frac{n(n-1)}{2}$。
    • 例如：
      • 如果 $n = 10$，需要 $\frac{10 \times 9}{2} = 45$ 个密钥。
      • 如果 $n = 1000$，需要 $\frac{1000 \times 999}{2} = 499,500$ 个密钥。
    • 随着 $n$ 的增加，密钥数量呈二次方增长（$O(n^2)$）。
  • 密钥管理问题：
    • 存储：每个用户需要存储大量密钥（对于 $n$ 个用户，每个用户需要存储 $n-1$ 个密钥）。
    • 分发：需要在每对用户之间安全地分发密钥。
    • 更新：如果密钥需要频繁更换，管理这些密钥的更新会非常复杂。
  • 解决方案：
    • 使用密钥分发中心（KDC）：
      例如，Kerberos 协议使用一个可信的 KDC 来分发会话密钥，减少直接密钥数量。
      每个用户只需要与 KDC 共享一个密钥（共 $n$ 个密钥），而不是每对用户之间共享密钥。
    • 使用非对称加密：
      非对称加密可以用来协商对称密钥，减少密钥管理的复杂性。

非对称加密

优点

• 只有私钥需要保密

  • 在非对称加密中，公钥可以公开分发给任何人，而私钥必须由持有者严格保密。这种设计减少了密钥分发的风险，因为即使公钥被拦截，也不会影响安全性。

• 只需要一个可信的第三方（TTP）

  • 非对称加密只需要一个功能上可信、诚实且公平的第三方（Trusted Third Party, TTP），例如证书颁发机构（CA），来验证公钥的真实性。相比之下，对称加密需要双方安全地共享同一个密钥，这在大型网络中更复杂。

• 根据使用模式，公钥和私钥对可以长期使用（受限于摩尔定律）

  • 非对称加密的密钥对可以长期使用，而不需要频繁更换。密钥的寿命受限于计算能力的增长（即摩尔定律，计算能力大约每 18-24 个月翻倍）。只要密钥长度足够长（例如 2048 位或更高），在当前技术条件下可以保持安全。

• 在大型网络中，只需要 $n$ 个密钥，而不是 $\frac{n(n-1)}{2}$ 个

  • 在对称加密中，如果有 $n$ 个用户，每对用户之间需要一个唯一的密钥，总共需要 $\frac{n(n-1)}{2}$ 个密钥。例如，10 个用户需要 45 个密钥。而在非对称加密中，每个用户只需要一对密钥（公钥和私钥），总共只需要 $n$ 个密钥对（例如 10 个用户只需要 10 对密钥）。这大大简化了密钥管理，特别是在大型网络中。

缺点

• 速度非常慢（对所有算法而言）

  • 非对称加密的计算复杂度远高于对称加密。例如，RSA 算法涉及大整数的模运算和指数运算，计算开销大，因此加密和解密速度慢。这使得非对称加密不适合直接加密大量数据，通常用于加密小数据（如对称加密的密钥）或数字签名。

• 密钥长度通常更大（1024 到 4096 位）

  • 非对称加密的密钥长度远大于对称加密（对称加密通常使用 128 位或 256 位密钥）。例如，RSA 算法常用的密钥长度为 1024 位、2048 位甚至 4096 位。更大的密钥长度增加了存储和计算的开销，但也提供了更高的安全性。

• 安全性基于少量数论问题的假设难度

  • 非对称加密的安全性依赖于某些数学问题的计算难度，例如：
    • RSA 依赖于大整数分解问题（即分解 $n$ 的质因数）。
    • ECC 依赖于椭圆曲线离散对数问题。
  • 这些问题目前被认为是难以解决的，但如果发现了有效的“捷径攻击”（short-cut attacks），例如量子计算机的 Shor 算法可以高效分解大整数，那么非对称加密的安全性将受到威胁。

• 公钥加密的公开历史较短，相比对称加密

  • 非对称加密的概念是 20 世纪 70 年代才提出的（例如 Diffie-Hellman 和 RSA），而对称加密（如 AES、DES）有更长的历史和更广泛的实践验证。由于非对称加密的历史较短，其长期安全性仍需更多时间和实践来验证，尤其是在面对新的攻击技术时。

对称加密和非对称加密是互补的

1. 非对称加密可用于为后续的更快对称加密建立密钥（例如会话密钥）

   • 非对称加密（如 RSA 或 Diffie-Hellman）通常用于安全地交换一个对称加密的密钥（称为会话密钥，session key）。
   • 原因是非对称加密速度慢，不适合直接加密大量数据，而对称加密（如 AES）速度快，适合加密大数据量。
   • 例如，在 TLS/SSL 协议（HTTPS 的基础）中，客户端和服务器使用非对称加密（如 RSA）来协商一个临时的对称密钥（会话密钥），然后用这个对称密钥进行后续的数据加密和解密。

2. Alice 和 Bob 可以通过发布他们的公钥，充分利用公钥加密的长期优势

   • 在非对称加密中，Alice 和 Bob 可以公开他们的公钥（通过证书或目录），而私钥保持秘密。
   • 公钥加密的长期优势在于，公钥可以长期使用（只要私钥不泄露），并且不需要双方事先共享密钥。这使得非对称加密非常适合密钥分发和身份验证。
   • 例如，Alice 可以用 Bob 的公钥加密一个会话密钥，发送给 Bob，Bob 用自己的私钥解密，获取会话密钥，然后双方用这个会话密钥进行对称加密通信。

3. 非对称加密擅长密钥管理和签名，对称加密擅长加密和某些数据完整性应用

   • 非对称加密的优势：
     • 密钥管理：非对称加密通过公钥和私钥的设计，简化了密钥分发问题。公钥可以公开，私钥由持有者保护，不需要在通信双方之间安全地传输密钥。
     • 数字签名：非对称加密常用于数字签名（例如用私钥签名，公钥验证），以验证数据的来源和完整性。例如，Alice 可以用她的私钥对消息签名，Bob 用 Alice 的公钥验证签名，确认消息确实来自 Alice 且未被篡改。
   • 对称加密的优势：
     • 加密：对称加密（如 AES）速度快，适合加密大量数据，例如文件加密或网络通信中的数据传输。
     • 数据完整性：对称加密可以结合消息认证码（MAC，Message Authentication Code）来确保数据的完整性和真实性。例如，HMAC（基于哈希的消息认证码）使用对称密钥来验证数据未被篡改。

实际场景

• TLS/SSL（HTTPS）：

  1. 客户端（Alice）和服务器（Bob）使用非对称加密（如 RSA 或 Diffie-Hellman）协商一个对称会话密钥。
  2. 随后，双方使用这个会话密钥（通过对称加密，如 AES）加密通信数据，确保高效和安全。
  3. 非对称加密还用于服务器的身份验证（通过数字证书和签名）。

• 电子邮件加密（PGP/GPG）：

  1. 非对称加密用于加密一个对称密钥（会话密钥），并用接收者的公钥加密后发送。
  2. 接收者用自己的私钥解密得到会话密钥，然后用会话密钥解密邮件内容（对称加密）。
  3. 非对称加密还用于签名，验证邮件的发送者身份。

数字签名

签名指的是用于验证文档或消息真实性和完整性的机制，通常在数字世界中指的是数字签名（Digital Signatures），而不是传统的手写签名。

1. 签名用于将作者与文档绑定。
   签名的主要功能是证明某个文档或消息是由特定的作者（或发送者）创建的。通过签名，作者表明自己对文档内容负责，类似于现实生活中在合同上签字以表示同意。
2. 签名所需的理想属性：
   • 真实性：签名必须能够让人确信它是签名者本人有意添加的，而不是被伪造或意外生成的。
   • 不可伪造：签名的设计应确保其他人无法伪造签名。只有真正的签名者（拥有私钥的人）才能生成有效的签名。
   • 不可重用：签名不能被“剪切粘贴”到另一个文档上使用。如果签名被转移到其他文档，验证过程应该会失败。
   • 不可更改：一旦签名生成，任何对签名本身的篡改都应该被检测到。
   • 不可否认：签名提供了一种法律和技术上的保障，签名者无法否认自己签署了文档。这在合同、交易等场景中非常重要。这是数字签名的核心优势，而 MAC 无法提供这一点，因为 MAC 的生成和验证依赖于共享密钥（类似对称加密），任何一方都可能伪造消息并生成相应的 MAC。
3. 与所有事物一样，这些属性可能会被攻击和破坏。我们在设计使用签名的系统时必须考虑这些攻击。
   • 伪造攻击：攻击者可能尝试伪造签名（例如通过窃取私钥）。
   • 重用攻击：攻击者可能尝试将签名从一个文档转移到另一个文
   • 篡改攻击：攻击者可能尝试修改文档或签名本身。
   • 否认攻击：签名者可能声称自己的私钥被盗，从而否认签名。

$$ S = F(m, k) $$

定义和符号：

• $m$：要签名的消息（message）。
• $k$：签名者的私钥（secret key），只有签名者知道。
• $F$：签名方案（signature scheme），是一个函数，用于生成签名。
• $S$：签名（signature），通过 $S = F(m, k)$ 计算得出。

简单来说，签名 $S$ 是通过消息 $m$ 和私钥 $k$ 经过签名函数 $F$ 生成的。

使用公钥的数字签名（Digital Signatures with Public Keys）

场景

Alice 想要签名一个消息 $m$ 并发送给 Bob，确保 Bob 能验证消息确实来自 Alice。

1. 密钥生成（Generation of a Key）

• 步骤 1：Alice 生成一对密钥：
  • $A_v$：公钥（public key），用于验证签名。
  • $A_s$：私钥（private key），用于生成签名。
• 步骤 2：Alice 将公钥 $A_v$ 发布到公共目录（public directory），让所有人（包括 Bob）都可以访问。
• 步骤 3：Alice 保持私钥 $A_s$ 的机密性，只有她自己知道。

2. 签名生成（Signature Generation）

• 步骤 1：Alice 选择一个随机的 $n$ 位字符串 $r = {0,1}^n$。
  • 这个随机数 $r$ 通常用于增加签名的安全性，防止某些攻击（例如重放攻击）。
• 步骤 2：Alice 对消息 $m$ 进行哈希（hash），得到消息摘要 $d = h(m)$。
  • $h$ 是一个哈希函数（例如 SHA-256），将任意长度的消息 $m$ 压缩为固定长度的摘要 $d$。
  • 哈希的目的是为了提高效率（签名固定长度的摘要比签名整个消息更快），同时保证消息的完整性（如果消息被篡改，哈希值会改变）。
• 步骤 3：Alice 使用她的私钥 $A_s$、消息摘要 $d$ 和随机数 $r$ 生成签名 $S = \text{signature}(d, r, A_s)$。
  • 具体签名算法不固定，但通常会涉及私钥对 $d$ 和 $r$ 的加密或数学运算。
• 步骤 4：Alice 将消息 $m$ 和签名 $S$ 一起发送给 Bob，即发送 $(m, S)$。

3. 签名验证（Signature Verification）

• 步骤 1：Bob 从公共目录获取 Alice 的公钥 $A_v$。
• 步骤 2：Bob 对收到的消息 $m$ 进行哈希，计算 $d = h(m)$。
  • 这确保 Bob 计算的摘要与 Alice 计算的摘要一致（如果消息未被篡改）。
• 步骤 3：Bob 使用公钥 $A_v$、消息摘要 $d$ 和签名 $S$ 运行验证函数 $\text{verify}(d, A_v, S)$。
  • 如果验证通过，说明签名有效，消息确实来自 Alice 且未被篡改。
  • 具体验证过程取决于签名算法。

阻止重放攻击（replay attack）

重放攻击是指攻击者（比如 Bob）截获一个合法的数字消息（比如 Alice 发出的数字支票），然后重复使用这个消息来欺骗系统或其他人。在这个场景中，Alice 发送了一张价值 100 美元的数字支票给 Bob，Bob 拿着支票去银行兑现，银行验证签名后将 100 美元存入 Bob 的账户。但如果 Bob 再次提交同一张支票，试图再骗取 100 美元，这就是重放攻击。

所以在数字签名中引入 $r = {0, 1}^n$，表示一个随机的 $n$ 位二进制值（即一个随机数，可能是 0 或 1 的序列，长度为 $n$）。这个随机值被称为 nonce（number used once，一次性使用的数字）。
将这个随机值 $r$ 包含在签名中，是为了确保每次签名都是独一无二的，即使消息内容（比如支票的金额和收款人）是相同的。

攻击模型

数字签名系统中可能面临的攻击模型，具体分为三种类型：Universal Forgery（通用伪造）、Selective Forgery（选择性伪造）和Existential Forgery（存在性伪造）。

(1) Universal Forgery（通用伪造）

• 定义：
  攻击者能够从公钥 $A_v$ 和已知的签名对 $(m, S)$（即消息 $m$ 和对应的签名 $S$）中恢复出签名者的私钥 $A_s$。

• 解释：
  如果攻击者能够恢复私钥 $A_s$，那么他们就可以伪造任何消息的签名，因为他们已经完全掌握了签名者的密钥。这是最严重的攻击，因为攻击者获得了对签名系统的完全控制。

• 危害：
  攻击者可以伪造任何消息的签名，冒充签名者（比如 Alice）进行任意操作，例如伪造合同、授权交易等。

• 现实性：
  在一个安全的数字签名系统中（比如 RSA、ECDSA），这种攻击通常是不可行的，因为从公钥和签名对中恢复私钥需要解决数学难题（比如大整数分解或离散对数问题），这在计算上是极其困难的。

(2) Selective Forgery（选择性伪造）

• 定义：
  攻击者能够为一个特定的消息（或一类特定的消息）伪造签名。

• 解释：
  在这种攻击中，攻击者可以选择一个特定的消息 $m’$，然后生成一个有效的签名 $S’$，使得签名 $S’$ 看起来像是签名者（比如 Alice）对 $m’$ 的合法签名。
  攻击者可能需要访问一些已有的签名对 $(m, S)$，或者通过其他方式（比如欺骗签名者签名某些消息）来收集信息。

• 危害：
  这种攻击的危害取决于攻击者选择的消息。例如，如果攻击者伪造了一张“给 Bob 支付 1000 美元”的支票签名，银行可能会被欺骗而执行这笔交易。

• 现实性：
  选择性伪造通常比通用伪造更可行，但仍然需要攻击者有一定的能力，比如通过“选择消息攻击”（Chosen Message Attack）获取签名者对某些消息的签名，然后利用这些签名来伪造目标消息的签名。
  安全的签名方案（比如使用随机填充的 RSA 签名或 ECDSA）会通过引入随机性来防止这种攻击。

(3) Existential Forgery（存在性伪造）

• 定义：
  攻击者能够伪造一个已知消息的签名，但这个消息可能是随机的或没有实际意义的。换句话说，攻击者无法控制伪造的消息内容。

• 解释：
  在存在性伪造中，攻击者可以生成一个消息 $m’$ 和对应的签名 $S’$，使得 $(m’, S’)$ 通过公钥验证，但 $m’$ 可能是无意义的（比如一串随机字符）。
  攻击者无法选择有意义的消息（比如“给 Bob 支付 1000 美元”），但他们仍然能够生成一个“合法”的签名对。

• 危害：
  这种攻击的危害通常较小，因为伪造的消息可能没有实际用途。但在某些情况下，攻击者可能通过伪造无意义的消息来制造混乱，或者利用系统漏洞进一步攻击。

• 现实性：
  存在性伪造在理论上比选择性伪造更容易实现，尤其是在一些不安全的签名方案中。例如，如果签名方案没有引入随机性，攻击者可能通过数学方法构造出伪造的签名对。

Naïve Protocol（基于 RSA 的简单签名协议）

1. 密钥生成（Key Generation）

   • $n = pq$：选择两个大素数 $p$ 和 $q$，计算它们的乘积 $n$。这是 RSA 算法的基础模数。
   • 选择两个整数 $d$ 和 $e$，使得它们满足 $d \times e \equiv 1 \pmod{\phi(n)}$，其中 $\phi(n) = (p-1)(q-1)$ 是欧拉函数，$e$ 必须与 $\phi(n)$ 互素。
   • $A_v = (n, e)$：公钥（验证密钥）是 $(n, e)$，用于验证签名。
   • $A_s = (n, d)$：私钥（签名密钥）是 $(n, d)$，用于生成签名。

2. 签名生成（Signature Generation）

   • 假设要签名的消息是 $m$，且 $m \in \mathbb{Z}_n^*$，即 $m$ 是模 $n$ 下的可逆元素（通常 $0 < m < n$，且 $m$ 与 $n$ 互素）。
   • 签名 $S$ 的计算方式是： $$ S = m^d \mod n $$ 这实际上是使用私钥 $(n, d)$ 对消息 $m$ 进行 RSA 解密操作（在 RSA 签名中，签名过程使用私钥，看起来像是“解密”）。

3. 签名验证（Signature Verification）

   • 验证者收到消息 $m$ 和签名 $S$，使用公钥 $(n, e)$ 验证： $$ S^e \mod n $$ 如果 $S^e \mod n = m$，则签名有效。这实际上是使用公钥对签名 $S$ 进行 RSA 加密操作，验证是否能恢复原始消息 $m$。

存在的问题

这个简单的 RSA 签名协议有一个致命的漏洞：攻击者（Eve）可以利用 RSA 的同态性质（homomorphic property）来欺骗 Alice（签名者），让她在不知情的情况下为某个消息 $m$ 生成签名。

RSA 的同态性质

RSA 的同态性质指的是：

• 如果 $S_1 = m_1^d \mod n$ 和 $S_2 = m_2^d \mod n$，
  那么： $$ S_1 \cdot S_2 = (m_1 \cdot m_2)^d \mod n $$ 也就是说，两个消息 $m_1$ 和 $m_2$ 的签名的乘积，等于它们的乘积 $m_1 \cdot m_2$ 的签名。

攻击步骤

Eve 利用这个性质，通过以下步骤欺骗 Alice 签署一个她不想签名的消息 $m$：

1. Eve 的目标：Eve 希望 Alice 签署一个隐藏的消息 $m$，但 Alice 并不知道 $m$ 的内容。
2. Eve 选择随机数：Eve 随机选择一个 $r \in \mathbb{Z}_n^*$，即 $r$ 是模 $n$ 下的可逆元素。
3. Eve 计算伪造消息：Eve 计算一个伪造的消息 $m’$，其中： $$ m’ = m \times r^e \mod n $$ 这里 $r^e \mod n$ 是 $r$ 使用公钥 $e$ 加密的结果。
4. Eve 让 Alice 签名：Eve 要求 Alice 签署这个伪造的消息 $m’$。Alice 使用她的私钥 $d$ 计算签名： $$ S’ = (m’)^d \mod n $$ 代入 $m’ = m \times r^e \mod n$，我们得到： $$ S’ = (m \times r^e)^d \mod n = m^d \times (r^e)^d \mod n $$ 因为 $e \times d \equiv 1 \pmod{\phi(n)}$，所以 $(r^e)^d = r^{e \cdot d} \equiv r \pmod{n}$。因此： $$ S’ = m^d \times r \mod n $$
5. Eve 计算目标签名：Eve 收到 $S’$，然后计算： $$ S = \frac{S’}{r} \mod n $$ 代入 $S’ = m^d \times r \mod n$，我们得到： $$ S = \frac{m^d \times r}{r} \mod n = m^d \mod n $$ 这样，Eve 就得到了消息 $m$ 的签名 $S = m^d \mod n$。
6. 结果：Eve 现在拥有一个有效的消息-签名对 $(m, S)$。当验证者使用公钥 $(n, e)$ 验证时： $$ S^e = (m^d)^e = m^{d \cdot e} \equiv m \pmod{n} $$ 签名通过验证！Eve 成功欺骗了 Alice，让她签署了消息 $m$，而 Alice 并不知道自己签署了什么。

PKCS#1 签名方案 (RFC2313)

PKCS#1（Public Key Cryptography Standards #1）是一个标准，定义了基于 RSA 算法的加密和签名方案。RFC2313 是它的一个早期版本（后来被更新为 RFC8017，即 PKCS#1 v2.2）。

签名生成（Sign Generation）

这是 Alice（发送者）生成签名的过程，分为以下步骤：

1. $n = pq$ (1024-bit modulus)

   • $n$ 是 RSA 模数，由两个大素数 $p$ 和 $q$ 相乘得到。
   • 这里 $n$ 是 1024 位，意味着 $n$ 的大小是 $2^{1024}$ 数量级。这是 RSA 算法的安全基础，1024 位在过去是常见的选择（但现在推荐使用更大的模数，如 2048 位或更高，以应对现代计算能力）。

2. Alice calculates $D = h(m)$ (160-bit hash)

   • Alice 对消息 $m$ 应用哈希函数 $h$，生成一个 160 位的哈希值 $D$。
   • 160 位通常对应于 SHA-1 哈希算法（SHA-1 输出 160 位）。哈希函数的作用是将任意长度的消息压缩为固定长度的摘要，同时确保消息的完整性（即消息改变时哈希值会改变）。

3. Define encryption block: $EB = [ 00 | BT | PS | 00 | D ]$

   • Alice 构造一个加密块 $EB$，这是 PKCS#1 签名方案的核心部分，用于将哈希值 $D$ 嵌入到一个固定格式的块中。
   • 加密块 $EB$ 的结构如下：
     • 00：一个字节的 0x00，用于分隔符。
     • BT（Block Type）：块类型，指示这是哪种类型的填充。PKCS#1 v1.5 中，签名使用 BT = 0x01（表示私钥操作）。
     • PS（Padding String）：填充字符串，用于将 $EB$ 的长度扩展到与模数 $n$ 相同的长度（1024 位）。对于 BT = 0x01，PS 是一串 0xFF 字节。
     • 00：另一个 0x00 字节，作为分隔符。
     • D：160 位的哈希值 $h(m)$。

   计算 $EB$ 的长度

   • 模数 $n$ 是 1024 位，因此 $EB$ 也必须是 1024 位。
   • 已知：
     • 第一个 0x00：8 位（1 字节）。
     • BT：8 位（1 字节）。
     • 第二个 0x00：8 位（1 字节）。
     • $D$: 160 位（20 字节）。
   • 总共：$8 + 8 + 8 + 160 = 184$ 位。
   • 还需要填充 $1024 - 184 = 840$ 位（即 105 字节）。
   • 因此，PS 是 105 字节的 0xFF。

   最终 $EB$ 长度是：$864$ 位（PS + 前缀）+ $160$ 位（$D$）= $1024$ 位，与模数 $n$ 长度一致。

4. Alice calculates $S = EB^d \mod n$

   • Alice 使用她的私钥指数 $d$，对加密块 $EB$ 进行 RSA 签名计算： $$ S = EB^d \mod n $$
   • 这是 RSA 签名的核心步骤，相当于用私钥对 $EB$ 进行“加密”。这里的 $EB$ 已经包含了消息的哈希值 $h(m)$，因此签名 $S$ 间接地绑定了消息 $m$。

5. Alice sends $(S, m)$

   • Alice 将签名 $S$ 和原始消息 $m$ 一起发送给 Bob。
   • 签名 $S$ 是 1024 位（与模数 $n$ 长度相同），消息 $m$ 是原始数据。

签名验证（Sign Verification）

这是 Bob（接收者）验证签名的过程，分为以下步骤：

1. $S = EB^d \mod n$

   • Bob 收到 $(S, m)$，其中 $S$ 是 Alice 用私钥生成的签名。
   • Bob 知道 Alice 的公钥 $(e, n)$，他用公钥指数 $e$ 对签名 $S$ 进行解密： $$ S^e \mod n $$
   • 根据 RSA 算法的性质： $$ (EB^d)^e \mod n = EB \mod n $$
   • 因此，Bob 得到： $$ S^e \mod n = EB \mod n $$
   • 这一步恢复了原始的加密块 $EB$。

2. Bob calculates $S^e \mod n = EB \mod n$

   • Bob 验证 $S^e \mod n$ 是否符合 $EB$ 的格式。
   • 回忆 $EB$ 的结构：$[ 00 | BT | PS | 00 | D ]$。
   • Bob 检查：
     • 第一个字节是否为 0x00。
     • BT 是否为 0x01（签名操作）。
     • PS 是否为 105 字节的 0xFF。
     • 第二个 0x00 是否存在。
     • 最后 160 位是否是一个有效的哈希值。

3. Bob checks the first 864 bits are valid

   • Bob 验证 $EB$ 的前 864 位（即 $[ 00 | BT | PS | 00 ]$）是否符合 PKCS#1 v1.5 的格式：
     • 第一个字节：0x00。
     • 第二个字节：0x01（BT）。
     • 接下来的 105 字节：0xFF（PS）。
     • 第 108 个字节：0x00。
   • 如果这些位不符合预期，签名无效。

4. Bob checks the last 160 bits are valid (i.e., $= h(m)$)

   • Bob 提取 $EB$ 的最后 160 位，得到 $D’$。
   • Bob 自己计算消息 $m$ 的哈希值： $$ D = h(m) $$
   • 然后比较： $$ D’ \stackrel{?}{=} D $$
   • 如果 $D’ = D$，说明签名是有效的，消息 $m$ 没有被篡改，且确实来自 Alice（因为只有 Alice 的私钥能生成这样的签名）。

数字签名算法 (DSA, Digital Signature Algorithm)

DSA 是一种基于离散对数问题的数字签名方案，由 NIST（美国国家标准与技术研究院）在 1991 年提出，并被选为数字签名标准 (DSS)。

参数选择 (Parameter Selection)

DSA 的第一步是选择全局参数，这些参数通常由系统或标准定义，供所有用户共享。

1. 选择哈希函数 $H$

   • 哈希函数 $H$ 用于将消息 $m$ 压缩为固定长度的摘要。
   • 最初使用 SHA-1：DSA 最初使用 SHA-1（输出 160 位）。SHA-1 是 1990 年代的主流哈希算法。
   • 目前推荐 SHA-2：由于 SHA-1 存在安全漏洞（如碰撞攻击），现代标准推荐使用 SHA-2 系列（如 SHA-256，输出 256 位）。在 DSA 中，哈希值通常会被截断或处理以匹配 $q$ 的位长度。

2. 选择长度 $N$，$L$

   • $N$：子群阶 $q$ 的位长度。
   • $L$：模数 $p$ 的位长度。
   • 要求 $N < L$，因为 $q$ 是 $p-1$ 的因子，$q$ 必须比 $p$ 小。
   • 常见的选择（根据 NIST 标准）：
     • 早期：$L = 1024$，$N = 160$。
     • 现代：$L = 2048$，$N = 224$ 或 $L = 3072$，$N = 256$。

3. 选择一个 $N$-位素数 $q$

   • $q$ 是一个 $N$-位素数，定义了子群的阶。
   • 例如，如果 $N = 160$，则 $q$ 是一个 160 位的素数。

4. 选择一个 $L$ 位素数模数 $p$，使得 $p-1$ 是 $q$ 的倍数

   • $p$ 是一个 $L$-位素数。
   • 要求 $p-1$ 是 $q$ 的倍数，即 $p-1 = k \cdot q$，其中 $k$ 是一个整数。
   • 这确保模 $p$ 的乘法群中存在一个阶为 $q$ 的子群。

5. 选择一个随机整数 $h$

   • $h$ 是一个随机整数，满足 $1 < h < p-1$。
   • $h$ 用于生成子群的生成元 $g$。

6. 计算 $g = h^{(p-1)/q} \mod p$

   • 计算生成元 $g$： $$ g = h^{(p-1)/q} \mod p $$
   • 由于 $p-1$ 是 $q$ 的倍数，$(p-1)/q$ 是一个整数。
   • $g$ 是模 $p$ 的一个元素，其阶为 $q$，即 $g^q \equiv 1 \mod p$，这是费马小定理的结论（$a^{p-1} \mod p \equiv 1$）。
   • 如果 $g = 1$，说明 $h$ 选择的不好，$g$ 无法生成阶为 $q$ 的子群，需要重新选择 $h$ 并重复计算。

密钥生成和分发 (Key Generation and Distribution)

在参数 $p, q, g$ 确定后，用户生成自己的密钥对。

1. 在 $0 < x < q$ 中随机选择密钥 $x$

   • 私钥 $x$ 是一个随机整数，满足 $0 < x < q$。
   • 例如，如果 $q$ 是 160 位，$x$ 是一个 160 位的随机数。

2. 计算公钥：$y = g^x \mod p$

   • $y$ 是模 $p$ 的一个元素，属于阶为 $q$ 的子群。

签名生成 (Sign Generation)

这是发送者（例如 Alice）对消息 $m$ 生成签名的过程。

1. 选择随机 $k \in \mathbb{Z}_q^*$

   • 选择一个随机整数 $k$，满足 $1 < k < q$。
   • $k$ 必须是 每个消息唯一 的（即不能重复使用），否则会泄露私钥（后面会解释原因）。
   • $\mathbb{Z}_q^*$ 表示模 $q$ 的可逆元素集合，即 ${1, 2, \ldots, q-1}$。

2. 计算 $r = (g^k \mod p) \mod q$

   • 如果 $r = 0$，需要重新选择 $k$，因为 $r = 0$ 是不允许的（会导致签名无效）。

3. 计算 $s = (k^{-1} (H(m) + x r)) \mod q$

   • $H(m)$：消息 $m$ 的哈希值。
   • $x$：私钥。
   • $k^{-1}$：$k$ 在模 $q$ 下的乘法逆元，即满足 $k \cdot k^{-1} \equiv 1 \mod q$。
   • 如果 $s = 0$，需要重新选择 $k$，因为 $s = 0$ 是不允许的。

4. 签名: $(r, s)$

   • 最终的签名是一个整数对 $(r, s)$。
   • 签名 $(r, s)$ 和消息 $m$ 一起发送给接收者。

签名验证 (Sign Verification)

这是接收者（例如 Bob）验证签名的过程。

1. 验证
   • 检查 $r$ 和 $s$ 是否在合法范围内：
     • $0 < r < q$
     • $0 < s < q$
   • 如果 $r$ 或 $s$ 不满足条件，签名无效。
2. 计算 $w = s^{-1} \mod q$
3. 计算 $u_1 = H(m) \times w \mod q$
4. 计算 $u_2 = r \times w \mod q$
5. 计算 $v = (g^{u_1} \times y^{u_2} \mod p) \mod q$
6. 如果 $v = r$ 则签名合法

DSA 的正确性 (Correctness of DSA)

我们可以通过数学推导证明 DSA 的签名验证是正确的。

• 签名生成时： $$ r = (g^k \mod p) \mod q $$ $$ s = k^{-1} (H(m) + x r) \mod q $$

• 验证时：

  $$ w = s^{-1} \mod q $$

  $$ u_1 = H(m) \times w \mod q $$

  $$ u_2 = r \times w \mod q $$

  $$ v = (g^{u_1} \times y^{u_2} \mod p) \mod q $$

• 从签名公式 $s = k^{-1} (H(m) + x r) \mod q$，可以得到：

  $$ k \cdot s \equiv H(m) + x r \mod q $$

  $$ k \equiv s^{-1} (H(m) + x r) \mod q $$

  $$ k \equiv w (H(m) + x r) \mod q $$

• 代入 $u_1$ 和 $u_2$： $$ u_1 = H(m) \times w \mod q $$ $$ u_2 = r \times w \mod q $$

• 因此：

  $$ u_1 + x u_2 = H(m) \times w + x (r \times w) = w (H(m) + x r) \equiv k \mod q $$

• 验证时计算： $$ v = (g^{u_1} \times y^{u_2} \mod p) \mod q $$

• 由于 $y = g^x \mod p$，代入： $$ g^{u_1} \times y^{u_2} = g^{u_1} \times (g^x)^{u_2} = g^{u_1 + x u_2} \mod p $$

• 根据上面的推导，$u_1 + x u_2 \equiv k \mod q$，所以： $$ g^{u_1 + x u_2} \equiv g^k \mod p \quad (\text{因为 } g \text{ 的阶是 } q) $$

• 因此： $$ v = (g^k \mod p) \mod q = r $$

• 这证明了 $v = r$，验证是正确的。

认证（Authentication）

在不安全信道上，在存在主动攻击者且没有共享秘密的情况下实现认证。

攻击类型

1. Imperson（冒充）
   攻击者假装成合法用户或实体，试图欺骗系统或另一方以获取访问权限或敏感信息。例如，攻击者可能伪造身份信息（如用户名和密码）来登录系统。

2. Relay（中继）
   攻击者拦截通信双方的消息，并将这些消息转发给另一方，假装自己是合法的通信方。这种攻击通常用于绕过身份验证机制。例如，攻击者可能拦截用户发送的登录请求，然后将其转发给服务器，获取访问权限。

3. Interleaving（交织）
   这种攻击涉及从一个或多个先前或并发的通信会话中选择性地组合信息。攻击者可能会利用多个会话中的数据片段，构造一个看似合法的通信，从而欺骗系统或用户。例如，攻击者可能从一个会话中获取部分认证数据，再从另一个会话中获取其他数据，组合后伪造身份。

4. Reflection（反射）
   攻击者将正在进行的通信会话中的信息发送回原始发送方，试图欺骗发送方认为这是合法的响应。这种攻击通常利用协议设计中的漏洞，例如缺乏对消息来源的严格验证。

5. Forced Delay（强制延迟）
   攻击者拦截消息并故意延迟其传递，而不是立即中继（与 Relay 不同）。这种延迟可能被用来制造混乱、干扰协议的正常运行，或者在特定时间点利用延迟的消息。例如，攻击者可能延迟一个认证消息，使系统认为会话已超时，从而迫使用户重新认证并暴露更多信息。

6. Chosen Text（选择文本）
   这种攻击是指攻击者针对挑战-响应（challenge-response）机制发起的攻击。在挑战-响应机制中，系统会发送一个挑战（challenge），用户需要提供正确的响应（response）以证明身份。攻击者可以选择特定的文本（挑战），试图通过分析响应来提取密钥或其他敏感信息。例如，攻击者可能通过多次选择特定的挑战，推导出加密密钥。

密码（Password）

1. 密码的定义与基本工作流程：

   • 简单性：密码是一种简单但较弱的身份验证方法。
   • 创建与共享：
     • Alice 创建一个秘密密码，并在某个时间点将其仅分享给 Bob。
     • 这意味着密码是双方都知道的秘密信息，用于后续的身份验证。
   • 身份验证过程：
     • 当 Alice 需要向 Bob 证明自己的身份时，她会提供她的名字和密码。
     • 如果密码匹配，Bob 就会相信 Alice 的身份。

2. 密码的存储方式：

   • 密码通常以哈希形式存储在服务器上，而不是明文形式。这是为了增加安全性。
   • 哈希是一种单向函数，将密码转换为固定长度的字符串（哈希值）。即使服务器被攻破，攻击者也无法直接获取原始密码，而是需要通过破解哈希来恢复密码。

问题

1. 密码易被窃听和重放攻击：

   • 问题：密码可以通过窃听（eavesdropping）被第三方获取，并且可以被重放（replayed），即攻击者可以重复使用窃听到的密码进行身份冒充。
   • 部分解决方案：通过加密通信通道可以部分解决这个问题，例如使用 Diffie-Hellman 协议和对称加密技术来保护数据传输。
   • 仍然存在的漏洞：即使通道被加密，密码仍然容易受到其他攻击，例如键盘记录器（keyloggers）、设备被盗等。

2. 密码空间有限和重复使用：

   • 问题：
     • 用户通常选择容易记住的密码，导致密码空间较小（keyspace small）。
     • 很多网站仍然限制密码长度为 8、12 或 16 个字符，这进一步缩小了密码的可能性。
     • 用户倾向于在多个网站上重复使用相同的密码，因为难以记住多个复杂的密码。
   • 后果：
     • 字典攻击（dictionary attacks）变得非常可能，因为攻击者可以尝试常用密码或基于字典的组合。
     • 如果一个网站的密码被破解，那么使用相同密码的其他网站也会受到影响。
     • 人类在设计无法被机器破解的密码方面表现不佳，导致密码强度不足。

增强方案

1. 多因素认证（Multi-Factor Authentication, MFA）：

   • 结合多种认证方式（如密码 + 手机验证码、密码 + 生物识别等），即使密码被泄露，攻击者仍然无法完全绕过身份验证。

2. 密码哈希与盐值（Password Hashing with Salt）：

   • 将用户输入的密码进行哈希处理，并加入随机盐值（Salt），以防止彩虹表攻击和哈希碰撞。

3. 密码强度检查：

   • 在注册或更改密码时，强制用户设置强密码（包含大小写字母、数字和特殊字符，长度足够长）。

Lamport’s One Time Passwords

这是一种基于哈希链的认证机制。

1. 设置阶段（Setup）

   Lamport 的 OTP 方案允许用户最多使用 n 次密码。设置阶段的主要步骤如下：

   • 步骤 1：生成哈希链

     • Alice 首先选择一个随机密钥 $k$。

     • 然后，Alice 使用一个单向哈希函数 $h$ 对 $k$ 进行多次哈希运算，形成一个哈希链。具体来说，她计算：

       $$ w = h^n(k) = h(h(\ldots h(k) \ldots)) $$

       其中，$h^n(k)$ 表示对 $k$ 进行 $n$ 次哈希运算的结果。

     • 哈希链的结构如下： $$ k \xrightarrow{h} h(k) \xrightarrow{h} h(h(k)) \xrightarrow{h} \cdots \xrightarrow{h} h^{n-1}(k) \xrightarrow{h} w $$

   • 步骤 2：发送哈希值到服务器

     • Alice 将最终的哈希值 $w$ 发送给服务器，并将计数器 $c$ 初始化为 $n-1$。

2. 认证阶段（Authentication）

   每次 Alice 需要进行身份验证时，她会执行以下步骤：

   • 步骤 1：发送当前哈希值

     • Alice 向服务器发送当前的哈希值 $x = h^c(k)$，其中 $c$ 是当前的计数器值。
     • 发送后，Alice 将计数器 $c$ 减 1。

   • 步骤 2：服务器验证

     • 服务器接收到 $x$ 后，计算 $h(x)$，并与存储的 $w$ 进行比较。
     • 如果 $h(x) = w$，则验证通过，服务器将 $w$ 更新为 $x$（即缩短哈希链）。

优点

1. 服务器上无秘密存储：

   • 服务器只需要存储最终的哈希值 $w$，而不需要存储任何敏感信息（如原始密钥 $k$）。这大大降低了服务器被攻击的风险。

2. 防止重放攻击（Replay Attacks）：

   • 每次认证使用的哈希值都是唯一的，且服务器会更新存储的哈希值 $w$。即使攻击者截获了某个哈希值并尝试重放，服务器也会发现该哈希值已经失效。

缺点

1. 有限的认证次数：

   • 由于哈希链的长度是固定的（最多 $n$ 次），一旦哈希链用尽（即 $c = 0$），用户需要重新生成一个新的哈希链。这意味着在重新生成哈希链之前，只能进行有限次数的认证。

2. 易受预播放攻击（Pre-play Attack）：

   • 如果攻击者能够获取原始密钥 $k$，他们可以提前计算整个哈希链，并在用户正常使用之前进行认证。这种攻击会导致用户的账户被非法访问。

HTOP（HMAC-Based One-Time Password Algorithm）

• HTOP 是一种基于 HMAC（Hash-based Message Authentication Code，基于哈希的消息认证码）的一次性密码算法。
• 它通过结合密钥和计数器生成动态密码，适用于需要强安全性的场景，例如双因素认证。

在使用 HOTP 算法之前，客户端和服务器需要完成以下设置步骤：

1. 协商密钥

   • 客户端和服务器必须事先协商一个足够大的共享密钥 $k$。
   • 密钥长度通常要求大于或等于 160 位（即至少 20 字节），以确保安全性。

2. 同步计数器

   • 客户端和服务器需要同步一个 8 字节（64 位）的计数器 $c$。
   • 计数器 $c$ 随时间递增，用于生成不同的 OTP（一次性密码）。每次认证成功后，计数器会增加 1。

认证阶段（Authentication）

在认证过程中，客户端和服务器通过以下步骤验证身份：

1. 定义 HOTP 函数

   • HOTP 函数的公式为： $$ \text{HOTP}(k, c) = \text{HMAC-SHA-1}(k, c) \mod 10^d $$ 其中：
     • $k$：共享密钥。
     • $c$：当前的计数器值。
     • $\text{HMAC-SHA-1}$：基于 SHA-1 的 HMAC 算法，用于生成消息认证码。
     • $\mod 10^d$：取 HMAC 结果的最低 $d$ 位十进制数字，作为最终的 OTP。通常 $d = 6$，即生成 6 位数字的 OTP。

2. 客户端计算 OTP 并发送

   • 客户端根据当前的计数器值 $c$，使用 HOTP 函数计算 OTP： $$ w = \text{HOTP}(k, c) $$
   • 然后，客户端将计算得到的 OTP $w$ 发送给服务器。

3. 服务器验证 OTP

   • 服务器根据当前的计数器值 $c$，使用相同的 HOTP 函数计算 OTP： $$ \text{HOTP}(k, c) $$
   • 如果服务器计算出的 OTP 与客户端发送的 OTP $w$ 相匹配，则认证成功。
   • 如果匹配成功，服务器会更新计数器 $c$ 的值（通常是加 1）。

TOTP（Time-Based One-Time Password Algorithm）

• TOTP 是一种基于时间的一次性密码算法，它是 HOTP（HMAC-Based One-Time Password Algorithm）的扩展。
• TOTP 的核心思想是将当前时间作为计数器 $c$ 的输入，从而生成动态的、随时间变化的一次性密码。

在 TOTP 中，计数器 $c$ 不再是一个简单的递增计数器，而是由当前时间计算得出的值。具体公式为：

$$ c = \frac{\text{Current time} - T_0}{X} $$

其中：

• Current time：当前的时间戳，通常以秒为单位。
• $T_0$：一个预设的时间基准点，可以是用户注册的时间，也可以是 Unix 时间零点（即 1970 年 1 月 1 日 00:00:00 UTC）。
• $X$：时间步长（time step），表示密码的有效期，通常以秒为单位。例如，$X = 30$ 表示密码每 30 秒更新一次。

挑战-响应认证（Challenge-Response Authentication）

挑战-响应认证是一种身份验证机制，其中一个实体通过证明其对某个秘密的了解来向另一个实体证明自己的身份，而无需直接透露该秘密本身。

关键点：

• 证明知识而不泄露秘密：

  • 实体 A（例如用户或设备）需要向实体 B（例如服务器）证明自己知道某个秘密（如密码、密钥等），但不需要直接将秘密告诉实体 B。
  • 这种方式可以防止秘密被泄露，即使通信被截获，攻击者也无法直接获取秘密。

• 通过响应挑战来证明：

  • 实体 B 向实体 A 发送一个时间相关的挑战（time-variant challenge），这个挑战是动态生成的，通常包含一些随机性或时间戳。
  • 实体 A 根据接收到的挑战和其已知的秘密，计算出一个响应（response）并发送给实体 B。
  • 响应的计算依赖于两个因素：
    1. 挑战：动态生成的内容，确保每次认证的唯一性。
    2. 秘密：实体 A 所拥有的秘密信息。

• 响应的依赖性：

  • 响应必须同时依赖于挑战和秘密，这意味着只有真正知道秘密的实体才能正确生成响应。
  • 如果实体 A 不知道秘密，即使它知道挑战的内容，也无法生成正确的响应。

时间相关参数的重要性

在挑战-响应认证中，使用时间相关的参数（time-variant parameters）是非常重要的，主要用于以下几个目的：

1. 防止重放攻击（Replay Attacks）

   • 重放攻击：攻击者截获一次合法的认证过程，并在后续尝试中重复使用相同的挑战和响应。
   • 解决方案：通过使用时间相关的参数（如 nonce、序列号或时间戳），每次认证的挑战都是唯一的，即使攻击者截获了之前的挑战和响应，也无法在新的认证中使用它们，因为挑战已经失效。

2. 防止交错攻击（Interleaving Attacks）

   • 交错攻击：攻击者试图通过交错多个认证请求和响应来混淆系统，从而绕过正常的认证流程。
   • 解决方案：时间相关的参数可以帮助系统识别每个认证请求的时间顺序，确保认证过程的正确性和完整性。

3. 提供唯一性和及时性保证

   • 唯一性：每次认证的挑战都是唯一的，确保认证过程不会重复或混淆。
   • 及时性：通过使用时间戳或其他时间相关的参数，系统可以验证认证请求是否在有效时间内发出，防止过期的认证请求被滥用。

4. 防止某些选择明文攻击（Chosen-Ciphertext Attacks）

   • 选择明文攻击：攻击者可以通过选择特定的输入（如挑战）来分析系统的响应，从而推断出秘密信息。
   • 解决方案：通过使用随机性和时间相关的参数，挑战变得不可预测，攻击者无法通过选择特定的挑战来获取有用的信息。

时间相关参数的示例

为了实现上述功能，挑战-响应认证通常会使用以下几种时间相关参数：

1. Nonces（随机数）

   • 定义：Nonce 是一个一次性使用的随机数，通常用于确保每次认证的唯一性。
   • 作用：
     • 每次认证时，服务器生成一个新的随机数作为挑战的一部分。
     • 客户端根据随机数和秘密计算响应，确保每次认证的响应都是唯一的。
     • 由于 nonce 是一次性使用的，即使攻击者截获了 nonce 和响应，也无法在未来的认证中重复使用。

2. Sequence Numbers（序列号）

   • 定义：序列号是一个递增的数字，用于标识认证请求的顺序。
   • 作用：
     • 每次认证时，服务器生成一个新的序列号作为挑战的一部分。
     • 客户端根据序列号和秘密计算响应，确保认证请求的顺序性。
     • 序列号可以帮助系统检测交错攻击或重复的认证请求。

3. Timestamps（时间戳）

   • 定义：时间戳是一个表示当前时间的值，通常以秒为单位。
   • 作用：
     • 每次认证时，服务器将当前时间作为挑战的一部分。
     • 客户端根据时间戳和秘密计算响应，确保认证请求的时效性。
     • 时间戳可以帮助系统验证认证请求是否在有效时间内发出，防止过期的认证请求被滥用。

基于对称加密的挑战-响应认证机制（Challenge-Response Authentication using Symmetric Crypto）

• 共享密钥：Alice 和 Bob 事先共享了一个密钥 $k$，并且双方同意使用某种基于密钥的加密算法或哈希算法（例如 $E_k$）。
• 目标：通过挑战-响应机制，Bob 验证 Alice 的身份，确保 Alice 知道共享密钥 $k$，而无需直接暴露密钥。

认证流程

1. Alice 初始化通信

   • Alice 向 Bob 发送一个简单的消息，例如 “hello”，表示她希望与 Bob 进行通信。

2. Bob 生成 nonce 并发送给 Alice

   • Bob 生成一个随机数（nonce），记为 $r$。
   • Bob 将 nonce $r$发送给 Alice。

3. Alice 生成 nonce 并发送响应

   • Alice 收到 Bob 的 nonce $r$后，也生成自己的随机数（nonce），记为 $r’$。
   • Alice 使用共享密钥 $k$和某种加密或哈希算法（例如 $E_k$），对两个 nonce 的组合 $r \parallel r’$进行加密或计算哈希值，得到一个令牌（token），即： $$ \text{Token} = E_k(r \parallel r’) $$
   • Alice 将自己的 nonce $r’$和令牌 $E_k(r \parallel r’)$一起发送给 Bob。

4. Bob 验证响应

   • Bob 收到 Alice 发送的 nonce $r’$和令牌 $E_k(r \parallel r’)$。
   • Bob 使用共享密钥 $k$和相同的加密或哈希算法 $E_k$，重新计算 $E_k(r \parallel r’)$。
   • Bob 比较自己计算出的 $E_k(r \parallel r’)$与 Alice 发送的令牌是否一致。
     • 如果两者一致，则说明 Alice 确实知道共享密钥 $k$，Bob 可以确认 Alice 的身份。
     • 如果不一致，则说明 Alice 不知道共享密钥 $k$，Bob 拒绝认证。

基于非对称加密的挑战-响应认证机制（Challenge-Response Authentication using Asymmetric Crypto）

• 非对称加密：Alice 和 Bob 使用非对称加密算法（如 RSA 或 ECC），其中 Alice 拥有一对密钥：
  • 私钥：$A_{\text{private}}$，仅 Alice 知道。
  • 公钥：$A_{\text{public}}$，Alice 将其公开，Bob 有该公钥的副本，并且在之前某个时间点验证过其真实性。

认证流程

1. Alice 初始化通信

   • Alice 向 Bob 发送一个简单的消息，例如 “hello”，表示她希望与 Bob 进行通信。

2. Bob 生成 nonce 并发送给 Alice

   • Bob 生成一个随机数（nonce），记为 $r$。
   • Bob 将 nonce $r$发送给 Alice。

3. Alice 对 nonce 进行签名并发送

   • Alice 收到 Bob 的 nonce $r$ 后，使用她的私钥 $A_{\text{private}}$ 对 nonce 进行数字签名。
     • 数字签名的过程可以表示为： $$ \text{Signature} = \text{sign}{A}(r) $$ 其中，$\text{sign}{A}(r)$ 表示使用 Alice 的私钥对 nonce $r$ 进行签名的结果。
   • Alice 将签名结果发送给 Bob。

4. Bob 验证签名

   • Bob 收到 Alice 发送的签名结果 $\text{sign}_{A}(r)$。
   • Bob 使用 Alice 的公钥 $A_{\text{public}}$ 对签名进行验证。
     • 验证的过程可以表示为： $$ \text{Verify}{A{\text{public}}}(\text{sign}_{A}(r), r) $$ 如果签名是有效的，则说明 Alice 确实使用了她的私钥对 nonce 进行签名，Bob 可以确认 Alice 的身份。
     • 如果签名无效，则说明 Alice 不是合法的实体，Bob 拒绝认证。

零知识证明（Zero Knowledge Proofs）

• 零知识证明（ZKP）是一种允许证明者（Prover）向验证者（Verifier）证明其知道某个秘密，同时不泄露任何关于该秘密的信息的协议。
• 这种协议的核心思想是：证明者能够说服验证者相信他们拥有某种知识，但不会透露具体的细节。

特点：

• 多轮挑战-响应机制：ZKP 通常由多轮挑战和响应组成。在每一轮中，验证者会提出一个随机的挑战，证明者需要根据这个挑战给出相应的响应。
• 欺骗概率：在一个单一的回合中，攻击者（Adversary）可能以很小的概率成功欺骗验证者。然而，随着回合数的增加，这种欺骗成功的概率会呈指数级下降。
• 安全性保证：当回合数足够大时，攻击者成功欺骗的概率可以接近于零，从而确保了协议的安全性。

应用：

• ZKP 协议虽然设计起来比较困难，但在挑战-响应认证（Challenge-Response Authentication）中有广泛的应用。

Ali Baba’s Cave

• 这是一个经典的零知识证明示例，由 Quisquater 和 Guillou 在 1989 年提出。
• 场景设定在一个有两个入口（A 和 B）的山洞中，山洞中间有一个只能用密码打开的机关门（Trapdoor）。只有知道密码的人才能通过机关门从一个入口移动到另一个入口。

角色：

• Peggy（证明者）：声称知道密码，并希望向 Victor（验证者）证明她确实知道密码，但不想透露密码本身。
• Victor（验证者）：想要确认 Peggy 是否真的知道密码，但不需要知道密码的具体内容。

过程：

• 步骤 1：Victor 站在山洞的入口处，而 Peggy 随机选择其中一个入口（A 或 B）进入山洞。
• 步骤 2：Peggy 站在机关门前，此时 Victor 进入山洞并随机喊出一个入口（A 或 B），要求 Peggy 从该入口出来。
• 结果：
  • 如果 Peggy 知道密码，她可以通过机关门自由移动，无论 Victor 要求她从哪个入口出来，她都能成功完成任务。
  • 如果 Peggy 不知道密码，她无法通过机关门，因此只有 $\frac{1}{2}$ 的概率能够正确回应 Victor 的要求。 重复与概率：
  • 每进行一次这样的交互，Peggy 成功欺骗 Victor 的概率为 $\frac{1}{2}$。
  • 如果重复 $n$ 次，Peggy 成功欺骗的概率为 $2^{-n}$。随着 $n$ 的增加，欺骗成功的概率迅速降低。

TLS

TLS（Transport Layer Security，传输层安全协议）是一种用于在网络上提供安全通信的协议，广泛用于 HTTPS。它通过非对称和对称加密的结合，确保客户端（如浏览器）与服务器之间的通信保密性、完整性和身份验证

基本握手流程

TLS 协议的核心是握手过程，用于建立安全连接。握手涉及以下步骤：

• 客户端（例如浏览器）发起连接，向服务器发送一条消息，包含：

  • 支持的 SSL/TLS 版本（例如 TLS 1.3）。
  • 客户端支持的加密算法列表（ciphers，如 AES、RSA 等）。
  • 其他信息（如随机数，用于后续密钥生成）。

• 服务器响应客户端，包含：

  • 确认使用的 SSL/TLS 版本（通常选择双方支持的最高版本）。
  • 从客户端提供的加密算法列表中选择一个（例如 AES-256-GCM）。
  • 服务器的证书（由 CA 签发的公钥证书，包含服务器的公钥和身份信息）。

身份验证

• 客户端验证服务器的身份：

  • 客户端使用内置的 CA 公钥验证服务器证书的签名，确保证书有效且未被篡改。
  • 验证证书中的域名是否与客户端访问的域名匹配（例如 www.example.com）。
  • 确认证书未过期或未被撤销。

• 可选步骤：服务器也可以要求客户端提供证书进行身份验证（双向认证）。

  • 这种方式常见于高安全需求的场景（如企业内部系统），但在普通 HTTPS 中通常只验证服务器身份。

密钥生成与加密

• 客户端生成 pre-master secret，并通过服务器的公钥（从证书中获取）加密后发送给服务器：

  • 具体方式取决于选择的加密算法。例如，在 RSA 密钥交换中，客户端直接生成 pre-master secret 并用服务器公钥加密。
  • 在现代 TLS（如 TLS 1.3）中，更常用 Diffie-Hellman 密钥交换（DHE/ECDHE），客户端和服务器协作生成共享密钥，确保前向安全性（forward secrecy）。
  • 服务器用自己的私钥解密，获取 pre-master secret。

• 客户端和服务器在消息中包含随机数（nonce），用于防止重放攻击（replay attack）：

  • 随机数确保每次握手生成的消息都是唯一的，即使攻击者截获并重发旧消息，也无法通过验证。

• 握手完成后，双方使用 pre-master secret 派生出会话密钥（master secret），并基于此进行对称加密通信（例如 AES）。从此刻起，所有消息都加密，确保机密性和完整性。

协议特点与安全性

• 身份验证：通过 CA 签发的证书，客户端可以信任服务器的身份。可选的双向认证进一步增强安全性。
• 防重放攻击：随机数的使用确保消息不可被重复利用。
• 前向安全性：现代 TLS（如使用 ECDHE）确保即使服务器私钥泄露，过去的会话密钥仍安全。
• 混合加密：非对称加密用于密钥交换（慢但安全），对称加密用于数据传输（快且高效）。

秘密分割 (Secret Splitting)

问题背景

• 情境：你是可口可乐的 CEO，需保护配方不被百事可乐的间谍获取。
• 风险：
  • 直接告诉最信任的员工可能导致：
    • 员工叛变投靠对手。
    • 员工被威胁或被迫泄露。
• 目标：将秘密分割成多个部分，每个部分单独无用。

解决方案：使用 XOR 进行秘密分割

基本方法（两人分割）

• 假设：Trent 想保护消息 $m$。
• 步骤：
  1. 生成一个与 $m$ 等长的随机字符串 $r$。
  2. 计算 $s = m \oplus r$。
  3. 将 $r$ 给 Alice，$s$ 给 Bob。
• 恢复消息：
  • Alice 和 Bob 合作，通过 $s \oplus r$ 恢复 $m$。
  • 公式：$s \oplus r = (m \oplus r) \oplus r = m$。

安全性

• 如果 $r$ 是真正随机的，系统是完全安全的（类似于一次性密码本，One-Time Pad）。
• 单独的 $r$ 或 $s$ 无法泄露 $m$ 的任何信息。

扩展到 $n$ 人

• 步骤：
  1. 生成 $n-1$ 个随机字符串 $r_1, r_2, \dots, r_{n-1}$。
  2. 将 $r_1$ 给第 1 个人，$r_2$ 给第 2 个人，依此类推，直到 $r_{n-1}$ 给第 $n-1$ 个人。
  3. 计算第 $n$ 个人的部分：$r_1 \oplus r_2 \oplus \dots \oplus r_{n-1} \oplus m$，并给第 $n$ 个人。
• 恢复消息：
  • 所有人合作，将所有部分进行 XOR 操作：$r_1 \oplus r_2 \oplus \dots \oplus r_{n-1} \oplus (r_1 \oplus r_2 \oplus \dots \oplus r_{n-1} \oplus m) = m$。

优点

• 每个部分单独无用，必须所有部分集合才能恢复秘密。
• 随机性保证了安全性，防止单一部分泄露信息。

秘密共享 (Secret Sharing)

问题背景

• 情境：你负责管理公司资金，需设计一个机制来保护资金安全。
• 目标：
  • 确保单个高管无法提取资金。
  • 确保任意两个高管联合也无法提取资金。
  • 至少需要五名高管中的三名（即“(3,5)-阈值方案”）达成一致才能提取资金。
• 定义：这种机制称为秘密共享，目标是将秘密分成多份，只有满足特定数量的份数集合时才能恢复秘密。

Shamir 秘密共享 (Shamir’s Secret Sharing, SSS)

基本概念

• Shamir 秘密共享：一种将秘密分成 $n$ 份的算法，其中至少需要 $t$ 份（$1 \leq t \leq n$）才能恢复秘密，少于 $t$ 份无法获取任何信息。
• 数学基础：利用多项式插值原理。
  • 一个 $t-1$ 次多项式需要 $t$ 个点才能唯一确定。
  • 例如：二次多项式 $y = ax^2 + bx + c$ 需要 3 个点来确定系数 $a, b, c$。

图示说明

• 图中展示了多个二次多项式（橙色、绿色、红色曲线），通过 2 个点（蓝色圆点）可以拟合出无数条曲线，说明 2 个点不足以确定唯一的多项式。
• 当有 3 个点时，唯一的多项式可以被确定（橙色曲线穿过所有 3 个点）。

具体步骤

• 假设：Trent 希望将消息 $m$ 分发给 $n$ 个用户，任何 $t$ 个用户（$1 \leq t \leq n$）可以恢复 $m$。

• 操作流程：

  1. 选择素数 $p$：
     • 选择一个大于 $\max(m, n)$ 的素数 $p$，以便在有限域 $\mathbb{Z}_p$ 中进行计算。
  2. 构造多项式 $f(x)$：
     • 创建一个 $t-1$ 次多项式：$f(x) = m + a_1 x + a_2 x^2 + \dots + a_{t-1} x^{t-1}$。
     • 其中：
       • $m$ 是秘密（即多项式的常数项，$f(0) = m$）。
       • 系数 $a_1, a_2, \dots, a_{t-1}$ 是随机选择的，且 $0 \leq a_i < p$，彼此独立。
  3. 生成共享点：
     • Trent 选择 $n$ 个不同的 $x_i$（满足 $1 \leq x_i < p$）。
     • 计算对应的 $y_i = f(x_i)$，得到 $n$ 个点 $(x_i, f(x_i))$。
  4. 分发共享：
     • 将点 $(x_i, f(x_i))$ 分配给第 $i$ 个用户。

• 恢复秘密：

  • 当 $t$ 个用户集合时，他们提供各自的点 $(x_i, f(x_i))$。
  • 使用拉格朗日插值法重建 $t-1$ 次多项式 $f(x)$。
  • 计算 $f(0)$，即可得到秘密 $m$。

拉格朗日插值

• 给定 $t$ 个点 $(x_1, y_1), (x_2, y_2), \dots, (x_t, y_t)$，多项式 $f(x)$ 可通过以下公式重建： $$ f(x) = \sum_{i=1}^t y_i \cdot \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} $$
• 特别地，秘密 $m = f(0)$，即： $$ m = f(0) = \sum_{i=1}^t y_i \cdot \prod_{j \neq i} \frac{-x_j}{x_i - x_j} $$
• 所有计算在模 $p$ 下进行。

应用到 (3,5)-阈值方案

• 参数：
  • $n = 5$（5 名高管）。
  • $t = 3$（至少 3 人才能恢复秘密）。
• 过程：
  1. 选择素数 $p > \max(m, 5)$。
  2. 构造一个 2 次多项式：$f(x) = m + a_1 x + a_2 x^2$，其中 $a_1, a_2$ 随机，$0 \leq a_1, a_2 < p$。
  3. 选择 5 个不同的 $x_i$（例如 $x_1 = 1, x_2 = 2, x_3 = 3, x_4 = 4, x_5 = 5$）。
  4. 计算 $f(x_i)$，分发点 $(x_i, f(x_i))$ 给 5 名高管。
• 恢复：
  • 任意 3 名高管集合，提供他们的点。
  • 通过拉格朗日插值重建 $f(x)$，计算 $f(0) = m$。
• 安全性：
  • 少于 3 个点（例如 1 或 2 个高管）无法确定唯一的 $f(x)$，因此无法恢复 $m$。

安全性分析

• 少于 $t$ 份的限制：
  • $t-1$ 个点只能确定一个 $t-2$ 次多项式，剩余的 $t-1$ 次项有无数可能（对应图中无数条曲线）。
  • 因此，少于 $t$ 个点无法获得任何关于 $m$ 的信息。
• $t$ 份或更多：
  • $t$ 个点可以唯一确定 $t-1$ 次多项式，恢复 $m$。
• 有限域 $\mathbb{Z}_p$：
  • 使用模 $p$ 运算确保计算可控，同时保持数学性质（例如多项式的唯一性）。

优点

• 灵活性：可以自由设置 $t$ 和 $n$，适用于不同场景。
• 安全性：少于 $t$ 份无法泄露任何信息（信息论意义上完全安全）。
• 简单性：基于多项式插值，易于实现。

局限性

• 计算复杂度：拉格朗日插值在 $t$ 较大时计算量增加。
• 信任假设：假设分发者（Trent）是可信的，且 $x_i$ 不重复。
• 存储需求：每个用户需存储一个点 $(x_i, f(x_i))$，随 $n$ 增加存储开销增大。

承诺协议

Bit Commitment Schemes

Bit Commitment Schemes（位承诺方案）是一种密码学工具，用于解决以下问题：Alice 想要向 Bob 发送一个秘密消息，但要求 Bob 只能在未来的某个阶段（通过 Alice 提供的额外信息）才能解密该消息，同时 Bob 能够验证消息在承诺阶段未被篡改。以下是两种方案的整理与扩展说明。

Bit Commitment Scheme（交互式位承诺方案）

问题描述
Alice 需要向 Bob 发送一个秘密消息 $m$，但要求：

• Bob 在特定阶段（揭示阶段之前）无法解密消息；
• Bob 能够验证消息在承诺阶段后未被更改。

承诺阶段

1. Bob 生成一个随机字符串 $r$，并将其发送给 Alice。
2. Alice 生成一个随机密钥 $k$，然后用该密钥加密 $r$ 和消息 $m$，生成加密结果 $E_k(r | m)$，并将该加密结果发送给 Bob。
   • $|$ 表示字符串拼接操作。
   • $E_k(\cdot)$ 表示使用密钥 $k$ 进行的加密操作，通常是对称加密算法（如 AES）。

揭示阶段

1. Alice 将密钥 $k$ 发送给 Bob。
2. Bob 使用 $k$ 解密消息，得到 $r | m$，并验证解密出的 $r$ 是否与自己之前生成的 $r$ 一致。
   • 如果一致，说明消息未被篡改，Bob 可以信任消息 $m$。
   • 如果不一致，说明消息可能被篡改，Bob 拒绝接受。

讨论与安全性分析

• 随机字符串 $r$ 的作用：
  $r$ 由 Bob 提供，确保了每次承诺的唯一性（即“新鲜性”）。它防止 Alice 通过预计算或寻找碰撞（如 $E_k(m) = E_k(m’)$）来伪造消息。

  • 例如，若没有 $r$，Alice 可能找到两个消息 $m$ 和 $m’$，使得 $E_k(m) = E_k(m’)$，从而可以在揭示阶段欺骗 Bob。
  • 有了 $r$，Alice 必须承诺 $E_k(r | m)$，这大大增加了碰撞攻击的难度，因为 $r$ 是 Bob 控制的未知变量。

• 密钥 $k$ 的保密性：
  Bob 在揭示阶段之前不知道 $k$，因此无法解密 $E_k(r | m)$。这保证了消息 $m$ 在承诺阶段对 Bob 是隐藏的（即满足“隐藏性”属性）。

• 绑定性（Binding）：
  该方案通过加密和 $r$ 的使用，确保了 Alice 在承诺阶段后无法更改消息 $m$。如果 Alice 试图用不同的消息 $m’$ 欺骗 Bob，她需要找到一个 $k’$，使得 $E_{k’}(r | m’) = E_k(r | m)$，但这在计算上是不可行的（假设 $E$ 是安全的加密算法）。

• 可能的改进：

  • 使用更强的加密算法（如 AES-GCM）可以同时提供保密性和完整性验证。
  • 可以引入时间戳或序列号，进一步增强 $r$ 的新鲜性，防止重放攻击。

Non-interactive Bit Commitment Scheme（非交互式位承诺方案）

问题描述
与交互式方案类似，但要求 Bob 不需要发送任何消息（即非交互式）。Alice 仍然需要承诺一个消息 $m$，并在未来揭示，同时保证消息未被篡改。

承诺阶段

1. Alice 自己生成两个随机字符串 $r$ 和 $s$，然后计算 $x = h(r | s | m)$，其中：
   • $h(\cdot)$ 是一个加密散列函数（如 SHA-256），生成固定长度的散列值（即“blob”）。
   • $r | s | m$ 表示将 $r$、$s$ 和 $m$ 拼接后输入散列函数。
2. Alice 将 $(r, x)$ 发送给 Bob。

揭示阶段

1. Alice 将剩余的数据 $(s, m)$ 发送给 Bob。
2. Bob 使用收到的 $(r, s, m)$，计算 $h(r | s | m)$，并验证其是否等于之前收到的 $x$。
   • 如果相等，说明消息 $m$ 未被篡改，Bob 接受。
   • 如果不相等，说明消息可能被篡改，Bob 拒绝。

讨论与安全性分析

• 非交互性：
  该方案中 Bob 不需要发送任何消息，Alice 独自完成承诺和揭示。这在某些场景（如分布式系统或区块链）中非常有用，因为它减少了通信开销。

• 隐藏性（Hiding）：

  • 散列函数 $h$ 是单向的，Bob 在揭示阶段之前无法从 $x = h(r | s | m)$ 反推出 $m$。
  • 随机字符串 $s$ 由 Alice 保密，防止 Bob 在揭示阶段之前通过暴力破解消息空间来猜测 $m$。
    • 例如，若没有 $s$，Bob 可以尝试用不同的 $m’$，计算 $h(r | m’)$，直到找到匹配的 $x$。但 $s$ 的存在使得这种攻击不可行。

• 绑定性（Binding）：
  散列函数 $h$ 的抗碰撞性保证了 Alice 无法找到另一个 $t$，使得 $h(r | s | m) = h(r | t | m’)$。

  • 如果 Alice 试图在揭示阶段提供 $(s, m’)$，Bob 会发现 $h(r | s | m’) \neq x$，从而拒绝接受。

• 随机字符串 $r$ 的作用：

  • $r$ 确保了每次承诺的唯一性，防止重放攻击。
  • 即使 Alice 控制了 $r$，她仍然无法违反绑定性，因为 $h$ 的抗碰撞性保护了承诺。

• 可能的改进：

  • 使用更强的散列函数（如 SHA-3）以应对未来的量子计算攻击。
  • 引入时间锁或延迟函数，确保 Bob 在特定时间之前无法暴力破解 $s$。
  • 在区块链场景中，可以将 $x$ 记录在链上，增强承诺的不可篡改性。