第2章 喷鼻农实际.docVIP

第2章 香农理论 1949年，克劳德·香农（Claude Shannon）在《Bell Systems Technical journal》上发表了一篇题为“Communication Theory of Secrecy System”（必威体育官网网址系统的通讯理论）的论文，这篇论文对密码学的研究产生了重大影响。本章我们将讨论部分香农的思想。 2.1 完善必威体育官网网址性 首先介绍两种评价密码系统安全性的基本方法。 计算安全性 这种度量只关心攻破一个密码系统在计算上所做的努力。如果用最好的算法攻破一个密码系统也至少需要次操作，其中是一个非常大的特定数字，我们就可以称这个密码系统是计算安全的。问题在于，在这个定义下，没有一个已知的密码系统能够被证明是安全的。在实际应用中，如果攻击一种密码系统的已知最好的方法也需要非常长的计算机时间，人们就称该密码系统是“计算安全的”(当然，这与安全性的证明有很大区别)。另一种方法是将密码系统的安全性归结为一些研究较为成熟的被认为是不难解的问题，以此提供计算安全性的证据。比如，人们可以证明这样一个论断：如果给定的整数不能被分解，则一个给定的密码系统就是安全的。这种类型的密码系统有时被称为“可证明安全的”，但必须理解，它只是证明了安全性是和另一个问题相关，并没有完全证明是安全的。 无条件安全性 这种度量考虑的是对攻击者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，加密函数定义为，，，，，。这个密码体制可以用如下加密矩阵表示： 1 2 2 3 3 4 现在我们计算如下： ＝ ＝ 现在计算给定密文后，明文空间上的条件概率分布，如下： 现在我们给出完善必威体育官网网址性的概念。非正式地，完善必威体育官网网址性就是说Oscar不能通过观察密文得到明文的任何信息。用概率分布的术语，精确的定义如下。 定义2.2 如果对于任意的P和C，有，我们就称一个密码体制具有完善必威体育官网网址性。也就是说，给定密文，明文为的后验概率等于明文的先验概率