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

密码学的信息论基础 本章主要内容 1、保密系统的数学模型 2、信息论与熵 3、完善保密性 C.E. Shannon （香农） 1948, A mathematical theory of communication.确立了现代信息论。 1949, Communication theory of secrecy systems.定义了密码系统的精确数学模型。 1. 保密系统的数学模型 通信系统模型 保密通信系统模型 Shannon的保密通信系统模型 Shannon的保密通信系统模型 密码学数学模型 2. 信息论与熵 (entropy) 熵（Entropy）定义为事件集X中事件出现的信息的统计平均值。 它表示X中出现一个事件平均给出的信息量，或事件的平均不确定性。 熵的含义 熵反映了集中事件出现的平均不确定性，或为确定集中出现一个事件平均所需的信息量（观测之前），或集中每出现一个事件平均给出的信息量（观测之后）。如果从编码的角度来考虑，熵也可以理解成用最优的二进制编码形式表示所需的比特数。 0*log20=0 熵的含义 采用以2为底的对数时，相应的信息单位称作比特（Bit）。?? 如果集X为均匀分布时，即， 则 。 ??，当X为确定性的事件时，即X概率分布为p(X=a)=1，则H(X)=0。 熵的实例 例1:设有一个密码系统,明文空间 的概率分布为 ；密钥空间 的概率分布为 。密文空间 ，且假定加密函数为 。可用右边的密矩阵表示： 熵的实例 按公式我们很容易计算出密文空间的概率分布及关于明文的条件分布： 1）密文空间的概率分布表如下： 2）明文关于密文的条件分布P(m/c)表如下： 熵的实例 明文空间的熵为： 类似地可计算 条件概率 在给定密文发生的条件下，某个明文发生的条件概率 条件熵 集X和Y的联合熵定义为 集相对于事件的条件熵定义为 集相对于集的条件熵定义为 含糊度、散布度 若将X视作一个系统的输入空间，Y视作是系统的输出空间。在通信中，通常将条件熵H(X|Y)称作含糊度(Equivocation)，将条件熵H(Y|X)称为散布度（Divergence）， X和Y之间的平均互信息 表示X熵减少量。 熵的基本特性 引理1 （Jensen不等式）假定f是区间I上的一个连续的严格凸函数: 那么 当且仅当 时等号成立。?? 熵的基本特性 定理1 假定X是有概率分布 的随机变量，其中 ，则 ，当 （即样本点是等概率分布）时取等号，即均匀分布下集X的不确定性最大。 熵的基本特性 定理2， ,当且仅当X和Y独立时等号成立。 定理3 。?? 推论1 ，当且仅当X和Y独立时等号成立。 各类熵之间的关系 3. 完善保密性 定理4 设 是一个密码系统。则 定义3 一个保密系统称为是完善的或无条件的保密系统，如果 或 。 定理3.5 。?? 由定理3.5知，完善保密系统存在的必要条件是 ，即 。 无条件安全 无条件安全的密码系统安全性依赖于每个密钥仅仅用在一次加密中，在每个消息被传送之前，一个新的密钥必须被产生。另外，每个消息必须与同样长度的密钥相伴，这是极其不利的，因为密钥应当在消息之前被安全传送。这些都给密钥管理带来了严重的问题。再加上一次一密系统对已知明文攻击非常脆弱。因