Chapter 2 完美保密加密

​ 在前一章中，我们介绍了一些历史加密方案，并说明它们很容易被破解。在本章中，我们将看看另一个极端，并研究加密方案，即使其面对具有无限计算能力的对手，也可证明是安全的。这样的计划被称为完美保密。我们严格地定义了这个概念，并探索了实现完全保密的条件。

​ 在某种意义上，本章的材料更多地属于“古典”密码学的世界，而不是“现代”密码学的世界。除了这里介绍的所有材料都是在20世纪70年代中期和80年代密码学革命之前开发的之外，我们在本章中研究的结构仅依赖于第1.4节中概述的第一和第三原理。也就是说，使用精确的数学定义并给出严格的证明，但不需要依赖任何未经证明的计算假设。显然，避免这种假设是有利的;然而，我们将看到，这样做有固有的局限性。因此，本章的结果除了为理解现代密码学的基本原理提供了良好的基础之外，还为我们后来采用上述三个原理提供了依据。

​ 从本章开始，我们将定义安全性并使用涉及随机算法的概率实验分析方案。通过“实验”给出了一个简单的例子，在“实验”中，希望使用私钥加密方案进行通信的双方生成一个随机密钥。由于随机性是如此重要，在回到密码学本身的讨论之前，我们简要讨论生成适合于密码学应用程序的随机性的问题。

生成随机数

​ 在本书中，为了简单起见，我们将假设各方可以获得无限的、独立的、无偏的(即统一的)比特。这些随机比特从何而来?由于经典计算是确定性的，所以根本不清楚如何使用计算机来生成随机比特。原则上，人们可以手工生成少量均匀的比特，例如，通过抛一枚均匀的硬币。但这种方法不太方便，也不具有可扩展性。

​ 现代随机数生成分为两个步骤。首先，收集高熵数据的“池”。(就我们的目的而言，不需要熵的正式定义，只要把熵看作是一种不可预测性的度量就足够了。)接下来，对这些高熵数据进行处理，生成一个几乎独立且无偏置的比特序列。第二步是必要的，因为高熵数据不一定是均匀的。

​ 对于第一步，需要一些不可预测的数据来源。这可能来自外部输入，例如，网络事件之间的延迟、硬盘访问时间、用户的击键或鼠标移动，等等。也可以使用更复杂的方法——通过设计，将随机数生成更紧密地结合到硬件级的系统中。这些依赖于物理现象，如热/射噪声或放射性衰变;例如，某些英特尔处理器利用热噪声在芯片上生成高熵数据。这类硬件随机数生成器通常比依赖外部源的技术更快地产生高熵数据。

​ “平滑”高熵数据以获得(几乎)独立和均匀的位所需要的处理是不平凡的。这里，我们考虑一个简单的例子来说明可以做些什么。假设我们的高熵池包含一个有偏差的比特序列，其中1出现的概率为p, 0出现的概率为1−p。（然而，我们确实假设所有的比特都是独立的。在实践中，这种假设通常是无效的，因此必须进行更复杂的处理。）数千个这样的比特有很大的熵，但不接近均匀。我们可以通过将原始的位成对计算得到一个统一的位序列:如果我们看到一个1后面跟着一个0，那么我们输出0，如果我们看到一个0后面跟着一个1，那么我们输出1。(如果我们在一行中看到两个0或两个1，我们就什么也不输出，只是继续进行下一对。)任意一对得到0的概率是p·(1−p)，这正好等于任意一对得到1的概率。(注意，我们甚至不需要知道p的值!)因此，我们从初始的高熵池中得到了一个均匀分布的输出。

​ 必须注意随机比特是如何产生的，使用糟糕的随机数生成器通常会使一个良好的密码系统容易受到攻击。应该使用为加密用途而设计的随机数生成器，而不是通常不适合加密应用的“通用”随机数生成器。特别是，C 语言stdlib.h库中的rand()函数在密码学上是不安全的，在密码学设置中使用它可能会产生灾难性的后果。

2.1 定义

​ 我们首先回顾和扩展前一章中介绍的加密语法。加密方案由Gen、Enc和Dec三种算法定义，并指定消息空间M为|M| > 1（如果|M| = 1，则只有一条消息，通信没有意义，更不用说加密了）。密钥生成算法Gen是一种根据某种分布选择的密钥k输出的概率算法。我们用K表示(有限)密钥空间，即，所有可能的密钥的集合，可以由Gen输出。加密算法Enc取密钥k∈K，消息m∈M作为输入，输出密文c。我们现在显式地允许加密算法是概率的(因此Enck(m)在运行多次时可能会输出不同的密文)，我们写c←Enck(m)来表示消息m使用密钥k加密得到密文c的可能的概率过程。(展望未来，我们有时也使用符号x←S来表示从集合S中均匀选择x。如果Enc是确定的，我们可以写c:= Enck(m)来强调这一点。)我们让C表示Enck(m)能输出的所有可能的密文集合，对于k∈K和m∈M的所有可能的选择(对于随机情况下的Enc的所有随机选择)。解密算法Dec以密钥k∈K和密文c∈C作为输入，输出消息m∈M。我们假设完全正确，这意味着对于所有k∈K, m∈M，以及Enck(m)输出的任何密文c，它满足Deck© = m，概率为1。完全正确意味着我们可以假设Dec是确定的而不丧失一般性，因为Deck©每次运行时必须给出相同的输出。因此我们用m:= Deck©来表示使用密钥k解密密文c产生消息m的(确定性)过程。

​ 在下面的定义和定理中，我们指的是K、M和C上的概率分布。K的分布是通过运行Gen并获取输出定义的。(Gen几乎总是从K中一致地选择一个密钥，事实上，我们可以假设这一点而不丧失一般性;见练习2.1。)设K为随机变量，表示Gen输出的密钥值;因此，对于任意k∈K, Pr[K = k]表示Gen输出的密钥等于k的概率。同样，我们设M为表示被加密消息的随机变量，因此Pr[M = m]表示消息取m∈M值的概率。消息的概率分布不是由加密方案本身决定的，而是反映了使用该方案的各方发送不同消息的可能性，以及敌手对将发送什么内容的不确定性。例如，敌手可能知道该消息今天将被攻击或不攻击。对手甚至可能(通过其他方式)知道，该消息的概率为0.7，是攻击的命令，而该消息的概率为0.3，是不攻击的命令。在这种情况下，Pr[M = attack today] = 0.7, Pr[M = don’t attack] = 0.3。

​ K和M被要求是独立的，也就是说，双方所通信的内容必须独立于他们共享的密钥。在其他原因中，这是有意义的，因为在K上的分布是由加密方案本身决定的(因为它是由Gen定义的)，而在M上的分布取决于使用加密方案的上下文。

​ 固定一个加密方案和M上的分布，确定密文C在空间上的分布，选择一个密钥k∈K(根据Gen)和一个消息m∈M(根据给定的分布)，然后计算密文C←Enck(M)。设C为随机变量，表示生成的密文，对于c∈C，取Pr[C = c]表示密文等于固定值c的概率。

Example 2.1

这里，根据定义，我们有K ={0，…， 25}，对于每个k∈K, Pr[K = k] = 1/26。假设我们给定M的以下分布:Pr[M = a] = 0.7, Pr[M = z] = 0.3。密文是B的概率是多少?只有两种情况:M = a和K = 1，或者M = z和K = 2。根据M和K的独立性，我们得到[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BiGNzk6p-1669001343748)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114142627355.png)]

同理，[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pAVVPEEf-1669001343749)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114142643699.png)]

因此，[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6CFkCBfO-1669001343750)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114142657783.png)]

我们也可以计算条件概率。例如，假设我们观察的是密文B，那么消息a被加密的概率是多少?利用贝叶斯定理，我们有

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TcCIjtU8-1669001343750)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114142828464.png)]

注意Pr[C = B | M = a] = 1/26，因为如果M = a，那么C = B发生的唯一可能是K = 1(发生的概率为1/26)。我们得出结论Pr[M = a | C = B] = 0.7。

Example 2

再次考虑移位密码，但在M上有如下分布:Pr[M = kim] = 0.5, Pr[M = ann] = 0.2, Pr[M = boo] = 0.3。C = DQQ的概率是多少?这个密文出现的唯一可能是M = ann和K = 3，或者M = boo和K = 2，这种情况发生的概率是0.2·1/26 + 0.3·1/26 = 1/52。

​ 我们还可以计算ann被加密的概率，条件是观察密文DQQ?以上利用贝叶斯定理计算得到Pr[M = ann | C = DQQ] = 0.4。

完美保密

我们现在准备给完全保密的概念下个定义。我们想象一个敌手，他知道M的概率分布;也就是说，敌手知道发送不同消息的可能性。敌手也知道正在使用的加密方案。敌手唯一不知道的是双方共享的密钥。由诚实的一方选择消息并加密，生成的密文传输给另一方。攻击者可以窃听双方的通信，从而观察到该密文。(也就是说，这是一种唯密文攻击，攻击者只看到单个密文。)对于一个完全保密的方案来说，观察这个密文应该不会影响对手对所发送的实际消息的了解;换句话说，某个消息m∈M被发送的后验概率，以被观察到的密文为条件，应该与m被发送的先验概率没有区别。这意味着密文没有透露任何关于底层明文的信息，而敌手完全不了解被加密的明文。正式地：

**定义2.3：**一个消息空间M的加密方案(Gen, Enc, Dec)是完全机密的，如果对于M的每个概率分布，每个消息m∈M，每个密文c∈C，其中Pr[C = c] > 0:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5mbVHHEj-1669001343750)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114144206701.png)]

(Pr[C = c] > 0的要求是为了防止对零概率事件产生条件作用而需要的技术要求。)

Example 2.4:

​ 我们证明，当使用移位密码与所有两个字符明文组成的消息空间M时，它不是完全保密的。为此，我们利用定义2.3，给出了一个在M上的概率分布，其中对于某些消息M和密文c,Pr[M=m|C=c]≠Pr[M=m]。

​ 许多这样的分布是可能的，但我们选择一个简单的:假设消息是aa或ab，每个都有一半的概率。设m = ab, c = XX。那么显然Pr[M = ab | C = XX] = 0，因为XX不可能是ab加密的结果。但是Pr[M = ab] = 1/2。

​ 我们现在给出一个完全保密的等价表述。这个公式通过要求密文的分布不依赖于明文来定义完全保密，即对于任意两条消息m, m‘∈m，当m被加密时密文的分布应该与m’被加密时密文的分布相同。也就是说，对于每一个m、m’∈M，和每一个c∈C，我们有Pr[Enck(m)=c]=Pr[Enck(m’)=c]—（式2.1）(其中概率大于K和随机的Enc。)请注意，上述概率仅依赖于加密方案，而不涉及M上的任何底层分布。上述条件意味着密文不包含明文的信息，不可能区分m的加密和m‘的加密，因为密文在每种情况下的分布是相同的。

引理2.5：

消息空间为M的加密方案(Gen, Enc, Dec)是完全机密的，当且仅当(2.1)式对每m, m’∈M和每c∈C都成立。

证明：

证明是很简单的，但是我们要详细地进行。关键的观察结果是，对于任何方案，任何M上的分布，任何m∈M，其中Pr[M = m] > 0，以及任何c∈C，我们有:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O9pA2oRu-1669001343751)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114145704407.png)]

第一个等式是根据随机变量C的定义定义的，第二个等式是因为我们对M = m的事件进行了条件反射，第三个等式是因为K与M无关。我们还利用了这样一个事实:对于任意c∈C, Pr[C = c] > 0，我们有[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NRb4iJQX-1669001343752)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114150018079.png)]

​ 取M的均匀分布。如果方案完全机密，则Pr[M=m | C=c] = Pr[M = m]，因此(2.3)式表明Pr[C=c | M=m] = Pr[C = c]。由于m和c是任意的，这表明对于每个m, m’∈M和每个c∈C，[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3HvMohPb-1669001343753)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114150343553.png)]

(利用式(2.2))，证明引理的一个方向。

​ 反过来，对于每个m, m’∈M，每个c∈C，式(2.1)成立。固定某个分布在M上，一个消息m∈M，一个密文c∈C, Pr[C=c] > 0。如果Pr[M=m] = 0，那么我们有Pr[M=m|C=c]=Pr[M=m]=0。

​ 假设Pr[M = m] > 0，对于c∈C，定义:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N8iKVJnc-1669001343753)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114150829075.png)]

式(2.1)和(2.2)表明对于每一个m’∈M, Pr[C=c| M=m’] = p_c

因此，[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6aXyDey9-1669001343754)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114151329702.png)]

其中求和基于m‘, Pr[M = m’] >0。式(2.3)表明Pr[M=m|C = c] = Pr[M = m]，因此该方案是完全机密的。

完全(对抗性)不可区分

​ 在本节结束时，我们提出了另一个等价的完全保密的定义。这个定义是基于一个实验:一个敌手被动地观察一个密文，然后试图猜测两个可能的消息中哪一个被加密了。我们引入这个概念，因为它将作为下一章定义计算安全的起点;在本书的其余部分中，我们将经常使用这样的实验来定义安全性。

​ 在目前的背景下，我们考虑以下实验:敌手A首先指定两个任意消息m₀, m₁∈M。接下来，使用Gen生成一个密钥k。然后，选择由A指定的两个消息中的一个(每个都有1/2的概率)，并使用k进行加密;生成的密文给A。最后，A输出两个消息中哪一个被加密了的“猜测”;如果A猜对了，则成功。如果没有对手A能以大于1/2的概率成功，则加密方案是完全不可区分的。(注意，对于任何加密方案，A通过输出一个统一的猜测，可以以1/2的概率成功;要求很简单，没有攻击者能做得比这更好。)我们强调对A的计算能力没有任何限制。

​ 形式上，设Π = (Gen, Enc, Dec)是消息空间为M的加密方案。假设A是一个对手，它在形式上只是一个(有状态的)算法，我们可以假设它是确定的而不丧失一般性。我们基于A和Π定义了一个实验[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VPG2muGB-1669001343755)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114152753921.png)]

对抗性不可区分实验[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZfOEddT6-1669001343756)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114152924061.png)]：

①敌手A输出一对消息m₀, m₁∈M。

②使用Gen生成密钥k，并选择均匀位b∈{0,1}。计算密文c←Enck(m_b)给A，称c为挑战密文。

③A输出比特b‘。

④实验的输出被定义为当b’ = b时为1，否则为0。如果实验的输出是1，在这种情况下我们说A成功了，记作[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lynAsabO-1669001343757)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114154349546.png)]

如前所述，A通过输出一个随机猜测以1/2的概率成功是微不足道的。完美的不可区分性要求任何A都不可能做得更好。

定义2.6：

​ 消息空间M的加密方案Π = (Gen, Enc, Dec)是完全不可区分的，如果它对每个A都保持该值[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PvSbkmT8-1669001343757)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114154612752.png)]

以下引理指出定义2.6与定义2.3等价。我们把引理的证明留在练习2.6。

引理2.7加密方案Π是完全机密的，当且仅当它完全不可区分

Example 2.8:

我们证明维吉尼亚密码不是完全不可区分的，至少对于某些参数是这样。具体地说，让Π表示两个字符串的消息空间的维吉尼亚密码，其中period在{1,2}中统一选择。为了表明Π不是完全不可区分的，我们展示了一个敌手A，其中[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lqNulK5G-1669001343758)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114155142615.png)]

敌手A可以：

①输出m₀=aa,m₁=ab

②当收到挑战密文c = c₁c₂时，执行以下操作:if c₁ = c₂ 输出0;否则输出1

计算[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aZQxjb6B-1669001343758)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114155439344.png)]很乏味但很简单。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A0n3cuAz-1669001343759)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114155525003.png)]

其中b是决定哪条消息被加密的统一位。根据定义，当且仅当密文c = c₁c₂的两个字符相等时，A输出0。当b=0(所以m₀ = aa被加密)时，如果(1)选择一个周期为1的密钥，或者(2)选择一个周期为2的密钥，且密钥的两个字符相等，则c₁ = c₂。前者发生的概率为1/2，后者发生的概率为1/2×1/26。所以：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lBieBju0-1669001343759)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114160124157.png)]

当b = 1时，只有当周期为2的密钥被选中且该密钥的第一个字符比第二个字符多一个字符时，c₁ = c₂，这种情况发生的概率为1/2×1/26。所以：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2YRlzWiv-1669001343762)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114160341252.png)]

代入式2.4得到[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F56q7iOy-1669001343765)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114160419160.png)]

因此该方案并非完全无法区分。

2.2 一次一密

​ 1917年，Vernam为一种完全保密的加密方案申请了专利，现在称为一次一密。在Vernam提出这个计划的时候，没有证据表明它是绝对机密的;事实上，完全保密的概念还没有定义。然而，大约25年后，香农提出了完全保密的定义，并证明一次一密满足该定义。

​ 在描述格式时，我们让a⊕b表示两个等长二进制字符串a和b的位异或(XOR)。(即，如果a = a₁···a_l和b = b₁··b_l是l位字符串，那么a⊕b是由(a₁⊕b₁)···(a_l⊕b_l)给出的l位字符串。在一次一密加密方案中，密钥是与消息长度相同的统一字符串，密文是通过简单地对密钥和消息进行异或计算得到的;其正式定义见结构2.9。在讨论安全性之前，我们首先验证正确性:对于每个密钥k和每个消息m，它认为Deck(Enck(m)) = k⊕k⊕m = m，因此一次一密构成了一个有效的加密方案。

​ 使用引理2.5可以很容易地证明一次一密的完全机密性，因为密文是统一分布的，而不管加密的消息是什么。在原定义的基础上，给出了直接的证明。

定理2.10 一次一密加密方案是完全机密的。

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

​ ①Gen:密钥生成算法从K ={0,1} ^l中根据均匀分布选择一个密钥；空间中每一个2^l的字符串都被选择为概率恰好为2^-l的密钥

​ ②Enc:给定密钥k∈{0,1}^l和消息m∈{0,1}^l，加密算法输出密文c:= k⊕m。

​ ③Dec:给定密钥k∈{0,1}^l和密文c∈{0,1}^l，解密算法输出消息m:= k⊕c。

​ **证明：**我们首先计算当Pr[M = m] > 0时对任意c∈C和m∈M的Pr[C = c|M = m]。对于一次一密，我们有：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2rcptCGh-1669001343765)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114163527627.png)]

其中第一个等式是根据方案的定义以及我们对事件M = m的条件，最后一个等式成立，因为密钥K是一个统一的l比特字符串，与M无关。固定M上的任意分布。利用上面的结果，我们可以看到，对于任意c∈C，我们有：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BUJ38QfL-1669001343765)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114164259443.png)]

贝叶斯定理给出了：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-n71MEKcD-1669001343766)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221114164335644.png)]

我们得出的结论是，一次一密是完全机密的。

​ 20世纪中期，数家国家情报机构曾使用这种一次一密对敏感通信进行加密。也许最著名的是，冷战期间连接白宫和克里姆林宫的“红色电话”使用了一次一密技术，美国和苏联政府可以通过可靠的信使交换超长的密钥，信使携带着装着随机字符的公文包。

​ 尽管如此，一次一密现在很少使用，因为它有一些缺点。最突出的是，密钥要和信息一样长。这限制了该方案在发送非常长的消息时的有用性(因为可能很难安全地共享和存储非常长的密钥)，并且当各方无法提前预测(消息长度的上限)时会出现问题。

​ 此外，一次一密——顾名思义——只有在使用一次(使用给定的密钥)时才安全。虽然我们还没有定义加密多个消息时的保密概念，但很容易看出，使用相同密钥加密多个消息会泄露大量信息。特别地，假设两个消息m和m‘使用相同的(未知)密钥k进行加密。得到c = m⊕k和c’= m‘⊕k的对手可以计算：c ⊕ c’ = (m ⊕ k) ⊕ (m‘ ⊕ k) = m ⊕ m’。从而了解两个消息的异或，或者等效地，确切地知道两个消息的不同之处。这种攻击还可以扩展到两个以上的消息，使攻击者能够了解所有消息对的异或。虽然这可能看起来不是很重要，但这足以排除使用相同密钥加密多个消息的完全保密主张。此外，如果消息对应于自然语言文本，那么给定足够多的消息对(甚至两个足够长的消息)的异或，就有可能执行频率分析(如前一章所述，尽管更复杂)并恢复消息本身。(示例见练习2.16)。VENONA项目提供了一个有趣的历史例子，作为该项目的一部分，美国和英国能够解密苏联发送的密文，这些密文被错误地加密了几十年，使用的是一个一次一密的重复部分。

2.3 完全保密的局限性

​ 在上一节结束时，我们注意到一次性pad加密方案的一些缺点。在这里，我们表明这些缺点并不是该方案特有的，而是完全保密的固有限制。具体地说，我们证明了任何完全保密加密方案都必须有一个至少与消息空间一样大的密钥空间。如果所有密钥的长度都相同，并且消息空间由所有固定长度的字符串组成，这意味着密钥至少与消息一样长。特别地，一次性pad的密钥长是最佳的。(另一个限制——即钥匙只能使用一次——也是固有的;见练习2.19。)

定理2.11如果(Gen, Enc, Dec)是消息空间M和密钥空间K的完全保密加密方案，则|K|≥|M|。

**证明：**我们证明，如果|K| < |M|，则方案不可能是完全机密的。假设|K| < |M|。考虑在M上的均匀分布，设c∈C是一个非零概率出现的密文。设M©是c可能解密的所有可能消息的集合，存在：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wFsQtSOM-1669001343766)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221115100601573.png)]

显然|M©|≤|K|。(回想一下，我们可以假设Dec是确定的。)

如果|K| < |M|，那么存在某个m’∈M，使得m’∈M©，但[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TgOkJfgb-1669001343767)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221115100914307.png)]

因此，该计划并非完全保密。

用更短的密钥完美保密？

​ 上述定理显示了实现完全保密的方案的固有局限性。即便如此，个别人士偶尔也会声称，他们已经开发出一种全新的加密方案，这种方案“牢不可破”，加密的内容不需使用密钥，就可以达到一次一密的安全性。上述证据表明，这种说法不可能是真的;做出这种断言的人要么对密码学知之甚少，要么就是在公然撒谎。

2.4香农定理

​ 在关于完全保密的研究中，香农还对完全保密的加密方案进行了描述。这一特性表明，**在特定条件下，密钥生成算法Gen必须从所有可能的密钥集合中均匀一致地选择密钥(如一次一密);此外，对于每一个消息m和密文c，都有一个唯一的密钥将m映射到c(同样，在一次一密中)。**除了本身有趣之外，这个定理还是证明(或反驳)方案完全保密的有用工具。我们将在证明之后进一步讨论这个问题。

​ 这里的定理假设|M| = |K| = |C|，这意味着明文、密钥和密文的集合都具有相同的大小。我们已经知道，为了达到完美的保密性，我们必须有|K|≥|M|。很容易看出，正确的解密需要|C|≥|M|。因此，在某种意义上，|M| = |K| = |C|的完全保密加密方案是“最优的”。

定理2.12 香农定理

​ 设(Gen, Enc, Dec)为消息空间M的加密方案，其中|M| = |K| = |C|。该计划是完全秘密的，当且仅当:

①每个密钥k∈K的被选择概率为(相等)1/| k |。

②对于每一个m∈M和每一个c∈C，存在一个唯一的密钥k∈K，使得Enck(m)输出c。

证明：

​ 证明背后的直觉如下。要看所述条件是否意味着完全保密，请注意条件2意味着任何密文c都可能是加密任何可能的明文m的结果，因为有某个密钥k将m映射到c。因为这样的密钥是唯一的，而且每把密钥的被选择概率都是相等的，所以就像一次性密钥一样，完全保密。对于另一个方向，完全保密立即意味着，对于每一个m和c，至少有一个密钥将m映射到c。此外，|M| = |K| = |C|这一事实意味着，每一个m和c都恰好有一个这样的密钥。在这种情况下，每个密钥都必须以相同的概率被选择，否则完全保密将无法保持。正式的证明如下。

​ 为了简单起见，我们假设Enc是确定的。(可以看出，这一点并不缺乏普遍性。)我们首先证明如果加密方案满足条件1和2，那么它是完全机密的。证明本质上与一次一密的完全保密证明是一样的，所以我们将相对简短。固定任意c∈C和m∈M，设k为唯一密钥，由条件2保证，其中Enck(m) = c。那么：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fFcNPxTI-1669001343768)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221115103253469.png)]

根据条件1，最后的等式成立。由于这对任意m和c成立，引理2.5意味着该方案是完全秘密的。

​ 对于第二个方向，假设加密方案是完全秘密的;我们证明条件1和2成立。固定任意c∈C。对于Pr[Enc_K(m*) = c] ≠ 0，必然存在某个消息m *。引理2.5表明对于每个m∈M，Pr[Enc_K(m) = c]≠ 0。换句话说，如果我们让M = {m₁, m₂，…}，那么对于每个m_i∈M，我们有一个非空的密钥集K_i⊂K，这样当且仅当k∈K_i时，Enc_k(m_i) = c此外，当i ≠ j时，K_i和K_j必须是不相交的，否则正确性不能成立。因为|K| = |M|，我们看到每个K_i只包含一个密钥k_i，这是条件2所要求的。引理2.5表明，对于任何m_i, m_j∈M,存在：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DKPkZcbM-1669001343769)(C:\Users\tongtong\AppData\Roaming\Typora\typora-user-images\image-20221115104604387.png)]

​ 因为这适用于所有1≤i, j≤|M|=|K|，并且对于i≠ j, k_i≠ k_j，这意味着每个密钥的选择概率为1/|K|，正如条件1所要求的那样。

​ 香农定理可以用来判断一个给定的方案是否完全机密。条件1很容易检查，条件2可以证明(或反驳)，而不需要计算任何概率(与直接使用定义2.3相比)。举个例子，用香农定理证明一次一密的完全保密是微不足道的。但是，我们强调，这个定理只适用于|M| = |K| = |C|。
001343769)]

​ 因为这适用于所有1≤i, j≤|M|=|K|，并且对于i≠ j, k_i≠ k_j，这意味着每个密钥的选择概率为1/|K|，正如条件1所要求的那样。

​ 香农定理可以用来判断一个给定的方案是否完全机密。条件1很容易检查，条件2可以证明(或反驳)，而不需要计算任何概率(与直接使用定义2.3相比)。举个例子，用香农定理证明一次一密的完全保密是微不足道的。但是，我们强调，这个定理只适用于|M| = |K| = |C|。