(第16章密码.docVIP

第16章 密码 本章学习Hill密码、Caesar密码和Vigenere密码等体制的加密、解密和破译过程，主要涉及代数，利用模运算意义下的矩阵乘法、求逆矩阵、线性无关、线性空间与线性变换等概念和运算。 16.1 密码学基本知识 密码学是一门古老而神秘的学科，其起源可以追溯到几千年前的埃及、巴比伦、古罗马和古希腊，历史极为久远。上世纪德国在1925年批量生产恩格玛（ENGMA）必威体育官网网址机用于军事，在1939年被波兰人雷日斯基破译。第二次世界大战期间，密码破译工作取得了惊人的成绩，欧美各国集聚了一批数学家从事破译工作，密码破译工作最出色是在美国，1942年美国破译了日本的“紫密”（欧文加密机），但日本人长期不知道此事，导致日本突袭中途岛海战的失败。1943年4月美国破译了日本联合舰队长官山本五十六视察前线阵地的详细日程表，在4月18日派18架战斗机在预定时间和地点 打下了山本的座机，成为密码史上精彩的一页。 美国数学家Shannon在二战期间期间建立了通信理论，他在1948年和1949年的文章《通信的数学理论》和《必威体育官网网址系统的通信理论》建立了信息论和必威体育官网网址通信的数学理论。 密码学的一个重要方面是试图给出一种方法，改变信息的原有形式，使得除了某些特定人员外，其他人难以读懂这一信息的内容。密码学中的信息代码称为密码，尚未转换成密码的文字信息称为明文，由密码表示的信息称为密文，从明文到密文的转换过程称为加密，相反的过程成为解密。显然，加密过程必须遵循某种规则。 16.1.1 信息传送的最简化数学模型 发方把信息x通过信道传送给对方。信息可以有许多具体形式，如声音、文字、图象、数据等，所有信息通常都变成电信号。脉冲电信号有两个状态，数学上把这两个状态表示成0和1。 如果发方要求把n个信息{0,1,…,n-1}传送给对方，可以把每个信息i做二进制展开，例如 19＝1+1×2+0×22+0×23+1×24 我们可以把信息19编成5位的（11001）传送。 16.1.2 算法复杂性的衡量标准 5位的二元序列共有25＝32种可能，可传递32种信息。 一般地，传送n 个信息时，每个信息编成长度为[log2n]的二元序列。序列的长度log2n直接影响通信速度，所以在讨论算法复杂性时，均以log2n作为衡量标准。 10.1.3 必威体育官网网址通信的最简单数学模型 发方发出信息x(明文)，发方需对x加密，加密是一种运算E，将明文x变成密文y=E(x)。发方把密文传给收方，收方收到密文y之后，用E的逆运算D＝E-1作用于y 恢复成明文， 即D(y)=DE(x)=x，这个运算叫做解密。 加密和解密运算{E，D} 由收发两方约定并保守秘密，叫做密钥。敌方在不知密钥的情况下即使截获密文y，也很难恢复成明文x。 必威体育官网网址通信的最简单数学模型可以通过以下图形来理解。 16.1.4 好的密码系统的基本要求 加密解密的方式叫做密码体制，在同一密码体制下可以有许多密钥，供收发方选择更换。 一个好的密码系统的至少应当满足：（1）要在敌方知道加密体制的情况下，很难破译收发方使用的密钥。因为加密体制（做出加密机）在较长时间是不更换的。 （2）要有充分多的密钥，供收发方选择和更换。 （3）加密和解密运算在实际中要容易操作，并且不过分增加通信所需的时间。 16.2 Caesar密码体制 16.2.1 Caesar密码体制 公元前后的罗马帝国大帝Caesar在《高卢战记》一书中描述了他把密信送给被敌人围困的西塞罗，但并未说明加密的方法。苏托尼厄斯在公元二世纪写《恺撒传》，对Caesar密码体制有详细的介绍。 Caesar密码的加密方法是取一个数k(1≤k≤25),然后将明文中每个英文字母改用在它k位之后的字母代替，注意最后一个字母z又回到a。 例如k=10为密钥是指将明文中每个英文字母改用在它10位之后的字母代替，如字母a用字母k代替。 16.2.2 Caesar密码体制的推广 Caesar密码体制的缺点是密钥太小，只有25个。如果知道密码体制，可以逐个试k的值，很容易恢复成明文。 Caesar密码体制的推广：考虑加密运算E是26个字母的任意一种置换（不同字母改用不同字母），一共有26！种置换，而解密运算D为E的逆置换，这时密钥量为26!.这种体制在公元9世纪才被阿拉伯人找到破译方法——频率统计分析。由于数学、统计学、语言学在阿拉伯高度发达，促使他们发明了统计破译术。 16.3 Vigenere密码体制 16.3.1 Vigenere密码体制 1586年，法国外交官Vigenere把恺撒密码模型做一种改进，恺撒密码的密钥是用同一个数字简单重复成序列与明文逐位模26相加， Vigenere则增加密钥的长度。比如发方和收方约定以finger作为密钥，