第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做二进制展开，例如191+12+022+023+124 我们可以把信息19编成5位的（11001）传送。发方：x收方：x 16.1.2 算法复杂性的衡量标准5位的二元序列共有2532种可能，可传递32种信息。一般地，传送n 个信息时，每个信息编成长度为log2n的二元序列。序列的长度log2n直接影响通信速度，所以在讨论算法复杂性时，均以log2n作为衡量标准。10.1.3 保密通信的最简单数学模型发方发出信息x(明文)，发方需对x加密，加密是一种运算E，将明文x变成密文y=E(x)。发方把密文传给收方，收方收到密文y之后，用E的逆运算DE-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(1k25),然后将明文中每个英文字母改用在它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、任意选定一个22矩阵，每个矩阵元素均为整数，设为要求A的行列式detA 是奇数且不能被13整除。2、将明文中的每个字母对，按照上表列出的对应关系，转换成一个二维向量p=p1,p2T。3、计算新的二维向量q=Ap，4、对q1,q2T的每一个分量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（明文），则用户Ai查到Aj的公钥Ei,Ai将密文y=Ej(x)发给Aj，Aj收到y之后，用自己的私钥Dj作用，恢复明文Dj(y)=D jEj(x)=x，Aj以外的人都可查到Aj的公钥Ej,但是由Ej求 Dj很难，所以不能恢复明文。这种公钥体制一提出，不但解决了大量密钥的保存问题，而且立刻发现还可以解决数字签名和身份认证问题。 显然，要实现公钥体制，关键是能找到许多单向函数。在公钥体制提出之后的几年里，人们设计出各种单向函数E，声称由E求其逆D是非常困难的，但其中大多数方案不久都被人否决，即找到由E求D的多项式算法。到目前为止还站得住脚的只有两种方案：RSA方案和离散对数方案。这两种方案在信息安全的各个领域已经得到实际应用。16.5.3 公钥密码体制中用到的几个数学定理定理1 设p 是一与整数x互素的素数，则 x p-11(mod p)，且对任何整数x，有x px(mod p) 定理2 若p, q 为不同的素数，n=pq ,那么(n)=(p-1)(q-1) ，其中(n)表示小于n且与n互素的正整数个数，称为欧拉函数。定理3 若p, q 为不同的素数，x与p, q互素, n=pq ,则1(mod n)定理4 (公开密钥体制的数学依据) 若p, q 为不同的素数， n=pq，e与(n)互素， ed1(mod(n), 则映射 Ee,n：x xe (mod n) 是Zn=0,1,n-1到自身的一一映射，且其逆映射为Ed,n16.5.4 公钥体制的实施例子 下面的例子由Vanden Eynden在1987年给出。He describes a method that illutrates how RSA encryption works for a smaller numbers.设p=29 , q=41 , 则n=pq=1189 ,(n)= (1189)=2840=1120假定参与密钥生成与交换的双方分别为A(Alice)和B（Bob）。实施过程如下：1、B选择n1189，eB3公开，但p和q完全保密（对A也保密）;2、A想给B发送一些信息，不妨设A将这些信息用数字序列发送（例如，A对应01，B对应02，Z对应26，空格对应00）。假设A想将信息“MATHEMATICS”发送给B，则产生的字节序列为 13 01 20 08 05 13 01 20 09 03 19 ;3、因为n=1189有4个字节，我们把信息分成3个字节一组，产生一个序列P1,P2,130 120 080 513 012 009 031 900 (最后两个0是空格补齐的);4、将P1,P2,用加密变换f变成C1,C2, (Ci=f(Pi)=P3i(mod 1189),因为n,e 是公开的，A发送给B的加密信息是 917 383 730 692 539 729 066 3205、