第4次课--Shannon信息论

1第三章信息论对密码学意义现代密码学2香农简介香农(1916-2001),生于美国密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。现代密码学3香农简介香农在信息论的领域中钻研了8年之久，终于在1949年在《贝尔系统技术杂志》发表了244页的长篇论著---《保密系统的通信理论》。次年，他又在同一杂志上发表了另一篇名著---《噪声下的通信》。现代密码学4香农理论简介第一篇文章奠定了香农信息基本理论的基础。他在文中用非常简洁的数学公式定义了信息时代的基本概念：熵。“熵”的概念起源于热力学，是度量分子不规则热运动的单位。香农的伟大贡献在于，利用概率分布的理论给出“熵”的严格定义。根据香农的定义，确定发生的事件如“太阳从东边升起”与确定不发生的事件如“太阳从西边升起”，其熵都是零。只有当发生与不发生的概率相同时，事件的熵才达到极大。现代密码学5香农理论简介在熵的基础上定义的信道容量也是通讯中一个至关重要的概念。由此，香农推出了一个公式，明确表达了在不同噪声情况下传输速率与失真的定量关系。从这一个公式导出的为达到无失真通讯的传输速率的极限，现已称为香农极限。打个比方来说，在周围干扰严重的情况下，要想使对方听清楚，你就只有慢慢地讲，甚至还要不断重复。现代密码学6香农理论应用如今，这两个原理已广泛应用于信息处理和实际通信中。只要涉及信息的压缩与传递，就要用到香农的理论。PC机上常用的WinZip(无损压缩算法)手机通讯(有损压缩无损压缩,纠错)在因特网上传递多媒体数据（MP3音乐压缩格式）现代密码学7第三章Shannon保密理论密码体制的数学模型随机事件的熵及其性质现代密码学8通信系统信源编码器解码器接收者干扰源信道设计目的：在信道有干扰的情况下，使得接收者接收到的信息无差错或差错尽可能的小。现代密码学9保密系统设计目的：使得窃听者即使完全准确地接收带了信道上传输的信号也无法恢复出原始的信息。现代密码学10密码体制的数学模型明文(离散信源)空间的统计特性：无记忆和有记忆密钥源通常是无记忆的，并且满足均匀分布密文空间的统计特性由明文空间和密钥空间的统计特性决定假定信道无干扰，假定分析者能够截获密文，且知道所用的密码体制以及明文空间和密钥空间的统计特性现代密码学11§3.2随机事件的熵及其性质主要内容:•如何定量刻划一个随机事件包含的信息量用熵的概念!•熵(entropy)这个数学工具自身的理论.现代密码学12何为信息?什么能提供信息?•我将你原来不知道的结果告诉你,就是提供了信息!例1当我给你一封信时，你就从我这里获得了信息，因为你事先并不知道其中的内容。例2设电脑彩票由8个10进制数组成.在开奖之前，我们不知道特等奖号码的信息，因为特等奖的号码是不确定。特等奖号码的信息只有在开奖时才获得。一旦开奖，就获得了8个十进制数的信息。这就是说，将未知的变成已知的时就获得了信息！信息寓于不确定之中！现代密码学13信息量•我向你提供的信息量的大小就是你事先不知道结果的程度!也即是信息的不确定度。•如果你事先全知道了,说明我提供的信息量等于0;•如果你事先一无所知,说明我提供的信息量最多.•不知道意味着在我告诉你之前你只能猜测!•猜测就是按照每个可能结果的出现概率进行猜测!•因此,你只知道这个事情的每个结果的发生概率!•所以,我提供的信息量就是由你事先知道的每个可能结果的发生概率(即随机事件的概率分布)决定.现代密码学14简单地说,信息就是:(1)当未知的变成已知的之后获取的信息;(2)当未知的还没变成已知之前包含的未知信息.信息寓于不确定之中！谁的信息!通常的信息是指:(1)一个实验提供的信息;(2)一个随机事件包含的信息;(3)一个随机变量包含的信息.其中(1)和(2)的含义相同,它们比(3)的意义更加广泛.现代密码学15随机事件和随机变量定义1：设一个实验有共n个可能的结果，则每个可能结果都称为一个事件。这个实验也称为一个随机事件。性质1：设X是一个离散随机变量，它有n个可能的取值，设每种取值出现的概率为p(xi),则nAAA,,,21niixp11)(nxxx,,,21现代密码学16一、随机事件的熵一个事件可能发生，也可能不发生！但我们总在每个事件发生的概率都已知的条件下分析！iA)(iAp这个实验提供的信息就是：(1)实验前该实验所包含的未知信息；(2)实验后这个实验所提供的信息.如何对信息量的大小进行定量刻划?再看一下彩票的例子.现代密码学17例3设电脑彩票由8个10进制数组成，在开奖之前，108个可能号码成为特等奖的概率相同,都是10-8.一旦开奖,我们就知道了特等奖的8个具体号码,因而就获得了8个十进制数的信息。我们获得的信息量与开奖前每个可能号码成为特等奖的概率10-8有何关系?显然,有8=-log1010-8信息量的定量刻划:定义2设是一个实验中事件发生的概率,则称为事件包含的自信息量.iA)(iAp)(log)(iiApAIiA现代密码学18熵的数学定义定义3.1(随机事件的熵):设一个实验X有共n个可能的结果,则称的数学期望为实验X的熵(Entropy).其中约定0log0=0.nxxx,,,21)(log)(iixpxIniiiniiixpxpxIxpXH11)(log)()()()(现代密码学19因此,一个实验的熵就是该实验的每个可能结果包含的自信息量的平均值!熵的单位与对数的底有关!约定对数的底大于1!当以2为底时,其单位称为比特(bit);当以e为底时,其单位称为奈特(nat);当以10为底时,其单位称为哈特(Hart);现代密码学20例5设一个实验有a和b两个可能的结果,且实验结果是a和b的概率分别为1/4和3/4,试计算该实验的熵.)](log)()(log)([22bpbpapapH解:根据熵的定义,有301.0477.0432]43log4341log41[22)]23(log43)2(41[2232log3log43211010811.0解毕现代密码学21下面介绍熵的性质.(1)结果确定的随机事件不提供信息量,因而提供的信息量最少!(2)可能结果等可能发生的随机事件提供的包含的信息量最大!这与我们的直觉是一致的!现代密码学22另一个角度理解“熵”H(X):假设所有消息是等可能的，对消息中所有可能的值进行编码所需要的最少位数。例：表示性别：man、female0112log21log2121log21)(222XH比特现代密码学23现实中的事件都不是孤立的!很多随机事件之间都有相互的联系和影响!那么,如何刻划和研究多个随机事件相互提供的信息呢?这就要引入两个实验的联合熵条件熵互信息等概念！现代密码学24因此,实验X与实验Y的联合熵(JointEntropy)就是事件(xi,yj)的自信息量的数学期望.它反映了联合分布p(x,y)包含的信息量.定义3.2(联合熵):实验X与实验Y的可能结果分别为和,定义X与Y的联合熵为nimjjijinimjjijiyxpyxpyxIyxpYXH1111),(log),(),(),(),(nxxx,,,21myyy,,,21现代密码学25定义3.3(条件熵):实验X与实验Y的可能结果分别为和.定义X与Y的条件熵为nxxx,,,21myyy,,,21(1)称为在实验Y的结果为yj的条件下,事件xi的条件自信息量.)|(log)|(jijiyxpyxI为在实验Y的结果为yj的条件下,实验X的条件熵.nijiinijiijyxpxpyxIxpyXH11)|(log)()|()()|((2)称现代密码学26(3)称nimjjijinimjjijiyxpyxpyxIyxpYXH1111)|(log),()|(),()|(为在实验X关于实验Y的条件熵.反映了)|(jyXHY的结果是yj条件下,实验X包含的信息量.)|(YXH反映了Y的结果已知条件下,实验X平均包含的信息量.现代密码学27联合熵与各自的熵的关系定理3.2)()(),(YHXHYXH且等号成立的充要条件是X与Y独立.两个实验提供的信息总量一定不超过这两个实验分别提供的信息量之和;当且仅当两个实验独立时,二者才相等.直观含义:现代密码学28联合熵与条件熵的关系定理3.3)|()()|()(),(XYHXHYXHYHYXH直观含义:两个实验提供的信息总量等于第一个信息提供的信息量加上在第一个实验的结果已知条件下,第二个实验提供的信息量.现代密码学29联合熵与熵的关系)()|(XHYXH故有定理3.2指出:)()(),(YHXHYXH定理3.3指出:)|()(),(YXHYHYXH)()()|()(XHYHYXHYH推论3.1)()|(XHYXH且等号成立X与Y独立.现代密码学30定义3.3(平均互信息):称),()()();(YXHYHXHYXI为实验X与实验Y的平均互信息.结论:)|()()|()();(XYHYHYXHXHYXI直观的含义：将X包含的未知信息量减去在实验Y的结果已知条件下,X仍具有的未知信息量.就是实验Y提供的X的信息了.现代密码学31例：密码体制M={a,b}，p(a)=1/4，p(b)=3/4K={k1,k2,k3}，p(k1)=1/2，p(k2)=p(k3)=1/4C={1,2,3,4}abk112k223k334计算：明文熵、密文熵、密钥熵。解：8141*21)1(p16741*4121*43)2(p4141*4141*43)3(p16341*43)4(p明文熵：811.043log4341log41)(22MH5.1)(KH85.1)(CH密钥熵：密文熵：现代密码学32对给定的Y，X的条件熵nimjjijiyxpyxpYXH11)|(log),()|(称为疑义度1）给定C，K的疑义度：2）给定C，M的疑义度：)|(log)|()()|(2jijijijckpckpcpCKH)|(log)|()()|(2jijijijcmpcmpcpCMH密码分析时，从密文中提取有关明文的信息，即：)|()();(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)+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不能太少，且应概率均匀。