2.Perfectly Secret Encryption

在前一章中，我们介绍了一些历史上的加密方案，并展示了它们很容易被破解。在本章中，我们将研究一些加密方案，这些方案能够被证明是完全安全的，即使对手具有无限的计算能力。这些方案被称为完全秘密的。我们将严格定义这个概念，并探讨实现完全秘密性的条件。

从某种意义上说，本章的材料更属于“古典”密码学而不是“现代”密码学的范畴。因为所有在这里介绍的材料都是在密码学的革命发生于20世纪70年代和80年代之前就已经发展出来的。本章介绍的构造仅依赖于第1.4节中概述的第一和第三个原则。也就是说，我们使用精确的数学定义和严格的证明，但不需要依赖于任何未经证明的计算假设。避免这种假设显然是有优势的；然而，我们将看到这样做具有固有的限制。因此，除了作为理解现代密码学原理的良好基础之外，本章的结果还证明了我们后来采用了前述三个原则的正确性。

从本章开始，我们将使用涉及随机算法的概率性实验来定义安全性并分析方案。（我们假设读者熟悉基本的概率论。相关概念在附录A.3中进行了回顾。）一个简单的例子是“实验”，其中希望使用私钥加密方案进行通信的各方生成随机密钥。由于随机性是如此重要，我们在回到密码学本身的讨论之前，简要讨论适用于密码应用的随机性生成问题。

这里不再介绍随机生成问题只强调下注意事项：
在生成随机比特时必须小心，使用低质量的随机数生成器往往会使良好的加密系统易受攻击。应该使用专门设计用于密码学的随机数生成器，而不是通常不适用于密码学应用的“通用”随机数生成器。特别是，C 语言的stdlib.h库中的rand()函数不具备密码学安全性，将其用于密码设置中可能会产生灾难性后果。

2.1Definitions

我们想象一个知道M的概率分布的对手；也就是说，对手知道不同消息被发送的可能性。对手还知道正在使用的加密方案。唯一未知的是对手不知道各方共享的密钥。一条消息由其中一个诚实的参与者选择并加密，加密后的密文被传输给另一方。对手可以监听各方的通信，因此可以观察到这个密文。（也就是说，这是一种仅知密文攻击，攻击者只看到一个密文。）为了使方案完全保密，观察这个密文不应该影响对手关于实际发送的消息的知识；换句话说，在观察到的密文条件下，某些消息m∈M被发送的后验概率应该与m被发送的先验概率没有区别。这意味着密文不透露有关底层明文的任何信息，对手对加密的明文绝对不会了解任何信息。

定义2.3：
如果对于任何消息概率分布，任何消息m∈M和任何密文c∈C，且满足Pr[C=c]>0，则加密方案(Gen, Enc, Dec)具有完美保密性，当且仅当： $$Pr[M=m|C=c]=Pr[M=m] $$
（要求Pr[C=c]>0是一项技术性要求，以防止在概率为零的事件上进行条件概率的运算）
引理2.5：
一个消息空间为M的加密方案(Gen，Enc，Dec)是完美保密的，当且仅当对于每个m，$m_0$ ∈ M和每个c ∈ C，等式成立:

$$Pr[En{c}_k(m)=c]=Pr[En{c}_{(}{m}_0)=c]$$

此定义可以理解为密文空间的概率分布独立于明文空间的概率分布，可以由上面定义推理出，这里不再详细推理

完美（敌手）不可区分性。本节我们通过介绍一个敌手被动观察密文然后试图猜测加密的是哪个可能的消息的实验，来呈现另一种等价的完美保密性定义。我们引入这个概念是因为它将作为下一章中定义计算安全性的起点；在本书的其余部分中，我们经常使用这种实验来定义安全性。

在当前的背景下，我们考虑以下实验：一个敌手A首先指定两个任意消息m0、m1 ∈ M。接下来，使用Gen生成一个密钥k。然后，使用k加密A指定的两个消息中的一个（每个消息的概率为1/2），并将得到的密文给A。最后，A输出对加密的两个消息中哪一个的“猜测”；如果A猜测正确，则A成功。如果没有敌手A能够成功的概率超过1/2，则加密方案是完美不可区分的。（请注意，对于任何加密方案，A可以通过输出一个均匀的猜测以概率1/2成功；要求仅仅是没有攻击者能够做得比这更好。）我们强调没有对A的计算能力施加任何限制。

定义2.6：
加密方案Π=(Gen, Enc, Dec)的消息空间为M，当且仅当对于每个A，以下式子成立：

$$Pr[Priv{K}_{A,\Pi }^{eav}]=1/2.$$

引理2.7：
加密方案Π是完美保密的，当且仅当它是完美不可区分的。

2.2 The One-Time Pad

The One-Time Pad，也称为一次性密码本，是一个加密方案，由 Gilbert Vernam 于1917年首次提出。该方案的核心思想是使用长度与明文相同的随机密钥，对明文进行一次性加密。在正确使用的情况下，一次性密码本可以提供完美保密

定义
一次性密码本加密方案的定义如下：

• 密钥生成算法Gen：产生一个长度为n的随机密钥k，其中n为明文长度。
• 加密算法Enc：对于长度为n的明文m和密钥k，计算密文c = m ⊕ k，其中 ⊕ 表示按位异或。
• 解密算法Dec：对于密文c和密钥k，计算明文m = c ⊕ k。

证明
证明一次性密码本满足完美保密的方式有很多种，这里给出一种基于原始定义的证明方式：

我们需要证明对于所有的明文$m_0$、$m_1$和所有密文c ∈ Enc(K, M)，都有：

$$Pr[En{c}_K(m_0)=c]=Pr[En{c}_K(m_1)=c]$$

其中，K为密钥集合，M为明文集合，Pr表示概率。

通过按位异或的定义，我们知道对于任意的两个二进制字符串a和b，有a ⊕ b = b ⊕ a。因此，对于任意的明文m和密钥k，有：

$$m\oplus k=k\oplus m$$

因此，对于任意的明文m和密钥k，有：

$$Pr[En{c}_K(m)=c]=Pr[m\oplus k=c]$$

根据一次性密码本的定义，密钥k是一个长度为n的随机字符串，因此k是等概率地生成的。因此，对于任意的明文m和密钥k，有：

$$Pr[En{c}_K(m)=c]=Pr[m\oplus k=c]=Pr[k\oplus m=c]$$

这意味着，对于给定的密文c，任意的明文m和密钥k都能够生成该密文。因此，密文c的分布与明文的分布相同，即密文的分布在给定明文的情况下是均匀分布的。

因此，我们可以得出结论：一次性密码本是完美保密的，即对于任何攻击者，无论其拥有多少计算资源，都无法从密文中获得有关明文的任何信息。

注意：一次性密码本只是一种理论上的加密方案，在实际应用中存在许多问题，如密钥管理和密钥分发等。因此，在实际应用中，通常使用更现代的加密算法。

2.3 Limitations of Perfect Secrecy

我们在前一节中指出了一次性密码本加密方案存在一些缺点。在这里，我们将证明这些缺点不是该方案特有的，而是完美保密的本质限制。具体来说，我们证明任何完美保密的加密方案都必须具有至少与消息空间相同大小的密钥空间。如果所有密钥的长度相同，并且消息空间包含所有固定长度的字符串，则这意味着密钥至少与消息一样长。特别地，一次性密码本的密钥长度是最优的。（另一个限制，即密钥只能使用一次，也是固有的；见习题2.19。）

证明如下：

假设存在一个完美保密的加密方案，具有密钥空间K和消息空间M，其中|K|<|M|。考虑两个长度相同的消息$m_0$和$m_1$，令c为它们的加密结果，即c=Enc(k, $m_0$)=Enc(k, $m_1$)。由于密文c是相同的，因此攻击者无法区分$m_0$和$m_1$。根据完美保密的定义，对于任何的$m_0$和$m_1$，攻击者都无法从密文中获得有关明文的任何信息，因此，Pr[Enc(k, $m_0$) = c] = Pr[Enc(k, $m_1$) = c]，即攻击者无法区分$m_0$和$m_1$。

然而，由于|K|<|M|，密钥空间K中的密钥数量少于消息空间M中的消息数量，因此，存在至少一对不同的消息$m_0$和$m_1$，满足Enc(k, $m_0$) = Enc(k, $m_1$)。这意味着攻击者无法区分这两个消息，与完美保密的定义相矛盾。因此，假设不成立，即任何完美保密的加密方案必须具有至少与消息空间相同大小的密钥空间。

如果所有的密钥都具有相同的长度，且消息空间M由所有长度固定的字符串组成，则密钥长度至少与消息长度相同。因此，一次性密码本的密钥长度是最优的，因为它使用了与明文长度相同的随机密钥，同时满足了密钥空间大小与消息空间大小相等的条件，从而达到完美保密。需要注意的是，一次性密码本的另一个限制是密钥只能使用一次，这也是完美保密的本质限制之一。

综上，我们证明了任何完美保密的加密方案都必须具有至少与消息空间相同大小的密钥空间，这是完美保密的本质限制。一次性密码本的密钥长度是最优的，但其密钥只能使用一次，这也是完美保密的本质限制之一。在实际应用中，需要综合考虑加密方案的安全性、效率、可扩展性等因素，选择最合适的加密方案。

使用更短的密钥实现完美保密？ 上面的定理证明了实现完美保密的方案存在固有限制。即便如此，有些人偶尔声称他们开发了一种全新的加密方案，可以“无法破解”并实现与一次性密码本相同的安全性，而不需要使用与被加密数据相同长度的密钥。上面的证明表明这种声称是不成立的，任何声称可以实现这样的方案的人要么对密码学知之甚少，要么就是在公然说谎。

2.4 *Shannon’s Theorem

在他的完美保密工作中，香农还提出了完美保密加密方案的特征描述。这种特征描述表明，在某些条件下，密钥生成算法Gen必须从所有可能的密钥集合中均匀地选择密钥（与一次性密码本相同）；此外，对于每个明文m和密文c，都存在唯一的密钥将m映射到c（再次与一次性密码本相同）。除了本身具有的重要性外，这个定理还是证明（或反驳）方案完美保密性的有用工具。我们在证明之后进一步讨论这个定理。

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

换句话说，如果明文、密钥和密文的集合大小相同，那么这个完美保密加密方案是最优的，因为它使用了与明文长度相同的密钥，并满足了密钥空间大小与消息空间大小相等的条件，从而达到了完美保密。需要注意的是，这个定理假定了这些集合大小相等，但在实际应用中，这种情况并不常见，因此我们需要考虑其他因素，如密文长度、加密算法的效率和安全性等，来选择最适合实际应用场景的加密方案。

定理2.12（香农定理）设(Gen, Enc, Dec)是一个消息空间为M，且|M|=|K|=|C|的加密方案。当且仅当以下两个条件成立时，该方案是完美保密的：

1. 对于Gen算法生成的每个密钥k∈K，其被选择的概率都是1/|K|（即密钥被等概率地选择）。
2. 对于每个m∈M和每个c∈C，都存在唯一的密钥k∈K，使得Enck(m)输出c（即每个明文只有唯一的密文对应）。

香农定理对于判断一个给定的加密方案是否具有完美保密性非常有用。条件1很容易检查，条件2则可以在不需要计算概率的情况下证明或否定（与直接使用定义2.3相比）。例如，使用香农定理可以轻松证明一次性密码本具有完美保密性。需要强调的是，该定理仅适用于 |M| = |K| = |C| 的情况。

这个定理表明了完美保密加密方案的两个必要条件：即密钥的等概率选择和每个明文只有唯一的密文对应。需要注意的是，定理假设消息空间、密钥空间和密文空间的大小相同，这在实际应用中不一定成立。但是，该定理仍然是证明完美保密性的有用工具，因为它提供了一种对加密方案进行检验的方法。
定理的第一部分表明，密钥必须被随机地选择，以确保攻击者无法推断出密钥的值。第二部分表明，对于每个明文和密文的组合，只有一个密钥可以将它们映射到一起，这保证了攻击者无法猜测出明文或密文的值。

总之，该定理为构建完美保密加密方案提供了指导，并为验证加密方案的完美保密性提供了有用的工具。