5.6 信息论 1948年 和 1949年，克劳德·香农（Claude Shannon）发表了两篇论文《A mathematical theory of communication》、《Communication theory of secrecy systems》，它们构成了现代密码学的数学基础。在这些论文中，他定义了完美（或无条件）安全的概念，介绍了自然语言熵和统计分析的概念，使用概率论提供了第一个安全性证明，并给出了可证明安全性与密钥、明文和密文空间大小之间的精确联系。 在公钥密码中，人们感兴趣的是破解系统的计算难度。因此，安全性问题是一个相对的问题，如果人们假设某些潜在问题很难解决，那么给定的密码系统就很难破解。正确表述这些概念需要一定的谨慎。在本节中，我们简要介绍了香农的思想，并解释了它们与对称密钥系统的相关性。在《Communication theory of secrecy systems》中，Shannon提出了一种密码系统的安全理论，该理论假设我们拥有无限的计算资源。例如，对称密码，如简单替换密码（第1.1节）和维吉尼亚密码（第5.2节）在计算上是不安全的。由于资源有限，对手可以轻易破解这些密码。如果我们寻求无条件的安全性，我们要么寻求新的算法，要么修改已知算法的实现。事实上，香农表明，无条件安全的密码系统必须至少有与明文一样多的密钥，并且每个密钥必须以相等的概率使用。这意味着大多数实用的密码系统都不是无条件安全的。我们将在5.6.1 一节中讨论无条件安全的概念。 在《A mathematical theory of communication》中，香农发表了一种数学理论，该理论测量随机变量所揭示的信息量。当随机变量表示用于加密自然语言（如英语）的密码的可能明文或密文或密钥时，我们获得了关于密码安全的严格数学研究框架。香农将熵一词用于这一度量，因为它在形式上与统计力学中波尔兹曼对熵的定义相似，也因为香农将语言视为一个随机过程，即一个由产生符号序列的概率控制的系统。后来，物理学家 E.T.Jaynes 认为热力学熵可以解释为某种信息论熵的应用。作为系统 “不确定性” 的度量，熵的对数公式是通过要求它是连续的、单调的，并且满足一定的加性性质来确定的。我们将在第 5.6.2 一节中讨论信息论熵及其在密码学中的应用。 5.6.1 无条件安全 如果对密文的分析不会给密码分析员有关明文的任何信息，也不给任何未来密文的信息，则密码系统具有完全保密性。为了形式化这个概念，我们引入了变量、、 ，它们表示可能的明文、密文和密钥。换句话说，、、 是相关的密度函数。密度函数与加密/解密公式 我们还考虑所有这些随机变量对的联合密度和条件密度，例如
定义 一个密码系统具有无条件安全，当其满足
（5.45）
式（5.45）是什么意思，它表示任何特定明文的概率
(5.46)f(c|m)=f(c),∀c∈C and ∀m∈M with f(m)≠0
式（ 5.46）表示，任何特定密文的出现都有可能，与明文无关。 如果我们知道
我们注意到，如果对于所有的密钥 例5.53
考虑第1.1节中描述的移位密码。假设以相等的概率选择26个可能的密钥（移位量）中的每一个，并且每个明文字符都使用新的、随机选择的移位量来加密。那么不难得出该密码系统具有无条件安全性。 回想一下，加密函数是一对一的，这意味着每个消息都会产生一个唯一的密文。也意味着密文至少和明文一样多。无条件安全对密钥、消息和密文空间的相对大小有额外的限制。我们首先研究一个不具有无条件安全的密码系统的例子。 例 5.54
假设密码系统具有两个密钥 、、 ，以及三个密文、、 。假设明文随机变量的密度函数 足
表 5. 12 描述了不同密钥如何作用于明文以产生密文 例如，用密钥 对明文 的加密是密文 。假设密钥使用的概率相等，我们可以使用式 (5.47) 计算密文等于 的概率：
另外，根据表中我们发现 我们前面提到过，密文的数量至少要和明文的数量一致，否则我们就无法进行正常的解密。然而对于无条件安全来说，密钥的数量至少要和明文的数量一样。 命题 5.55
一个具备无条件安全的密码学系统，其 证明 ：
我们首先固定一些密文
即
都是非空的。此外，这些集合对于不同的 在无条件安全的系统中，由于密钥、密文和明文空间的相对大小受到限制，即
方便起见我们可以假设密钥空间、明文空间和密文空间的大小都相等。在这样的假设前提下，Shannon证明了一个描述无条件安全的定理 定理 5.56
假设密码系统满足
对于给出的消息
证明
我们先证明 2，对于任意的明文
那么我们证明如果该密码系统具有无条件安全性，则对于每一个 Claim 1： 如果
假设 Claim 2： 如果密码系统是无条件安全的，那么对于每一个
我们使用
但式子 Claim 3 如果密码系统是无条件安全的，那么
那么，根据 Claim 2 的每个 上面我们提到， Claim 3 等价于定理的条件 2，那么我们现在证明条件 1。考虑三元组集合
显然，
（有一些密码系统，其中消息是密钥的一部分，在这种情况下，
注意， 我们的证明表明，（5.50）对每个 和每个 都是正确的，因为对于每个 ，都有一个（唯一的） 满足 。 我们在
这表明 例 5.57（一次一密）
Vernam 的一次一密于1917年获得专利，是一种极其简单、完全保密的密码系统，尽管效率很低。密钥
每个密钥只使用一次，然后被丢弃，系统的名称也由此产生。由于每个密钥的使用概率相等，并且只有一个密钥将给定的 不幸的是，如果 Bob 和 Alice 想要使用 Vernam 一次一密交换 同样值得注意的是，只有在其钥匙从未被重复使用的情况下， 一次一密才能保持完全安全。当由于错误或难以提供足够的密钥材料而多次使用密钥时，则该密码系统可能容易受到密码分析的影响。这发生在现实世界中，当时苏联在第二次世界大战期间重用了一次一密。美国开展了一项名为 VENONA 项目的大规模密码分析工作，成功解密了大量文件。
评论