目录

2.4 Shannon’s Theorem

THEOREM 2.12 (Shannon’s theorem) 香农原理

THEOREM 2.12 香农原理的证明

香农原理的作用和局限性

使用香农原理证明一次性密码本具有完善保密性

2.4 Shannon’s Theorem

THEOREM 2.12 (Shannon’s theorem) 香农原理

假设对明文空间M上的加密方案Π(Gen, Enc, Dec)有|M| = |K| = |C|，则这种加密方案具有完善保密性当且仅当：

• 条件一：对任意密钥k ∈ K，k 被选中的概率都相等，都等于 1/|K|
• 条件二：对于任意的明文m ∈ M，以及任意的密文c ∈ C，则存在一个唯一的密钥 k ∈ K使得Enck(m) = c

THEOREM 2.12 香农原理的证明

我们假设Enc是确定性的。

• 我们先来证明，符合香农原理两个条件的加密方案具有完善保密性

对于任意的c ∈ C 和 m ∈ M，根据香农原理的条件二

存在唯一确定的密钥k，使得 Enck(m) = c

Pr[Enck(m) = c] = Pr[K = k] = 1/|K|

注意，上式的第二个等号是根据香农原理的条件一得来的

由于m和c是任意选取的，因此我们可以得到

Pr[Enck(m) = c]=Pr[Enck(m’) = c]= 1/|K|

这样我们就证明了该方案是具有完善保密性的。为何？

补充（三）完善保密性三种定义的通俗表述及等价性的证明_南鸢北折的博客-CSDN博客

上面文章中我们给出来完善保密性的三种等价表述

我们刚刚得到的式子恰好符合LEMMA 2.5 的表述

• 我们再来证明，具有完善保密性的方案符合香农原理的两个条件

我们先证明具有完善保密性的方案符合香农原理的条件二

LEMMA 2.5的表述是对于任意m∈M，有Pr[EncK(m) = c]=Pr[EncK(m’) = c]

这说明对于任意m∈M，有Pr[EncK(m) = c]≠0

通俗来讲就是，对于任何一个密文空间C中的密文c，所有的m∈M都能够通过某个密钥加密为c，即任意m都存在加密为任意c的可能性

我们更严谨的描述是，假设M = {m1, m2, . . .}，

那么对于每一个mi ∈ M都有一个非空的集合Ki ⊂ K

使得 Enck(mi) = c 当且仅当k ∈ Ki

同时，如果i≠j，则Ki与Kj不能有交集，否则正确性就不能成立

（想想为什么？正确性是指Decᴋ(Encᴋ(m)) = m。如果Ki和Kj相交，那就意味着两个不同的明文，比如是m和m’，可以被某个相同的密钥加密为相同的c。那么我们在对c利用密钥k进行解密时，到底是解密为m还是解密为m’呢？这显然就不符合正确性要求了）

因此，我们既要保证对于每一个mi ∈ M都有一个非空的集合Ki ⊂ K，还得保证i≠j时Ki与Kj不能有交集，

由于|K| = |M|，显然只有每Ki只包含唯一的 ki时才能满足条件

这也就意味着对于任意的明文m∈M，以及任意的密文c∈C，存在一个唯一的密钥 k∈K使得Enck(m) = c

因此我们证明了具有完善保密性的方案符合香农原理的条件二

我们再证明具有完善保密性的方案符合香农原理的条件一

根据LEMMA 2.5，对于任意的 1 ≤ i, j ≤ |M| = |K|且i ≠j，我们得到

Pr[K = ki] = Pr[EncK(mi) = c] = Pr[EncK(mj ) = c] = Pr[K = kj ].

上式说明对任意密钥k ∈ K，k 被选中的概率都相等，都等于 1/|K|

因此我们证明了具有完善保密性的方案符合香农原理的条件一

香农原理的作用和局限性

作用：香农原理对于证明某方案是否具有完善保密性十分有用。因为条件1很容易检查，并且条件2可以被证明（或反驳），而不需要计算任何概率，如果直接使用定义2.3则需要进行概率计算。例如，一次性密码本用香农定理证明是十分简单的

局限性：香农原理只能在|M| = |K| = |C|时使用

使用香农原理证明一次性密码本具有完善保密性

现代密码学导论-5-一次性密码本_南鸢北折的博客-CSDN博客

一次性密码本的具体描述可参考上文：

确定一个整数l> 0。消息空间M、密钥空间K、密文空间C都等于{0, 1}^l (所有长度为l的二进制字符串的集合)

Gen：根据均匀分布从K中选择一个密钥（一共2^l个不同的密钥，任意一个密钥被选中的概率为2^-l）

Enc：根据明文和选定的密钥，输出密文 c = k ⊕ m

Dec：根据密文和选定的密钥，输出明文m = k ⊕ c

我们现在使用香农原理证明其具有完善保密性

首先，消息空间M、密钥空间K、密文空间C都等于{0, 1}^l ，其符合|M| = |K| = |C|

我们再来判断其是否符合香农原理的两个条件。香农原理的条件一为：

• 条件一：对任意密钥k ∈ K，k 被选中的概率都相等，都等于 1/|K|

根据一次性密码本Gen算法的描述：根据均匀分布从K中选择一个密钥（一共2^l个不同的密钥，任意一个密钥被选中的概率为2^-l），判断其显然符合条件一

香农原理的条件二为：

• 条件二：对于任意的明文m ∈ M，以及任意的密文c ∈ C，则存在一个唯一的密钥 k ∈ K使得Enck(m) = c

在一次性密码本中，对于给定的任意m ∈ M和c ∈ C，有唯一确定的k= m⊕c使得

Enck(m) =m⊕m⊕c = c

因此一次性密码本符合条件二。

综上，一次性密码本具有完善保密性

对比

现代密码学导论-5-一次性密码本_南鸢北折的博客-CSDN博客

中的证明方法，一次性密码本用香农定理证明是十分简单的