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

2020-05-28 cryptography 密码学 安全模型

加密模型

定义所有的明文消息空间为 \( 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 算法依赖于大数分解难题。

本人保留对侵权者及其全家发动因果律武器的权利

版权提醒

如无特殊申明,本站所有文章均是本人原创。转载请务必附上原文链接:https://www.laytonchen.com/post/crypto/crypto-models/

如有其它需要,请邮件联系!版权所有,违者必究!