第16章密码.doc

第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）传送发方：x收方：x 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 保密通信的最简单数学模型可以通过以下图形来理解敌方x解密xy信道y加密截获y发方加密：E(x)=y 收方解密：D(y)=x16.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作为密钥，它的数字表示为（5,8,13,6,4,17）加密时将明文序列与这六个数字不断重复的“周期序列”逐位做模26加法10.3.2 Vigenere的例子以下是用Vigenere密码，发方和收方约定以finger作为密钥进行加密的一个例子。

b a t t l e o n t u e s d a y (明文)1 0 19 19 11 4 14 13 19 20 4 18 3 0 24 (x)5 8 13 6 4 17 5 8 13 6 4 17 5 8 13 (密钥序列)6 8 6 25 15 21 19 21 6 0 8 9 8 8 11 （y=E(x)）G I G Z P V T V G A I J I I L （密文）Vigenere密码体制是200年后才找到破译方法，破译者是英国人巴比奇（1854年）和德国人卡西斯基（1863年）破译手段采用更为精确的数学统计方法，但由于英国情报机关的要求，巴比奇破译Vigenere 密码一事一直到20世纪才公诸于世16.4 Hill(希尔)密码系统16.4.1 希尔密码的加密Hill密码以矩阵变换的方法建立字母组间的对应关系，该方法由Hill于1929年提出，它使得密码学进入以数学方法处理问题的阶段。

在下面的讨论中，无论明文或密文，均假设每一个字母对应一个非负整数即：A B Ｃ Ｄ E Ｆ ………………………… X Y Z 1 2 3 4 5 6 …………………………24 25 0考虑明文字母按先后顺序每两个分为一组的情况如电文字母总数为奇数，则在最后位置任意补充一个，采用如下步骤将每组字母转换为密码： 1、任意选定一个2×2矩阵，每个矩阵元素均为整数，设为要求A的行列式detA 是奇数且不能被13整除2、将明文中的每个字母对，按照上表列出的对应关系，转换成一个二维向量p=[p1,p2]T3、计算新的二维向量q=Ap，4、对[q1,q2]T的每一个分量qi计算同余再根据字母对应表表，将 转化成字母，得到所要的密文注：整数a在模m下的余数可以如下计算：其中a是任意一个整数，m是一个正整数，r是商为整数时|a|÷m的余数16.4.2 希尔密码的破译由于 故只要知道了矩阵A在mod 26意义下的逆，则从密文字母所对应的二维向量q,即可得到明文字母所对应的向量p因此当矩阵A在mod 26意义下可逆时，解密HILL密码是简单的事，问题是：是否任意一个矩阵A在mod 26意义下都是可逆的？16.4.3 Mod 26意义下矩阵A可逆的条件定理（Mod 26意义下矩阵A可逆的条件：）说明：在mod 26 意义下对a Z26求a-1，就是求一整数x Z26,使得存在另一整数k,满足 x a=k ×26+1 (1)如果这样的x 存在，则 x=a-1由此可见，Z26中与26有公因子的元素，不存在乘法逆元素；反之，当a Z26且与26不可约时，存在x Z26及k，使（1）式成立；并且此时逆元素是唯一的。

下面给出Z26中有乘法逆的元素及其逆元素：a 1 3 5 7 9 11 15 17 19 21 23 25a-1 1 9 21 15 3 19 7 23 11 5 17 25所以只要detA不是偶数且不含因子13，则在mod 26意义下，A-1存在16.4.4 Hill密码的实例我们用如下简单的例子说明上述方法假设截获的密文是：goqbxcbuglosnfal,猜测它是两个字母为一组的希尔密码，又由各种积累资料和一般行文习惯判定，前4个密文字母对应的明文是dear ,再猜测字母与数字按字母表顺序对应，则明文字母分组 de与ar对应的两个二维向量是 P1=(4，5)T，P2=(1，18)T而按照同一字母数字对应关系，密文的字母分组 go与qb对应的向量依次为 AP1=(7，15)T,AP2=(17，2)T为破译这一密码，将上述信息按下面的方式进行计算，右边的文字是对相应操作的说明 形成矩阵[Q | P] 以7-1=15（mod26）乘第一行 对每个数模26 第一行乘-17加到第二行 对每个数模26 第二行乘25-1=25（mod26） 对每个数模26 第一行减第二行17倍 对每个数模26由最后一个等式得到：利用这一逆矩阵，破译出的电文是：Dear Mac God forbid (亲爱的麦克：但愿此事未曾发生). 此例说明，为破译一密码，捕获的任何片段信息都可能有重大价值，同时还需要大量的猜测与尝试，工作量是惊人的。

数学理论对破译有重要指导作用，但问题绝非纯靠理论能够解决 16.5 公钥密码体制中的数学模型10.5.1 公钥密码体制的基本思想传统的密码通讯只能在事先约定的双方间进行，双方必须掌握相同的密钥，而密钥的传送必须使用另外的 “安全信道” ，而这在科技相当发达的现代社会，完全实现几乎是不可能的公开密钥体制的提出就是为了从根本上解决上述问题 公开密钥体制的基本思想是把密钥划分为公开密钥和秘密密钥两部分，二者互为逆变换，但几乎不可能从公开密钥推断出秘密密钥每个使用者均有自己的公开及秘密密钥公开密钥供别人向自己发送信息时加密使用，这种密钥可以像号码一样供人查阅；而每个用户对自己的秘密密钥则严加保密，只供自己解密使用16.5.2 公钥密码体制的实现方法现在设公司有 n个 用户A1, A2,…, An,彼此通信均需保密公司取n组单向函数组{Ei, Di},其中Ei和Di是互逆的运算，但是由Ei求 Di非常困难 Ei和Di分别叫做用户Ai的公钥和私钥公司把所有Ei都公开，而 Di只由Ai保存，这样用户Ai无论和多少人通信，只需保留一个密钥，即Di若用户Ai向用户Aj发信息x（明文）。