第四章基于线性代数与差分方程方法的模型实用课件.ppt

1、第四章第四章 浙江大学数学建模浙江大学数学建模 实践基地实践基地在第三章中，我们有多处对不连续变化的变量采取了连续在第三章中，我们有多处对不连续变化的变量采取了连续化的方法，从而建立了相应的微分方程模型。但是由于以化的方法，从而建立了相应的微分方程模型。但是由于以下原因：下原因：第一第一，有时变量事实上只能取自一个有限的集合；，有时变量事实上只能取自一个有限的集合；第二第二，有时采取连续化方法后建立的模型比较复杂，无法，有时采取连续化方法后建立的模型比较复杂，无法求出问题的解，从而只能求它们的数值解。也就是说，在求出问题的解，从而只能求它们的数值解。也就是说，在建模时我们对离散变量作了连续化处

2、理，而在求解时，又建模时我们对离散变量作了连续化处理，而在求解时，又对连续变量作了离散化处理，使之重新变为离散变量。所对连续变量作了离散化处理，使之重新变为离散变量。所以采取连续化方法的效果有时并不很好，因而是不可取的。以采取连续化方法的效果有时并不很好，因而是不可取的。电子计算机的广泛应用为我们处理大量信息电子计算机的广泛应用为我们处理大量信息提供了实现的可能，这就十分自然地提出了提供了实现的可能，这就十分自然地提出了一个问题，对具有离散变量的实际问题直接一个问题，对具有离散变量的实际问题直接建立一个离散模型是否更为可取？本章介绍建立一个离散模型是否更为可取？本章介绍的几个模型就是基于这种想

3、法建立起来的。的几个模型就是基于这种想法建立起来的。例例4.1 人、狗、鸡、米过河问题人、狗、鸡、米过河问题 这是一个人所共知而又十分简单的智力游戏。某人要带狗、这是一个人所共知而又十分简单的智力游戏。某人要带狗、鸡、米过河，但小船除需要人划外，最多只能载一物过河，鸡、米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。在本问题中，可采取如下方法：一物在此岸时相应分量为在本问题中，可采取如下方法：一物在此岸时相应分量为1，而在彼岸时则取而在彼岸时则取 为为0，例如，例如（1,0,1,0）表示

4、人和鸡在此岸，表示人和鸡在此岸，而狗和米则在对岸。而狗和米则在对岸。（i）可取状态可取状态：根据题意，并非所有状态都是允许的，例如：根据题意，并非所有状态都是允许的，例如（0,1,1,0）就是一个不可取的状态。本题中可取状态（即系）就是一个不可取的状态。本题中可取状态（即系统允许的状态）可以用穷举法列出来，它们是：统允许的状态）可以用穷举法列出来，它们是：人在此岸人在此岸 人在对岸人在对岸(1，1，1，1)(0，0，0，0)(1，1，1，0)(0，0，0，1)(1，1，0，1)(0，0，1，0)(1，0，1，1)(0，1，0，0)(1，0，1，0)(0，1，0，1)总共有十个可取状态，对一般情

5、况，应找出状态为可取的充总共有十个可取状态，对一般情况，应找出状态为可取的充要条件。要条件。（ii）可取运算可取运算：状态转移需经状态运算来实现。在实际问题：状态转移需经状态运算来实现。在实际问题中，摆一次渡即可改变现有状态。为此也引入一个四维向量中，摆一次渡即可改变现有状态。为此也引入一个四维向量（转移向量），用它来反映摆渡情况。例如（转移向量），用它来反映摆渡情况。例如（1，1，0，0）表示人带狗摆渡过河。根据题意，允许使用的转移向量只能表示人带狗摆渡过河。根据题意，允许使用的转移向量只能有（有（1，0，0，0，）、（，）、（1，1，0，0）、（）、（1，0，1，0）、）、（1，0，0，1

6、）四个。）四个。在具体转移时，只考虑由可取状态到可取状态的转移。问题在具体转移时，只考虑由可取状态到可取状态的转移。问题化为：化为：由初始状态（由初始状态（1，1，1，1）出发，经奇数次上述运算转化为）出发，经奇数次上述运算转化为（0，0，0，0）的转移过程。）的转移过程。我们可以如下进行分析我们可以如下进行分析 ：（第一次渡河）（第一次渡河）(不不可可取取)(不不可可取取)(可可取取)(不不可可取取)(0 0,1 1,1 1,1 1)(0 0,1 1,1 1,0 0)(0 0,1 1,0 0,1 1)(0 0,0 0,1 1,1 1)(1 1,0 0,0 0,0 0)(1 1,0 0,0 0

7、,1 1)(1 1,0 0,1 1,0 0)(1 1,1 1,0 0,0 0)(1 1,1 1,1 1,1 1)（第二次渡河）（第二次渡河）(1 1,0 0,0 0,0 0)(1 1,0 0,0 0,1 1)(1 1,0 0,1 1,0 0)(1 1,1 1,0 0,0 0)(0 0,1 1,0 0,1 1)(可可取取)(不不可可取取)过过的的状状态态)(循循环环,回回到到原原先先出出现现(不不可可取取)(1 1,1 1,0 0,1 1)(1 1,1 1,0 0,0 0)(1 1,1 1,1 1,1 1)(1 1,0 0,0 0,1 1)以下可继续进行下去，直至转移目的实现。上述分析实际以下可

8、继续进行下去，直至转移目的实现。上述分析实际上采用的是穷举法，对于规模较大的问题是不宜采用的。上采用的是穷举法，对于规模较大的问题是不宜采用的。这是一个古老的阿拉伯数学问题。有三对夫妻要这是一个古老的阿拉伯数学问题。有三对夫妻要过河，船最多可载两人，约束条件是根据阿拉伯过河，船最多可载两人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不场的情况下与其法律，任一女子不得在其丈夫不场的情况下与其他男子在一起，问此时这三对夫妻能否过河？他男子在一起，问此时这三对夫妻能否过河？这一问题的状态和运算与这一问题的状态和运算与前一问题有所不同，根据前一问题有所不同，根据题意，状态应能反映出两题意，状态应能

9、反映出两岸的男女人数，过河也同岸的男女人数，过河也同 样要反映出性别样要反映出性别 故可如下定义：故可如下定义：（i）可取状态可取状态：用用H和和W分别表示此岸的男子和女子分别表示此岸的男子和女子数，状态可用矢量数，状态可用矢量（H，W）表示，其中表示，其中0H、W3。可取状态为（。可取状态为（0,i），），(i,i)，(3,i)，0i3。(i,i)为可取状态，这是因为总可以适当安排而使他为可取状态，这是因为总可以适当安排而使他们是们是 i对夫妻。对夫妻。（ii）可取运算可取运算：过河方式可以是一对夫妻、两个男人或两个女人，过河方式可以是一对夫妻、两个男人或两个女人，当然也可以是一人过河。转移

10、向量可取成当然也可以是一人过河。转移向量可取成(1)im,(1)in)，其中其中m、n可取可取0、1、2，但必须，但必须满足满足1m+n2。当。当j为奇数时表示过河。为奇数时表示过河。当当j为偶为偶数时表示由对岸回来，运算规则同普通向量的加数时表示由对岸回来，运算规则同普通向量的加法。法。问题归结为由状态问题归结为由状态(3,3)经经奇数次奇数次可取运算，即由可取状可取运算，即由可取状态到可取状态的转移，转化态到可取状态的转移，转化 为为(0,0)的转移问题。和上题一样，的转移问题。和上题一样，我们既可以用计算机求解，也可以分析求解，此外，本题还我们既可以用计算机求解，也可以分析求解，此外，本

11、题还可用可用作图作图方法来求解。方法来求解。在在HW平面坐标中，以平面坐标中，以“”表示可取状态，表示可取状态，从从A(3,3)经奇数经奇数次转移到次转移到 达达O(0,0)。奇数次。奇数次转移时向左或下移转移时向左或下移 动动1-2格而落格而落在一个可取状态上，在一个可取状态上，偶数次偶数次转移时向右或上移转移时向右或上移 动动1-2格而落在格而落在一个可取状态上。为了区分起见一个可取状态上。为了区分起见 ,用用红红箭线表示箭线表示奇奇数次转移，数次转移，用用蓝蓝箭线表示第箭线表示第偶偶数数 次转移次转移,下图给出了一种可实现的方案下图给出了一种可实现的方案 ,故故 A(3,3)O(0,0)

12、HW这这三三对夫妻是可以过河的对夫妻是可以过河的。假如按。假如按这样的方案过这样的方案过 河河,共需经过共需经过十一十一次摆次摆渡。渡。不难看出不难看出,在上述规则下在上述规则下,4对夫妻就对夫妻就无法过河了无法过河了,读者可以自行证明之读者可以自行证明之.类类似可以讨论船每次可载三人的情况似可以讨论船每次可载三人的情况,其结果其结果 是是5对夫妻是可以过河的对夫妻是可以过河的,而而六六对以上时就对以上时就 无法过河无法过河了。了。步1 将THANK YOU转换成 （20，8，1，14，11，25，15，21）农场计划采用 AA型的植物与每种基因型植物相结合的方案培育植物后代。以这一方法得到的

13、密文电码是：基于线性代数与 差分方程方法的模型16）的解，其 中c1、c2为任意常数，这说明，传统的密码通讯只能在事先约定的双方间进行，双方必须掌握相同的密钥，而密钥的传送必须使用另外 的“安全信道”。（iii）在每一代中，配偶的同胞对也是六种类型之一，并现希望根据 前5年的统计数据预测 第6年起该商品在各季度中的销售量。在一段足够长且非特别专门化的文章中，字母的使用频率是比较稳定的。经过计算，矩阵 M的特征值和特征向量为对应的明文(i=1,2,n)是什么，即可确定A，并将密码破译。由前，表兄妹结婚的近交系数为 1/16,故其子女发生该疾病的概率为只要相应的整数小于n即可。(mod26)即记全

14、体明文组成的集合 为U，全体密文组成的集合 为V，称U为明文空间，V为密文空间。的随机矩阵。双亲随机结合的较一般模型相对比较复杂，这些我们仅研究一个较简单的特例。如果初始的父母体同胞对 是（A,Aa）型，即b0=1，而a0=c0=d0=e0=f0=0，于是，当密码的设计和使用至少可从追溯到四千多年前的埃及密码的设计和使用至少可从追溯到四千多年前的埃及 ,巴比巴比伦、罗马和希腊，历史极为久远伦、罗马和希腊，历史极为久远 。古代古代隐藏信息的方法隐藏信息的方法 主主要有两大类：要有两大类：其一其一为为隐藏信息载体，采用隐写术隐藏信息载体，采用隐写术 等；等；其二其二为为变换信息载体，使之无法为一般

15、人所理解变换信息载体，使之无法为一般人所理解 。在密码学中，信息代码被称为在密码学中，信息代码被称为 密码密码，加密，加密前的信息被称为前的信息被称为 明文明文，经加密后不为常人，经加密后不为常人所理解的用密码表示的信息被称为所理解的用密码表示的信息被称为 密文密文(ciphertext)，将明文转变成密文的过程被，将明文转变成密文的过程被称为称为加密加密(enciphering)，其逆过程则被称，其逆过程则被称为为解密解密(deciphering)，而用以加密、解密，而用以加密、解密的方法或算法则被称为的方法或算法则被称为 密码体制密码体制(crytosystem)。记全体明文组成的集合记全

16、体明文组成的集合 为为U，全体密文组成的集合，全体密文组成的集合 为为V，称，称U为明文空间，为明文空间，V为密文空间。加密常利用某一被称为密钥的东为密文空间。加密常利用某一被称为密钥的东西来实现，它通常取自于一个被称为密钥空间的含有若干参西来实现，它通常取自于一个被称为密钥空间的含有若干参数的集合数的集合K。按数学的观点来看，加密与解密均可被看成是一。按数学的观点来看，加密与解密均可被看成是一种变换：取一种变换：取一kK，uU，令，令 ，v为明为明文文u在密钥在密钥K下的密文，而解码则要用下的密文，而解码则要用 到到K的逆变换的逆变换K-1，。由，。由此可见，密码体系虽然可以千姿百态，但其关

17、键还在此可见，密码体系虽然可以千姿百态，但其关键还在 于于密钥密钥的选取的选取。V Vv vu uk k随着计算机与网络技术的迅猛发展，大量各具特色的密码体随着计算机与网络技术的迅猛发展，大量各具特色的密码体系不断涌现。离散数学、数论、计算复杂性、混沌、系不断涌现。离散数学、数论、计算复杂性、混沌、，许多相当高深的数学知识都被用上，逐步形成了（并仍在迅许多相当高深的数学知识都被用上，逐步形成了（并仍在迅速发展的）具有广泛应用面的速发展的）具有广泛应用面的 现代密码学现代密码学。替代密码替代密码 移位密码移位密码 代数密码代数密码 代替法密码代替法密码采用另一个字母表中的字母来代替明文中的字母，

18、采用另一个字母表中的字母来代替明文中的字母，明文字母与密文字母保持一一对应关系，但采用的符号改变明文字母与密文字母保持一一对应关系，但采用的符号改变了。加密时，把明文换成密文，即将明文中的字母用密文字了。加密时，把明文换成密文，即将明文中的字母用密文字母表中对应位置上的字母取代。解密时，则把密文换成明文，母表中对应位置上的字母取代。解密时，则把密文换成明文，即把密文中的字母用明文字母表中对应位置上的字母代回，即把密文中的字母用明文字母表中对应位置上的字母代回，解密过程是加密过程的逆过程。在代替法加密过程中，密文解密过程是加密过程的逆过程。在代替法加密过程中，密文字母表即代替法密钥，密钥可以是标

19、准字母表，也可以是任字母表即代替法密钥，密钥可以是标准字母表，也可以是任意建立的。意建立的。1.代替法密码代替法密码明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJ密钥常用一密钥单词或密钥短语生成混淆字母表。密钥单词密钥常用一密钥单词或密钥短语生成混淆字母表。密钥单词 或密钥短语可以存放在识别码、通行字或密钥的秘密表格中。或密钥短语可以存放在识别码、通行字或密钥的秘密表格中。混合一个字母表，常见的有两种方法，这两种方法都采用混合一个字母表，常见的有两种方法，这两种方法都采用了一个了一个密钥单词密

20、钥单词或一个或一个密钥短语密钥短语。方法方法1：a)选择一个密钥单词或密钥短语，例如：选择一个密钥单词或密钥短语，例如：constructb)去掉其中重复的字母，得：去掉其中重复的字母，得：construc)在修改后的密钥后面接上从标准字母表中去掉密钥中已有在修改后的密钥后面接上从标准字母表中去掉密钥中已有的字母后剩下的字母，得：的字母后剩下的字母，得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZ在设计密钥时，也可在明文字母表中选择一个特定字母，然在设计密钥时，也可在明文字母表中选择一个特定

21、字母，然后从该特定字母开始写密钥单词将密钥单词隐藏于其中。例后从该特定字母开始写密钥单词将密钥单词隐藏于其中。例如，对于上例，选取特定字如，对于上例，选取特定字 母母 k k，则可得：，则可得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ 方法方法2 2：a)a)选择一个密钥单词或密钥短语，例如：选择一个密钥单词或密钥短语，例如：constructconstructb)b)去掉其中重复的字母，得：去掉其中重复的字母，得：construconstruc)c)这些字母构成矩阵的第一行，矩阵的后续

22、各行由标准字母这些字母构成矩阵的第一行，矩阵的后续各行由标准字母表中去掉密钥单词的字母后剩下的字母构成表中去掉密钥单词的字母后剩下的字母构成d)d)将所得矩阵中的字母按列的顺序排出将所得矩阵中的字母按列的顺序排出 得：得：cugmyoahpznbiqsdjvrtekwrflx按照此方法产生的字母表称为按照此方法产生的字母表称为 混淆字母表混淆字母表。还可以使用还可以使用混淆数混淆数。混淆数由以下方法产生：。混淆数由以下方法产生：a)选一密钥单词或密钥短语，例如：选一密钥单词或密钥短语，例如：constructb)按照这些字母在标准字母表中出现的相对顺序给它们编号，按照这些字母在标准字母表中出现

23、的相对顺序给它们编号，对序列中重复的字母则自左向右编号，得对序列中重复的字母则自左向右编号，得 ：construct 143675928c)自左向右选出这些数自左向右选出这些数 字字,得到一个混淆数字得到一个混淆数字 组组:143675928，混淆字母表由从小到大的顺序取矩阵中相应列得出。混淆字母表由从小到大的顺序取矩阵中相应列得出。为增加保密性，在使用为增加保密性，在使用代替法时还可利用一些代替法时还可利用一些其他技巧，如单字母表其他技巧，如单字母表对多字母表、单字母对对多字母表、单字母对多字母、多重代替等。多字母、多重代替等。2.移位密码体制移位密码体制移位密码移位密码采用移位法进行加密，

24、明文中的字母重新排列，本采用移位法进行加密，明文中的字母重新排列，本身不变，只是位置改变了。身不变，只是位置改变了。早在早在4000多年前，古希腊人就用一种名多年前，古希腊人就用一种名 叫叫“天书天书”的器械的器械来加密消息。该密码器械是用一条窄长的草纸缠绕在一个来加密消息。该密码器械是用一条窄长的草纸缠绕在一个直径确定的圆筒上，明文逐行横写在纸带上，当取下纸带直径确定的圆筒上，明文逐行横写在纸带上，当取下纸带时，字母的次序就被打乱了，消息得以隐蔽。收方阅读消时，字母的次序就被打乱了，消息得以隐蔽。收方阅读消息时，要将纸带重新绕在直径与原来相同的圆筒上，才能息时，要将纸带重新绕在直径与原来相同

25、的圆筒上，才能看到正确的消息。在这里圆筒的直径起到了密钥的作用。看到正确的消息。在这里圆筒的直径起到了密钥的作用。另一种移位另一种移位 法法采用将字母表中的字母平移若干位的方法来构造采用将字母表中的字母平移若干位的方法来构造密文字母表，传说这类方法是由古罗马皇帝凯撒最早使用的，密文字母表，传说这类方法是由古罗马皇帝凯撒最早使用的，故这种密文字母表被称为凯撒字母表。例如，如用将字母表向故这种密文字母表被称为凯撒字母表。例如，如用将字母表向右平移右平移3位的方法来构造密文字母表，可位的方法来构造密文字母表，可 得：得：明文字母表明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字

26、母表密文字母表：DEFGHIJKLMNOPQRTSUVWXYZABC因此因此 “THANK YOU”“WKDQN BRX”以上两种移位较易被人破译，为打破字母表中原有的顺序还可以上两种移位较易被人破译，为打破字母表中原有的顺序还可采用所谓路线加密法，即把明文字母表按某种既定的顺序安排采用所谓路线加密法，即把明文字母表按某种既定的顺序安排在一个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密在一个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密文表。文表。27）有两个平衡点，即x*=0和 。的形式，其对应的齐次方程为根据定理6，甲队最后获胜的概率表兄妹（或堂兄妹）结婚使子女发生该疾病的概率增大了

27、大 约7.c)自左向右选出这些数 字,得到一个混淆数字 组:143675928，混淆字母表由从小到大的顺序取矩阵中相应列得出。如果初始的父母体同胞对 是（A,Aa）型，即b0=1，而a0=c0=d0=e0=f0=0，于是，当类似地，可以定义yt的n阶差分。随着人类的进化，为了揭示生命的奥秘，人们越来越注重遗传学的研究，特别是遗传特征的逐代传播，已引起人们广泛的注意。第一，有时变量事实上只能取自一个有限的集合；现在利用差 分方程方法来研究蛛网模型，以验证上述猜测是否正确。某人要带狗、鸡、米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。在应用差

28、分方程研究问题时，一般不需要求出方程的通解，在给定初值后，通常可用 计算机迭代求解，但我们常常需要讨论解的稳定性。记全体明文组成的集合 为U，全体密文组成的集合 为V，称U为明文空间，V为密文空间。为任意常数，i=1,k。得a0=-8，a1=-1，a2=3。农场计划采用 AA型的植物与每种基因型植物相结合的方案培育植物后代。例如，对明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.14（市场经济的蛛网模 型）我们知道，平衡 点M*是否稳定取决于 在M*附近供、需曲线的局部性态。希尔密码体系为破译者设置了多道关口，加大了破译难度。例如，对明

29、文：例如，对明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以以7列矩阵表示如下：列矩阵表示如下：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS再按事先约定的方式选出密文。例如，如按列选出，得到再按事先约定的方式选出密文。例如，如按列选出，得到密文：密文：touthyhrihueeysanahomndrifoorsszrnetjeed使用不同的顺序进行编写和选择，可以得到各种不同的路使用不同的顺序进行编写和选择，可以得到各种不同的路线加密体制。对于同一明文消息矩阵，采用不同的抄写方线加密体制。对于同一明

30、文消息矩阵，采用不同的抄写方式，得到的密文也是不同的。式，得到的密文也是不同的。当明文超过规定矩阵的大小时，可以另加一矩阵。当需要当明文超过规定矩阵的大小时，可以另加一矩阵。当需要加密的字母数小于矩阵大小时，可以在矩阵中留空位或以加密的字母数小于矩阵大小时，可以在矩阵中留空位或以无用的字母来填满矩阵。无用的字母来填满矩阵。移位法也可和代替法结合使用，并使用约定的单词或短语作移位法也可和代替法结合使用，并使用约定的单词或短语作密钥，以进一步加强保密性，这就密钥，以进一步加强保密性，这就 是是钥控列序加密钥控列序加密 法法。例如例如，用密钥单词，用密钥单词 construct对明文对明文MATHE

31、MATICAL MODELING IS USEFUL加密：加密：CONSTRUCT 1 4 3 675 9 28MATHEMATICALMODELINGISUSEFU L 按混淆数的顺序选出各列，得到密文：按混淆数的顺序选出各列，得到密文：MCNLTLFTLIAAGMDSHMSEOSIIUAEE移位法的使用可重复多次，只进行一次移位加密的称为一移位法的使用可重复多次，只进行一次移位加密的称为一 次移位法次移位法，经多次移位的则称，经多次移位的则称 为为多次移位法多次移位法 代替法与移位法密码代替法与移位法密码 的的破译破译 对窃听到的密文进行分析时对窃听到的密文进行分析时 ，穷举法穷举法和和统

32、计法统计法是最基本的是最基本的破译方法破译方法 。穷举分析法穷举分析法 就是对所有可能的密钥或明文进行逐一试探，就是对所有可能的密钥或明文进行逐一试探，直至试探到直至试探到“正确正确”的为止。此的为止。此 方法方法需要事先知道密码体需要事先知道密码体制或加密算法制或加密算法（但不知道密钥或加密具体办法）。破译时（但不知道密钥或加密具体办法）。破译时需将猜测到的明文和选定的密钥输入给算法，产生密文，需将猜测到的明文和选定的密钥输入给算法，产生密文，再将该密文与窃听来的密文比较。如果相同，则认为该密再将该密文与窃听来的密文比较。如果相同，则认为该密钥就是所要求的，否则继续试探，直至破译。以英文字母

33、钥就是所要求的，否则继续试探，直至破译。以英文字母为例，当已知对方在采用代替法加密时，如果使用穷举字为例，当已知对方在采用代替法加密时，如果使用穷举字母表来破译，那么对于最简单的一种使用单字母表单字母表来破译，那么对于最简单的一种使用单字母表单字母单元代替法加密的密码，字母表的可能情况母单元代替法加密的密码，字母表的可能情况 有有26！种，种，可见，单纯地使用穷举法，在实际应用中几乎是行不通的，可见，单纯地使用穷举法，在实际应用中几乎是行不通的，只能与其它方法结合使用。只能与其它方法结合使用。统计法统计法是根据统计资料进行猜测的。在一段足够长且非特别是根据统计资料进行猜测的。在一段足够长且非特

34、别专门化的文章中，字母的使用频率是比较稳定的。在某些技专门化的文章中，字母的使用频率是比较稳定的。在某些技术性或专门化文章中的字母使用频率可能有微小变化。术性或专门化文章中的字母使用频率可能有微小变化。在上述两种加密方法中字母表中的字母是一一对应的，因此，在上述两种加密方法中字母表中的字母是一一对应的，因此，在截获的密文中各字母出现的概率提供了重要的密钥信息。根在截获的密文中各字母出现的概率提供了重要的密钥信息。根据权威资料报道，可以据权威资料报道，可以 将将26个英文字母按其出现的频率大小个英文字母按其出现的频率大小较合理地分为五组：较合理地分为五组：t,a,o,i,n,s,h,r;e;d,

35、l;c,u,m,w,f,g,y,p,b;v,k,j,x,q,z;不仅单个字母以相当稳定的频率出现，不仅单个字母以相当稳定的频率出现，相邻字母对相邻字母对和和三字母三字母对对同样如此。同样如此。按按频率大小频率大小 将双字母排列如下：将双字母排列如下：th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,ea,ng,as,or,ti,is,er,it,ar,te,se,hi,of使用最多的三字母按频率大小排列如下：使用最多的三字母按频率大小排列如下：The,ing,and,her,ere,ent,tha,nth,was,eth,for,dth统计的

36、章节越长，统计结统计的章节越长，统计结果就越可靠。对于只有几果就越可靠。对于只有几个单词的密文，统计是无个单词的密文，统计是无意义的。意义的。下面介绍一下统计观察的三个结果：下面介绍一下统计观察的三个结果：a)单词单词the在这些统计中有重要的作用；在这些统计中有重要的作用；b)以以e，s，d，t为结尾的英语单词超过了一半；为结尾的英语单词超过了一半；c)以以t，a，s，w为起始字母的英语单词约为一半。为起始字母的英语单词约为一半。对于对于a)，如果，如果 将将the从明文中删除，那从明文中删除，那 么么t的频率将要降的频率将要降到第二组中其他字母之后，到第二组中其他字母之后，而而h将降到第三

37、组中，并将降到第三组中，并 且且th和和he就不再是最众多的字母了。就不再是最众多的字母了。以上对英语统计的讨论是在仅涉以上对英语统计的讨论是在仅涉 及及26个字母的假设条件个字母的假设条件下进行的。实际上消息的构成还包括间隔、标点、数字下进行的。实际上消息的构成还包括间隔、标点、数字等字符。总之，破译密码并不是件很容易的事。等字符。总之，破译密码并不是件很容易的事。2.希尔密码希尔密码代替密码与移位密码的一个致命弱点代替密码与移位密码的一个致命弱点 是是明文字符明文字符和和密文字密文字符符有相同的有相同的使用频率使用频率,破译者可从统计出来的字符频率中找破译者可从统计出来的字符频率中找到规律

38、，进而找出破译的突破口。要克服这一缺陷，提高到规律，进而找出破译的突破口。要克服这一缺陷，提高保密程度就必须改变字符间的一一对应。保密程度就必须改变字符间的一一对应。1929年，希尔利用线性代数中的矩阵运算，打破了字符间的年，希尔利用线性代数中的矩阵运算，打破了字符间的对应关系，设计了一种被称为希尔密码的代数密码。为了便对应关系，设计了一种被称为希尔密码的代数密码。为了便于计算，希尔首先将字符变换成数，例如，对英文字母，我于计算，希尔首先将字符变换成数，例如，对英文字母，我们可以作如下变换：们可以作如下变换：ABC DE FG H I J K L M N O P Q R S T U V W X

39、 Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0将密文分成将密文分成 n个一组，用对应的数字代替，就变成了一个个一组，用对应的数字代替，就变成了一个 个个n维向量。如果取定一维向量。如果取定一 个个n阶的非奇异矩阶的非奇异矩 阵阵A（此矩阵为主（此矩阵为主要密钥），要密钥），用用A去乘每一向量，即可起到加密的效果，解密去乘每一向量，即可起到加密的效果，解密也不麻烦，将密文也分也不麻烦，将密文也分 成成n个一组，同样变换个一组，同样变换 成成n维向量，维向量，只需用去乘这些向量，即可将他们变回原先的明

40、文。只需用去乘这些向量，即可将他们变回原先的明文。定理定理1 ,若若 使得使得 (mod26)，则必有，则必有 =1，其，其中中 为为 与与26的最大公因子。的最大公因子。0 0,.,2 25 5 a a0,250,25a a1 11 1a aa aa aa a1 11 1g gc cd d a a,2 26 6 g gc cd d a a,2 26 6 a a证证 任取任取 0 0,.,2 25 5 p p，令，令q q2 26 6k ka ap p，于是，于是k k2 26 6a ap p2 26 6k k)(a ap pa aq qa aa ap pa a1 11 11 11 1，故，故

41、k k2 26 6a a1 1)p pa a(a a1 11 1，由，由p p的任意性可知必有的任意性可知必有 1 1a aa a1 1 (mod26)即即 1 12 26 6k ka aa a,k k1 1上式说明必有上式说明必有1 1g gc cd d a a,2 26 6，不然它将整，不然它将整 除除1，而这是不可能的。，而这是不可能的。在具体实施时在具体实施时，我们很快会发现一些困，我们很快会发现一些困难：难：(1)为了使数字与字符间可以互换，必须为了使数字与字符间可以互换，必须使用取自使用取自025之间的整数之间的整数 (2)由线性代数知识，由线性代数知识，其中，其中 为为A的伴随矩

42、阵。由于使用了除法，的伴随矩阵。由于使用了除法，在在 求求A的逆矩阵时可能会出现分数。不的逆矩阵时可能会出现分数。不解决这些困难，上述想法仍然无法实现。解决这些困难，上述想法仍然无法实现。解决的办法是引进同余运算，并用乘法解决的办法是引进同余运算，并用乘法来代替除法，（如同线性代数中用逆矩来代替除法，（如同线性代数中用逆矩阵代替矩阵除法一样）。阵代替矩阵除法一样）。d de et t(A A)A AA A1 1A A 此外，我们还不难证明这样的此外，我们还不难证明这样的1 1a a还是由还是由a a唯一确定的。事实上设有唯一确定的。事实上设有 1 12 26 6k ka aa a1 11 11

43、 1 和和 1 12 26 6k ka aa a2 21 12 2 )0 0,.,2 26 6 a a,(a a1 12 21 11 1则则 )k k2 26 6(k k)a aa a(a a2 21 11 12 21 11 1 故必有故必有2 21 1k kk k（也因为（也因为1 1g gc cd d a a,2 26 6），即），即1 12 21 11 1a aa a 由定理由定理1，026中除中除13以外的奇数均可取作这里的以外的奇数均可取作这里的a a，下表为经计算求得的逆元素，下表为经计算求得的逆元素 a a 1 3 5 7 9 11 15 17 19 21 23 251 1a a

44、 1 9 21 15 3 19 7 23 11 5 17 25例例1 取取a=3用希尔密码体系加密语句用希尔密码体系加密语句THANK YOU步步1 将将THANK YOU转换成转换成 （20，8，1，14，11，25，15，21）步步2 每一分量乘以每一分量乘以 3并关于并关于26取余得取余得 （8，24，3，16，7，23，19，11）密文为密文为HXCPG WSK现在我们已不难将方法推现在我们已不难将方法推 广到广到n为一般整数为一般整数的情况了的情况了,只需在乘法运算中结合应用取余，只需在乘法运算中结合应用取余，求逆矩阵时用逆元素相乘来代替除法即可。求逆矩阵时用逆元素相乘来代替除法即可

45、。例例2 取取A=则则 (具体求法见具体求法见后后),用用A加密加密THANK YOU,再用再用 对密文解密对密文解密 0 01 13 32 20 01 1A A1 19 98 81 1A A 8 82 20 01 14 41 12 25 51 11 12 21 11 15 5用矩阵用矩阵A左乘各向量加密（关左乘各向量加密（关 于于26取余）得取余）得 2410 163 239 115得到密文得到密文 JXCPI WEK 解解:(希尔密码加希尔密码加 密密)用相应数字代替字符，划分为两个元素一用相应数字代替字符，划分为两个元素一 组并表示为向量：组并表示为向量：（希尔密码解密希尔密码解密）用用

46、A-1左乘求得的向量，即可还原为原来的向量。左乘求得的向量，即可还原为原来的向量。(自行验证自行验证)希尔密码是以希尔密码是以矩阵矩阵 法法为基础的，明文与密文的对为基础的，明文与密文的对 应由应由n阶矩阶矩阵阵A确定。矩阵确定。矩阵A的阶数是事先约定的，与明文分组时每组字的阶数是事先约定的，与明文分组时每组字母的字母数量相同，如果明文所含字数母的字母数量相同，如果明文所含字数 与与n不匹配，则最后不匹配，则最后几个分量可任意补足。几个分量可任意补足。A-1的求法的求法方法方法1 利用公式利用公式 ，例如，若取，例如，若取 ，则则 ,(mod26)，即，即 方法方法2 利用高斯消去法。将矩利用

47、高斯消去法。将矩 阵阵(A,E)中的矩阵中的矩阵A消为消为E，则原先的则原先的E即被消成了即被消成了A-1，)det(1AAA 01A 323)det(A9)det(1 A 039A1 12 011A 98 如如 01 32，01 10(用用9乘第二行并取同乘第二行并取同 余余)01 12，01 90第一行减去第二行第一行减去第二行 的的2倍并取同余，得倍并取同余，得 01 10，01 98左端矩阵已化为单位阵，故右端矩阵即为左端矩阵已化为单位阵，故右端矩阵即为 A-1希尔密码系统的解密依赖于以下几把钥匙希尔密码系统的解密依赖于以下几把钥匙 （key）：）：Key1 矩阵矩阵A的阶数的阶数n，

48、即，即 明文是按几个字母来明文是按几个字母来 划分的。划分的。Key2 变换矩阵变换矩阵A，只有知，只有知 道了道了A才可能推算出才可能推算出Key3 明文和密文由字母表明文和密文由字母表 转换成转换成 n维向量所对维向量所对 应的非负整数表（上应的非负整数表（上 面，为方便起见，我面，为方便起见，我 们采用了字母的自然们采用了字母的自然 顺序）。顺序）。希尔密码体系为破译者设置了多道关口，加大了破译难度。破希尔密码体系为破译者设置了多道关口，加大了破译难度。破译和解密是两个不同的概念，虽然两者同样是希望对密文加以译和解密是两个不同的概念，虽然两者同样是希望对密文加以处理而得到明文的内容，但是

49、他们有一个最大的不处理而得到明文的内容，但是他们有一个最大的不 同同破破译密码时，解密必需用到的钥匙未能取得，破译密码的一方需译密码时，解密必需用到的钥匙未能取得，破译密码的一方需要依要依 据据密文的长度密文的长度，文字的本身特征文字的本身特征，以及，以及行文习惯行文习惯 等等各等等各方面的信息进行破译。破译密码虽然需要技术，但更加重要的方面的信息进行破译。破译密码虽然需要技术，但更加重要的是是“猜测猜测”的艺术。的艺术。“猜测猜测”的成功与否直接决定着破译的结的成功与否直接决定着破译的结果。果。破译希尔密码的关键是猜测文字被转换成成几维向量所、对应破译希尔密码的关键是猜测文字被转换成成几维向

50、量所、对应的字母表是怎样的，更为重要的是要设法获取加密矩的字母表是怎样的，更为重要的是要设法获取加密矩 阵阵A。（希尔密码的破译希尔密码的破译）由线性代数的知识可以知道，矩阵完全由线性代数的知识可以知道，矩阵完全由一组基的变换决定，对由一组基的变换决定，对 于于n阶矩阵阶矩阵A，只要猜出密文只要猜出密文 中中n个线性无关的向量个线性无关的向量 iiApq (i=1,2,n)对应的明文对应的明文(i=1,2,n)是什么是什么，即，即可确定可确定A，并将密码破译。，并将密码破译。得到密文 JXCPI WEK（1）当 时，其中W为一分量均大于零另一种移位 法采用将字母表中的字母平移若干位的方法来构造