密码学｜5.6 信息论

密码学 2年前 (2023) admin

340 0 0

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.47）。

我们还考虑所有这些随机变量对的联合密度和条件密度，例如和等等。我们可以将变量名简化表示，例如，我们将写做以表示随机变量和的条件概率密度。

同样我们将写作以表示的概率。

定义一个密码系统具有无条件安全，当其满足

密码学｜5.6 信息论（5.45）

式（5.45）是什么意思，它表示任何特定明文的概率都与密文无关。直观地说，这意味着密文对明文一无所知。

根据贝叶斯定理（定理 5.33），我们有

因此无条件安全等同于

$(5.46) f (c | m) = f (c), \forall c \in C a n d \forall m \in M w i t h f (m) \neq 0$

式（5.46）表示，任何特定密文的出现都有可能，与明文无关。

如果我们知道和，则能确定。为了表示这一点，我们注意到，对于给定密钥，密文等于的概率与的解密是明文的概率相同，当然假设是由密钥加密明文而来。这允许我们通过对所有可能的密钥求和，并使用命题5.24的分解公式（5.20），来计算总概率。像往常一样，我们让表示所有可能的密钥的集合，和是与密钥相关的加密和解密函数。然后密文等于的概率由以下公式给出

我们注意到，如果对于所有的密钥都满足加密映射（在实践中也通常是这样），那么式 (5.47) 中的和就是在所有上。

例5.53

考虑第1.1节中描述的移位密码。假设以相等的概率选择26个可能的密钥（移位量）中的每一个，并且每个明文字符都使用新的、随机选择的移位量来加密。那么不难得出该密码系统具有无条件安全性。

回想一下，加密函数是一对一的，这意味着每个消息都会产生一个唯一的密文。也意味着密文至少和明文一样多。无条件安全对密钥、消息和密文空间的相对大小有额外的限制。我们首先研究一个不具有无条件安全的密码系统的例子。

例 5.54

假设密码系统具有两个密钥和，三个明文，以及三个密文。假设明文随机变量的密度函数足

密码学｜5.6 信息论

表 5.12 描述了不同密钥如何作用于明文以产生密文

例如，用密钥对明文的加密是密文。假设密钥使用的概率相等，我们可以使用式 (5.47) 计算密文等于的概率：

另外，根据表中我们发现，因此，该密码系统不具备无条件安全性。这是符合我们直觉的，因为很明显这个系统的密文会泄露一些有关明文的信息。例如，如果我们看到密文，那么我们就知道消息是或，它不可能是。

我们前面提到过，密文的数量至少要和明文的数量一致，否则我们就无法进行正常的解密。然而对于无条件安全来说，密钥的数量至少要和明文的数量一样。

命题 5.55

一个具备无条件安全的密码学系统，其，其中，是有概率被选作明文的元素集合。

证明：

我们首先固定一些密文，根据式（5.46），无条件安全要求

即有概率加密为密文，即实际存在一个密钥满足。另外，如果我们选取另外一个明文，那么与之对应的就需要另外一个密钥，否则的话就有，这与我们加密函数一对一的性质是相悖的。

概括地说，我们已经证明，对于每个，集合

都是非空的。此外，这些集合对于不同的是不相交的。因此，每个明文与一个或多个密钥相匹配，不同的与不同的密钥匹配，这表明密钥的数量至少与中明文的数量一样。

在无条件安全的系统中，由于密钥、密文和明文空间的相对大小受到限制，即

方便起见我们可以假设密钥空间、明文空间和密文空间的大小都相等。在这样的假设前提下，Shannon证明了一个描述无条件安全的定理

定理 5.56

假设密码系统满足，即密钥、明文和密文的数量都相等。当且仅当以下两个条件成立则系统满足无条件安全性：

每个密钥都有相同的概率被使用
对于给出的消息和密文，都存在一个密钥使得可以加密问密文

证明

首先我们假设该密码系统具有无条件安全性。

我们先证明 2，对于任意的明文和密文，我们考虑能够将明文加密为密文的密钥集合

那么我们证明如果该密码系统具有无条件安全性，则对于每一个和都有，这等价于我们的条件2。

证明分为三点，

Claim 1：如果，那么

假设，那么，由于加密函数是单射的，也就意味着，于是我们反证了 Claim1。

Claim 2： 如果密码系统是无条件安全的，那么对于每一个，集合都是非空的。

我们使用的形式来描述无条件安全。我们知道，每个是至少一个密钥的有效明文，因此。类似地，每个都是使用某个密钥对至少一个明文进行加密而来，因此。因此，无条件安全意味着

但式子只是表示可能是加密而来的另一种方式。因此，必须至少有一个密钥满足，即，存在某个密钥，这证明了 Claim 2

Claim 3 如果密码系统是无条件安全的，那么

固定密文，那么

因此，所有这些不等式都是相等的，特别

那么，根据 Claim 2 的每个都大于或等于1的事实，于是每个都必须等于1。这就完成了 Claim 3 的证明。

上面我们提到， Claim 3 等价于定理的条件 2，那么我们现在证明条件 1。考虑三元组集合

显然，和确定了的唯一值，条件 2 表示和确定了的唯一值，以及的假设，表明和确定的唯一值。于是，对于任意满足的三元组，我们计算

（有一些密码系统，其中消息是密钥的一部分，在这种情况下，和将不是独立的。）

整理一下，我们得到

密码学｜5.6 信息论

注 意， 我们的证明表明，（5.50）对每个 和每个 都是正确的，因为对于每个 ，都有一个（唯一的） 满足 。

我们在下对式子（5.50）进行求和，然后除以得到

这表明是常数，与的选择无关，这正是条件 1。同时，我们证明了是常数这一有用事实，即每个密文都以相等的概率使用。

例 5.57（一次一密）

Vernam 的一次一密于1917年获得专利，是一种极其简单、完全保密的密码系统，尽管效率很低。密钥由一串二进制数字。它用于加密二进制明文字符串，通过将两个字符串逐位 “异或”（）运算在一起。。然后密文由下式给出

每个密钥只使用一次，然后被丢弃，系统的名称也由此产生。由于每个密钥的使用概率相等，并且只有一个密钥将给定的加密到给定的，即密钥，根据定理5.56 表明 Vernam 的一次一密具有无条件安全性。

不幸的是，如果 Bob 和 Alice 想要使用 Vernam 一次一密交换位信息，他们必须已经知道位共享的秘密信息，才能用作密钥。这使得一次一密对于大规模通信网络来说太过不足。然而，在某些情况下，它们被使用，例如外交部门之间的绝密通信或间谍与其基地之间的短消息。

同样值得注意的是，只有在其钥匙从未被重复使用的情况下，一次一密才能保持完全安全。当由于错误或难以提供足够的密钥材料而多次使用密钥时，则该密码系统可能容易受到密码分析的影响。这发生在现实世界中，当时苏联在第二次世界大战期间重用了一次一密。美国开展了一项名为 VENONA 项目的大规模密码分析工作，成功解密了大量文件。