现代密码学第3章：密码学的信息论基础

1、1密码学的信息论基础密码学的信息论基础现代密码学现代密码学第第3章章2本章主要内容本章主要内容n1 1、保密系统的数学模型、保密系统的数学模型n2 2、信息论与熵、信息论与熵n3 3、完善保密性、完善保密性3 C.E. Shannon （香农） 1948, A mathematical theory of communication.确立了现代信息论。 1949, Communication theory of secrecy systems.定义了密码系统的精确数学模型。41. 保密系统的数学模型保密系统的数学模型n通信系统模型n保密通信系统模型5Shannon的保密通信系统模型的保密通信系

2、统模型nShannon的保密通信系统模型6密码学数学模型密码学数学模型样本空间样本空间密钥空间密钥空间密文空间密文空间72. 信息论与熵信息论与熵 (entropy)n 熵（熵（Entropy）定义为事件集）定义为事件集X中事件出中事件出现的信息的统计平均值。现的信息的统计平均值。 它表示它表示X中出现一个事件平均给出的信中出现一个事件平均给出的信息量，或事件的平均不确定性。息量，或事件的平均不确定性。0 )(1log)()(iiaixpxpXH8熵的含义熵的含义n 熵反映了集中事件出现的平均不确定性，或为确定集中出现一个事件平均所需的信息量（观测之前），或集中每出现一个事件平均给出的信息量（

3、观测之后）。如果从编码的角度来考虑，熵也可以理解成用最优的二进制编码形式表示所需的比特数。 0*log20=09熵的含义熵的含义n 采用以2为底的对数时，相应的信息单位称作比特（Bit）。n 如果集X为均匀分布时，即， 则 。n ，X为确定性的事件时，即X概率分布为p(X=a)=1，则H(X)=0。10熵的实例熵的实例n例1:设有一个密码系统,明文空间 的概率分布为 ；密钥空间 的概率分布为 。密文空间 ，且假定加密函数为 。可用右边的密矩阵表示：11熵的实例熵的实例n 按公式我们很容易计算出密文空间的概率分布及关于明文的条件分布： 1）密文空间的概率分布表如下： 2）明文关于密文的条件分布P

4、(m/c)表如下： 12熵的实例熵的实例 明文空间的熵为： 类似地可计算13条件概率条件概率n 在给定密文发生的条件下，某个明文发生的条件概率14条件熵条件熵n集X和Y的联合熵定义为n集相对于事件的条件熵定义为n集相对于集的条件熵定义为15含糊度、散布度含糊度、散布度n 若将X视作一个系统的输入空间，Y视作是系统的输出空间。在通信中，通常将条件熵H(X|Y)称作含糊度(Equivocation)，将条件熵H(Y|X)称为散布度（Divergence）， X和Y之间的平均互信息 表示X熵减少量。16熵的基本特性熵的基本特性n引理1 （Jensen不等式）假定f是区间I上的一个连续的严格凸函数:

5、那么 ，且仅， 时等号成立。17熵的基本特性熵的基本特性 定理1 假定X是有概率分布 的随机变量，其中 ，则 ， （即样本点是等概率分布）时取等号，即均匀分布下集X的不确定性最大。ni1 ,n1pi18熵的基本特性熵的基本特性n定理2， ,，且仅，X和Y独立时等号成立。n定理3 。n推论1 ，且仅，X和Y独立时等号成立。19各类熵之间的关系各类熵之间的关系203. 完善保密性完善保密性n定理4 设 是一个密码系统。则n定义3 一个保密系统称为是完善的或无条件的保密系统，如果 或 。n定理3.5 。n由定理3.5知，完善保密系统存在的必要条件是 ，即 。21无条件安全无条件安全n 无条件安全的密

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

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

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