密码学专题| 一、论加密模型的完美安全、计算安全和实际安全

加密模型

定义所有的明文消息空间为 \( M \)，Alice 希望将其中一条明文 \( m \in M \) 通过密码学加密算法 \(Enc\) 变换成了密文 \(c\)，然后通过不可靠信道传输。Bob 收到 \(c\) 后则通过对应解密算法 \(Dec\) 将 \(c\) 还原成 \(m\)。此时也就是说：

\[Dec(Enc(m)) = m\]

这就是古典密码学加密模型的基本原理，是基于算法 \(\{Enc,Dec\}\)的保密性来提供安全性。但是这种保护的成本是非常大的，密码学人员流动、算法泄密都需要更换密码学算法。此外，古典密码学的安全性是无法进行量化考量的。因此，引入了秘钥 \(k\) 的概念，Kerckhoffs 原理 是说：

Kerckhoffs 原理: 一个密码学系统中，除了秘钥 \(k\) 之外的其他部分都被公开，仍然需要能够提供安全性保护。

此时引入了现代的加密模型，\( \{M, Gen, Enc, Dec\} \) 定义了一个加密方案：

• 有一个明文空间 \( M \) 和其中的待加密明文 \( m \in M \)
• 有一个密文空间 \( C \) 以及加密后得到的密文 \( c \in C \)
• 有一个秘钥生成算法 \( Gen \)，以及一个秘钥 \(k = Gen(\delta) \)，其中 \(\delta\) 是一个安全参数
• 一个加密算法 \(Enc\) 满足 \(c = Enc_k(m)\) 和一个解密算法 \(Dec\) 满足 \(m = Dec_k(c)\)

那么什么样的加密模型是安全的呢？在《Introductino of Modern Cryptography》 中给出的答案：

如果没有敌手 A 能够从密文计算出任何关于明文的函数，则认为该加密方案是安全的。

完美安全

此时引入了完美安全的概念。我们假设敌手可以知道明文空间 \( M \) 以及 \(M\) 的分布 \(Pr[M = m] \)（先验概率）。敌手观察密文并没有获得任何信息，也就是后验概率等于先验概率。从信息论的角度来看，也就是说密文和明文的互信息 \( I(C,M) = 0\) 。由此定义了完美安全或者说信息论安全：

定义：对于明文空间 \( M \) 的加密方案 {Gen, Enc, Dec}是信息论安全的，当且晋档对于 \( M \) 上的任意概率分布，\( \forall m \in M , \forall c \in C ( Pr[C=c] \ne 0) \)，有： $$ Pr[ M = m | C = c] = Pr[M = m]$$

根据贝叶斯公式，我们可以得到一个等价的公式：

$$ Pr[ C = c | M = m] = Pr[C = c] $$

由于密文概率分布和明文概率分布是独立的，因此：

对于 \( \forall m_0, m_1 \in M, \forall c \in C\) 有： \[ Pr[C = c| M = m_0] = Pr[C = c| M = m_1] \]

下面一种安全性试验经常出现在各个安全性论文中。这里将安全描述为一个假象试验。

1. 敌手 A 生成消息 \(m_0,m_1\)
2. 由一个随机秘钥 \(k = Gen(\delta) \),任选 \( b \leftarrow \{0,1\} \) \(m_b\) 进行加密得到 \(c = Enc_k(m_b) \)
3. 如果 A 通过 c 猜测猜测 \(b’\) ，定义一个示性函数 \(Adv_A^\Pi = 1\) 当且仅当 \( b = b’\)

如果系统是信息论安全的，则 \(Pr[Adv_A^\Pi = 1] = \frac{1}{2}\)

一次一密加密

有一种加密算法是满足完美安全的，也就是一次一密加密。也就是说秘钥长度和明文长度相同；秘钥的是随机生成的，且永不重复使用。假设 \(m_i\) 表示消息 m 的第 i 位。那么：

$$ Enc: c_i = m_i \bigotimes k_i $$ $$ Dec: m_i = c_i \bigotimes k_i $$

当然是存在其他完美安全的加密算法。当时如果需要实现完美安全，那么存在一个必要性条件：

如果一个加密系统是完美安全的，那么必须有 \(|K| \ge |M| \)。

那么有没有完美安全的充分毕业条件呢？是有的，也就是基于信息论的香农定理:

香农定理: 如果存在 \( |K| = |M| = |C| \)，那么当且满足如下条件，则该加密方案是完美安全的：

1. \( \forall k \in K, Pr[K = k] = \frac{1}{|K|} \)
2. 对于 \( \forall m \in M, \forall c \in C\)， 有且仅有一个 \(k \in K \) s.t. \(Enc_k(m) = c\)

必要性条件告诉我们：秘钥空间至少要和明文空间等大。不是一般性地，一次一密要求秘钥和明文等长，这导致了其在 real world 中往往是不可用的，。（有可靠信道去进行超长秘钥交换的话，那为什么不直接利用该信道传输明文呢？）

计算安全

因此完美安全就像是海市蜃楼，在现实生活中是可望不可及的。因此人们提出了计算安全的概念。

计算安全：一个加密方案是 \( (t, \epsilon) \) 安全的，那么一个运行时间最多为 t 的敌手 A 至多只有 \( \epsilon \gt 0\) 的概率成功破解方案。

和算法类似，我们可以使用渐进符号来定义了计算安全。引入一个安全参数 n （通常可能是密钥长度），那么定义渐进形式的计算安全为：

1. 敌手有任意多项式时间 \( t = an^c\) 来进行破解
2. 对于任意 c ，只有 \( Pr[Adv_A = 1] \lt n^{-c} \) 的概率破解成功

什么样的算法复杂度满足这样的特性呢？我们定义可忽略函数 negl 的概念

函数 negl 是可忽略的，当且仅当对于任意多项式 \( p() \)，\( \exists N \) 使得对于 \( \forall n \gt N \) 使得 \( negl(n) < \frac{1}{p(n)}\)。

那么上面的定义也可以说成：对于任意多项式时间的敌手，只有 negl 的概率破解成功，那么认为方案是计算安全的。n 很小的时候，方案往往是不安全的，但是当 n 很大的时候，会保证方案的计算安全。

与 N=NP 的关系: 也就是说计算安全依赖于 \(P \ne NP \) 的假设，否则一个非多项式时间的算法可以以多项式时间进行破解，此时不再保证计算安全。事实上，整个非量子密码学都是建立在 \(P \ne NP \) 假设之上的。

此时我们可以重新定义计算安全假设下的加密算法：

1. Gen 是一个随机算法，它的输入参数是 \(1^n\) 的安全参数。\(k \leftarrow Gen(1^n) \)。不失一般性地，\( |k| \ge n \)
2. 对于加密算法有： \(m \leftarrow \{0,1\}^*\) 和 k，有 \(c \leftarrow Enc_k(m)\)
3. 以及解密算法有： \( m = Dec_k(c)\)

也就是说，此时在秘钥空间 |K| 的增长是非多项式的，导致了 n 很大的时候，攻击的难度快速上升。一个直观的例子就是当秘钥长度从 n=128 增长到 n=256 的时候，秘钥空间的增长是非常剧烈的（ \( 2^256 - 2^128 \)，这也导致了在多项式时间内，破解的难度也大幅度增加。也就是说， 即使敌手 A 有限的计算能力即便再强，也可以简单地通过增长 n 来获取一个充分的安全保障。

此时定义的安全模型为：

1. 敌手 A 生成两个相同长度的消息 \(m_0,m_1\)
2. 由一个随机秘钥 \(k = Gen(1^n) \),任选 \( b \leftarrow \{0,1\} \) \(m_b\) 进行加密得到 \(c = Enc_k(m_b) \)
3. 如果 A 通过 c 猜测猜测 \(b’\) ，定义一个示性函数 \(Adv_A^\Pi = 1\) 当且仅当 \( b = b’\)

如果系统是计算安全的，则：

\[Pr[Adv_A^\Pi = 1] \le \frac{1}{2} + negl(n) \]

这个不等式说明了攻击者任选两个消息，猜测出 c 来自哪一个消息的可能性都不显著大于 1/2 。对于消息中的每一个比特，也有类似的结论，消息中的每一个 bit ，攻击者都无法知道是来自那一个明文：

\[Pr[ A(1^n, Enc_k(m)) = m^i ] \le \frac{1}{2} + negl(n) \]

实际安全

通过我们还会引入理论安全的概念，将一个密码学安全依赖于一个数学难解问题之上，此时密码学算法的安全性等于该数学问题的困难程度。这时候，只要证明了该问题困难程度符合安全需求，那么可以认为算法是实际安全的。一个例子是 RSA 算法依赖于大数分解难题。