第2章 香农理论
1949年，克劳德·香农（Claude Shannon）在《Bell Systems Technical journal》上发表了一篇题为“Communication Theory of Secrecy System”（保密系统的通讯理论）的论文，这篇论文对密码学的研究产生了重大影响。本章我们将讨论部分香农的思想。
首先介绍两种评价密码系统安全性的基本方法。
计算安全性
这种度量只关心攻破一个密码系统在计算上所做的努力。如果用最好的算法攻破一个密码系统也至少需要次操作，其中是一个非常大的特定数字，我们就可以称这个密码系统是计算安全的。问题在于，在这个定义下，没有一个已知的密码系统能够被证明是安全的。在实际应用中，如果攻击一种密码系统的已知最好的方法也需要非常长的计算机时间，人们就称该密码系统是“计算安全的”(当然，这与安全性的证明有很大区别)。另一种方法是将密码系统的安全性归结为一些研究较为成熟的被认为是不难解的问题，以此提供计算安全性的证据。比如，人们可以证明这样一个论断：如果给定的整数不能被分解，则一个给定的密码系统就是安全的。这种类型的密码系统有时被称为“可证明安全的”，但必须理解，它只是证明了安全性是和另一个问题相关，并没有完全证明是安全的。
无条件安全性
这种度量考虑的是对攻击者Oscar的计算量没有任何限制时的安全性。即使提供了无穷的计算资源也无法攻破的密码体制被称为是无条件安全的。
当我们讨论一个密码系统的安全性时，应该指定正在考虑的攻击类型。在第1章，我们可以看出，一旦给定足够数量的密文，移位密码、代换密码和维吉尼亚密码对惟密文攻击都不
是计算上安全的。
本节我们将研究一个对惟密文攻击是无条件安全的密码体制的相关理论。可以证明，如果用给定的密钥仅仅加密明文中的一个元素，那么上述三种密码体制都是无条件安全的。 很显然，一个密码系统的无条件安全性不能以计算复杂性的观点来研究，因为我们允许计算时间是无限的。研究无条件安全性的最合适的方法是概率论。我们仅需要概率论的一些基本知识，主要的定义回顾如下：
定义2.1 设和都是随机变量，以表示取时的概率，以表示取时的概率。联合概率表示取并且取时的概率。条件概率表示取时取的概率。如果对任意的和，都有，则称随机变量和赵安近况是统计独立的。
联合概率和条件概率的关系如下
交换和，我们有
从上述两个表达式，我们可以得到下面的结果，也就是著名的Bayes定理。
定理2.1 (Bayes定理) 如果，那么
推论2.2 和是统计独立的随机变量，当且仅当对所有的和，有。
在本节所有部分，我们都假设一个特定的密钥仅用于一次加密。假设在明文空间P上有一个概率分布，以表示明文发生的先验概率，还假设(Alice和Bob)以固定的概率分布选取密钥(通常密钥是随机选取的，因此所有的密钥都是等概率的，但这并不是必须的)，以表示密钥的选取概率。回忆一下密钥是在Alice知道明文之前选取的，因此我们就可以合理的假设密钥和明文相互独立的事件。
P和K的概率分布诱导出密文空间C上的概率分布。事实上，不难计算出密文的概率，对于密钥K，定义
也就是说C代表密钥是时所有可能的密文集合。对任意的C，我们有
我们也可以看到，对于任意的C和P，可如下计算条件概率（即给定明文x，密文为y的概率），计算如下：
。阿基米德螺线
现在可以应用Bayes定理计算条件概率(也就是给定密文，明文为的概率)，计算如下:
可见，知道了概率分布的任何人都可以完成这些运算。
现在，我们给出一个例子来说明具体如何计算这些概率。
例2.1 设满足，，设，，，设C，加密函数定义为，，，，，。这个密码体制可以用如下加密矩阵表示：
现在我们计算如下：
＝
＝
现在计算给定密文后，明文空间上的条件概率分布，如下：
现在我们给出完善保密性的概念。非正式地，完善保密性就是说Oscar不能通过观察密文
得到明文的任何信息。用概率分布的术语，精确的定义如下。
定义2.2 如果对于任意的P和C，有，我们就称一个密码体制具有完善保密性。也就是说，给定密文，明文为的后验概率等于明文的先验概率。
在例招商嘉铭珑原2.1中，对于密文满足完善保密性的定义，但是对于其他的密文不满足。
现在证明移位密码具有完善保密性。从直觉上看这是很显然的，因为对于任意给定的密文，任何都可能是对应的明文。下面的定理用概率分布给出了正式的陈述和证明。
定理2.3 假设移位密码的26个密钥都是以相同的概率使用的，则对于任意的明文概率分布，移位密码具有完善保密性。
证明： 这里PKC，对于，加密函数定义为。首先计算C上的概率分布。设，则
。
现在固定，值构成的一个置换。因此有
，
可得对于任意的，都有
。
接下来，对于任意的，，我们有
，
(这是因为对任意的，，满足的惟一的密钥为)。现在运用Bayes定理，很容易得到
所以这个密码体制是完善保密的。
因此，如果用一个新的随机密钥来加密每个明文字母，则移位密码是“不可攻破的”。
让我们考察一般的完善保密性。首先，我们可以发现，使用Bayes定理，对于所有的P雅克141和C,等价于对于所有的P和C,有。我们可以合理地假设对于所有的C， (如果，则密文从不会使用到，可以从中去掉)。
固定任意的P，对于任意的C，我们都有。因此，对于任意的C，一定至少存在一个密钥使得。于是就有|K||C|。在任意一个密码体制中，因为加密函数是单射的，一定有|C||P|。当|K||C||P|时，我们有一个关于什么时候取得完善保密性的很好的性质，这个性质最早也是由香农提出来的。
定理2.4 假设密码体制(P,C,K)满足|K||C||P|。这个密码体制是完善保密的，当且仅当每个密钥被使用的概率都是1/|K|，并且对于任意的P和C，存在惟一的密钥使得。
证明： 假设这个密码体制是完善保密的，由上面可知，对于任意的P和C，一定至少存在一个密钥使得成立，因此有不等式
|C|
但是我们假设|C||K|，因此一定有
也就是说，不存在两个不同的密钥和，使得。因此对于任意P和C，刚好存在一个密钥使得。
记|K|。设P并且固定一个密文C。设密钥为，并且，。使用Bayes定理，我们有
考虑完善保密的条件，从这里，我们有，。也就是说，所有的密钥都是等概率使用的(概率为)。但是密钥的数目为|K|，我们得到对任意的，有。
相反地，如果两个假设的条件是成立的，类似于定理鼻尖雕塑2.3的证明，很容易得到密码体制是完善保密的。证明留给读者自己完成。
一个著名的具有完善保密性的密码体制是“一次一密”密码体制。这个体制首先由Gilbert Vernam于1917年用于报文消息的自动加密和解密。有趣的是，“一次一密”很多年来被认为是不可攻破的，但是一直都没有一个数学的证明，直到30年后香农提出了完善保密性的概念。
mgs1
“一次一密”的描述如图2.1所示。
图2.1 一次一密
由定理2.4容易看出，“一次一密”提供了完善保密性。这个密码体制的加密和解密很容易，也有一定的吸引力。
Vernam希望他的思想有广泛的商业用途，为此他还申请了专利。遗憾的是，诸如“一次一密”这样的无条件安全的密码体制存在一个较大的不利因素。意味着秘密使用的密钥数量必须至少和和明文的数量一样多。例如，在“一次一密”的密码体制中，我们要求用比特的密钥加密比特的明文。如果相同的密钥可用于加密不同的消息则这不是一个重要的问题，但是密码体制的无条件安全性是基于每个密钥仅用一次的事实。
例如，“一次一密”对已知明文攻击将是脆弱的，因为可以通过异或比特串和得到。因此，对每一个将要发送的明文，必须生成新的密钥并在安全信道上传输，这就带来了一个严峻的密钥管理问题，因此限制了“一次一密”在商业上的应用。但是“一次一密”在要求无条件安全的军事和外交环境中有着很重要的应用。
在密码学的发展历史中，人们试图设计出密钥可以用于加密相对长的明文(也就是一个密钥可以加密许多消息)，并且仍然可以保持一定的计算安全性的密码系统，我们将要在下一章讨论的数据加密标准就是一个这样的例子。
2.2 熵
在上一节，我们讨论了完善保密性的概念。我们将注意力集中在密钥只能用于一次加密的特殊情况下。现在看看用一个密钥加密多个消息会发生什么，并且还要看看如果给密码分析员足够时间，进行一次成功的的惟密文攻击有多大的可能性。
研究这个问题的基本工具是熵，这个概念来自于香农于1948年创建的信息论。熵可以看作是对消息或不确定性的数学度量，它是通过一个概率分布函数来计算的。
假设离散的随机变量按照特定的概率分布从一个有限集合中取值。我们可以从按照这个概率分布的事件结果中得到什么信息呢?或者说，在事件发生之前，结果的不确定性是什么呢？这个量被称为的熵，记为。
上述描述看起来还是相当抽象，让我们看看更为具体的例子。假设随机变量代表掷硬币。如前文所述，概率分布。由于可以将“heads”编码为1，将“tails”编码为0，我们可以合理地说，一次掷硬币的信息或者熵是1比特。用同样的方式，次独立的掷硬币的熵是比特，因为次投掷可以用长为比特的比特串进行编码。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议