信息理论《密码学：加密演算法》

1、 返回总目录 第4章信息理论教学目的回忆概率的基本概念和定理了解什么是完美秘密？了解熵了解自然之熵 概率本章内容 完美秘密 熵 自然之熵概率4.1 概率定义令S为一非空的有限集合，称为样本空间（Sample Space），其部分集合称为事件（Events）。在样本空间上的概率分布（Probability Distribution）即用一个函数p将事件映至某实数， （其中 表S的幂集合，即 ）满足下列各条件：（1） 对所有的事件 （2）（3） 当两事件与互斥（即 ）若A为事件，则p(A)为此事件的概率。 概率的性质 性质（1）（2）若 则（3）当 （4）（5）若 均两两相斥，则（6）其中条件概率

2、和独立事件 定义条件概率，Conditional Probability 令A与B为事件，且 ，A在条件B成立下的条件概率定义为 定义两事件A与B称为独立事件（Independent Events） 此等式也等价于 若等式不成立，则称A与B为相依事件（Dependent Events） Bayes定理 Bayes定理若A与B为事件，且 ， ，则 证明：由条件概率的定义，得： 和因此：完美秘密4.2 完美秘密定义：一个密码系统定义为完美秘密（Perfect Secrecy） 所有给定密文出现的事件与所有特定明文出现的事件，皆是独立事件。 对所有明文m以及所有密文c皆成立。 Shannon定理令

3、（所有密文的可能数目等于所有密钥的可能数目）且任一明文m出现的概率均为正数，即 。此密码系统为完美秘密 下列条件皆成立： （1）在密钥空间上的概率分布函数为pK均匀分布。（2）对任一明文m以及任一密文c，均恰好仅存在一把密钥k使得熵4.3 熵 定义熵，Entropy 令A为样本空间，X为定义在样本空间上的随机变量，则随机变量X的熵定义为 定义连接熵，Joint Entropy 令X与Y为样本空间A与B上的随机数，则连接熵H（X，Y）定义为条件熵 定义 条件熵，Conditional Entropy 令X与Y为样本空间A与B上的随机数，则在条件X下的Y条件熵定义为链式规则 定理链式规则，Chai

4、n Rule 证明：条件概率定义指数律熵 性质（1） ，“=”成立当样本空间A的各元素出现的概率相同。（2） 。（3） ，“=”成立当X与Y为独立事件。 定理 令M为明文空间M的随机变量，C为密文空间C的随机变量。密码系统为完美秘密。 熵 定理证明：链式规则K与M为独立事件 链式规则故由链式规则自然语言之熵4.4 自然语言之熵定义 假密钥，Spurious Key 令 为含n个字元的某密文。令 c，其中m为符合语法，有意义的明文为产生密文c的假密钥的集合。定义 自然语言熵，Entropy of the Natural Language 令M为某自然语言的字母集合，Mn表长度为n的各种不同字母排列。该自然语言L之熵值定义为：此处熵值HL就是该自然语言的熵值；而由此M中字母所产生的随机信息熵是log2|M|，该自然语言的“重复率”（Redundancy）可定义为：Unicity距离 定义Unicity距离n0，就是该密码系统所产生密文而惟一决定惟一密钥值的密文长度。 定理Unicity距离n0估计为：其中|K|表示所有可能的密钥数，而|M|表示所有的字母总数，R即重复率。Unicity距离示例例：（恺撒挪移）此时可能的密钥总数|K|=26，（含未加密）故Unicity距离为 ：（仿射密码）此时可能密钥总数|K|=1226=312