第 6 章：现代加密技术¶

柯克霍夫原则¶

现代加密技术和古典加密技术的一个显著区别是，现代加密技术即使把加密算法公开，攻击者也无从下手。

三个原则¶

相比以前的加密方法，现代加密技术讲究三个原则：

有形式的定义。
有精确的假设。
安全性可以证明。

形式的精确定义¶

设计
用途
保护效果

安全的定义是什么¶

首先定义什么是“不安全”（即什么时候认为是被破解了）；然后定义对这个算法进行打击的对手的能力。

如果这个能力的对手无法让这个系统变得不安全，那这个系统就是安全的。

加密¶

无论攻击者有什么信息，密文都不应泄露有关底层明文的额外信息。攻击者不能从密文中恢复出整个明文。

密码的对抗模型¶

假设对手（攻击者）知道明文应该长什么样子，以及密码的性质。

仅密文攻击：对手只知道一些密文。
已知明文攻击：对手知道一些密文和相应的明文对。
选择明文攻击 CPA：对手可以自定义一些明文，并获得它们的密文。
选择密文攻击：对手可以自定义一些密文，并获得它们的明文。

精确的假设¶

验证假设
比较不同的场合
促进正式的安全证明

证明¶

密码学上面的证明都是证明“某个层面的攻击者可以攻破这个加密”。

信息论意义上的安全¶

密文 C 应该不提供任何明文 M 的“信息”。或者说：

随机变量 C 和随机变量 M 是独立的。
观察 C 的值对求 M 的分布没有意义，反过来也一样。
加密不同的 M 的密文分布完全相同。

完美安全¶

对信息空间 M 上面的生成、加密、解密操作，如果满足：

概率分布完全覆盖了 M；
并且任何明文 message \(m \in M\)；
并且相对应的密文 \(c \in C\)，并且 \(\Pr[C = c] > 0\)，

那么就可以得到

\(\Pr[M = m | C = c] = \Pr[M = m]\)，

也就是说对手相信明文 M 等于 m 的概率，不会随其看过对应密文 c 所改变。这个叫做完美安全。

相应的，\(\Pr[C = c | M = m_0] = \Pr[C = c | M = m_1]\)。

不可区分性+¶

引入一个叫 \(PrivK^{eav}\) 的实验。

攻击方：选择明文 \(m_0\)、\(m_1\)，发送给挑战者。
挑战者：随机选择两个明文中的一个 \(b\)，加密它，发送 \(C = E_k[m_b]\) 给攻击者。
攻击方：猜测挑战者选择的那个 \(b\) 等于 \(b'\)。

\(PrivK^{eav} = 1\) 如果 \(b = b'\)（猜对），否则 \(PrivK^{eav} = 0\)。

如果生成、加密、解密操作满足对于所有的对手 A 有 \(\Pr[PrivK^{eav}(A, \Pi) = 1] = 1 / 2\)，那么这些操作就是完美安全的。这意味着攻击者真的没法从密文拿到任何信息，只能乱猜。

完美安全的困难¶

假设现在在进行向量异或（One-Time Pad）实现的加密。为了实现完美安全，密钥的长度得大于等于信息的长度，但是实际上这很难实现。

所以我们只能退而求其次，进行下列削弱：

仅针对高效（计算有限）的对手保留安全性。
对手只能在可行的时间内运行。
对手有可能蒙中答案，但也仅仅能蒙。

\((t, \epsilon)\) 安全¶

如果有个系统对于所有对手，他们在 \(t\) 时间内只有 \(\epsilon\) 概率成功破解，那么这个系统就是 \((t, \epsilon)\) 安全的。比如一个很强的 n 位加密算法是 \((t, t / 2^n)\) 安全的。

差不多安全的算法¶

对于所有的 PPT（概率多项式时间）对手，如果他们都只能以可忽略的概率攻破这个系统，那么这个系统就是安全的。

概率多项式时间¶

概率多项式时间算法在多项式时间内给出输出，并且这个输出对于同一输入可以是不同的。或者说“这个算法可以访问到一个无偏抛硬币序列”。

“可忽略的概率”¶

如果对于函数 \(f(n)\)，对于任意一个多项式 \(p(.)\) 都有一个 \(N\) 满足 \(n > N\) 时 \(f(n) < 1/p(n)\)，那么 \(f(n)\) 就是可忽略的，比如 \(f(n) = 2^{-n}\)、\(f(n) = 2^{-\sqrt{n}}\)、\(f(n) = n^{-\log n}\) 什么的。