信息保障与安全课件：第4次课-Shannon信息论.ppt

1、1第三章第三章 信息论对密码学意义信息论对密码学意义2香农简介 香农香农(1916-2001),生于生于美国美国密执安州的加洛德。密执安州的加洛德。1940年获得麻省理工学年获得麻省理工学院数学博士学位和电子院数学博士学位和电子工程硕士学位。工程硕士学位。1941年年他加入了贝尔实验室数他加入了贝尔实验室数学部，在此工作了学部，在此工作了15年。年。 3香农简介 香农在信息论的领域香农在信息论的领域中钻研了中钻研了8年之久，终于年之久，终于在在1949年在年在贝尔系统贝尔系统技术杂志技术杂志发表了发表了244页页的长篇论著的长篇论著-保密系统保密系统的通信理论的通信理论。次年，他。次年，他又在

2、同一杂志上发表了另又在同一杂志上发表了另一篇名著一篇名著-噪声下的通噪声下的通信信。4香农理论简介 第一篇文章奠定了香农信息基本理论的基础。第一篇文章奠定了香农信息基本理论的基础。他在文中用非常简洁的数学公式定义了信息时代他在文中用非常简洁的数学公式定义了信息时代的基本概念：熵。的基本概念：熵。 “熵熵”的概念起源于热力学，是度量分子不的概念起源于热力学，是度量分子不规则热运动的单位。香农的伟大贡献在于，利用规则热运动的单位。香农的伟大贡献在于，利用概率分布的理论给出概率分布的理论给出“熵熵”的严格定义。的严格定义。 根据香农的定义，确定发生的事件如根据香农的定义，确定发生的事件如“太阳太阳从

3、东边升起从东边升起”与确定不发生的事件如与确定不发生的事件如“太阳从西太阳从西边升起边升起”，其熵都是零。，其熵都是零。只有当发生与不发生只有当发生与不发生 的的概率相同时，事件的熵才达到极大。概率相同时，事件的熵才达到极大。5香农理论简介 在熵的基础上定义的在熵的基础上定义的信道容量信道容量也是通讯中一也是通讯中一个至关重要的概念。由此，香农推出了一个公式，个至关重要的概念。由此，香农推出了一个公式，明确表达了明确表达了在不同噪声情况下传输速率与失真的在不同噪声情况下传输速率与失真的定量关系定量关系。从这一个公式导出的为达到无失真通。从这一个公式导出的为达到无失真通讯的传输速讯的传输速 率的

4、极限，现已称为率的极限，现已称为香农极限香农极限。打个。打个比方来说，在周围干扰严重的情比方来说，在周围干扰严重的情 况下，要想使对况下，要想使对方听清楚，你就只有慢慢地讲，甚至还要不断重方听清楚，你就只有慢慢地讲，甚至还要不断重复。复。 6香农理论应用香农理论应用n如今，这两个原理已广泛应用于信息处理如今，这两个原理已广泛应用于信息处理和实际通信中。只要涉及信息的和实际通信中。只要涉及信息的压缩压缩与与传传递递，就要用到香农的理论。，就要用到香农的理论。 nPC机上常用的机上常用的WinZip (无损压缩算法无损压缩算法)n手机通讯手机通讯 (有损压缩有损压缩无损压缩无损压缩,纠纠 错错)n

5、在因特网上传递多媒体数据在因特网上传递多媒体数据（MP3音乐压缩格式音乐压缩格式）7第三章第三章 Shannon保密理论保密理论n 密码体制的数学模型密码体制的数学模型n 随机事件的熵及其性质随机事件的熵及其性质8通信系统信源信源编码器编码器解码器解码器接收者接收者干扰源干扰源信道信道设计目的：设计目的：在信道有干扰的情况下，使得接收者接在信道有干扰的情况下，使得接收者接 收到的信息无差错或差错尽可能的小。收到的信息无差错或差错尽可能的小。9保密系统设计目的：设计目的：使得窃听者即使完全准确地使得窃听者即使完全准确地接收带了信道上传输的信号接收带了信道上传输的信号也无法恢复出原始的信息。也无法

6、恢复出原始的信息。10密码体制的数学模型密码体制的数学模型n明文明文(离散信源离散信源)空间的统计特性：无空间的统计特性：无记忆记忆和有记和有记忆忆n密钥源通常是密钥源通常是无记忆无记忆的，并且满足的，并且满足均匀均匀分布分布n密文空间的统计特性由明文空间和密钥空间的统密文空间的统计特性由明文空间和密钥空间的统计特性决定计特性决定n假定信道无干扰，假定分析者能够截获密文，且假定信道无干扰，假定分析者能够截获密文，且知道所用的密码体制以及明文空间和密钥空间的知道所用的密码体制以及明文空间和密钥空间的统计特性统计特性113.2 随机事件的熵及其性质随机事件的熵及其性质 主要内容: 如何定量刻划一个

7、随机事件包含的信息量用熵的概念! 熵(entropy)这个数学工具自身的理论.12何为信息何为信息? 什么能提供信息什么能提供信息? 我将你原来不知道的结果告诉你,就是提供了信息! 例例1 当我给你一封信时，你就从我这里获得了信息，因为你事先并不知道其中的内容。 例例2 设电脑彩票由8个10进制数组成.在开奖之前，我们不知道特等奖号码的信息，因为特等奖的号码是不确定。特等奖号码的信息只有在开奖时才获得。一旦开奖，就获得了8个十进制数的信息。 这就是说，将未知的变成已知的时就获得了信这就是说，将未知的变成已知的时就获得了信息！息！ 信息寓于不确定之中！信息寓于不确定之中！13信息量信息量我向你提

8、供的信息量的大小就是你事先不知道结果的程度!也即是信息的不确定度。如果你事先全知道了,说明我提供的信息量等于0;如果你事先一无所知,说明我提供的信息量最多.不知道意味着在我告诉你之前你只能猜测!猜测就是按照每个可能结果的出现概率进行猜测!因此,你只知道这个事情的每个结果的发生概率!所以,我提供的信息量就是由你事先知道的每个可能结果的发生概率(即随机事件的概率分布)决定.14简单地说简单地说,信息就是信息就是: (1) 当未知的变成已知的当未知的变成已知的之后之后获取的信息获取的信息; (2) 当未知的还没变成已知当未知的还没变成已知之前之前包含的未知信息包含的未知信息.信息寓于不确定之中！信息

9、寓于不确定之中！谁的信息谁的信息! 通常的信息是指通常的信息是指: (1) 一个实验提供的信息一个实验提供的信息; (2) 一个随机事件包含的信息一个随机事件包含的信息; (3) 一个随机变量包含的信息一个随机变量包含的信息.其中其中(1)和和(2)的含义相同的含义相同,它们比它们比(3)的意义更的意义更 加广泛加广泛. 15随机事件和随机变量随机事件和随机变量定义定义1：设一个实验有设一个实验有 共共n个可能的结果，个可能的结果，则每个可能结果都称为一个事件。则每个可能结果都称为一个事件。这个实验也称这个实验也称为一个随机事件。为一个随机事件。性质性质1：设设X是一个离散随机变量，它有是一个

10、离散随机变量，它有n个可能的个可能的取值，设每种取值出现的概率为取值，设每种取值出现的概率为p(xi),则则nAAA,21niixp11)(nxxx,2116 一、随机事件的熵一、随机事件的熵 一个事件可能发生，也可能不发生！但我们总一个事件可能发生，也可能不发生！但我们总在每个事件在每个事件 发生的概率发生的概率 都已知的条件下分析！都已知的条件下分析！iA)(iAp 这个实验提供的信息就是：这个实验提供的信息就是： (1) 实验前实验前该实验所包含的未知信息；该实验所包含的未知信息； (2) 实验后实验后这个实验所提供的信息这个实验所提供的信息. 如何对信息量的大小进行定量刻划如何对信息量

11、的大小进行定量刻划? 再看一下彩票的例子再看一下彩票的例子.17例例3 设电脑彩票由设电脑彩票由8个个10进制数组成，在开奖之前，进制数组成，在开奖之前，108个可能号码成为特等奖的概率相同个可能号码成为特等奖的概率相同,都是都是10-8.一旦一旦开奖开奖,我们就知道了特等奖的我们就知道了特等奖的8个具体号码个具体号码,因而就获因而就获得了得了8个十进制数的信息。个十进制数的信息。 我们获得的信息量与开奖前每个可能号码成为我们获得的信息量与开奖前每个可能号码成为特等奖的概率特等奖的概率10-8有何关系有何关系? 显然显然,有有 8 = - log10 10-8 信息量的定量刻划信息量的定量刻划

12、: 定义定义2 设设 是一个实验中事件是一个实验中事件 发生的概率发生的概率,则称则称 为为事件事件 包含的包含的自信息量自信息量.iA)(iAp)(log)(iiApAIiA18定义定义3.1(随机事件的熵随机事件的熵):设一个实验设一个实验X有有 共共n个可能的结果个可能的结果,则称则称 的数学期的数学期望望为实验为实验X的熵的熵(Entropy). 其中约定其中约定 0log0 = 0. nxxx,21)(log)(iixpxIniiiniiixpxpxIxpXH11)(log)()()()(19因此因此,一个实验的熵就是该实验的每个可能结一个实验的熵就是该实验的每个可能结果包含的自信息

13、量的果包含的自信息量的平均值平均值!熵的单位与对数的底有关熵的单位与对数的底有关!约定对数的底大于约定对数的底大于1! 当以当以2为底时为底时,其单位称为比特其单位称为比特(bit); 当以当以e为底时为底时,其单位称为其单位称为奈奈特特(nat); 当以当以10为底时为底时,其单位称为其单位称为哈哈特特(Hart);20 例例5设一个实验有设一个实验有a和和b两个可能的结果两个可能的结果,且实验结且实验结果是果是a和和b的概率分别为的概率分别为1/4和和3/4,试计算该实验的熵试计算该实验的熵.)(log)()(log)(22bpbpapapH解解: 根据熵的定义根据熵的定义,有有301.

14、0477. 043243log4341log4122)23(log43)2(412232log3log43211010811. 0解毕解毕21 下面介绍熵的性质下面介绍熵的性质.(1) 结果确定的随机事件不提供信息量结果确定的随机事件不提供信息量, 因而提因而提供的信息量最少供的信息量最少!(2) 可能结果可能结果等可能发生等可能发生的随机事件提供的包的随机事件提供的包含的信息量最大含的信息量最大! 这与我们的直觉是一致的这与我们的直觉是一致的!22另一个角度理解另一个角度理解“熵熵”nH(X): 假设所有消息是等可能的，对消息中所有可假设所有消息是等可能的，对消息中所有可能的值进行编码所需要

15、的最少位数。能的值进行编码所需要的最少位数。n例：表示性别：例：表示性别：man、female 0 1 12log21log2121log21)(222XH比特比特23 现实中的事件都不是孤立的现实中的事件都不是孤立的! 很多随机事很多随机事件之间都有相互的联系和影响件之间都有相互的联系和影响!那么那么,如何刻划如何刻划和研究多个随机事件相互提供的信息呢和研究多个随机事件相互提供的信息呢? 这就这就要引入两个实验的要引入两个实验的联合熵联合熵条件熵条件熵 互信息互信息等概念！等概念！24 因此因此,实验实验X与实验与实验Y的联合熵的联合熵(Joint Entropy)就是事件就是事件(xi ,

16、yj )的的自信息量自信息量的数学的数学期望期望. 它反映了联合分布它反映了联合分布p(x, y )包含的信息量包含的信息量. 定义定义3.2(联合熵联合熵): 实验实验X与实验与实验Y的可能结果分的可能结果分别为别为 和和 ,定义定义X与与Y的联合熵的联合熵 为为nimjjijinimjjijiyxpyxpyxIyxpYXH1111),(log),(),(),(),(nxxx,21myyy,2125 定义定义3.3(条件熵条件熵): 实验实验X与实验与实验Y的可能结果分别的可能结果分别为为 和和 .定义定义X与与Y的条件熵为的条件熵为nxxx,21myyy,21 (1) 称称 为在为在实验实

17、验Y的结果为的结果为 yj的条件下的条件下,事件事件xi的的条件自信息量条件自信息量.)|(log)|(jijiyxpyxI为在为在实验实验Y的结果为的结果为yj的条件下的条件下,实验实验X的的条件熵条件熵.nijiinijiijyxpxpyxIxpyXH11)|(log)()|()()|( (2)称称 26(3) 称称nimjjijinimjjijiyxpyxpyxIyxpYXH1111)|(log),()|(),()|(为在为在实验实验X关于实验关于实验Y的的条件熵条件熵. 反映了反映了)|(jyXHY的结果是的结果是yj条件下条件下,实验实验X包含的信息量包含的信息量.)|(YXH反映了

18、反映了Y的结果已知条件下的结果已知条件下,实验实验X平均平均包含的信息量包含的信息量.27联合熵与各自的熵的关系联合熵与各自的熵的关系 定理定理3.2)()(),(YHXHYXH且等号成立的且等号成立的充要条件是充要条件是X与与Y独立独立. 两个实验提供的信息总量一定不超过这两两个实验提供的信息总量一定不超过这两个实验分别提供的信息量之和个实验分别提供的信息量之和;当且仅当两个实当且仅当两个实验独立时验独立时,二者才相等二者才相等.直观含义直观含义:28联合熵与条件熵的关系联合熵与条件熵的关系 定理定理3.3)|()()|()(),(XYHXHYXHYHYXH直观含义直观含义: 两个实验提供的

19、信息总量等于第一个信两个实验提供的信息总量等于第一个信息提供的信息量加上在第一个实验的结果已息提供的信息量加上在第一个实验的结果已知条件下知条件下,第二个第二个实验实验提供的信息量提供的信息量.29联合熵与熵的关系联合熵与熵的关系)()|(XHYXH故有故有 定理定理3.2指出指出:)()(),(YHXHYXH 定理定理3.3指出指出:)|()(),(YXHYHYXH)()()|()(XHYHYXHYH 推论推论3.1)()|(XHYXH且等号成立且等号成立X与与Y独立独立.30 定义定义3.3(平均互信息平均互信息): 称称),()()();(YXHYHXHYXI为实验为实验X与实验与实验Y

20、的平均互信息的平均互信息. 结论结论:)|()()|()();(XYHYHYXHXHYXI 直观的含义：直观的含义：将将X包含的未知信息量减去在实验包含的未知信息量减去在实验Y的的结果已知条件下结果已知条件下,X仍具有的未知信息量仍具有的未知信息量.就是实验就是实验Y提供的提供的X的信息了的信息了.31例：密码体制例：密码体制 M=a,b，p(a)=1/4，p(b)=3/4 K=k1,k2,k3，p(k1)=1/2，p(k2)=p(k3)=1/4 C=1,2,3,4abk1 12k2 23k3 34计算：明文熵、密文熵、密钥熵。计算：明文熵、密文熵、密钥熵。解：解：8141*21) 1 (p1

21、6741*4121*43)2(p4141*4141*43) 3(p16341*43)4(p明文熵：明文熵：811. 043log4341log41)(22MH5 . 1)(KH85. 1)(CH密钥熵：密钥熵：密文熵：密文熵：32对给定的对给定的Y，X的条件熵的条件熵nimjjijiyxpyxpYXH11)|(log),()|(称为疑义度称为疑义度1）给定）给定C，K的疑义度：的疑义度：2）给定）给定C，M的疑义度：的疑义度：)|(log)|()()|(2jijijijckpckpcpCKH)|(log)|()()|(2jijijijcmpcmpcpCMH密码分析时，从密文中提取有关明文的信息

22、，即：密码分析时，从密文中提取有关明文的信息，即：)|()();(CMHMHCMI从密文中提取有关密钥的信息，即：从密文中提取有关密钥的信息，即：)|()();(CKHKHCKI H(M|C)、H(K|C)越大，窃听者从密文能提取的有关明文越大，窃听者从密文能提取的有关明文和密钥的信息就越小。和密钥的信息就越小。33对于合法的接收者：对于合法的接收者： H(M|CK)=0 即即 I(M;CK)=H(M) H(M|CK)=H(M)又又设设： ： H(K|C)=H(K|C)+H(M|CK) =H(KC)-H(C)+H(MCK)-H(CK) =H(MCK)-H(C) =H(MK|C) =H(M|C)

23、+H(K|CM) H(M|C) 说说明：明： 已知密文后，密已知密文后，密钥钥的疑的疑义义度度总总大于等于明文的疑大于等于明文的疑义义度。度。可能可能满满足足c=Ek(m)的的k不止一个，但用同一个不止一个，但用同一个k对对不同的不同的m加密得到相同的加密得到相同的c， ，较难较难。 。H(XY)=H(Y)+H(X|Y) =H(X)+H(Y|X)34又因又因为为 H(K) H(K|C) H(M|C)那么从那么从C中中获获得得M的信息的信息为为： ： I(M;C)=H(M)-H(M|C) H(M)-H(C)说说明：明： 若若k的数量少，的数量少，则则H(K)小，小，则则密文中含有关明文的信密文中含有关明文的信息量息量I(M;C)大。所以大。所以k不能太少，且不能太少，且应应概率均匀。概率均匀。