计算安全性 (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>