密码学信息论基础课件

1、密码学的信息论基础现代密码学第3章1本章主要内容1、保密系统的数学模型2、信息论与熵3、完善保密性2 C.E. Shannon （香农） 1948, A mathematical theory of communication.确立了现代信息论。 1949, Communication theory of secrecy systems.定义了密码系统的精确数学模型。31. 保密系统的数学模型通信系统模型保密通信系统模型4Shannon的保密通信系统模型Shannon的保密通信系统模型5密码学数学模型样本空间密钥空间密文空间62. 信息论与熵 (entropy) 熵（Entropy）定义为事件

2、集X中事件出现的信息的统计平均值。 它表示X中出现一个事件平均给出的信息量，或事件的平均不确定性。7熵的含义 熵反映了集中事件出现的平均不确定性，或为确定集中出现一个事件平均所需的信息量（观测之前），或集中每出现一个事件平均给出的信息量（观测之后）。如果从编码的角度来考虑，熵也可以理解成用最优的二进制编码形式表示所需的比特数。 0*log20=08熵的含义 采用以2为底的对数时，相应的信息单位称作比特（Bit）。 如果集X为均匀分布时，即， 则 。 ，当X为确定性的事件时，即X概率分布为p(X=a)=1，则H(X)=0。9熵的实例例1:设有一个密码系统,明文空间 的概率分布为 ；密钥空间 的概

3、率分布为 。密文空间 ，且假定加密函数为 。可用右边的密矩阵表示：10熵的实例 按公式我们很容易计算出密文空间的概率分布及关于明文的条件分布： 1）密文空间的概率分布表如下： 2）明文关于密文的条件分布P(m/c)表如下： 11熵的实例 明文空间的熵为： 类似地可计算12条件概率 在给定密文发生的条件下，某个明文发生的条件概率13条件熵集X和Y的联合熵定义为集相对于事件的条件熵定义为集相对于集的条件熵定义为14含糊度、散布度 若将X视作一个系统的输入空间，Y视作是系统的输出空间。在通信中，通常将条件熵H(X|Y)称作含糊度(Equivocation)，将条件熵H(Y|X)称为散布度（Diver

4、gence）， X和Y之间的平均互信息 表示X熵减少量。15熵的基本特性引理1 （Jensen不等式）假定f是区间I上的一个连续的严格凸函数: 那么 当且仅当 时等号成立。16熵的基本特性 定理1 假定X是有概率分布 的随机变量，其中 ，则 ，当 （即样本点是等概率分布）时取等号，即均匀分布下集X的不确定性最大。17熵的基本特性定理2， ,当且仅当X和Y独立时等号成立。定理3 。推论1 ，当且仅当X和Y独立时等号成立。18各类熵之间的关系193. 完善保密性定理4 设 是一个密码系统。则定义3 一个保密系统称为是完善的或无条件的保密系统，如果 或 。定理3.5 。由定理3.5知，完善保密系统存

5、在的必要条件是 ，即 。20无条件安全 无条件安全的密码系统安全性依赖于每个密钥仅仅用在一次加密中，在每个消息被传送之前，一个新的密钥必须被产生。另外，每个消息必须与同样长度的密钥相伴，这是极其不利的，因为密钥应当在消息之前被安全传送。这些都给密钥管理带来了严重的问题。再加上一次一密系统对已知明文攻击非常脆弱。因此无条件安全的保密系统是很不实用的，也具有很大的局限性，但在军事和外交上很早就使用了这种体制。 密码学的历史发展一直在试图设计一个用一个密钥就可以加密一个相当长的明文串（即一个密钥可用来加密许多消息）的密码系统，且仍能保持至少计算上安全。21理论安全性和实际安全性图 密钥，消息和密钥显

6、现含糊度作为S的函数22语言的多余度定义4 假如L是一种自然语言，语言L的熵为语言的多余度定义为 其中A表示语言L的字母集，表示A中字母的个数， 表示所有明文n字母报构成的全体。23密钥含糊度定理6 密钥含糊度有下列下界 其中，S表示接受到的密文序列长度， 表示明文语言的冗余度， 表示密文空间中符号或字母的数目。 定理7 当明文由一个离散独立信源产生，如果 ，其中 是字母表的大小。密钥的含糊度能变为零。24估计一个系统的实际保密性 理论上，当截获的密报量大于唯一解距离时，原则上就可破译。 由于自然语言的复杂性，没有任何一种分析方法能够假定分析者能利用明文语言的全部统计知识，所以，一般破译所需的

7、密文量都远大于理论值。 没有涉及为了得到唯一解需完成多少计算量。从实际破译来看，有时虽然截获的密文量远大于唯一解距离，但由于所需的工作量还太大而难以实现破译。25估计一个系统的实际保密性 理论保密性是假定密码分析者有无限的时间、设备和资金的条件下，研究唯密文攻击时密码系统的安全性。比如一次一密体制。 实际安全性又称为计算上的安全性，这个方法关心的是破译一个具体的密码系统所需的计算量。 在实际中，人们说一个密码系统是“计算上安全的”，意指利用已有的最好的方法破译该系统所需要的努力超过了敌手的破译能力（诸如时间、空间、和资金等资源）或破译该系统的难度等价于解数学上的某个已知难题26估计一个系统的实际保密性密码分析者的计算能力；他所采用的破译算法的有效性。27Shannon关于设计密码的一些基本观点 通过合并简单密码系统而形成它们的“积”挫败统计分析的观点： 在加密之前将语言的一些多余度除去。 采用所谓的“扩散（Diffusion）”和“混淆（Confus