基于线性代数与差分方程方法的模型省公共课一等奖全国赛课获奖课件.pptx

第四章第四章第四章第四章 基于线性代数方法数学模型基于线性代数方法数学模型浙江大学数学建模浙江大学数学建模 实践基地实践基地第1页基于线性代数与基于线性代数与 差分方程方法模型差分方程方法模型 在第三章中，我们有多处对不连续改变变量采取了连续化在第三章中，我们有多处对不连续改变变量采取了连续化方法，从而建立了对应微分方程模型。不过因为以下原因：方法，从而建立了对应微分方程模型。不过因为以下原因：第一第一，有时变量实际上只能取自一个有限集合；，有时变量实际上只能取自一个有限集合；第二第二，有时采取连续化方法后建立模型比较复杂，无法求，有时采取连续化方法后建立模型比较复杂，无法求出问题解，从而只能求它们数值解。也就是说，在建模时出问题解，从而只能求它们数值解。也就是说，在建模时我们对离散变量作了连续化处理，而在求解时，又对连续我们对离散变量作了连续化处理，而在求解时，又对连续变量作了离散化处理，使之重新变为离散变量。所以采取变量作了离散化处理，使之重新变为离散变量。所以采取连续化方法效果有时并不很好，因而是不可取。连续化方法效果有时并不很好，因而是不可取。电子计算机广泛应用为我们处理大量信息提电子计算机广泛应用为我们处理大量信息提供了实现可能，这就十分自然地提出了一个供了实现可能，这就十分自然地提出了一个问题，对含有离散变量实际问题直接建立一问题，对含有离散变量实际问题直接建立一个离散模型是否更为可取？本章介绍几个模个离散模型是否更为可取？本章介绍几个模型就是基于这种想法建立起来。型就是基于这种想法建立起来。第2页4.1 状态转移问题状态转移问题 所谓状态转移问题讨论是在一定条件下，系统由一状态所谓状态转移问题讨论是在一定条件下，系统由一状态所谓状态转移问题讨论是在一定条件下，系统由一状态所谓状态转移问题讨论是在一定条件下，系统由一状态逐步转移到另一状态是否可能，假如能够转移话，应怎样逐步转移到另一状态是否可能，假如能够转移话，应怎样逐步转移到另一状态是否可能，假如能够转移话，应怎样逐步转移到另一状态是否可能，假如能够转移话，应怎样详细实现？详细实现？详细实现？详细实现？例例4.1 人、狗、鸡、米过河问题人、狗、鸡、米过河问题 这是一个人所共知而又十分简单智力游戏。某人要带狗、鸡、这是一个人所共知而又十分简单智力游戏。某人要带狗、鸡、米过河，但小船除需要人划外，最多只能载一物过河，而当米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应怎样过河。人不在场时，狗要咬鸡、鸡要吃米，问此人应怎样过河。在本问题中，可采取以下方法：一物在此岸时对应分量为在本问题中，可采取以下方法：一物在此岸时对应分量为1，而在彼岸时则取而在彼岸时则取 为为0，比如，比如（1,0,1,0）表示人和鸡在此岸，表示人和鸡在此岸，而狗和米则在对岸。而狗和米则在对岸。第3页（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)总共有十个可取状态，对普通情况，应找出状态为可取充要总共有十个可取状态，对普通情况，应找出状态为可取充要条件。条件。（ii）可取运算可取运算：状态转移需经状态运算来实现。在实际问题：状态转移需经状态运算来实现。在实际问题中，摆一次渡即可改变现有状态。为此也引入一个四维向量中，摆一次渡即可改变现有状态。为此也引入一个四维向量（转移向量），用它来反应摆渡情况。比如（转移向量），用它来反应摆渡情况。比如（1，1，0，0）表示人带狗摆渡过河。依据题意，允许使用转移向量只能有表示人带狗摆渡过河。依据题意，允许使用转移向量只能有（1，0，0，0，）、（，）、（1，1，0，0）、（）、（1，0，1，0）、）、（1，0，0，1）四个。）四个。第4页要求一个状态向量与转移向量之间运算。要求状态向量与要求一个状态向量与转移向量之间运算。要求状态向量与要求一个状态向量与转移向量之间运算。要求状态向量与要求一个状态向量与转移向量之间运算。要求状态向量与转移向量之和为一新状态向量，其运算为对应分量相加，转移向量之和为一新状态向量，其运算为对应分量相加，转移向量之和为一新状态向量，其运算为对应分量相加，转移向量之和为一新状态向量，其运算为对应分量相加，且要求且要求且要求且要求0+0=00+0=0，1+0=0+1=11+0=0+1=1，1+1=01+1=0。在详细转移时，只考虑由可取状态到可取状态转移。问题化为：在详细转移时，只考虑由可取状态到可取状态转移。问题化为：由初始状态（由初始状态（1，1，1，1）出发，经奇数次上述运算转化为）出发，经奇数次上述运算转化为（0，0，0，0）转移过程。）转移过程。我们能够以下进行分析我们能够以下进行分析 ：（第一次渡河）（第一次渡河）第5页（第二次渡河）（第二次渡河）以下可继续进行下去，直至转移目标实现。上述分析实际以下可继续进行下去，直至转移目标实现。上述分析实际上采取是穷举法，对于规模较大问题是不宜采取。上采取是穷举法，对于规模较大问题是不宜采取。第6页例例4.2 夫妻过河问题夫妻过河问题这是一个古老阿拉伯数学问题。有三对夫妻要过这是一个古老阿拉伯数学问题。有三对夫妻要过河，船最多可载两人，约束条件是依据阿拉伯法河，船最多可载两人，约束条件是依据阿拉伯法律，任一女子不得在其丈夫不场情况下与其它男律，任一女子不得在其丈夫不场情况下与其它男子在一起，问此时这三对夫妻能否过河？子在一起，问此时这三对夫妻能否过河？这一问题状态和运算与前这一问题状态和运算与前一问题有所不一样，依据一问题有所不一样，依据题意，状态应能反应出两题意，状态应能反应出两岸男女人数，过河也同岸男女人数，过河也同 样样要反应出性别要反应出性别 故能够下定义：故能够下定义：（i）可取状态可取状态：用用H和和W分别表示此岸男子和女分别表示此岸男子和女子数，状态可用矢量子数，状态可用矢量（H，W）表示，其中表示，其中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为偶数时表示由对岸回来，运算规则同为偶数时表示由对岸回来，运算规则同普通向量加法。普通向量加法。第7页 问题归结为由状态问题归结为由状态(3,3)经经奇数次奇数次可取运算，即由可取状可取运算，即由可取状态到可取状态转移，转化态到可取状态转移，转化 为为(0,0)转移问题。和上题一样，我转移问题。和上题一样，我们既能够用计算机求解，也能够分析求解，另外，本题还可用们既能够用计算机求解，也能够分析求解，另外，本题还可用作图作图方法来求解。方法来求解。在在HW平面坐标中，以平面坐标中，以“”表示可取状态，表示可取状态，从从A(3,3)经奇经奇数次转移到数次转移到 达达O(0,0)。奇数次。奇数次转移时向左或下移转移时向左或下移 动动1-2格而格而落在一个可取状态上，落在一个可取状态上，偶数次偶数次转移时向右或上移转移时向右或上移 动动1-2格而落格而落在一个可取状态上。为了区分起见在一个可取状态上。为了区分起见 ,用用红红箭线表示箭线表示奇奇数次转数次转移，用移，用蓝蓝箭线表示第箭线表示第偶偶数数 次转移次转移,下列图给出了一个可实现方下列图给出了一个可实现方案案 ,故故 A(3,3)O(0,0)HW这这三三对夫妻是能够过河对夫妻是能够过河。假如按这。假如按这么方案过么方案过 河河,共需经过共需经过十一十一次摆渡。次摆渡。不难看出不难看出,在上述规则下在上述规则下,4对夫妻对夫妻就无法过河了就无法过河了,读者能够自行证实之读者能够自行证实之.类似能够讨论船每次可载三人情况类似能够讨论船每次可载三人情况,其结果其结果 是是5对夫妻是能够过河对夫妻是能够过河,而而六六对以上时就对以上时就 无法过河无法过河了。了。第8页4.2 密码设计，解码与破译密码设计，解码与破译 密码设计和使用最少可从追溯到四千多年前埃及密码设计和使用最少可从追溯到四千多年前埃及 ,巴比伦、巴比伦、罗马和希腊，历史极为久远罗马和希腊，历史极为久远 。古代古代隐藏信息方法隐藏信息方法 主要有两主要有两大类：大类：其一其一为为隐藏信息载体，采取隐写术隐藏信息载体，采取隐写术 等；等；其二其二为为变换信息载体，使之无法为普通人所了解变换信息载体，使之无法为普通人所了解 。在密码学中，信息代码被称为在密码学中，信息代码被称为 密码密码，加密，加密前信息被称为前信息被称为 明文明文，经加密后不为常人所，经加密后不为常人所了解用密码表示信息被称为了解用密码表示信息被称为 密文密文(ciphertext)，将明文转变成密文过程被称，将明文转变成密文过程被称为为加密加密(enciphering)，其逆过程则被称为，其逆过程则被称为解密解密(deciphering)，而用以加密、解密方，而用以加密、解密方法或算法则被称为法或算法则被称为 密码体制密码体制(crytosystem)。第9页记全体明文组成集合记全体明文组成集合 为为U，全体密文组成集合，全体密文组成集合 为为V，称，称U为明为明文空间，文空间，V为密文空间。加密常利用某一被称为密钥东西来实为密文空间。加密常利用某一被称为密钥东西来实现，它通常取自于一个被称为密钥空间含有若干参数集合现，它通常取自于一个被称为密钥空间含有若干参数集合K。按数学观点来看，加密与解密均可被看成是一个变换：取一按数学观点来看，加密与解密均可被看成是一个变换：取一kK，uU，令，令 ，v为明文为明文u在密钥在密钥K下下密文，而解码则要用密文，而解码则要用 到到K逆变换逆变换K-1，。由此可见，密码体系，。由此可见，密码体系即使能够千姿百态，但其关键还在即使能够千姿百态，但其关键还在 于于密钥选取密钥选取。伴随计算机与网络技术迅猛发展，大量各具特色密码体系不停伴随计算机与网络技术迅猛发展，大量各具特色密码体系不停涌现。离散数学、数论、计算复杂性、混沌、涌现。离散数学、数论、计算复杂性、混沌、，许多相当，许多相当高深数学知识都被用上，逐步形成了（并仍在快速发展）含有高深数学知识都被用上，逐步形成了（并仍在快速发展）含有广泛应用面广泛应用面 当代密码学当代密码学。第10页 早期密码早期密码 替换密码替换密码 移位密码移位密码 代数密码代数密码 第11页代替法密码代替法密码采取另一个字母表中字母来代替明文中字母，明采取另一个字母表中字母来代替明文中字母，明文字母与密文字母保持一一对应关系，但采取符号改变了。文字母与密文字母保持一一对应关系，但采取符号改变了。加密时，把明文换成密文，即将明文中字母用密文字母表中加密时，把明文换成密文，即将明文中字母用密文字母表中对应位置上字母取代。解密时，则把密文换成明文，即把密对应位置上字母取代。解密时，则把密文换成明文，即把密文中字母用明文字母表中对应位置上字母代回，解密过程是文中字母用明文字母表中对应位置上字母代回，解密过程是加密过程逆过程。在代替法加密过程中，密文字母表即代替加密过程逆过程。在代替法加密过程中，密文字母表即代替法密钥，密钥能够是标准字母表，也能够是任意建立。法密钥，密钥能够是标准字母表，也能够是任意建立。1.代替法密码代替法密码明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJ密钥惯用一密钥单词或密钥短语生成混同字母表。密钥单词密钥惯用一密钥单词或密钥短语生成混同字母表。密钥单词 或密钥短语能够存放在识别码、通行字或密钥秘密表格中。或密钥短语能够存放在识别码、通行字或密钥秘密表格中。第12页混合一个字母表，常见有两种方法，这两种方法都采取了一混合一个字母表，常见有两种方法，这两种方法都采取了一个个密钥单词密钥单词或一个或一个密钥短语密钥短语。方法方法1：a)选择一个密钥单词或密钥短语，比如：选择一个密钥单词或密钥短语，比如：constructb)去掉其中重复字母，得：去掉其中重复字母，得：construc)在修改后密钥后面接上从标准字母表中去掉密钥中已经有字在修改后密钥后面接上从标准字母表中去掉密钥中已经有字母后剩下字母，得：母后剩下字母，得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZ在设计密钥时，也可在明文字母表中选择一个特定字母，然后在设计密钥时，也可在明文字母表中选择一个特定字母，然后从该特定字母开始写密钥单词将密钥单词隐藏于其中。比如，从该特定字母开始写密钥单词将密钥单词隐藏于其中。比如，对于上例，选取特定字对于上例，选取特定字 母母 k k，则可得：，则可得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ 第13页方法方法2 2：a)a)选择一个密钥单词或密钥短语，比如：选择一个密钥单词或密钥短语，比如：constructconstructb)b)去掉其中重复字母，得：去掉其中重复字母，得：construconstruc)c)这些字母组成矩阵第一行，矩阵后续各行由标准字母表中这些字母组成矩阵第一行，矩阵后续各行由标准字母表中去掉密钥单词字母后剩下字母组成去掉密钥单词字母后剩下字母组成d)d)将所得矩阵中字母按列次序排出将所得矩阵中字母按列次序排出 得：得：cugmyoahpznbiqsdjvrtekwrflx按照此方法产生字母表称为按照此方法产生字母表称为 混同字母表混同字母表。还能够使用还能够使用混同数混同数。混同数由以下方法产生：。混同数由以下方法产生：a)选一密钥单词或密钥短语，比如：选一密钥单词或密钥短语，比如：constructb)按照这些字母在标准字母表中出现相对次序给它们编号，对按照这些字母在标准字母表中出现相对次序给它们编号，对序列中重复字母则自左向右编号，得序列中重复字母则自左向右编号，得 ：construct 143675928c)自左向右选出这些数自左向右选出这些数 字字,得到一个混同数字得到一个混同数字 组组:143675928，混同字母表由从小到大次序取矩阵中对应列得出。混同字母表由从小到大次序取矩阵中对应列得出。为增加保密性，在使用为增加保密性，在使用代替法时还可利用一些代替法时还可利用一些其它技巧，如单字母表其它技巧，如单字母表对多字母表、单字母对对多字母表、单字母对多字母、多重代替等。多字母、多重代替等。第14页2.移位密码体制移位密码体制移位密码移位密码采取移位法进行加密，明文中字母重新排列，本身采取移位法进行加密，明文中字母重新排列，本身不变，只是位置改变了。不变，只是位置改变了。早在早在4000多年前，古希腊人就用一个名多年前，古希腊人就用一个名 叫叫“天书天书”器械来器械来加密消息。该密码器械是用一条窄长草纸缠绕在一个直径确加密消息。该密码器械是用一条窄长草纸缠绕在一个直径确定圆筒上，明文逐行横写在纸带上，当取下纸带时，字母次定圆筒上，明文逐行横写在纸带上，当取下纸带时，字母次序就被打乱了，消息得以隐蔽。收方阅读消息时，要将纸带序就被打乱了，消息得以隐蔽。收方阅读消息时，要将纸带重新绕在直径与原来相同圆筒上，才能看到正确消息。在这重新绕在直径与原来相同圆筒上，才能看到正确消息。在这里圆筒直径起到了密钥作用。里圆筒直径起到了密钥作用。另一个移位另一个移位 法法采取将字母表中字母平移若干位方法来结构密文采取将字母表中字母平移若干位方法来结构密文字母表，传说这类方法是由古罗马皇帝凯撒最早使用，故这种字母表，传说这类方法是由古罗马皇帝凯撒最早使用，故这种密文字母表被称为凯撒字母表。比如，如用将字母表向右平移密文字母表被称为凯撒字母表。比如，如用将字母表向右平移3位方法来结构密文字母表，可位方法来结构密文字母表，可 得：得：明文字母表明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表：DEFGHIJKLMNOPQRTSUVWXYZABC所以所以 “THANK YOU”“WKDQN BRX”以上两种移位较易被人破译，为打破字母表中原有次序还可采以上两种移位较易被人破译，为打破字母表中原有次序还可采取所谓路线加密法，即把明文字母表按某种既定次序安排在一取所谓路线加密法，即把明文字母表按某种既定次序安排在一个矩阵中，然后用另一个次序选出矩阵中字母来产生密文表。个矩阵中，然后用另一个次序选出矩阵中字母来产生密文表。第15页比如，对明文：比如，对明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以以7列矩阵表示以下：列矩阵表示以下：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS再按事先约定方式选出密文。比如，如按列选出，得到密文：再按事先约定方式选出密文。比如，如按列选出，得到密文：touthyhrihueeysanahomndrifoorsszrnetjeed使用不一样次序进行编写和选择，能够得到各种不一样路线使用不一样次序进行编写和选择，能够得到各种不一样路线加密体制。对于同一明文消息矩阵，采取不一样誊录方式，加密体制。对于同一明文消息矩阵，采取不一样誊录方式，得到密文也是不一样。得到密文也是不一样。当明文超出要求矩阵大小时，能够另加一矩阵。当需要加密当明文超出要求矩阵大小时，能够另加一矩阵。当需要加密字母数小于矩阵大小时，能够在矩阵中留空位或以无用字母字母数小于矩阵大小时，能够在矩阵中留空位或以无用字母来填满矩阵。来填满矩阵。第16页移位法也可和代替法结合使用，并使用约定单词或短语作密移位法也可和代替法结合使用，并使用约定单词或短语作密钥，以深入加强保密性，这就钥，以深入加强保密性，这就 是是钥控列序加密钥控列序加密 法法。比如比如，用密钥单词，用密钥单词 construct对明文对明文MATHEMATICAL MODELING IS USEFUL加密：加密：CONSTRUCT 1 4 3 675 9 28MATHEMATICALMODELINGISUSEFU L 按混同数次序选出各列，得到密文：按混同数次序选出各列，得到密文：MCNLTLFTLIAAGMDSHMSEOSIIUAEE移位法使用可重复屡次，只进行一次移位加密称为一移位法使用可重复屡次，只进行一次移位加密称为一 次移次移位法位法，经屡次移位则称，经屡次移位则称 为为屡次移位法屡次移位法 第17页代替法与移位法密码代替法与移位法密码 破译破译 对窃听到密文进行分析时对窃听到密文进行分析时 ，穷举法穷举法和和统计法统计法是最基本破译是最基本破译方法方法 。穷举分析法穷举分析法 就是对全部可能密钥或明文进行逐一试探，直就是对全部可能密钥或明文进行逐一试探，直至试探到至试探到“正确正确”为止。此为止。此 方法方法需要事先知道密码体制或需要事先知道密码体制或加密算法加密算法（但不知道密钥或加密详细方法）。破译时需将猜（但不知道密钥或加密详细方法）。破译时需将猜测到明文和选定密钥输入给算法，产生密文，再将该密文与测到明文和选定密钥输入给算法，产生密文，再将该密文与窃听来密文比较。假如相同，则认为该密钥就是所要求，不窃听来密文比较。假如相同，则认为该密钥就是所要求，不然继续试探，直至破译。以英文字母为例，当已知对方在采然继续试探，直至破译。以英文字母为例，当已知对方在采取代替法加密时，假如使用穷举字母表来破译，那么对于最取代替法加密时，假如使用穷举字母表来破译，那么对于最简单一个使用单字母表单字母单元代替法加密密码，字简单一个使用单字母表单字母单元代替法加密密码，字母表可能情况母表可能情况 有有26！种，可见，单纯地使用穷举法，在实种，可见，单纯地使用穷举法，在实际应用中几乎是行不通，只能与其它方法结合使用。际应用中几乎是行不通，只能与其它方法结合使用。第18页统计法统计法是依据统计资料进行猜测。在一段足够长且非尤其专是依据统计资料进行猜测。在一段足够长且非尤其专门化文章中，字母使用频率是比较稳定。在一些技术性或专门化文章中，字母使用频率是比较稳定。在一些技术性或专门化文章中字母使用频率可能有微小改变。门化文章中字母使用频率可能有微小改变。在上述两种加密方法中字母表中字母是一一对应，所以，在截在上述两种加密方法中字母表中字母是一一对应，所以，在截获密文中各字母出现概率提供了主要密钥信息。依据权威资料获密文中各字母出现概率提供了主要密钥信息。依据权威资料报道，能够报道，能够 将将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;不但单个字母以相当稳定频率出现，不但单个字母以相当稳定频率出现，相邻字母对相邻字母对和和三字母对三字母对一样如此。一样如此。第19页按按频率大小频率大小 将双字母排列以下：将双字母排列以下：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统计章节越长，统计结果统计章节越长，统计结果就越可靠。对于只有几个就越可靠。对于只有几个单词密文，统计是无意义。单词密文，统计是无意义。下面介绍一下统计观察三个结果：下面介绍一下统计观察三个结果：a)单词单词the在这些统计中有主要作用；在这些统计中有主要作用；b)以以e，s，d，t为结尾英语单词超出了二分之一；为结尾英语单词超出了二分之一；c)以以t，a，s，w为起始字母英语单词约为二分之一。为起始字母英语单词约为二分之一。对于对于a)，假如，假如 将将the从明文中删除，那从明文中删除，那 么么t频率将要降到频率将要降到第二组中其它字母之后，第二组中其它字母之后，而而h将降到第三组中，并将降到第三组中，并 且且th和和he就不再是最众多字母了。就不再是最众多字母了。以上对英语统计讨论是在仅涉以上对英语统计讨论是在仅涉 及及26个字母假设条件下进个字母假设条件下进行。实际上消息组成还包含间隔、标点、数字等字符。行。实际上消息组成还包含间隔、标点、数字等字符。总之，破译密码并不是件很轻易事。总之，破译密码并不是件很轻易事。第20页2.希尔密码希尔密码代替密码与移位密码一个致命弱点代替密码与移位密码一个致命弱点 是是明文字符明文字符和和密文字符密文字符有相同有相同使用频率使用频率,破译者可从统计出来字符频率中找到规律，破译者可从统计出来字符频率中找到规律，进而找出破译突破口。要克服这一缺点，提升保密程度就必进而找出破译突破口。要克服这一缺点，提升保密程度就必须改变字符间一一对应。须改变字符间一一对应。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 22 23 24 25 0将密文分成将密文分成 n个一组，用对应数字代替，就变成了一个个一组，用对应数字代替，就变成了一个 个个n维向量。假如取定一维向量。假如取定一 个个n阶非奇异矩阶非奇异矩 阵阵A（此矩阵为主要密（此矩阵为主要密钥），钥），用用A去乘每一向量，即可起到加密效果，解密也不麻去乘每一向量，即可起到加密效果，解密也不麻烦，将密文也分烦，将密文也分 成成n个一组，一样变换个一组，一样变换 成成n维向量，只需用维向量，只需用去乘这些向量，即可将他们变回原先明文。去乘这些向量，即可将他们变回原先明文。第21页定理定理1 ,若若 使得使得 (mod26)，则必有，则必有 =1，其，其中中 为为 与与26最大公因子。最大公因子。证证任取任取，令，令，于是，于是，故，故，由，由任意性可知必有任意性可知必有 (mod26)即即 上式上式说说明必有明必有，不然它将整，不然它将整除除1，而，而这这是不可能。是不可能。在详细实施时在详细实施时，我们很快会发觉一些困，我们很快会发觉一些困难：难：(1)为了使数字与字符间能够交换，必须为了使数字与字符间能够交换，必须使用取自使用取自025之间整数之间整数 (2)由线性代数知识，由线性代数知识，其中，其中 为为A伴随矩阵。因为使用了除法，在伴随矩阵。因为使用了除法，在 求求A逆矩阵时可能会出现分数。不处理逆矩阵时可能会出现分数。不处理这些困难，上述想法依然无法实现。处这些困难，上述想法依然无法实现。处理方法是引进同余运算，并用乘法来代理方法是引进同余运算，并用乘法来代替除法，（如同线性代数中用逆矩阵代替除法，（如同线性代数中用逆矩阵代替矩阵除法一样）。替矩阵除法一样）。第22页另外，我另外，我们还们还不不难证实这难证实这么么还还是由是由唯一确定。唯一确定。实际实际上上设设有有和和 则则故必有故必有（也因（也因为为），即），即由定理由定理1，026中除中除13以外奇数均可取作以外奇数均可取作这这里里，下表，下表为经计为经计算求得逆元素算求得逆元素13579111517192123251921153197231151725第23页例例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为普通整数为普通整数情况了情况了,只需在乘法运算中结合应用取余，求只需在乘法运算中结合应用取余，求逆矩阵时用逆元素相乘来代替除法即可。逆矩阵时用逆元素相乘来代替除法即可。第24页 例例2 取取A=则则 (详细求法见详细求法见后后),用用A加密加密THANK YOU,再用再用 对密文解密对密文解密 用矩用矩阵阵A左乘各向量加密（关左乘各向量加密（关于于26取余）得取余）得 得到密文得到密文JXCPIWEK解解:(希希尔尔密密码码加加密密)用用对应对应数字代替字符，划分数字代替字符，划分为为两个元素一两个元素一组组并表示并表示为为向量：向量：第25页（希尔密码解密希尔密码解密）用用A-1左乘求得向量，即可还原为原来向量。左乘求得向量，即可还原为原来向量。(自行验证自行验证)希尔密码是以希尔密码是以矩阵矩阵 法法为基础，明文与密文对为基础，明文与密文对 应由应由n阶矩阵阶矩阵A确定。矩阵确定。矩阵A阶数是事先约定，与明文分组时每组字母字母阶数是事先约定，与明文分组时每组字母字母数量相同，假如明文所含字数数量相同，假如明文所含字数 与与n不匹配，则最终几个分量不匹配，则最终几个分量可任意补足。可任意补足。A-1求法求法方法方法1 利用公式利用公式 ，比如，若取，比如，若取 ，则则 ,(mod26)，即，即 方法方法2 利用高斯消去法。将矩利用高斯消去法。将矩 阵阵(A,E)中矩阵中矩阵A消为消为E，则，则原先原先E即被消成了即被消成了A-1，第26页 如如 ，(用用9乘第二行并取同乘第二行并取同 余余)，第一行减去第二行第一行减去第二行 2倍并取同余，得倍并取同余，得 ，左端矩阵已化为单位阵，故右端矩阵即为左端矩阵已化为单位阵，故右端矩阵即为 A-1希尔密码系统解密依赖于以下几把钥匙希尔密码系统解密依赖于以下几把钥匙 （key）：）：Key1 矩阵矩阵A阶数阶数n，即，即 明文是按几个字母来明文是按几个字母来 划分。划分。Key2 变换矩阵变换矩阵A，只有知，只有知 道了道了A才可能推算出才可能推算出Key3 明文和密文由字母表明文和密文由字母表 转换成转换成 n维向量所对维向量所对 应非负整数表（上应非负整数表（上 面，为方便起见，我面，为方便起见，我 们采取了字母自然们采取了字母自然 次序）。次序）。第27页希尔密码体系为破译者设置了多道关口，加大了破译难度。破希尔密码体系为破译者设置了多道关口，加大了破译难度。破译和解密是两个不一样概念，即使二者一样是希望对密文加以译和解密是两个不一样概念，即使二者一样是希望对密文加以处理而得到明文内容，不过他们有一个最大不处理而得到明文内容，不过他们有一个最大不 同同破译密破译密码时，解密必需用到钥匙未能取得，破译密码一方需要依码时，解密必需用到钥匙未能取得，破译密码一方需要依 据据密密文长度文长度，文字本身特征文字本身特征，以及，以及行文习惯行文习惯 等等各方面信息进行破等等各方面信息进行破译。破译密码即使需要技术，但愈加主要是译。破译密码即使需要技术，但愈加主要是“猜测猜测”艺术。艺术。“猜测猜测”成功是否直接决定着破译结果。成功是否直接决定着破译结果。破译希尔密码关键是猜测文字被转换成成几维向量所、对应字破译希尔密码关键是猜测文字被转换成成几维向量所、对应字母表是怎样，更为主要是要设法获取加密矩母表是怎样，更为主要是要设法获取加密矩 阵阵A。（希尔密码破译希尔密码破译）由线性代数知识能够知道，矩阵完全由由线性代数知识能够知道，矩阵完全由一组基变换决定，对一组基变换决定，对 于于n阶矩阵阶矩阵A，只，只要猜出密文要猜出密文 中中n个线性无关向量个线性无关向量(i=1,2,n)对应明文对应明文(i=1,2,n)是什么是什么，即可，即可确定确定A，并将密码破译。，并将密码破译。第28页 在实际计算中，能够利用以下方法：在实际计算中，能够利用以下方法：令令则则，取矩阵取矩阵Q|P,经过一系列初等行变换，将由密文决定经过一系列初等行变换，将由密文决定 n维维矩阵矩阵Q化为化为n阶单位阵阶单位阵 I时候，由明文决定矩时候，由明文决定矩 阵阵P自动化为自动化为(A-1)T，即，即：第29页例例5 有密文以下有密文以下:goqbxcbuglosnfal;依据英文行文依据英文行文习惯以及获取密码路径和背景，猜测是两个字母为习惯以及获取密码路径和背景，猜测是两个字母为一组希尔密码，前四个明文字母一组希尔密码，前四个明文字母 是是dear，试破译，试破译这段秘文。这段秘文。解解：前两组明文字前两组明文字 母母de和和ar 对应二维向量是：对应二维向量是：按同一对应整数表，密文中对应这两组二维向量是：按同一对应整数表，密文中对应这两组二维向量是：，由此可得由此可得，对应上例则有，对应上例则有第30页 ,利用这一逆矩阵，可对截获密文进行解密，破译出电文是利用这一逆矩阵，可对截获密文进行解密，破译出电文是Dear Mac God forbid.这只是对最简单情况进行举例，假如加密矩阵阶数大于这只是对最简单情况进行举例，假如加密矩阵阶数大于2，需，需要密文应该有较长长度，所需计算量也是很大。破译关键是猜要密文应该有较长长度，所需计算量也是很大。破译关键是猜 中中n及及n个独立个独立n维向量，其后求解加密矩阵计算量仅为维向量，其后求解加密矩阵计算量仅为 O(n2)。希尔密码体制中有两个要素非常主要：希尔密码体制中有两个要素非常主要：第一第一是字母是字母 与与n维向量进行转换所依维向量进行转换所依据非负整数表，本节中所举是最自然据非负整数表，本节中所举是最自然情况；当然假如依据其它整数表也是情况；当然假如依据其它整数表也是完全能够进行，其情况将会更复杂一完全能够进行，其情况将会更复杂一些，破译难度就会增大。些，破译难度就会增大。第二第二个要素是加密矩阵，怎样定义、个要素是加密矩阵，怎样定义、求解这个矩阵对于密码加密和破译愈求解这个矩阵对于密码加密和破译愈加关键。唯一要求是加密时应选择行加关键。唯一要求是加密时应选择行列式值与列式值与 26无公因子矩阵。无公因子矩阵。第31页RSA公开密钥体制公开密钥体制 传统密码通讯只能在事先约定双方间进行，双方必须掌握相传统密码通讯只能在事先约定双方间进行，双方必须掌握相同密钥，而密钥传送必须使用另外同密钥，而密钥传送必须使用另外 “安全信道安全信道”。这么假。这么假如要使如要使 n个用户都能够秘密交换信息，则每个用户将需要用个用户都能够秘密交换信息，则每个用户将需要用个密钥，这种巨大密钥量给密钥分配与管理带来了极大困难；个密钥，这种巨大密钥量给密钥分配与管理带来了极大困难；另外在有些情况下，事先约定密钥还是不可能。另外在有些情况下，事先约定密钥还是不可能。公开密钥体制提出就是为了从根本上处理上述问题公开密钥体制提出就是为了从根本上处理上述问题 。其其基基本思想本思想是：是：把密钥划分为公开密钥和秘密密钥两部分把密钥划分为公开密钥和秘密密钥两部分 ,二者二者互为逆变换，但几乎不可能从公开密钥推出秘密密钥互为逆变换，但几乎不可能从公开密钥推出秘密密钥 .每个每个使用者都有自己公开及秘密密钥。使用者都有自己公开及秘密密钥。即使只要能解密密文，从理论上讲即使只要能解密密文，从理论上讲都是可破译，但假如破译所需要都是可破译，但假如破译所需要 工作量过大，要求花费时间过工作量过大，要求花费时间过 长，以致超出了保密期限，则该密长，以致超出了保密期限，则该密 码系统应该被认为是安全可靠。码系统应该被认为是安全可靠。第32页定义定义1 设设n为一正整数，将小为一正整数，将小 于于n且与且与n互素正整数个数记互素正整数个数记为为(n)，称之为欧拉（称之为欧拉（Euler L.）函数。函数。不难证实：若不难证实：若 p，q为两个相异素数，为两个相异素数，n=pq，则，则 (n)=(p-1)(q-1)令令p,q为随机选取两个大素数（大约为十进为随机选取两个大素数（大约为十进 制制100位或更大）位或更大）,n=pq,n是公开，是公开，而而p,q则是保密。仅知道欧拉函数则是保密。仅知道欧拉函数(n)=(p-1)(q-1)，但假如不知道因式分解就不能用这个公式计算。但假如不知道因式分解就不能用这个公式计算。随机选取一个随机选取一个 数数e，e为小于为小于(n)且与它互素正整数。利用辗且与它互素正整数。利用辗转相除法，能够找到整转相除法，能够找到整 数数d和和r，使，使 ed+r(n)=1即即 ed 1 (mod(n)数数n,e和和d分别称为分别称为模模、加密密钥加密密钥和和解密密钥解密密钥。数数n和和e组成公组成公开密钥开密钥加密密钥加密密钥，而其余，而其余 项项p,q,(n)和和 d 组成了秘密陷门。组成了秘密陷门。很显然，陷门信息包含了四个相关项。很显