密码学的信息论基础-Read

第3章密码学的信息论基础3.1保密系统的数学模型编码器信源信道信宿译码器干扰器图3.1通信系统模型加密器信源信道接收者解密器分析者图3.2保密系统模型密钥无噪信道安全信道密钥源加密分析者解密接收者发送者信源图3.3Shannon的保密系统模型数学模型样本空间密钥空间密文空间在给定密文发生的条件下，某个明文发生的条件概率3.2信息量和熵定义3.1

设随机变量，出现的概率为。则X的不确定性或熵（Entropy）定义为

反映了集中事件出现的平均不确定性，或为确定集中出现一个事件平均所需的信息量（观测之前），或集中每出现一个事件平均给出的信息量（观测之后）。如果从编码的角度来考虑，熵也可以理解成用最优的二进制编码形式表示所需的比特数。采用以2为底的对数时，相应的信息单位称作比特（Bit）。如果集X为均匀分布时，即，则。，当X为确定性的事件时，即X概率分布为，则。例3.1

设有一个密码系统明文空间的概率分布为； 密钥空间的概率分布为。 密文空间，且假定加密函数为 。 可用右边的加密矩阵表示： 则按公式3.1和3.2我们很容易计算出密文空间的概率分布及关于明文的条件分布：

1）密文空间的概率分布表如下：

2）明文关于密文的条件分布表如下：

明文空间的熵为： 类似地可计算c12341/87/161/43/16ab122334c\mab11021/76/731/43/4401定义3.2

设，出现的概率为。，出现的概率为，则联合事件集 ，令的概率为，此时。集X和Y的联合熵定义为集相对于事件的条件熵定义为集相对于集的条件熵定义为若将X视作一个系统的输入空间，Y视作是系统的输出空间。在通信中，通常将条件熵H(X|Y)称作含糊度(Equivocation)，将条件熵H(Y|X)称为散布度（Divergence），X和Y之间的平均互信息表示X熵减少量。熵的基本特性引理3.1（Jensen不等式）假定f是区间I

上的一个连续的严格凸函数，。那么 。 当且仅当时等号成立。定理3.1

假定X是有概率分布的随机变量，其中，则，当（即样本点是等概率分布）时取等号，即均匀分布下集X的不确定性最大。定理3.2

，当且仅当X和Y独立时等号成立。定理3.3

。推论3.1，当且仅当X和Y独立时等号成立。图3.4各类熵之间的关系3.3完善保密性定理3.4

设是一个密码系统。则。定义3.3

一个保密系统称为是完善的或无条件的保密系统，如果或。定理3.5

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

假如L是一种自然语言，语言L的熵为 语言的多余度定义为 其中A表示语言L的字母集，表示A中字母的个数，表示所有明文n－字母报构成的全体。定理3.6

密钥含糊度有下列下界 其中，S表示接受到的密文序列长度，表示明文语言的冗余度，表示密文空间中符号或字母的数目。定理3.7

当明文由一个离散独立信源产生，如果 其中是字母表的大小。 密钥的含糊度能变为零。理论上，当截获的密报量大于唯一解距离时，原则上就可破译。由于自然语言的复杂性，没有任何一种分析方法能够假定分析者能利用明文语言的全部统计知识，所以，一般破译所需的密文量都远大于理论值。没有涉及为了得到唯一解需完成多少计算量。从实际破译来看，有时虽然截获的密文量远大于唯一解距离，但由于所需的工作量还太大而难以实现破译。理论保密性是假定密码分析者有无限的时间、设备和资金的条件下，研究唯密文攻击时密码系统的安全性。比如一次一密体制。实际安全性又称为计算上的安全性，这个方法关心的是破译一个具体的密码系统所需的计算量。在实际中，人们说一个密码系统是“计算上安全的”，意指利用已有的最好的方法破译该系统所需要的努力超过了敌手的破译能力（诸如时间、空间、和资金等资源）或破译该系统的难度等价于解数学上的某个已知难题估计一个系统的实际保密性密码分析者的计算能力；他所采用的破译算法的有效性