08 · 安全定义

⏱ 24 分钟 ｜ ⭐⭐ 全教程的思维转折点

🎯 一句话

前面七章你一直在看"这个方案被这样打破了"。 这一章问一个更根本的问题：「安全」到底是什么意思？ 答案会让你意识到，你之前对"安全"的理解一直是错的。

🤔 一、先看看"直觉的安全"错在哪

   直觉版本 ①："攻击者不能从密文恢复出明文"

   ❌ 反例：一个方案泄露明文的【前一半】，但后一半完美隐藏
      → 它满足"不能恢复出完整明文"
      → 但显然不安全 💀

   直觉版本 ②："攻击者不能恢复出明文的任何一个 bit"

   ❌ 反例：一个方案泄露"明文里 1 的个数是奇数还是偶数"
      → 没有泄露任何单独的 bit
      → 但泄露了信息 💀

   直觉版本 ③："攻击者不能恢复出密钥"

   ❌ 反例：Enc(K, m) = m（根本不加密）
      → 密钥完全没泄露！
      → 但这是个笑话 💀

🔑 问题的本质：这些定义都在说"攻击者不能做到某件具体的事"。 但攻击者想要的可能是任何关于明文的信息 —— 我们没法穷举所有他可能想知道的事。

💡 二、思路的翻转：不问"他学到了什么"，问"他能不能分辨"

   ⭐ 关键的翻转：

   与其说"攻击者学不到任何信息"（无法穷举"任何"），
   不如说：

   "攻击者【分辨不出】密文对应的是 m₀ 还是 m₁"
                              ↑ 他自己挑的两条消息！

为什么这个说法覆盖了"任何信息"：

   假设攻击者能学到明文的【任何一点信息】P
   （比如"第一个字符是不是 A"、"长度是不是偶数"、"是不是中文"）

   那他就可以挑：
     m₀ = 满足 P 的消息
     m₁ = 不满足 P 的消息

   → 只要他能算出 P，他就能分辨 → 定义被违反 ⭐

   反过来：如果他【分辨不出】任何一对 m₀/m₁，
          就说明他关于明文【什么都算不出来】

🔑 这就是"不可区分性（Indistinguishability）"的威力： 用一个可操作的、可证伪的条件，覆盖了"任何信息"这个不可穷举的要求。

💡 你在第 4 章 PRG 已经见过同一个模式了 —— 这不是巧合， 整个现代密码学都建立在"不可区分"这个模板上。

🎮 三、IND-CPA：把定义写成一个游戏

⭐ 方案是 IND-CPA 安全的，当且仅当对所有高效的 A：Pr[b' = b] ≤ 1/2 + negl

💡 人话翻译：

就算攻击者能随便让你加密他挑的任何东西， 再让你在他挑的两条消息里随机加密一条， 他也猜不出你加密的是哪条 —— 优势不超过瞎猜。

⭐ 这个定义立刻推出三个重要结论

① 确定性加密永远不安全

   如果 Enc 是确定性的（同样输入 → 同样输出）：

   攻击者：
   ① 先问"加密 m₀" → 得到 c₀
   ② 提交 (m₀, m₁)  → 得到 c*
   ③ 比较 c* 和 c₀ 是否相等 → 100% 判对 💀

   ⭐ 所以【任何 IND-CPA 安全的方案都必须是随机化的】
     （或者带 nonce/状态）

🔑 这一条解释了前面所有的"为什么"： - 为什么 ECB 不安全 → 它是确定性的 - 为什么 CBC 要 IV → 提供随机化 - 为什么 CTR 要 nonce → 提供随机化 - 为什么教科书 RSA 不安全 → 它是确定性的（第 14 章）⭐

一个定义，串起了四个看似无关的设计规则。

② 密文必然比明文长

   随机化 ⟹ 同一条明文有多个可能的密文
   ⟹ 密文空间必须大于明文空间
   ⟹ 密文更长（IV/nonce 就是那个额外开销）

③ 明文长度无法隐藏

   定义里要求 m₀ 和 m₁ 【等长】—— 这不是疏忽，是承认：
   加密【无法隐藏消息长度】

   💥 真实后果：
   · 语音加密里，包长度泄露了说话内容（有研究能识别出词汇）
   · HTTPS 下，页面大小能暴露你访问了哪个页面 ⭐
   · 加密搜索里，结果数量泄露查询内容

   → 要隐藏长度必须【额外填充】，而这是有代价的

🔐 四、IND-CCA：更强的要求

   IND-CPA 的攻击者：只能【加密】他挑的东西
   IND-CCA 的攻击者：还能【解密】他挑的密文（挑战密文 c* 除外）⭐

为什么需要这么强的要求：

   现实中攻击者常常能间接获得"解密结果"：
   ├─ 服务器解密后返回"格式错误" ← padding oracle（第 7 章）
   ├─ 解密成功和失败的响应时间不同
   ├─ 解密后的内容被显示在页面上
   └─ 解密失败会写日志，日志能被观察

   ⭐ 只满足 IND-CPA 的方案在这些场景下会被打穿

🔑 现代标准：能用 IND-CCA 就别用 IND-CPA。 而达到 IND-CCA 的实用方法就是 —— 认证加密（AEAD）。

   AEAD 的思路很直接：
   密文带一个认证标签，验证不通过就【直接拒绝，根本不解密】
   → 攻击者的"解密预言机"变成了一个只会说"无效"的东西
   → 拿不到任何信息 ⭐

🔗 第 11 章讲怎么正确地构造它。

📉 五、"可忽略"到底有多小

   negl(n)：比【任何】多项式的倒数都小

   直觉：1/2ⁿ、1/2^(n/2) 是可忽略的
        1/n¹⁰⁰⁰ 【不是】—— 它只是"很小"

为什么标准要定得这么严：

   如果每次攻击成功率是 1/n¹⁰⁰⁰（看起来极小）
   → 攻击者重复 n¹⁰⁰⁰ 次就成功了
   → 而 n¹⁰⁰⁰ 仍然是【多项式】次 —— 对攻击者是可行的 ⭐

   而 1/2ⁿ 的话，要重复 2ⁿ 次 —— 不可行 ✅

💡 实际参数：128-bit 安全意味着攻击者需要约 2¹²⁸ 次操作。 作为对照：宇宙自大爆炸以来的秒数约 2⁵⁹，全球算力一年约 2⁹⁰ 次运算。

🧭 六、这一章该带走的方法论

   ⭐ 判断"一个方案安全吗"的正确流程：

   ① 它声称达到什么安全目标？（机密性/完整性/...）
   ② 在什么攻击模型下？（CPA / CCA）
   ③ 归约到什么假设？（"破它 ⟹ 分解大整数"）
   ④ 假设本身可信吗？（研究了多少年、有没有量子威胁）

   ❌ 错误的流程："我想不出怎么破它" —— 这什么都不算

🔑 可证明安全（Provable Security）的真实含义： 它不证明"这个方案安全"，它证明"这个方案的安全性归约到某个数学难题"。 如果那个难题被解决了（比如量子计算机解决了因子分解），方案照样完蛋。

"可证明安全"是把信任从"这个方案"转移到"这个数学问题" —— 而后者被全世界研究了几十年，比前者可信得多。

🔗 和站内其他章的关系

✅ 检查点

1. "攻击者不能恢复明文"这个定义错在哪？给一个反例。
2. 不可区分性的思路翻转是什么？它为什么能覆盖"任何信息"？
3. 描述 IND-CPA 游戏的五个步骤。
4. 为什么确定性加密永远不满足 IND-CPA？这解释了哪四个设计规则？
5. 为什么 IND-CPA 的定义要求 m₀ 和 m₁ 等长？有什么真实后果？
6. IND-CCA 比 IND-CPA 强在哪？为什么现实中需要它？
7. AEAD 是怎么达到 IND-CCA 的？
8. 为什么 1/n¹⁰⁰⁰ 不算"可忽略"？
9. "可证明安全"到底证明了什么？

🛑 可以停在这里

⚡ 走神救援

⭐⭐全教程的思维转折点。直觉的"安全"定义全错：①"不能恢复明文"→反例是泄露前一半 ②"不能恢复任何一bit"→反例是泄露奇偶性 ③"不能恢复密钥"→反例是根本不加密。根本问题：攻击者想要的可能是任何信息，没法穷举。⭐思路翻转：不问"他学到什么"，问"他能不能分辨密文对应 m₀ 还是 m₁"（他自己挑的两条）——能覆盖"任何信息"是因为：若他能算出任何性质 P，就挑一个满足P、一个不满足P 的消息立刻分辨。IND-CPA 游戏：随意查加密预言机 → 提交等长 m₀,m₁ → 挑战者抛硬币返回 Enc(m_b) → 继续查 → 猜 b'，要求优势 ≤ negl。⭐三个推论：①确定性加密永远不安全（先问 m₀ 拿 c₀，再比较 c）——这一条串起了 ECB不安全/CBC要IV/CTR要nonce/教科书RSA不安全四个规则 ②密文必然更长 ③明文长度无法隐藏（定义要求等长是承认而非疏忽；💥 HTTPS 下页面大小暴露你访问了哪页）。IND-CCA 多了解密预言机——现实形态是 padding oracle、响应时间、日志；⭐AEAD 达到 CCA 的办法：验证不通过就根本不解密，把解密预言机变成只会说"无效"的东西。negl 要比任何多项式倒数都小（1/n¹⁰⁰⁰ 不算，因为重复 n¹⁰⁰⁰ 次是可行的）；128-bit 安全 = 2¹²⁸ 次操作，对照宇宙年龄约 2⁵⁹ 秒、全球算力一年约 2⁹⁰ 次。⭐方法论：问它①声称什么目标②什么攻击模型③归约到什么假设④假设可信吗——"我想不出怎么破"什么都不算。⭐"可证明安全"不证明方案安全，只证明它归约到某个数学难题*——是把信任从方案转移到被研究几十年的数学问题上。

下一节 👉 09-哈希函数.md