【密码学复习】【Chapter 2】【完美保密】

第二章 完美保密

Part 0 任务

  • 证明一比特完美保密
  • 证明完美保密的等价公式
  • 证明完美保密等价不可区分性
  • 证明一次一密是完美保密
  • 证明完美保密的局限性

Part 1 定义和基本属性

  • 随机变量: K , M , C K, M, C K,M,C
  • 概率: Pr ⁡ [ K = k ] , Pr ⁡ [ M = m ] , Pr ⁡ [ C = c ] \Pr[K = k], \Pr[M = m], \Pr[C = c] Pr[K=k],Pr[M=m],Pr[C=c]

1.1 定义完美保密

  • 在 M \mathcal{M} M上 Π \Pi Π是完美保密的,若对于 M \mathcal{M} M上的任意概率分布, ∀ m ∈ M \forall m \in \mathcal{M} ∀m∈M 与 ∀ c ∈ C \forall c \in \mathcal{C} ∀c∈C , 且 Pr ⁡ [ C = c ] > 0 \Pr[C = c] > 0 Pr[C=c]>0:

    Pr ⁡ [ M = m ∣ C = c ] = Pr ⁡ [ M = m ] . \Pr[M=m | C=c] = \Pr[M=m]. Pr[M=m∣C=c]=Pr[M=m].

  • 某个明文被发送的后验似然与该明文被发送的先验概率没有差别

1.2 一比特上的完美保密

  • M = K = { 0 , 1 } , E n c k ( m ) = m ⊕ k \mathcal{M}=\mathcal{K} = \{ 0,1 \} , \mathsf{Enc}_k(m)= m \oplus k M=K={0,1},Enck​(m)=m⊕k
  • 证明
  • 只要密钥是均匀随机的,那么密文的概率分布就不收明文概率分布的影响;
  • 虽然密文不独立与明文,但是密文是由明文和密钥共同决定的

1.3 完美保密的等价形式

  • Pr ⁡ [ C = c ∣ M = m ] = Pr ⁡ [ C = c ] \Pr[C=c | M=m] = \Pr[C=c] Pr[C=c∣M=m]=Pr[C=c]
  • 密文的先验概率等于其后验概率

1.4 完美不可区分性

  • Pr ⁡ [ C = c ∣ M = m 0 ] = Pr ⁡ [ C = c ∣ M = m 1 ] \Pr[C = c | M = m_0] = \Pr[C = c | M = m_1] Pr[C=c∣M=m0​]=Pr[C=c∣M=m1​]
  • 攻击者无法区分出密文是由哪个明文加密得到的

Part 2 一次一密 Vernam’s Cipher

  • 定义
    • M = K = C = { 0 , 1 } l \mathcal{M} = \mathcal{K} = \mathcal{C} = \{0, 1\}^l M=K=C={0,1}l
    • k ← G e n k \leftarrow Gen k←Gen,以 2 − l 2^{-l} 2−l的概率随机选择 k k k
    • c : = E n c k ( m ) = k ⊕ m c := Enc_k(m) = k \oplus m c:=Enck​(m)=k⊕m
    • m : = D e c k ( c ) = k ⊕ c m := Dec_k(c) = k \oplus c m:=Deck​(c)=k⊕c
  • 证明其完美保密性

Part 3 完美保密的局限性

  • 密钥空间必须大于等于明文空间

  • 证明

  • 二次加密是错误的

  • c ⊕ c ′ = ( m ⊕ k ) ⊕ ( m ′ ⊕ k ) = m ⊕ m ′ c\oplus c'=(m\oplus k)\oplus (m'\oplus k)=m\oplus m' c⊕c′=(m⊕k)⊕(m′⊕k)=m⊕m′

Part 4 香农定理

  • 当明文空间、密钥空间和密文空间规模相同时,加密方案是完美保密的,当且仅当满足两个条件:
    • (1)每个密钥是从密钥空间中均匀随机生成的;
    • (2)对于任意明文和密文对,存在唯一的密钥使得该明文加密成该密文。

Part 5 窃听不可区分性

5.1 窃听不可区分实验 P r i v K A , Π e a v ( n ) PrivK_{\Alpha, \Pi}^{eav}(n) PrivKA,Πeav​(n)

  • 定义

    1. 给敌手 A \Alpha A指定 1 n 1^n 1n作为输入,(敌手在多项式时间内)输出一对等长的消息 m 0 , m 1 m_0, m_1 m0​,m1​
    2. 产生随机密钥 k ← G e n ( 1 n ) k \leftarrow Gen(1^n) k←Gen(1n),随机选择一个比特 b ← { 0 , 1 } b \leftarrow \{0, 1\} b←{0,1},计算密文 c ← E n c k ( m b ) c \leftarrow Enc_k(m_b) c←Enck​(mb​)并交给 A \Alpha A
    3. A \Alpha A输出一个比特 b ′ b^{\\'} b′
    4. 如果 b ′ = b b^{\\'} = b b′=b,则实验输出为 1 1 1,否则为 0 0 0。如果 P r i v K A , Π e a v ( n ) = 1 PrivK_{\Alpha, \Pi}^{eav}(n) = 1 PrivKA,Πeav​(n)=1,则称敌手成功。
  • 注意:每次实验使用生成的密钥
    【密码学复习】【Chapter 2】【完美保密】

5.2 完美保密下的窃听不可区分性

  • Pr ⁡ [ P r i v k A , Π e a v = 1 ] = 1 2 \Pr[Privk_{\mathcal{A}, \Pi}^{eav} = 1] = \frac{1}{2} Pr[PrivkA,Πeav​=1]=21​
上一篇:Chapter 11使用类


下一篇:chapter 4:添加一个球体