第2章 香农理论.doc

《第2章 香农理论.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章香农理论1949年，克劳德·香农（ClaudeShannon）在《BellSystemsTechnicaljournal》上发表了一篇题为“CommunicationTheoryofSecrecySystem”（保密系统的通讯理论）的论文，这篇论文对密码学的研究产生了重大影响。本章我们将讨论部分香农的思想。2.1完善保密性首先介绍两种评价密码系统安全性的基本方法。计算安全性这种度量只关心攻破一个密码系统在计算上所做的努力。如果用最好的算法攻破一个密码系统也至少需要次操作，其中是一个非常大的特定数字，我们就可以称这个密码系统

2、是计算安全的。问题在于，在这个定义下，没有一个已知的密码系统能够被证明是安全的。在实际应用中，如果攻击一种密码系统的已知最好的方法也需要非常长的计算机时间，人们就称该密码系统是“计算安全的”(当然，这与安全性的证明有很大区别)。另一种方法是将密码系统的安全性归结为一些研究较为成熟的被认为是不难解的问题，以此提供计算安全性的证据。比如，人们可以证明这样一个论断：如果给定的整数不能被分解，则一个给定的密码系统就是安全的。这种类型的密码系统有时被称为“可证明安全的”，但必须理解，它只是证明了安全性是和另一个问题相关，并没有完全证明是安

3、全的。无条件安全性这种度量考虑的是对攻击者Oscar的计算量没有任何限制时的安全性。即使提供了无穷的计算资源也无法攻破的密码体制被称为是无条件安全的。当我们讨论一个密码系统的安全性时，应该指定正在考虑的攻击类型。在第1章，我们可以看出，一旦给定足够数量的密文，移位密码、代换密码和维吉尼亚密码对惟密文攻击都不是计算上安全的。本节我们将研究一个对惟密文攻击是无条件安全的密码体制的相关理论。可以证明，如果用给定的密钥仅仅加密明文中的一个元素，那么上述三种密码体制都是无条件安全的。很显然，一个密码系统的无条件安全性不能以计算复杂性的观点

4、来研究，因为我们允许计算时间是无限的。研究无条件安全性的最合适的方法是概率论。我们仅需要概率论的一些基本知识，主要的定义回顾如下：定义2.1设和都是随机变量，以表示取时的概率，以表示取时的概率。联合概率表示取并且取时的概率。条件概率表示取时取的概率。如果对任意的和，都有，则称随机变量和是统计独立的。联合概率和条件概率的关系如下交换和，我们有从上述两个表达式，我们可以得到下面的结果，也就是著名的Bayes定理。定理2.1(Bayes定理)如果，那么推论2.2和是统计独立的随机变量，当且仅当对所有的和，有。在本节所有部分，我们都假设

5、一个特定的密钥仅用于一次加密。假设在明文空间P上有一个概率分布，以表示明文发生的先验概率，还假设(Alice和Bob)以固定的概率分布选取密钥(通常密钥是随机选取的，因此所有的密钥都是等概率的，但这并不是必须的)，以表示密钥的选取概率。回忆一下密钥是在Alice知道明文之前选取的，因此我们就可以合理的假设密钥和明文相互独立的事件。P和K的概率分布诱导出密文空间C上的概率分布。事实上，不难计算出密文的概率，对于密钥K，定义也就是说C代表密钥是时所有可能的密文集合。对任意的C，我们有我们也可以看到，对于任意的C和P，可如下计算条件概

6、率（即给定明文x，密文为y的概率），计算如下：。现在可以应用Bayes定理计算条件概率(也就是给定密文，明文为的概率)，计算如下:可见，知道了概率分布的任何人都可以完成这些运算。现在，我们给出一个例子来说明具体如何计算这些概率。例2.1设满足，，设，，，设C，加密函数定义为，，，，，。这个密码体制可以用如下加密矩阵表示：122334现在我们计算如下：＝＝现在计算给定密文后，明文空间上的条件概率分布，如下：现在我们给出完善保密性的概念。非正式地，完善保密性就是说Oscar不能通过观察密文得到明文的任何信息。用概率分布的术语，精确的

7、定义如下。定义2.2如果对于任意的P和C，有，我们就称一个密码体制具有完善保密性。也就是说，给定密文，明文为的后验概率等于明文的先验概率。在例2.1中，对于密文满足完善保密性的定义，但是对于其他的密文不满足。现在证明移位密码具有完善保密性。从直觉上看这是很显然的，因为对于任意给定的密文，任何都可能是对应的明文。下面的定理用概率分布给出了正式的陈述和证明。定理2.3假设移位密码的26个密钥都是以相同的概率使用的，则对于任意的明文概率分布，移位密码具有完善保密性。证明：这里PKC，对于，加密函数定义为。首先计算C上的概率分布。设，则

8、。现在固定，值构成的一个置换。因此有，可得对于任意的，都有。接下来，对于任意的，，我们有，(这是因为对任意的，，满足的惟一的密钥为)。现在运用Bayes定理，很容易得到所以这个密码体制是完善保密的。因此，如果用一个新的随机密钥来加密每个明文字母，则移位密码是“不