《密码学——加密演算法》-第4章 信息理论

《《密码学——加密演算法》-第4章 信息理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、itionalProbability令A与B为事件，且，A在条件B成立下的条件概率定义为定义两事件A与B称为独立事件（IndependentEvents）此等式也等价于若等式不成立，则称A与B为相依事件（DependentEvents）Bayes定理Bayes定理若A与B为事件，且，，则证明：由条件概率的定义，得：和因此：完美秘密4.2完美秘密定义：一个密码系统定义为完美秘密（PerfectSecrecy）所有给定密文出现的事件与所有特定明文出现的事件，皆是独立事件。对所有明文m以及所有密文c皆成立。Shannon定理令（所有密文的可能数目等于所有密钥的可能数目）且任一明文m出现的概率均为正数

3、，即。此密码系统为完美秘密下列条件皆成立：（1）在密钥空间上的概率分布函数为pK均匀分布。（2）对任一明文m以及任一密文c，均恰好仅存在一把密钥k使得熵4.3熵定义熵，Entropy令A为样本空间，X为定义在样本空间上的随机变量，则随机变量X的熵定义为定义连接熵，JointEntropy令X与Y为样本空间A与B上的随机数，则连接熵H（X，Y）定义为条件熵定义条件熵，ConditionalEntropy令X与Y为样本空间A与B上的随机数，则在条件X下的Y条件熵定义为链式规则定理链式规则，ChainRule证明：条件概率定义指数律熵性质（1），“=”成立当样本空间A的各元素出现的概率相同。（2）。

4、（3），“=”成立当X与Y为独立事件。定理令M为明文空间M的随机变量，C为密文空间C的随机变量。密码系统为完美秘密。熵定理证明：链式规则K与M为独立事件链式规则故由链式规则自然语言之熵4.4自然语言之熵定义假密钥，SpuriousKey令为含n个字元的某密文。令c，其中m为符合语法，有意义的明文}为产生密文c的假密钥的集合。定义自然语言熵，EntropyoftheNaturalLanguage令M为某自然语言的字母集合，Mn表长度为n的各种不同字母排列。该自然语言L之熵值定义为：此处熵值HL就是该自然语言的熵值；而由此M中字母所产生的随机信息熵是log2

5、M

6、，该自然语言的“重复率”（Redu

7、ndancy）可定义为：Unicity距离定义Unicity距离n0，就是该密码系统所产生密文而惟一决定惟一密钥值的密文长度。定理Unicity距离n0估计为：其中

8、K

9、表示所有可能的密钥数，而

10、M

11、表示所有的字母总数，R即重复率。Unicity距离示例例：（恺撒挪移）此时可能的密钥总数

12、K

13、=26，（含未加密）故Unicity距离为：（仿射密码）此时可能密钥总数

14、K

15、=12×26=312，（含未加密）故：例：若Alice以单次密码本加密法将长度为二元字串信息加密，传讯给Bob。其中可能密钥总数（含未加密）为

16、K

17、=2n，Eve计算例：