可证明安全——对称加密

计算安全性 (computational security)

达不到完美安全(无信息泄露),安全性基于计算的复杂性。对于一个高效的敌手(计算的时间不很长),其攻击成功的概率很低。具体来说,有以下两种正式定义:

具体方法

如果一个加密方案,对任意至多计算时间为 t t t 的敌手,攻击成功概率不超过 ϵ \epsilon ϵ,则称这个方案是 ( t , ϵ ) − s e c u r e (t,\epsilon)-secure (t,ϵ)−secure。

很显然,这个定义并不是很直接,因为不好描述“任意敌手”。

渐进方法

首先,渐进方法定义了一个安全参数 n n n。通常来说,这个参数可以简单地理解为秘钥的长度。

如果一个方案,对于任意多项式时间的敌手,攻破成功的概率为可忽略量,则称该方案是安全的。

敌手本质是一个算法,多项式时间是指 ∃ k ∈ N \exist k \in N ∃k∈N, 这个算法的复杂度是 O ( n k ) O(n^k) O(nk)。可忽略量是小于任何多项式的倒数,也就是说,对 ∀ k ∈ N \forall k \in N ∀k∈N,攻破成功的概率为 O ( n − k ) O(n^{-k}) O(n−k)。

安全等级

单次加密 EAV-secure

EAV-secure,是指在窃听攻击的情况下安全。

针对加密方案 Π = ( Gen, Enc, Dec ) \Pi = (\text{Gen, Enc, Dec}) Π=(Gen, Enc, Dec) 和敌手 A \mathcal{A} A, 首先定义实验 PrivK A , Π eav ( n ) \text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}(n) PrivKA,Πeav​(n)

  • 给敌手 A \mathcal{A} A 安全参数 n n n,敌手输出两个等长的明文 m 0 m_0 m0​, m 1 m_1 m1​
  • 通过 Gen ( 1 n ) \text{Gen}(1^n) Gen(1n) 生成秘钥 k k k,并随机选择 b ∈ { 0 , 1 } b \in \{0, 1\} b∈{0,1},计算密文 c ← Enc ( m b ) c \leftarrow \text{Enc}(m_b) c←Enc(mb​),并将 c c c 给 A \mathcal{A} A。
  • A \mathcal{A} A 输出 b ′ b' b′。定义 out A ( PrivK A , Π eav ( n , b ) ) = b ′ \text{out}_{\mathcal{A}}(\text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}(n,b))=b' outA​(PrivKA,Πeav​(n,b))=b′。
  • 如果 b ′ = b b' = b b′=b,则 PrivK A , Π eav ( n ) = 1 \text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}(n) = 1 PrivKA,Πeav​(n)=1,否则 PrivK A , Π eav ( n ) = 0 \text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}(n) = 0 PrivKA,Πeav​(n)=0。

对任意加密方案 Π \Pi Π,EAV-secure 有如下两个定义:
对任意多项式时间敌手 A \mathcal{A} A,
Pr ⁡ [ PrivK A , Π eav ( n ) = 1 ] ≤ 1 2 + negl ( n ) \Pr[\text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}(n) = 1] \le \frac 12 + \text{negl}(n) Pr[PrivKA,Πeav​(n)=1]≤21​+negl(n)

∣ Pr ⁡ [ out A ( PrivK A , Π eav ( n , 0 ) ) = 1 ] − Pr ⁡ [ out A ( PrivK A , Π eav ( n , 1 ) ) = 1 ] ∣ ≤ negl ( n ) |\Pr[\text{out}_{\mathcal{A}}(\text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}(n,0))=1]-\Pr[\text{out}_{\mathcal{A}}(\text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi}(n,1))=1]| \le \text{negl}(n) ∣Pr[outA​(PrivKA,Πeav​(n,0))=1]−Pr[outA​(PrivKA,Πeav​(n,1))=1]∣≤negl(n)

值得一提的是,两个定义都是基于概率的。实验的随机性正来自于秘钥的生成。现实中,都是先确定秘钥后有攻击的敌手。而实验中却是先有敌手后生成秘钥。但由于成功攻破的概率是可忽略量,这样的差距是可以忽略不计的。

以上两个定义的等价性是显然的。

多次加密 EAV-secure

针对加密方案 Π = ( Gen, Enc, Dec ) \Pi = (\text{Gen, Enc, Dec}) Π=(Gen, Enc, Dec) 和敌手 A \mathcal{A} A, 定义实验 PrivK A , Π mult ( n ) \text{PrivK}^{\text{mult}}_{\mathcal{A},\Pi}(n) PrivKA,Πmult​(n)

  • 给敌手 A \mathcal{A} A 安全参数 n n n,敌手输出两列等长的明文 M 0 = { m 0 , 1 , . . . , m 0 , t } M_0 = \{m_{0,1},...,m_{0,t}\} M0​={m0,1​,...,m0,t​}, M 1 = { m 1 , 1 , . . . , m 1 , t } M_1 = \{m_{1,1}, ..., m_{1,t}\} M1​={m1,1​,...,m1,t​}。 M 1 M_1 M1​ 与 M 2 M_2 M2​ 的明文对应等长。
  • 通过 Gen ( 1 n ) \text{Gen}(1^n) Gen(1n) 生成秘钥 k k k,并随机选择 b ∈ { 0 , 1 } b \in \{0, 1\} b∈{0,1},计算密文 c i ← Enc k ( m b , i ) c_i \leftarrow \text{Enc}_k(m_{b,i}) ci​←Enck​(mb,i​),并将 C = ( c 1 , . . . , c t ) C = (c_1, ..., c_t) C=(c1​,...,ct​) 给 A \mathcal{A} A。
  • A \mathcal{A} A 输出 b ′ b' b′。
  • 如果 b ′ = b b' = b b′=b,则 PrivK A , Π mult ( n ) = 1 \text{PrivK}^{\text{mult}}_{\mathcal{A},\Pi}(n) = 1 PrivKA,Πmult​(n)=1,否则 PrivK A , Π mult ( n ) = 0 \text{PrivK}^{\text{mult}}_{\mathcal{A},\Pi}(n) = 0 PrivKA,Πmult​(n)=0。

任意加密方案 Π \Pi Π,是多次加密 EAV-secure,当且仅当
Pr ⁡ [ PrivK A , Π mult ( n ) = 1 ] ≤ 1 2 + negl ( n ) \Pr[\text{PrivK}^{\text{mult}}_{\mathcal{A},\Pi}(n) = 1] \le \frac 12 + \text{negl}(n) Pr[PrivKA,Πmult​(n)=1]≤21​+negl(n)

显然,多次加密 EAV-secure 强于单次加密 EAV-secure。一个多次加密 EAV-secure 的加密方案,必然在加密时需要引入随机性。

CPA-secure

CPA-secure 是在选择明文攻击的情况下保持安全,敌手可以无限加密任何想加密的明文。

单次加密 CPA-secure

针对加密方案 Π = ( Gen, Enc, Dec ) \Pi = (\text{Gen, Enc, Dec}) Π=(Gen, Enc, Dec) 和敌手 A \mathcal{A} A, 定义实验 PrivK A , Π cpa ( n ) \text{PrivK}^{\text{cpa}}_{\mathcal{A},\Pi}(n) PrivKA,Πcpa​(n):

  • 通过 Gen ( 1 n ) \text{Gen}(1^n) Gen(1n) 生成秘钥 k k k。
  • 给敌手 A \mathcal{A} A 安全参数 n n n 和 Enc k ( ⋅ ) \text{Enc}_k(\cdot) Enck​(⋅),敌手两个等长的明文 m 0 m_0 m0​, m 1 m_1 m1​。
  • 随机选择 b ∈ { 0 , 1 } b \in \{0, 1\} b∈{0,1},计算密文 c ← Enc k ( m b ) c \leftarrow \text{Enc}_k(m_b) c←Enck​(mb​),并将 c c c 给 A \mathcal{A} A。
  • A \mathcal{A} A 仍能继续使用 Enc k ( ⋅ ) \text{Enc}_k(\cdot) Enck​(⋅),并输出 b ′ b' b′。
  • 如果 b ′ = b b' = b b′=b,则 PrivK A , Π cpa ( n ) = 1 \text{PrivK}^{\text{cpa}}_{\mathcal{A},\Pi}(n) = 1 PrivKA,Πcpa​(n)=1,否则 PrivK A , Π cpa ( n ) = 0 \text{PrivK}^{\text{cpa}}_{\mathcal{A},\Pi}(n) = 0 PrivKA,Πcpa​(n)=0。

事实上,CPA-secure 显著强于多次加密 EAV-secure。不妨设在 PrivK A , Π eav \text{PrivK}^{\text{eav}}_{\mathcal{A},\Pi} PrivKA,Πeav​ 实验中,敌手查询前 t − 1 t-1 t−1 个时攻破的概率为可忽略量,查询第 t t t 个时攻破的概率为不可忽略量。那么对于 PrivK A , Π cpa \text{PrivK}^{\text{cpa}}_{\mathcal{A},\Pi} PrivKA,Πcpa​ 实验,可以先查 m 0 , i m_{0,i} m0,i​ 和 m 1 , i m_{1,i} m1,i​, i ≤ t − 1 i \le t - 1 i≤t−1,然后输出 m 0 , t m_{0,t} m0,t​ 和 m 1 , t m_{1, t} m1,t​ 进行最终的判断。

相比 EAV-secure,CPA-secure 的敌手不需要一次性给出所有的明文,可以一点点查询。这样的好处是后面的查询可以根据此前的查询进行调整。

多次加密 CPA-secure

简单来说,对于敌手需要猜测的 b b b,敌手可以无限构造等长的 m 0 m_0 m0​, m 1 m_1 m1​,查询 Enc k ( m b ) \text{Enc}_k(m_b) Enck​(mb​)。

一个结论是 CPA-secure 与多次加密 CPA-secure 等价。对此的直观理解是,多次加密的好处是能多次获得 b b b 的信息,而不能多获得任何关于 Π \Pi Π 的信息。破解密码的本质是通过各种手段,对明文的分布的认识发生了变化。那么多获得 b b b 的信息是无法实现的。

CCA-secure

CCA-secure 是在选择密文的情况下保证安全

针对加密方案 Π = ( Gen, Enc, Dec ) \Pi = (\text{Gen, Enc, Dec}) Π=(Gen, Enc, Dec) 和敌手 A \mathcal{A} A, 定义实验 PrivK A , Π cca ( n ) \text{PrivK}^{\text{cca}}_{\mathcal{A},\Pi}(n) PrivKA,Πcca​(n):

  • 通过 Gen ( 1 n ) \text{Gen}(1^n) Gen(1n) 生成秘钥 k k k。
  • 给敌手 A \mathcal{A} A 安全参数 n n n, Enc k ( ⋅ ) \text{Enc}_k(\cdot) Enck​(⋅) 和 Dec ( ⋅ ) \text{Dec}(\cdot) Dec(⋅),敌手两个等长的明文 m 0 m_0 m0​, m 1 m_1 m1​。
  • 随机选择 b ∈ { 0 , 1 } b \in \{0, 1\} b∈{0,1},计算密文 c ← Enc k ( m b ) c \leftarrow \text{Enc}_k(m_b) c←Enck​(mb​),并将 c c c 给 A \mathcal{A} A。
  • A \mathcal{A} A 仍能继续使用 Enc k ( ⋅ ) \text{Enc}_k(\cdot) Enck​(⋅) 和 Dec k ( ⋅ ) \text{Dec}_k(\cdot) Deck​(⋅),但不许查 Dec k ( m b ) \text{Dec}_k(m_b) Deck​(mb​),并输出 b ′ b' b′。
  • 如果 b ′ = b b' = b b′=b,则 PrivK A , Π cpa ( n ) = 1 \text{PrivK}^{\text{cpa}}_{\mathcal{A},\Pi}(n) = 1 PrivKA,Πcpa​(n)=1,否则 PrivK A , Π cpa ( n ) = 0 \text{PrivK}^{\text{cpa}}_{\mathcal{A},\Pi}(n) = 0 PrivKA,Πcpa​(n)=0。

感觉 CCA-secure 主要是有理论价值,使用价值可能不太大。

伪随机

现实中生成长度为 n n n 的随机数,复杂度远超生成长度为 1 1 1 的随机数的 n n n 倍。因为生成随机数需要足够的随机源。通常来讲,这样的随机源是有限的。这时就需要伪随机了。

伪随机生成器

G G G 是一个确定性多项式时间算法,且对于任意输入 s ∈ { 0 , 1 } n s \in \{0,1\}^n s∈{0,1}n, G ( s ) G(s) G(s) 为长度为 l ( n ) l(n) l(n) 的字符串。

G G G 是伪随机生成器当且仅当:

  • 对任意 n n n 都有 l ( n ) > n l(n) > n l(n)>n
  • 对任意多项式时间算法 D D D
    ∣ Pr ⁡ [ D ( G ( s ) ) = 1 ] − Pr ⁡ [ D ( r ) = 1 ] ∣ ≤ negl ( n ) |\Pr[D(G(s))=1]-\Pr[D(r)=1]| \le \text{negl}(n) ∣Pr[D(G(s))=1]−Pr[D(r)=1]∣≤negl(n)
    其中 s s s 是 { 0 , 1 } n \{0,1\}^n {0,1}n 的随机数, r r r 是 { 0 , 1 } n \{0,1\}^n {0,1}n 的随机数。

相比此前定义安全等级的实验,敌手可以选择明文,判断伪随机生成器的算法是不能指定 s s s 的,甚至它不能知道输入的 s s s。每次调用伪随机生成器,都只是从中获取一个结果。

伪随机函数

F : { 0 , 1 } ∗ × { 0 , 1 } ∗ → { 0 , 1 } ∗ F :\{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^* F:{0,1}∗×{0,1}∗→{0,1}∗,是一个高效算法。输入的第一个参数是秘钥,第二个参数是自变量,输出与自变量等长。

F F F 是伪随机函数当且仅当:

  • 对任意多项式时间算法 D D D
    ∣ Pr ⁡ [ D F k ( ⋅ ) ( 1 n ) = 1 ] − Pr ⁡ [ D f ( ⋅ ) ( 1 n ) = 1 ] ∣ ≤ negl ( n ) |\Pr[D^{F_k(\cdot)}(1^n)=1]-\Pr[D^{f(\cdot)}(1^n)=1] |\le \text{negl}(n) ∣Pr[DFk​(⋅)(1n)=1]−Pr[Df(⋅)(1n)=1]∣≤negl(n)

同理可定义伪随机排列

CPA-secure 构造

固定长度

F F F 是一个伪随机函数。定义加密长度为 n n n 的加密方案如下:

  • Gen \text{Gen} Gen:输入 1 n 1^n 1n,输出随机的 k ∈ { 0 , 1 } n k \in \{0,1\}^n k∈{0,1}n
  • Enc \text{Enc} Enc:输入 k ∈ { 0 , 1 } n k\in \{0,1\}^n k∈{0,1}n 和明文 m ∈ { 0 , 1 } n m \in \{0,1\}^n m∈{0,1}n,选择随机的 r ∈ { 0 , 1 } n r \in \{0,1\}^n r∈{0,1}n 并输出 c ← < r , F k ( r ) ⨁ m > c \leftarrow <r, F_k(r)\bigoplus m> c←<r,Fk​(r)⨁m>
  • Dec \text{Dec} Dec:输入 k ∈ { 0 , 1 } n k \in \{0,1\}^n k∈{0,1}n 和密文 c = < r , s > c = <r,s> c=<r,s>,输出 m ← F k ( r ) ⨁ s m \leftarrow F_k(r) \bigoplus s m←Fk​(r)⨁s

任意长度

最常用的是 CBC 模型:
可证明安全——对称加密
其中 I V IV IV 是长度为 n n n 的初始化向量。最终的密文是 < I V , c 1 , c 2 , . . . , c l > <IV, c_1, c_2, ... ,c_l> <IV,c1​,c2​,...,cl​>

上一篇:ZJNU 1365 - Window--中级


下一篇:题解 - P1204 [USACO1.2]挤牛奶Milking Cows