Shannon与现代密码学.doc

Shannon与现代密码学 王育民 西安电子科技大学 教育部计算机网络与信息安全重点实验室 1949年公开发表《保密系统的通信理论》[8]开辟了用信息论研究密码学的新方向，使他成为密码学的先驱近代密码理论的奠基人。这篇文章是他在1945年为贝尔实验室所完成的一篇机密报告《A Mathematical Theory of Cryptograph》[1，[24]]。Boston环球报称此文将密码从艺术变成为科学。（Transformed cryptography from an art to a science.）。本文发表后促使他被聘为美国政府密码事务顾问。 这一工作的背景是他在1941年在贝尔曾从事密码学研究工作，接触到SIGSALY电话，是一种马桶大小的语言置乱设备，供丘吉尔和罗斯福进行热线联系。这一电话保密机所用的密码就是在今天也破不了[1，p.xx]。 SIGSALY电话机 这篇文章对于研究密码的人来说是需要认真读的一篇经典著作。本文奠定了现代密码理论的基础。可以说，最近几十年来密码领域的几个重要进展都与Shannon这篇文章所提出的思想有密切关系。保密通信系统的数学模型Shannon以概率统计的观点对消息源、密钥源、接收和截获的消息进行数学描述和分析，用不确定性和唯一解距离度量密码体制的保密性，阐明了密码系统、完善保密性、纯密码、理论保密性和实际保密性等重要概念，从而大大深化了人们对于保密学的理解。这使信息论成为研究密码学和密码分析学的一个重要理论基础，宣告了科学的密码学时代的到来。 2. 2. 正确区分信息隐藏和信息保密Shannon在引论中就明确区分了信息隐藏（隐匿信息的存在）和信息保密（隐匿信息的真意）模拟保密变换和数字信号加密（密码）不同之处。Shannon称后者为真保密系统（True secrecy system）3. 密码系统与传信系统的对偶性 传信系统是对抗系统中存在的干扰（系统中固有的或敌手有意施放的），实现有效、可靠传信。 Shannon说：“从密码分析者来看，一个保密系统几乎就是一个通信系统。待传的消息是统计事件，加密所用的密钥按概率选出，加密结果为密报，这是分析者可以利用的，类似于受扰信号。” 密码系统中对消息m的加密变换的作用类似于向消息注入噪声。密文c就相当于经过有扰信道得到的接收消息。密码分析员就相当于有扰信道下原接收者。所不同的是，这种干扰不是信道中的自然干扰，而是发送者有意加进的、可由己方完全控制、选自有限集的强干扰（即密钥），目的是使敌方难于从截获的密报c中提取出有用信息，而己方可方便地除去发端所加的强干扰，恢复出原来的信息。 传信系统中的信息传输、处理、检测和接收，密码系统中的加密、解密、分析和破译都可用信息论观点统一地分析研究。密码系统本质上也是一种传信息系统。是普通传信系统的对偶系统。 4. 含糊度在破译和设计密码中的作用 保密系统也可采用含糊度（Equivocation）作为不确定性（Uncertainty）的量度。 已知密报C的条件下密钥K的含糊度C的条件下消息M的含糊度 如果我们考虑长为L的消息序列被加密成长为N的密文序列，明文熵为H(()＝H(M L)，密钥熵为H(()，密文熵为H(()=H(C N)，在已知密文条件下明文的含糊度为H(ML/CN)，在已知密文条件下密钥的含糊度为H((/CN)。从唯密文破译来看，密码分析者的任务是从截获的密文中提取有关明文的信息 I(ML; CN)=H(ML)－H(ML/C N) 或从密文中提取有关密钥的信息 I((; C N)=H(()－H((/C N) 对于合法的接收者，在已知密钥和密文条件下提取明文信息，由加密变换的可逆性知 H(ML/C N)=0 因而此情况下有 I(ML; C N)=H(ML) 由上述可知，H((/C N)和H(ML/CN)，窃听者从密文能够提取出的有关明文和密钥的信息就越小。 这两个含糊度都是截获密报N的非增函数，一般随掌握的密报增多而减小，并最终趋于零。从而可以唯一地确定出密钥或消息，实现破译目的。 利用信息论的一些结果不难推出[10]，对任意保密系统有： I(ML; C N)(H(ML)－H(() 保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。密码分析者能否有效地提取出来，则是另外的问题了。作为系统设计者，自然要选择有足够多的密钥量才行。 Shannon用信息论清楚地描述了破译问题。当然要实行起来需要大量有关消息、密钥、密报的统计知识和计算量，往往是极为繁琐和困难的事。 Shannon详细讨论了含糊度有关理论。并从加密和构造密码的角度指出了这一概念的重要指导意义。 5. 完善保密性 一个密码系统，若其密文与明文之间的互信息 I(ML; C)=0 则窃听者从密文就得不到任何有关明文的信息，不管