第5章-信息论与保密学

150第5章信息论与保密学前面的研究，都是关于信息传输的可靠性和有效性，用信道编码来提高通信的可靠性，用信源编码来提高通信的有效性，从而使得信息传输既可靠又有效。信源在可靠而又有效地向信宿（合法的接收者）传输信息的同时，也要防止截取者（非法接收者）窃取到信源信息，通常有两种可能的方法、（1）使截取者根本无法接触到信源消息，信源和信宿间采用专门的保密有线信道，例如光纤等。或者是定向性极强的无线信道，例如红外或激光无线定向通信等。这种方法总的来讲需要建立专用信道，因而仅适用于国家的安全或军事部门，而不适用于公共用户。这种方法这里不讨论。（2）先将信源信息或者说明文，用加密的方法（通过加密编码）变成截取者无法理解（或破译）的密文，再通过公用信道（公用电话，电报网，Internet网，无线公用网等）传输给信宿，截取者虽然容易获得密文，但由于没有解密必须的密钥，因而仍不能获得明文，等于没有获得关于信源的任何有效信息。而合法接收者（信宿），由于拥有解密必须的密钥，可以用密钥从密文中解出明文，从而获得信源信息。随着人类进入信息时代，除传统的有线电话迅速普及外，移动通信，国际公共互联网（Internet）也获得了快速发展和普遍使用。以互联网为基础的电子商务和电子支付系统应用也日渐广泛，人们可以通过互联网互相通信，聊天，查询资料，获取资料，了解世界政局的动荡以及最近新闻。也可以通过互联网进修提高，观摩电影电视，阅读网上书刊，甚至和远在数千公里外的陌生人下棋打牌。还可以通过互联网购物消费，转帐，订货订票，电子支付结帐等。可以说互联网已经深入到国民经济、国防建设、个人生活中，成为社会生活不可分割的一部分。而信息安全和保密问题也变得越来越重要，因为这关系到系统的安全，国家的安全，企业的安全，商务机密和个人的隐私等。人们对保密法的研究由来已久，但由于保密学往往与国家安全和军事机密联系紧密，因而很长一段时间内保密学成为公开研究的禁区，直到1976年Diffe和Hellman发表了“密码学的新方向”科学论文，提出了一种全新的密码类型—公开密钥密码体系，以及稍后美国国家标准局正式发布数据加密标准，公开了加密算法，并在商业数据加密方面得到了普遍应用后，保密学才得到了广泛研究和飞速发展，出现了许多切实可用的保密技术。山农在“保密通信的信息理论”一文中首先提出了通信的保密系统的数学模型，并首先用信息论的观点对通信保密问题进行了理论分析，从而使信息论成为研究加密、解密等保密学重要研究课题的理论基础。本章仅简单介绍信息论在保密学中的基本应用，有关现代密码系统的分析设计方法，请参阅有关文献。1515.1保密系统的数学模型保密系统的数学模型如图5.1.1所示。图5.1.1保密系统的数学模型保密系统通过用密钥对信源明文S的加密编码，变成密文C后，通过公开信道向信宿传输信息，由于信宿是合法接收者，因此拥有由保密信道得到的密钥，于是就可以用密钥，通过解密译码器由密文C解出明文S，从而完成了保密通信。而截取者虽然可以由公开信道获得密文C，但由于没有密钥，所以在密码系统设计优良的情况下，就难以甚至实际上不可能由密文解出明文。现在来分析图5.1.1中各部分的作用。信源是产生明文S的源，现在设信源是简单的离散无记忆信源。12112,,,1(),,,,qqiiqSSSSppSppp===éùéùêúêúëûëûåLLLL信源S共有12,,,qSSSLL共q个符号，L个符号看成是一个信源（消息）序列，因而共有Lq个不同的信源序列，称LS为明文空间，可以看成是S的L次扩展信源。密钥源是产生用于加密和解密序列的源，密钥一般总是离散的，设密钥的符号集为：{}()()12,tii=1,,0,b1tiBbbbPbp=³=åLLr个符号看成一个密钥源序列，因而共有rt个不同的密钥序列，称rB为密钥空间，可以看成是B的r次扩展密钥源。密钥空间与明文空间一般应互相统计独立，信宿（合法接收者）知道密钥空间，而截取者却不知道。加密编码器对明文S进行加密变换（加密编码），在密钥的控制下，将其变成密文C，即：()BCES=152上式中，BE表示在B的控制下进行加密变换，一般，密文符号集应与明文符号集相同，故密文空间的符号也为q个，其n次扩展密文空间为nC，而且nL=，即密文序列的长度（符号数）与明文序列的长度（符号数）相同。为了分析简单，密码系统的信道总是假定为无干扰的，如果实际信道有干扰，可以先引入信道编码和信道译码，使信道成为无干扰信道，然后进行分析。解密译码器对接收到的密文进行解密变换（解密译码），因为信宿知道密钥和解密变换D，因而可以借助于解密译码器从密文中解出明文，即：()()()BBBSDCDES==截取者可以获得密文，但由于没有特定的密钥，所以即使知道加密算法，也无法从密文中解出明文，可见密钥是非常重要的。信源应通过保密信道传递密钥，并确保密钥不至外泄。另一方面，也不能让任何截取者从密文中归纳出密钥来。密码系统的性能用其保密性来衡量，共有两种衡量标准，一种称为理论保密性，是指在截取者具有无限的时间和计算能力条件下密码系统的抗破译能力。另一种称为实际保密性，是指在截取者仅具有有限时间和计算能力，或者某种限制条件下，密码系统的抗破译能力。一个安全而又实用的密码系统应满足：（1）系统即使达不到理论上绝对不可破，也应保证实际上不可破。（2）系统的保密性应不依赖于对加密、解密算法的保密，而应仅依赖于密钥。（3）加密、解密算法不应过于复杂，最好简便易行。（4）加密和解密算法适用于所有密钥空间的元素。5.2古典密码体制如前所述，密码由来已久，不过由于发展的局限性，古典密码比较简单，一般是用手工或机器的方法编制，因而容易被破译。在计算机飞速发展的今天已失去实用价值，但古典密码原理容易理解，是进一步学习现代密码的基础，也是用信息论的方法对信息保密问题进行分析的基础。5.2.1单表密码单表密码是一种代换密码，加密编码时用一固定的字符集（称为密钥）中的字符代替明文中的对应字符，从而将明文变换为密文，而信宿（合法接收者）则在接收到密文后，借助于密钥将其译为明文，即：加密：()BECS=解密：()BSDC=153[例5.2.1]用英文26个字母为例。明文字符集ABCDEFGHIJKLMNOPQRSTUVWXYZ密钥字符集XYZUVWRSTOPQNMJKLGHIDEFABC若明文为：S=Besurenottosayanythingtohim则密文()BECS==yvhdgvmjiijhxbxmbistmrijstn而明文()BSDC==Besurenottosayanythingtohim加密和解密用的密钥是相同的。密钥字符集根据排列原理共有26！个，其数量是十分巨大的，这有利于保密，但如果信源符号太少，例如二元信元则由此简单生成的单表密码的密钥只有2！即2个，就象一种锁只有两种钥匙，这显然太少。解决的办法是将二元信源变换成N次扩展信源，如N足够大，则采用单表密码就有一定的保密性。5.2.2移位代换密码（加法密码）移位代换密码也是单表密码。历史上，在高卢战争中使用过的凯萨密码就是移位代换密码。它的基本方法是将明文字符集顺序循环左移K位构成密钥，并以此密钥来加密和解密。[例5.2.2]以英文26个字母为例(2K=)。明文字符集ABCDEFGHIJKLMNOPQRSTUVWXYZ密钥字符集CDEFGHIJKLMNOPQRSTUVWXYZAB若明文为：S=Thelidhasbeenputonfurtherleaksofinformation则密文()BECS==vjgnkfjcudggprwvqphwtvjgtngcmuqhkphqtocvkqp而明文()BSDC==Thelidhasbeenputonfurtherleaksofinformation英文凯萨密码共有26个字符，因而共有26个可能的代换表，其中26K=使得密钥字符集与明文字符集中的字母完全一致，因而不能采用，可作密钥用的只有25个。可见移位代换密码的密钥数量在相同情况下比前述的单表密码少得多，因而保密性不好，但凯萨密码加密和解密均很简单。5.2.3乘数密码乘数密码的规则是：（1）将明文字符集内的字符顺序编号，例如，英文字母符号集可编为下标025i=:号，共有26q=个。（2）寻找一个与q互素，且小于q的正整数k。（3）密钥字符集对应的英文字母符号集可编为下标：154jik=（模q）（,kq互素）[例5.2.3]以英文26个字母为例1226,32qkk===及。明文字符集ABCDEFGHIJKLMNOPQRSTUVWXYZ明文字符下标012345678910111213141516171819202122232425密钥字符下标13k=036912151821241471013161922252581114172023密钥字符集ADGJMPSVYBEHKNQTWZCFILORUX密钥字符集下标22k=024681012141618202224024681012141618202224错误的密钥字符集ACEGIKMOQSUWYACEGIKMOQSUWY由例可知，k必须与q互素（例如k=3，5，7，9，11，15，17，19，21，23，25共11种），以保证密文代换表与明文字符集是一一对应的。例中，22k=与26q=不是互素，造成密钥与明文字符集不是一一对应，就无法用于密码。由于要求k与q互素，故可能的k只有11种，因而密钥数量比前几种更少，保密性也就更差。为了改进保密性，可以把乘数密码与加法密码相结合起来，即使规则3变成：12jikk=+（模q）1k,q互素，20qk£以此规则编出的码称为仿射密码，其密钥数量为12×26－1=311种，保密性得到了提高。5.2.4固定周期位移置换固定周期位移置换加密方法将明文每d个字符划分成一组一组（最后一组不足长度d部分补x），在每组内进行相同的置换算法，从而将明文变换成密文。[例5.2.4]由26个英文字母组成的明文字符集，取5d=，各组中字符位置下标号按下面的置换表变换：0123432410BE=æöç÷èø若明文为S=Thisltteriscompletelyconfidential则密文为C()BES==silhtetrteocmsiteelpocnyledniflaxit反变换：0123443102BD=æöç÷èø解密后明文为S()BDC==Thisltteriscompletelyconfidential密钥（即置换表）的数量为5！个，一般情况下，密钥的数量为!d个。1555.2.5多表代换密码1．维吉尼亚密码维吉尼亚密码的编码步骤是：（1）将q个明文字符按顺序编好下标。（2）选定字符数为d的密钥字，(d＜q)也编好下标。（3）用明文字符下标i和密钥字下标k进行模q加，得到下标j。（4）用下标j构造出密文。（5）解密用与上述相反的过程借助于密钥进行。[例5.2.5]现有26个英文字母组成的明文字符集26q=，确定密钥字为secret，6d=，如明文为，明文S=Howisthenegotiationgoingon下标i=7,14,228,1819,7,413,4,6,14,19,8,0,19,8,14,136,14,8,13,614,13密钥k=secretsecretsecretsecretse下标t=18,4,2,17,4,19,18,4,2,17,4,19,18,4,2,17,4,19,18,4,2,17,4,19,18,4下标j=25,18,2425,2212,25,815,21,10,7,11,12,2,10,12,7,510,16,25,17,256,17密文C=zsyzwmzipvkhlmckmhfkqzrzgr注意到明文中某些不同字母例如h，i变成了密文中相同的字母z。而明文中某些相同字母例如o变成了密文中不同的字母h，q，g。显然这为破译增加了困难，因而其保密性较好。2．滚动密钥密码周期位移置换密码，其保密性随周期d增大而变强，当密钥长度d和明文序列长度q一样长时，保密性最好，该密码