基于线性代数与差分方程方法的模型.ppt

《基于线性代数与差分方程方法的模型.ppt》由会员分享，可在线阅读，更多相关《基于线性代数与差分方程方法的模型.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、更为可取？本章介绍建立一个离散模型是否更为可取？本章介绍的几个模型就是基于这种想法建立起来的。的几个模型就是基于这种想法建立起来的。4.1 状态转移问题状态转移问题 所谓状态转移问题讨论的是在一定的条件下，系统由一状态所谓状态转移问题讨论的是在一定的条件下，系统由一状态所谓状态转移问题讨论的是在一定的条件下，系统由一状态所谓状态转移问题讨论的是在一定的条件下，系统由一状态逐步转移到另一状态是否可能，如果可以转移的话，应如何逐步转移到另一状态是否可能，如果可以转移的话，应如何逐步转移到另一状态是否可能，如果可以转移的话，应如何逐步转移到另一状态是否可能，如果可以转移的话，应如何具体实现？具体实现

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

5、，而狗和米则在对岸。而狗和米则在对岸。（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)总共有十个可取状态，对一般情况，应找出状态为可取的充总共有

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

7、量与转移向量之间的运算。规定状态向量与规定一个状态向量与转移向量之间的运算。规定状态向量与规定一个状态向量与转移向量之间的运算。规定状态向量与规定一个状态向量与转移向量之间的运算。规定状态向量与转移向量之和为一新的状态向量，其运算为对应分量相加，转移向量之和为一新的状态向量，其运算为对应分量相加，转移向量之和为一新的状态向量，其运算为对应分量相加，转移向量之和为一新的状态向量，其运算为对应分量相加，且规定且规定且规定且规定0+0=00+0=0，1+0=0+1=11+0=0+1=1，1+1=01+1=0。在具体转移时，只考虑由可取状态到可取状态的转移。问题化在具体转移时，只考虑由可取状态到可取状

8、态的转移。问题化为：为：由由初始状态（初始状态（1，1，1，1）出发，经奇数次上述运算转化为（）出发，经奇数次上述运算转化为（0，0，0，0）的转移过程。）的转移过程。我们可以如下进行分析我们可以如下进行分析 ：（第一次渡河）（第一次渡河）（第二次渡河）（第二次渡河）以下可继续进行下去，直至转移目的实现。上述分析实际以下可继续进行下去，直至转移目的实现。上述分析实际上采用的是穷举法，对于规模较大的问题是不宜采用的。上采用的是穷举法，对于规模较大的问题是不宜采用的。例例4.2 夫妻过河问题夫妻过河问题这是一个古老的阿拉伯数学问题。有三对夫妻要这是一个古老的阿拉伯数学问题。有三对夫妻要过河，船最多

9、可载两人，约束条件是根据阿拉伯过河，船最多可载两人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不场的情况下与其法律，任一女子不得在其丈夫不场的情况下与其他男子在一起，问此时这三对夫妻能否过河？他男子在一起，问此时这三对夫妻能否过河？这一问题的状态和运算与这一问题的状态和运算与前一问题有所不同，根据前一问题有所不同，根据题意，状态应能反映出两题意，状态应能反映出两岸的男女人数，过河也同岸的男女人数，过河也同 样要反映出性别样要反映出性别 故可如下定义：故可如下定义：（i）可取状态可取状态：用用H和和W分别表示此岸的男子和分别表示此岸的男子和女子数，状态可用矢量女子数，状态可用矢量（H，W）表

10、示，其中表示，其中0H、W3。可取状态为（。可取状态为（0,i），），(i,i)，(3,i)，0i3。(i,i)为可取状态，这是因为总可以适为可取状态，这是因为总可以适当安排而使他们是当安排而使他们是 i对夫妻。对夫妻。（ii）可取运算可取运算：过河方式可以是一对夫妻、两个：过河方式可以是一对夫妻、两个男人或两个女人，当然也可以是一人过河。转移男人或两个女人，当然也可以是一人过河。转移向量可取成向量可取成(1)im,(1)in)，其中其中m、n可取可取0、1、2，但必须满足，但必须满足1m+n2。当。当j为奇数时表示为奇数时表示过河。过河。当当j为偶数时表示由对岸回来，运算规则同为偶数时表示由

11、对岸回来，运算规则同普通向量的加法。普通向量的加法。问题归结为由状态问题归结为由状态(3,3)经经奇数次奇数次可取运算，即由可取状可取运算，即由可取状态到可取状态的转移，转化态到可取状态的转移，转化 为为(0,0)的转移问题。和上题一样，的转移问题。和上题一样，我们既可以用计算机求解，也可以分析求解，此外，本题还可我们既可以用计算机求解，也可以分析求解，此外，本题还可用用作图作图方法来求解。方法来求解。在在HW平面坐标中，以平面坐标中，以“”表示可取状态，表示可取状态，从从A(3,3)经奇经奇数次转移到数次转移到 达达O(0,0)。奇数次。奇数次转移时向左或下移转移时向左或下移 动动1-2格而

12、格而落在一个可取状态上，落在一个可取状态上，偶数次偶数次转移时向右或上移转移时向右或上移 动动1-2格而落格而落在一个可取状态上。为了区分起见在一个可取状态上。为了区分起见 ,用用红红箭线表示箭线表示奇奇数次转数次转移，用移，用蓝蓝箭线表示第箭线表示第偶偶数数 次转移次转移,下图给出了一种可实现的方下图给出了一种可实现的方案案 ,故故 A(3,3)O(0,0)HW这这三三对夫妻是可以过河的对夫妻是可以过河的。假如按。假如按这样的方案过这样的方案过 河河,共需经过共需经过十一十一次次摆渡。摆渡。不难看出不难看出,在上述规则下在上述规则下,4对夫妻对夫妻就无法过河了就无法过河了,读者可以自行证明之

13、读者可以自行证明之.类似可以讨论船每次可载三人的情类似可以讨论船每次可载三人的情况况,其结果其结果 是是5对夫妻是可以过河的对夫妻是可以过河的,而而六六对以上时就对以上时就 无法过河无法过河了。了。4.2 密码的设计，解码与破译密码的设计，解码与破译 密码的设计和使用至少可从追溯到四千多年前的埃及密码的设计和使用至少可从追溯到四千多年前的埃及 ,巴巴比伦、罗马和希腊，历史极为久远比伦、罗马和希腊，历史极为久远 。古代古代隐藏信息的方法隐藏信息的方法 主要有两大类：主要有两大类：其一其一为为隐藏信息载体，采用隐写术隐藏信息载体，采用隐写术 等；等；其二其二为为变换信息载体，使之无法为一般人所理解

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

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

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

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

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

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

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

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

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

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

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

25、表：DEFGHIJKLMNOPQRTSUVWXYZABC因此因此 “THANK YOU”“WKDQN BRX”以上两种移位较易被人破译，为打破字母表中原有的顺序还可以上两种移位较易被人破译，为打破字母表中原有的顺序还可采用所谓路线加密法，即把明文字母表按某种既定的顺序安排采用所谓路线加密法，即把明文字母表按某种既定的顺序安排在一个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密在一个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密文表。文表。例如，对明文：例如，对明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以以7列矩阵表示如下：列矩

26、阵表示如下：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS再按事先约定的方式选出密文。例如，如按列选出，得到密再按事先约定的方式选出密文。例如，如按列选出，得到密文：文：touthyhrihueeysanahomndrifoorsszrnetjeed使用不同的顺序进行编写和选择，可以得到各种不同的路线使用不同的顺序进行编写和选择，可以得到各种不同的路线加密体制。对于同一明文消息矩阵，采用不同的抄写方式，加密体制。对于同一明文消息矩阵，采用不同的抄写方式，得到的密文也是不同的。得到的密文也是不同的。当明文超过规定矩阵的大小时，可以另加一矩阵。当需要加当明文超过规

27、定矩阵的大小时，可以另加一矩阵。当需要加密的字母数小于矩阵大小时，可以在矩阵中留空位或以无用密的字母数小于矩阵大小时，可以在矩阵中留空位或以无用的字母来填满矩阵。的字母来填满矩阵。移位法也可和代替法结合使用，并使用约定的单词或短语作移位法也可和代替法结合使用，并使用约定的单词或短语作密钥，以进一步加强保密性，这就密钥，以进一步加强保密性，这就 是是钥控列序加密钥控列序加密 法法。例如例如，用密钥单词，用密钥单词 construct对明文对明文MATHEMATICAL MODELING IS USEFUL加密：加密：CONSTRUCT 1 4 3 675 9 28MATHEMATICALMODE

28、LINGISUSEFU L 按混淆数的顺序选出各列，得到密文：按混淆数的顺序选出各列，得到密文：MCNLTLFTLIAAGMDSHMSEOSIIUAEE移位法的使用可重复多次，只进行一次移位加密的称为一移位法的使用可重复多次，只进行一次移位加密的称为一 次移位法次移位法，经多次移位的则称，经多次移位的则称 为为多次移位法多次移位法 代替法与移位法密码代替法与移位法密码 的的破译破译 对窃听到的密文进行分析时对窃听到的密文进行分析时 ，穷举法穷举法和和统计法统计法是最基本的是最基本的破译方法破译方法 。穷举分析法穷举分析法 就是对所有可能的密钥或明文进行逐一试探，就是对所有可能的密钥或明文进行逐

29、一试探，直至试探到直至试探到“正确正确”的为止。此的为止。此 方法方法需要事先知道密码体需要事先知道密码体制或加密算法制或加密算法（但不知道密钥或加密具体办法）。破译时需（但不知道密钥或加密具体办法）。破译时需将猜测到的明文和选定的密钥输入给算法，产生密文，再将将猜测到的明文和选定的密钥输入给算法，产生密文，再将该密文与窃听来的密文比较。如果相同，则认为该密钥就是该密文与窃听来的密文比较。如果相同，则认为该密钥就是所要求的，否则继续试探，直至破译。以英文字母为例，当所要求的，否则继续试探，直至破译。以英文字母为例，当已知对方在采用代替法加密时，如果使用穷举字母表来破译，已知对方在采用代替法加密

30、时，如果使用穷举字母表来破译，那么对于最简单的一种使用单字母表单字母单元代替法那么对于最简单的一种使用单字母表单字母单元代替法加密的密码，字母表的可能情况加密的密码，字母表的可能情况 有有26！种，可见，单纯地种，可见，单纯地使用穷举法，在实际应用中几乎是行不通的，只能与其它方使用穷举法，在实际应用中几乎是行不通的，只能与其它方法结合使用。法结合使用。统计法统计法是根据统计资料进行猜测的。在一段足够长且非特别是根据统计资料进行猜测的。在一段足够长且非特别专门化的文章中，字母的使用频率是比较稳定的。在某些技专门化的文章中，字母的使用频率是比较稳定的。在某些技术性或专门化文章中的字母使用频率可能有

31、微小变化。术性或专门化文章中的字母使用频率可能有微小变化。在上述两种加密方法中字母表中的字母是一一对应的，因此，在上述两种加密方法中字母表中的字母是一一对应的，因此，在截获的密文中各字母出现的概率提供了重要的密钥信息。根在截获的密文中各字母出现的概率提供了重要的密钥信息。根据权威资料报道，可以据权威资料报道，可以 将将26个英文字母按其出现的频率大小个英文字母按其出现的频率大小较合理地分为五组：较合理地分为五组：I.t,a,o,i,n,s,h,r;II.e;III.d,l;IV.c,u,m,w,f,g,y,p,b;V.v,k,j,x,q,z;不仅单个字母以相当稳定的频率出现，不仅单个字母以相当

32、稳定的频率出现，相邻字母对相邻字母对和和三字母三字母对对同样如此。同样如此。按按频率大小频率大小 将双字母排列如下：将双字母排列如下：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统计的章节越长，统计结统计的章节越长，统计结果就越可靠。对于只有几果就越可靠。对于只有几个单词的密文，统计是无个单词的密文

33、，统计是无意义的。意义的。下面介绍一下统计观察的三个结果：下面介绍一下统计观察的三个结果：a)单词单词the在这些统计中有重要的作用；在这些统计中有重要的作用；b)以以e，s，d，t为结尾的英语单词超过了一半；为结尾的英语单词超过了一半；c)以以t，a，s，w为起始字母的英语单词约为一半。为起始字母的英语单词约为一半。对于对于a)，如果，如果 将将the从明文中删除，那从明文中删除，那 么么t的频率将要降的频率将要降到第二组中其他字母之后，到第二组中其他字母之后，而而h将降到第三组中，并将降到第三组中，并 且且th和和he就不再是最众多的字母了。就不再是最众多的字母了。以上对英语统计的讨论是在

34、仅涉以上对英语统计的讨论是在仅涉 及及26个字母的假设条件个字母的假设条件下进行的。实际上消息的构成还包括间隔、标点、数字下进行的。实际上消息的构成还包括间隔、标点、数字等字符。总之，破译密码并不是件很容易的事。等字符。总之，破译密码并不是件很容易的事。2.希尔密码希尔密码代替密码与移位密码的一个致命弱点代替密码与移位密码的一个致命弱点 是是明文字符明文字符和和密文字密文字符符有相同的有相同的使用频率使用频率,破译者可从统计出来的字符频率中找破译者可从统计出来的字符频率中找到规律，进而找出破译的突破口。要克服这一缺陷，提高保到规律，进而找出破译的突破口。要克服这一缺陷，提高保密程度就必须改变字

35、符间的一一对应。密程度就必须改变字符间的一一对应。1929年，希尔利用线性代数中的矩阵运算，打破了字符间的年，希尔利用线性代数中的矩阵运算，打破了字符间的对应关系，设计了一种被称为希尔密码的代数密码。为了便对应关系，设计了一种被称为希尔密码的代数密码。为了便于计算，希尔首先将字符变换成数，例如，对英文字母，我于计算，希尔首先将字符变换成数，例如，对英文字母，我们可以作如下变换：们可以作如下变换：ABC DE FG H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

36、 22 23 24 25 0将密文分成将密文分成 n个一组，用对应的数字代替，就变成了一个个一组，用对应的数字代替，就变成了一个 个个n维向量。如果取定一维向量。如果取定一 个个n阶的非奇异矩阶的非奇异矩 阵阵A（此矩阵为主要（此矩阵为主要密钥），密钥），用用A去乘每一向量，即可起到加密的效果，解密也去乘每一向量，即可起到加密的效果，解密也不麻烦，将密文也分不麻烦，将密文也分 成成n个一组，同样变换个一组，同样变换 成成n维向量，只维向量，只需用去乘这些向量，即可将他们变回原先的明文。需用去乘这些向量，即可将他们变回原先的明文。定理定理1 ,若若 使得使得 (mod26)，则必有，则必有 =1

37、，其，其中中 为为 与与26的最大公因子。的最大公因子。证证任取任取，令，令，于是，于是，故，故，由，由的任意性可知必有的任意性可知必有 (mod26)即即 上式上式说说明必有明必有，不然它将整，不然它将整除除1，而，而这这是不可能的。是不可能的。在具体实施时在具体实施时，我们很快会发现一些困，我们很快会发现一些困难：难：(1)为了使数字与字符间可以互换，必须为了使数字与字符间可以互换，必须使用取自使用取自025之间的整数之间的整数 (2)由线性代数知识，由线性代数知识，其中，其中 为为A的伴随矩阵。由于使用了除法，的伴随矩阵。由于使用了除法，在在 求求A的逆矩阵时可能会出现分数。不的逆矩阵时

38、可能会出现分数。不解决这些困难，上述想法仍然无法实现。解决这些困难，上述想法仍然无法实现。解决的办法是引进同余运算，并用乘法解决的办法是引进同余运算，并用乘法来代替除法，（如同线性代数中用逆矩来代替除法，（如同线性代数中用逆矩阵代替矩阵除法一样）。阵代替矩阵除法一样）。此外，我此外，我们还们还不不难证难证明明这样这样的的还还是由是由唯一确定的。事唯一确定的。事实实上上设设有有和和 则则故必有故必有（也因（也因为为），即），即由定理由定理1，026中除中除13以外的奇数均可取作以外的奇数均可取作这这里的里的，下表，下表为经计为经计算求得的逆元素算求得的逆元素1357911151719212325

39、1921153197231151725例例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为一般整数为一般整数的情况了的情况了,只需在乘法运算中结合应用取余，只需在乘法运算中结合应用取余，求逆矩阵时用逆元素相乘来代替除法即可。求逆矩阵时用逆元素相乘来代替除法即可。例例2 取取A=则则

40、(具体求法见具体求法见后后),用用A加密加密THANK YOU,再用再用 对密文解密对密文解密 用矩用矩阵阵A左乘各向量加密（关左乘各向量加密（关于于26取余）得取余）得 得到密文得到密文JXCPIWEK解解:(希希尔尔密密码码加加密密)用相用相应应数字代替字符，划分数字代替字符，划分为为两个元素一两个元素一组组并表示并表示为为向量：向量：（希尔密码解密希尔密码解密）用用A-1左乘求得的向量，即可还原为原来的向量。左乘求得的向量，即可还原为原来的向量。(自行验证自行验证)希尔密码是以希尔密码是以矩阵矩阵 法法为基础的，明文与密文的对为基础的，明文与密文的对 应由应由n阶矩阶矩阵阵A确定。矩阵确

41、定。矩阵A的阶数是事先约定的，与明文分组时每组字的阶数是事先约定的，与明文分组时每组字母的字母数量相同，如果明文所含字数母的字母数量相同，如果明文所含字数 与与n不匹配，则最后不匹配，则最后几个分量可任意补足。几个分量可任意补足。A-1的求法的求法方法方法1 利用公式利用公式 ，例如，若取，例如，若取 ，则则 ,(mod26)，即，即 方法方法2 利用高斯消去法。将矩利用高斯消去法。将矩 阵阵(A,E)中的矩阵中的矩阵A消为消为E，则原先的则原先的E即被消成了即被消成了A-1，如如 ，(用用9乘第二行并取同乘第二行并取同 余余)，第一行减去第二行第一行减去第二行 的的2倍并取同余，得倍并取同余

42、，得 ，左端矩阵已化为单位阵，故右端矩阵即为左端矩阵已化为单位阵，故右端矩阵即为 A-1希尔密码系统的解密依赖于以下几把钥匙希尔密码系统的解密依赖于以下几把钥匙 （key）：）：Key1 矩阵矩阵A的阶数的阶数n，即，即 明文是按几个字母来明文是按几个字母来 划分的。划分的。Key2 变换矩阵变换矩阵A，只有知，只有知 道了道了A才可能推算出才可能推算出Key3 明文和密文由字母表明文和密文由字母表 转换成转换成 n维向量所对维向量所对 应的非负整数表（上应的非负整数表（上 面，为方便起见，我面，为方便起见，我 们采用了字母的自然们采用了字母的自然 顺序）。顺序）。希尔密码体系为破译者设置了多

43、道关口，加大了破译难度。破希尔密码体系为破译者设置了多道关口，加大了破译难度。破译和解密是两个不同的概念，虽然两者同样是希望对密文加以译和解密是两个不同的概念，虽然两者同样是希望对密文加以处理而得到明文的内容，但是他们有一个最大的不处理而得到明文的内容，但是他们有一个最大的不 同同破破译密码时，解密必需用到的钥匙未能取得，破译密码的一方需译密码时，解密必需用到的钥匙未能取得，破译密码的一方需要依要依 据据密文的长度密文的长度，文字的本身特征文字的本身特征，以及，以及行文习惯行文习惯 等等各等等各方面的信息进行破译。破译密码虽然需要技术，但更加重要的方面的信息进行破译。破译密码虽然需要技术，但更

44、加重要的是是“猜测猜测”的艺术。的艺术。“猜测猜测”的成功与否直接决定着破译的结的成功与否直接决定着破译的结果。果。破译希尔密码的关键是猜测文字被转换成成几维向量所、对应破译希尔密码的关键是猜测文字被转换成成几维向量所、对应的字母表是怎样的，更为重要的是要设法获取加密矩的字母表是怎样的，更为重要的是要设法获取加密矩 阵阵A。（希尔密码的破译希尔密码的破译）由线性代数的知识可以知道，矩阵完全由线性代数的知识可以知道，矩阵完全由一组基的变换决定，对由一组基的变换决定，对 于于n阶矩阵阶矩阵A，只要猜出密文，只要猜出密文 中中n个线性无关的向量个线性无关的向量(i=1,2,n)对应的明文对应的明文(

45、i=1,2,n)是什么是什么，即，即可确定可确定A，并将密码破译。，并将密码破译。在实际计算中，可以利用以下方法：在实际计算中，可以利用以下方法：令令则则，取矩阵取矩阵Q|P,经过一系列初等行变换，将由密文决定经过一系列初等行变换，将由密文决定 的的n维矩阵维矩阵Q化为化为n阶单位阵阶单位阵 I的时候，由明文决定的矩的时候，由明文决定的矩 阵阵P自自动化为动化为(A-1)T，即，即：例例5 有密文如下有密文如下:goqbxcbuglosnfal;根据英文的行根据英文的行文习惯以及获取密码的途径和背景，猜测是两个字文习惯以及获取密码的途径和背景，猜测是两个字母为一组的希尔密码，前四个明文字母母为

46、一组的希尔密码，前四个明文字母 是是dear，试破译这段秘文。试破译这段秘文。解解：前两组明文字前两组明文字 母母de和和ar 对应的二维向量是：对应的二维向量是：按同一对应整数表，密文中对应这两组的二维向量是：按同一对应整数表，密文中对应这两组的二维向量是：，由此可得由此可得，对应上例则有，对应上例则有 ,利用这一逆矩阵，可对截获密文进行解密，破译出的电文是利用这一逆矩阵，可对截获密文进行解密，破译出的电文是Dear Mac God forbid.这只是对最简单情况进行的举例，如果加密矩阵的阶数大于这只是对最简单情况进行的举例，如果加密矩阵的阶数大于2，需要的密文应该有较长长度，所需的计算量

47、也是很大的。破，需要的密文应该有较长长度，所需的计算量也是很大的。破译的关键是猜译的关键是猜 中中n及及n个独立的个独立的n维向量，其后求解加密矩阵维向量，其后求解加密矩阵的计算量仅为的计算量仅为 O(n2)。希尔密码体制中有两个要素非常重要：希尔密码体制中有两个要素非常重要：第一第一是字母是字母 与与n维向量进行转换所依维向量进行转换所依据的非负整数表，本节中所举的是最据的非负整数表，本节中所举的是最自然的情况；当然如果依据其它的整自然的情况；当然如果依据其它的整数表也是完全可以进行的，其情况将数表也是完全可以进行的，其情况将会更复杂一些，破译的难度就会增大。会更复杂一些，破译的难度就会增大

48、。第二第二个要素是加密矩阵，如何定义、个要素是加密矩阵，如何定义、求解这个矩阵对于密码的加密和破译求解这个矩阵对于密码的加密和破译更加关键。唯一的要求是加密时应选更加关键。唯一的要求是加密时应选择行列式值与择行列式值与 26无公因子的矩阵。无公因子的矩阵。RSA公开密钥体制公开密钥体制 传统的密码通讯只能在事先约定的双方间进行，双方必须掌传统的密码通讯只能在事先约定的双方间进行，双方必须掌握相同的密钥，而密钥的传送必须使用另外握相同的密钥，而密钥的传送必须使用另外 的的“安全信道安全信道”。这样如果要使。这样如果要使 n个用户都能够秘密的交换信息，则每个个用户都能够秘密的交换信息，则每个用户将

49、需要用个密钥，这种巨大的密钥量给密钥的分配与管用户将需要用个密钥，这种巨大的密钥量给密钥的分配与管理带来了极大的困难；此外在有些情况下，事先约定密钥还理带来了极大的困难；此外在有些情况下，事先约定密钥还是不可能的。是不可能的。公开密钥体制的提出就是为了从根本上解决上述问题公开密钥体制的提出就是为了从根本上解决上述问题 。其其基本思想基本思想是：是：把密钥划分为公开密钥和秘密密钥两部分把密钥划分为公开密钥和秘密密钥两部分 ,两两者互为逆变换，但几乎不可能从公开密钥推出秘密密钥者互为逆变换，但几乎不可能从公开密钥推出秘密密钥 .每每个使用者均有自己的公开及秘密密钥。个使用者均有自己的公开及秘密密钥

50、。虽然只要能解密的密文，从理论上讲虽然只要能解密的密文，从理论上讲都是可破译的，但如果破译所需要都是可破译的，但如果破译所需要 的工作量过大，要求花费的时间过的工作量过大，要求花费的时间过 长，以致超过了保密期限，则该密长，以致超过了保密期限，则该密 码系统应当被认为是安全可靠的。码系统应当被认为是安全可靠的。定义定义1 设设n为一正整数，将小为一正整数，将小 于于n且与且与n互素的正整数个数互素的正整数个数记为记为(n)，称之为欧拉（称之为欧拉（Euler L.）函数。函数。不难证明：若不难证明：若 p，q为两个相异素数，为两个相异素数，n=pq，则，则 (n)=(p-1)(q-1)令令p,