《密码学——加密演算法》-第4章-信息理论概要课件.ppt

返回总目录返回总目录返回总目录返回总目录 第第4章章信息理论信息理论1.2 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论教学目的教学目的回忆概率的基本概念和定理回忆概率的基本概念和定理回忆概率的基本概念和定理回忆概率的基本概念和定理了解什么是完美秘密？了解什么是完美秘密？了解什么是完美秘密？了解什么是完美秘密？了解熵了解熵了解熵了解熵了解自然之熵了解自然之熵了解自然之熵了解自然之熵1.3 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论 概率概率本章内容本章内容本章内容本章内容 完美秘密完美秘密 熵熵 自然之熵自然之熵1.4 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论概率概率4.1 概率定义令令S S为一非空的有限集合，称为为一非空的有限集合，称为样本空间样本空间（Sample Sample SpaceSpace），其部分集合称为），其部分集合称为事件事件（EventsEvents）。在样本空）。在样本空间上的概率分布（间上的概率分布（Probability DistributionProbability Distribution）即用一个函）即用一个函数数p p将事件映至某实数，将事件映至某实数，（其中（其中 表表S S的幂集合，即的幂集合，即 ）满足下列各条件：）满足下列各条件：（1 1）对所有的事件对所有的事件 （2 2）（3 3）当两事件与互斥（即当两事件与互斥（即 ）若若A A为事件，则为事件，则p(Ap(A)为此事件的概率。为此事件的概率。1.5 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论概率的性质概率的性质 性质（1 1）（2 2）若）若 则则（3 3）当）当 （4 4）（5 5）若）若 均两两相斥，则均两两相斥，则（6 6）其中其中1.6 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论条件概率和独立事件条件概率和独立事件 定义条件概率，条件概率，Conditional Probability Conditional Probability 令令A A与与B B为事件，且为事件，且 ，A A在条件在条件B B成立下的条件概率成立下的条件概率定义为定义为 定义两事件两事件A A与与B B称为称为独立事件独立事件（Independent EventsIndependent Events）此等式也等价于此等式也等价于 若等式不成立，则称若等式不成立，则称A A与与B B为为相依事件相依事件（Dependent EventsDependent Events）1.7 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论BayesBayes定理定理 Bayes定理若若A A与与B B为事件，且为事件，且 ，则，则 证明：证明：由条件概率的定义，得：由条件概率的定义，得：和和因此：因此：1.8 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论完美秘密完美秘密4.2 完美秘密定义：一个密码系统定义为一个密码系统定义为完美秘密完美秘密（Perfect SecrecyPerfect Secrecy）所有给定密文出现的事件与所有特定明文出现的事件，皆是独立事件。所有给定密文出现的事件与所有特定明文出现的事件，皆是独立事件。对所有明文对所有明文mm以及所有密文以及所有密文c c皆成立。皆成立。Shannon定理令令 （所有密文的可能数目等于所有密钥的可能数目）且任一明（所有密文的可能数目等于所有密钥的可能数目）且任一明文文mm出现的概率均为正数，即出现的概率均为正数，即 。此密码系统为完美秘密。此密码系统为完美秘密 下列下列条件皆成立：条件皆成立：（1 1）在密钥空间上的概率分布函数为）在密钥空间上的概率分布函数为p pK K均匀分布。均匀分布。（2 2）对任一明文）对任一明文mm以及任一密文以及任一密文c c，均恰好仅存在一把密钥，均恰好仅存在一把密钥k k使得使得1.9 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论熵熵4.3 熵 定义熵，熵，Entropy Entropy 令令A A为样本空间，为样本空间，X X为定义在样本空间上的随机变量，则随为定义在样本空间上的随机变量，则随机变量机变量X X的熵定义为的熵定义为 定义连接熵，连接熵，Joint Entropy Joint Entropy 令令X X与与Y Y为样本空间为样本空间A A与与B B上的随机数，则连接熵上的随机数，则连接熵H H（X X，Y Y）定义为定义为1.10 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论条件熵条件熵 定义 条件熵，条件熵，Conditional Entropy Conditional Entropy 令令X X与与Y Y为样本空间为样本空间A A与与B B上的随机数，则在条件上的随机数，则在条件X X下的下的Y Y条件条件熵定义为熵定义为1.11 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论链式规则链式规则 定理链式规则，链式规则，Chain Rule Chain Rule 证明：证明：条件概率定义条件概率定义指数律指数律1.12 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论熵熵 性质（1 1），“=”=”成立当样本空间成立当样本空间A A的各元素出现的概的各元素出现的概率相同。率相同。（2 2）。（3 3），“=”=”成立当成立当X X与与Y Y为独立事件为独立事件。定理 令令MM为明文空间为明文空间MM的随机变量，的随机变量，C C为密文空间为密文空间C C的随机变量。的随机变量。密码系统为完美秘密。密码系统为完美秘密。1.13 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论熵熵 定理证明：证明：链式规则链式规则K K与与MM为独立事件为独立事件 链式规则链式规则故由链式规则故由链式规则1.14 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论自然语言之熵自然语言之熵4.4 自然语言之熵定义 假密钥，假密钥，Spurious Key Spurious Key 令令 为含为含n n个字元的某密文。令个字元的某密文。令 c c，其中，其中mm为符合语法，有意义的明文为符合语法，有意义的明文 为产生密文为产生密文c c的的假密钥的集合假密钥的集合。定义 自然语言熵，自然语言熵，Entropy of the Natural Language Entropy of the Natural Language 令令MM为某自然语言的字母集合，为某自然语言的字母集合，MMn n表长度为表长度为n n的各种不同字的各种不同字母排列。该自然语言母排列。该自然语言L L之熵值定义为：之熵值定义为：此处熵值此处熵值H HL L就是该自然语言的熵值；而由此就是该自然语言的熵值；而由此MM中字母所产中字母所产生的生的随机信息熵随机信息熵是是loglog2 2|M|M|，该自然语言的，该自然语言的“重复率重复率”（RedundancyRedundancy）可定义为：）可定义为：1.15 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论UnicityUnicity距离距离 定义UnicityUnicity距离距离n n0 0，就是该密码系统所产生密文而惟一决定惟一，就是该密码系统所产生密文而惟一决定惟一密钥值的密文长度。密钥值的密文长度。定理Unicity距离n0估计为：其中其中|K|K|表示所有可能的密钥数，而表示所有可能的密钥数，而|M|M|表示所有的字母总数，表示所有的字母总数，R R即重复率。即重复率。1.16 2006第第第第4 4章章章章 信息理论信息理论信息理论信息理论UnicityUnicity距离示例距离示例例：（恺撒挪移）此时可能的密钥总数（恺撒挪移）此时可能的密钥总数|K|=26|K|=26，（含未加密），（含未加密）故故UnicityUnicity距离为距离为 ：（仿射密码）此时可能密钥总数（仿射密码）此时可能密钥总数|K|=1226=312|K|=1226=312，（含未加，（含未加密）故密）故 ：例：若若AliceAlice以以单次密码本单次密码本加密法将长度为二元字串信息加密，加密法将长度为二元字串信息加密，传讯给传讯给BobBob。其中可能密钥总数（含未加密）为。其中可能密钥总数（含未加密）为|K|=2|K|=2n n，EveEve计算计算 例：