现代密码学2.4--香农定理/Shannon Theorem

• 香农定理/Shannon Theorem

博主正在学习INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些笔记供自己回忆，如有错误请指正。整理成一个系列现代密码学，方便检索。

《现代密码学》第一章所介绍的古典密码全都已经被破解了，而2.1节介绍了完美安全的定义，在2.2、2.3节向我们介绍了一次一密以及具有完美安全的密码方案的共同缺点，第2.4节将介绍具有完美安全的密码方案的充分必要条件，也就是香农定理/Shannon Theorem。

香农定理/Shannon Theorem

• 因为在一次一密以及具有完美安全的密码方案的共同缺点中已经证明过：满足完美安全的密码方案必有密钥空间 ∣ K ∣ ≥ ∣ M ∣ |\mathcal{K}|\ge|\mathcal{M}| ∣K∣≥∣M∣；
• 因为从明文空间 M \mathcal{M} M映射到密文空间 C \mathcal{C} C的加密算法一定是一种单射函数，也就是不能有两个明文 m , m ′ m,m' m,m′映射到同一个密文 c c c的情况出现（如果出现这种情况，那密文 c c c可能会解密得到明文 m m m或 m ′ m' m′，不满足解密的确定性），那么密文空间 ∣ C ∣ ≥ |\mathcal{C}|\ge ∣C∣≥明文空间 ∣ M ∣ |\mathcal{M}| ∣M∣；

综合以上，我们认为满足完美安全的密码方案总是有 ∣ K ∣ ≥ ∣ M ∣ |\mathcal{K}|\ge|\mathcal{M}| ∣K∣≥∣M∣， ∣ C ∣ ≤ ∣ M ∣ |\mathcal{C}|\le|\mathcal{M}| ∣C∣≤∣M∣。现在假设 ∣ K ∣ = ∣ M ∣ = ∣ C ∣ |\mathcal{K}|=|\mathcal{M}|=|\mathcal{C}| ∣K∣=∣M∣=∣C∣，某种意义上这是一种最优解的情况，在这种情况下满足完美安全的密码方案的充分必要条件。

有两个条件：

• (1) 密钥空间 K \mathcal{K} K中的每个密钥 k k k是靠生成密钥算法 G e n Gen Gen等概率选择的，每一个密钥 k k k被选择的概率都是 1 / ∣ K ∣ 1/|\mathcal{K}| 1/∣K∣；
• (2) 对于每个 m ∈ M m\in \mathcal{M} m∈M， c ∈ C c\in \mathcal{C} c∈C，存在唯一的密钥 k ∈ K k\in \mathcal{K} k∈K使得 E n c k ( m ) = c Enc_k(m)=c Enck​(m)=c。

证明：

• 充分性：即证以上两个条件可推出完美安全 P r [ M = m ∣ C = c ] = P r [ M = m ] Pr[M=m|C=c]=Pr[M=m] Pr[M=m∣C=c]=Pr[M=m]。
  • 由条件(2)得 P r [ C = c ∣ M = m ] = P r [ K = k ] Pr[C=c|M=m]=Pr[K=k] Pr[C=c∣M=m]=Pr[K=k]，由条件(1)得 P r [ K = k ] = 1 / ∣ K ∣ Pr[K=k]=1/|\mathcal{K}| Pr[K=k]=1/∣K∣，故 P r [ C = c ∣ M = m ] = P r [ K = k ] = 1 / ∣ K ∣ Pr[C=c|M=m]=Pr[K=k]=1/|\mathcal{K}| Pr[C=c∣M=m]=Pr[K=k]=1/∣K∣
  • → P r [ C = c ] = ∑ m ∈ M P r [ E n c K ( m ) = c ] ⋅ P r [ M = m ] = 1 / ∣ K ⋅ ∑ m ∈ M P r [ M = m ] = 1 / ∣ K ∣ \rightarrow Pr[C=c]=\sum_{m\in \mathcal{M}}Pr[Enc_K(m)=c]\cdot Pr[M=m]=1/|\mathcal{K}\cdot \sum_{m\in \mathcal{M}}Pr[M=m]=1/|\mathcal{K}| →Pr[C=c]=∑m∈M​Pr[EncK​(m)=c]⋅Pr[M=m]=1/∣K⋅∑m∈M​Pr[M=m]=1/∣K∣
  • → P r [ M = m ∣ C = c ] = P r [ C = c ∣ M = m ] ⋅ P r [ M = m ] P r [ C = c ] = P r [ E n c K ( m ) = c ] ⋅ P r [ M = m ] P r [ C = c ] = 1 / ∣ K ∣ ⋅ P r [ M = m ] 1 / ∣ K ∣ = P r [ M = m ] \rightarrow Pr[M=m|C=c]=\frac{Pr[C=c|M=m]\cdot Pr[M=m]}{Pr[C=c]}=\frac{Pr[Enc_K(m)=c]\cdot Pr[M=m]}{Pr[C=c]}=\frac{1/|\mathcal{K}|\cdot Pr[M=m]}{1/|\mathcal{K}|}=Pr[M=m] →Pr[M=m∣C=c]=Pr[C=c]Pr[C=c∣M=m]⋅Pr[M=m]​=Pr[C=c]Pr[EncK​(m)=c]⋅Pr[M=m]​=1/∣K∣1/∣K∣⋅Pr[M=m]​=Pr[M=m]
• 必要性：即证完美安全可推出两个条件。
  • 首先证明条件(2)一定满足：根据 P r [ E n c K ( m ) = c ] > 0 Pr[Enc_K(m)=c]>0 Pr[EncK​(m)=c]>0