数学建模：第6周-代数模型

1、 第第6 6章章 代数模型代数模型 应用线性代数解决一些实际问题应用线性代数解决一些实际问题 6.1 6.1 兔子数量增长兔子数量增长 6.2 6.2 植物基因的分布植物基因的分布 6.3 6.3 常染色体的隐性疾病常染色体的隐性疾病 6.4 6.4 加密与解密加密与解密 6.5 6.5 森林的管理森林的管理 6.1 兔子数量增长兔子数量增长 一地区开始时有10000对刚出生的小 兔。设兔子出生以后两个月就能生小兔, 如果每月每对兔子恰好生一对小兔。 若出生的兔子都成活,试问一年以后 共有多少对兔子,两年后有多少对兔子? 直接推算直接推算 第1月,只有1对兔子; 第2月,也只有一对兔子; 第3

2、月,这对兔子生了1对小兔子,共有2对兔子; 第4月,老兔子又生了1对小兔子,共有3对兔子 第5月,老兔子生1对小兔子,且在第3月出生的 小兔也生育1对小兔子,故共有5对小兔子, 如此类推,不难得到月份和小兔对数的关系如 表1所示. 该问题在理论状态下完全解决！ 兔子能长生不老吗？ 1） 所有兔子在每个月均死亡1/3，试讨论兔子数量 变化的规律。 2） 所有兔子在每个月死亡的比例均是d，试讨论兔 子 数量变化的规律，并探讨兔子数量稳定时d的 值。 3） 兔子的寿命均为6个月，试讨论兔子数量变化的 规律。 1）兔子在每个月均死亡）兔子在每个月均死亡1/3时兔子数量变化的规律时兔子数量变化的规律 2

3、）兔子在每个月均死亡）兔子在每个月均死亡d时数量变化的规律时数量变化的规律 3）兔子的寿命为）兔子的寿命为6个月时论兔子数量变化个月时论兔子数量变化 进一步的推广进一步的推广 兔子出生后总共存活12月，从第7个 月后就开始生小兔,在第7、8这两个月中 每月每一对兔子恰好生1对小兔，从9、 10两个月月内每一对兔子恰好生2对小兔， 然后停止生育，在第12月末死亡问第k月 有多少对兔子？ 6.2 植物基因的分布植物基因的分布 随着人类的进化，为了揭示生命的奥随着人类的进化，为了揭示生命的奥 秘，人们越来越注重遗传学的研究，特秘，人们越来越注重遗传学的研究，特 别是别是遗传特征遗传特征的逐代传播，已

4、引起人们的逐代传播，已引起人们 广泛的注意。无论是人，还是动、植物广泛的注意。无论是人，还是动、植物 都会将本身的特征遗传给下一代，这主都会将本身的特征遗传给下一代，这主 要是因为要是因为后代继承了双亲的基因后代继承了双亲的基因，形成，形成 自己的基因对，由基因又确定了后代所自己的基因对，由基因又确定了后代所 表现的特征。表现的特征。 植物基因的分布的变化植物基因的分布的变化 设一农业研究所植物园中某植物的基 因型为AA、Aa 和 aa ,研究所计划采用 AA型的植物与每一种基因型植物相结合 的方案培育植物后代。问经过若干年后, 这种植物的任意一代的三种基因型分布 如何? 基因的继承基因的继承

5、 在常染色体遗传中，后代从每个亲在常染色体遗传中，后代从每个亲 体的基因对中各继承一个基因，形成自体的基因对中各继承一个基因，形成自 己的基因时，基因对也称为基因型。如己的基因时，基因对也称为基因型。如 果我们所考虑的遗传特征是由两个基因果我们所考虑的遗传特征是由两个基因A 和和a控制的，（控制的，（A、a为表示两类基因的符为表示两类基因的符 号）那么就有三种基因对，记为号）那么就有三种基因对，记为AA，Aa， aa。 双亲体基因型的可能结合双亲体基因型的可能结合 及其后代形成每种基因型的概率及其后代形成每种基因型的概率 讨论题 若在上述问题中，不选用基若在上述问题中，不选用基 因因AA型的型

6、的 植物与每一植物结合，而是将植物与每一植物结合，而是将具有相同具有相同 基因型植物相结合基因型植物相结合，那么后代具有三种，那么后代具有三种 基因型的概率将如何变化？请基因型的概率将如何变化？请给出相邻给出相邻 两代基因转换的概率两代基因转换的概率，建立数学模型，建立数学模型分分 析各代之间概率变化的规律和极限析各代之间概率变化的规律和极限。 后代具有三种基因型的概率后代具有三种基因型的概率 11/40aa 01/20Aa 01/41AA后后 代代 基基 因因 型型 aaaaAaAa AA AA 父体父体母体的基因型母体的基因型 解答 模型为：模型为： )0()( xLx nn 2/ )0(

7、)0()( , 0)( , 2/ )0()0()( 14/10 02/10 04/11 233 2 211 xxnx nx xxnx n L 6.3 常染体隐性疾病模型常染体隐性疾病模型 遗传性疾病是常染色体的基因缺陷由父母代传给子 代的疾病。常染色体遗传的正常基因记为A,不正常的 基因记为a,并以AA、Aa、aa分别表示正常人、隐性患 者、显性患者的基因型。若在开始时的一代人口中AA、 Aa、aa型基因的人所占百分比分别为a0、b0、c0,讨论 在下列两种情况下第n代中三类基因型人口所占的比例： (1) 控制结合: 显示性患者不能生育后代,且为了使每个儿 童至少有一个正常的父亲或母亲,正常人

8、、隐性患者必 须与一个正常人结合生育后代; (2) 自由结合: 这三种基因的人任意结合生育后代。 背景背景: 现在世界上已经发现的遗传病有将现在世界上已经发现的遗传病有将 近近4000种。种。 在一般情况下，遗传疾病和特殊的种族、部落及群在一般情况下，遗传疾病和特殊的种族、部落及群 体体 有关。例如，遗传病库利氏贫血症的患者以居住有关。例如，遗传病库利氏贫血症的患者以居住 在在 地中海沿岸为多，镰状网性贫血症一般流行在黑地中海沿岸为多，镰状网性贫血症一般流行在黑 人中，家族黑蒙性白痴症则流行在东欧犹太人中间。人中，家族黑蒙性白痴症则流行在东欧犹太人中间。 患者经常未到成年就痛苦地死去，而他们的

9、父母则患者经常未到成年就痛苦地死去，而他们的父母则 是疾病的病源。假若我们能识别这些疾病的隐性患是疾病的病源。假若我们能识别这些疾病的隐性患 者，并且规定两个隐性患者不能结合（因为两个隐者，并且规定两个隐性患者不能结合（因为两个隐 性病患者结合，他们的后代就可能成为显性患者），性病患者结合，他们的后代就可能成为显性患者）， 那么未来的儿童，虽然有可能是隐性患者，但绝不那么未来的儿童，虽然有可能是隐性患者，但绝不 会出现显性特征，不会受到疾病的折磨。会出现显性特征，不会受到疾病的折磨。 表表6-2：双亲体基因型的可能结合：双亲体基因型的可能结合 及其后代形成每种基因型的概率及其后代形成每种基因型

10、的概率 1 1 11 32 21 32 kkk kkk xxy yxy 00 12 ,. 33 xy 1kk XLX 0 1 2 () 3 3 T X 11 32 21 32 L 递推关系式为 , 写成矩阵形式即 , ，其中状态转移矩阵 3 3 30 111139 323324 212185 323324 XL X 第三年两家电器店的市场份额分别为 139/324与185/324。 6.4 加密与解密加密与解密 密码的设计和使用至少可从追溯到密码的设计和使用至少可从追溯到 四千多年前的埃及四千多年前的埃及, 巴比伦、罗马和希腊，巴比伦、罗马和希腊， 历史极为久远历史极为久远 。古代古代隐藏信息

11、的方法隐藏信息的方法 主主 要有两大类：要有两大类： 其一其一为为隐藏信息载体，采隐藏信息载体，采 用隐写术用隐写术等；等；其二其二为为变换信息载体，使变换信息载体，使 之无法为一般人所理解之无法为一般人所理解 。 简单定义 在密码学中，信息代码被称为在密码学中，信息代码被称为密码密码， 加密前的信息被称为加密前的信息被称为 明文明文，经加密后不，经加密后不 为常人所理解的用密码表示的信息被称为常人所理解的用密码表示的信息被称 为为密文密文(ciphertext)，将明文转变成密文，将明文转变成密文 的过程被称为的过程被称为加密加密(enciphering)，其逆过，其逆过 程则被称为程则被称

12、为解密解密(deciphering)，而用以加，而用以加 密、解密的方法或算法则被称为密、解密的方法或算法则被称为 密码体密码体 制制(crytosystem)。 常规加密简化模型常规加密简化模型 记全体明文组成的集合记全体明文组成的集合 为为U，全体密文组成的集合，全体密文组成的集合 为为V，称，称U 为明文空间，为明文空间，V为密文空间。加密常利用某一被称为密钥的东为密文空间。加密常利用某一被称为密钥的东 西来实现，它通常取自于一个被称为密钥空间的含有若干参西来实现，它通常取自于一个被称为密钥空间的含有若干参 数的集合数的集合K。按数学的观点来看，加密与解密均可被看成是一。按数学的观点来看

13、，加密与解密均可被看成是一 种变换：取一种变换：取一kK， uU，令，令 ，v为明为明 文文u在密钥在密钥K下的密文，而解码则要用下的密文，而解码则要用 到到K的逆变换的逆变换K-1，。由，。由 此可见，密码体系虽然可以千姿百态，但其关键还在此可见，密码体系虽然可以千姿百态，但其关键还在 于于密钥密钥 的选取的选取。 V Vv vu u k k 随着计算机与网络技术的迅猛发展，大量各具特色的密码体随着计算机与网络技术的迅猛发展，大量各具特色的密码体 系不断涌现。离散数学、数论、计算复杂性、混沌、系不断涌现。离散数学、数论、计算复杂性、混沌、， 许多相当高深的数学知识都被用上，逐步形成了（并仍在

14、迅许多相当高深的数学知识都被用上，逐步形成了（并仍在迅 速发展的）具有广泛应用面的速发展的）具有广泛应用面的 现代密码学现代密码学 。 移位密码体制移位密码体制 移位密码移位密码采用移位法进行加密，明文中的字母重新排列，本采用移位法进行加密，明文中的字母重新排列，本 身不变，只是位置改变了。身不变，只是位置改变了。 早在早在4000多年前，古希腊人就用一种名多年前，古希腊人就用一种名 叫叫“天书天书”的器械的器械 来加密消息。该密码器械是用一条窄长的草纸缠绕在一个来加密消息。该密码器械是用一条窄长的草纸缠绕在一个 直径确定的圆筒上，明文逐行横写在纸带上，当取下纸带直径确定的圆筒上，明文逐行横写

15、在纸带上，当取下纸带 时，字母的次序就被打乱了，消息得以隐蔽。收方阅读消时，字母的次序就被打乱了，消息得以隐蔽。收方阅读消 息时，要将纸带重新绕在直径与原来相同的圆筒上，才能息时，要将纸带重新绕在直径与原来相同的圆筒上，才能 看到正确的消息。在这里圆筒的直径起到了密钥的作用。看到正确的消息。在这里圆筒的直径起到了密钥的作用。 另一种移位另一种移位 法法采用将字母表中的字母平移若干位的方法来构造采用将字母表中的字母平移若干位的方法来构造 密文字母表，传说这类方法是由古罗马皇帝凯撒最早使用的，密文字母表，传说这类方法是由古罗马皇帝凯撒最早使用的， 故这种密文字母表被称为凯撒字母表。例如，如用将字母

16、表向故这种密文字母表被称为凯撒字母表。例如，如用将字母表向 右平移右平移3位的方法来构造密文字母表，可位的方法来构造密文字母表，可 得：得： 明文字母表明文字母表： ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表密文字母表： DEFGHIJKLMNOPQRTSUVWXYZABC 因此因此 “THANK YOU” “WKDQN BRX” 以上两种移位较易被人破译，为打破字母表中原有的顺序还可以上两种移位较易被人破译，为打破字母表中原有的顺序还可 采用所谓采用所谓路线加密法路线加密法，即把明文字母表按某种既定的顺序安排，即把明文字母表按某种既定的顺序安排 在一个矩阵中，然后用另一

17、种顺序选出矩阵中的字母来产生密在一个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密 文表。文表。 例如，对明文：例如，对明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以以7列矩阵表示如下：列矩阵表示如下： THEHIST ORYOFZJ UISMORE THANONE HUNDRED YEARS 再按事先约定的方式选出密文。例如，如按列选出，得到再按事先约定的方式选出密文。例如，如按列选出，得到 密文：密文：touthyhrihueeysanahomndrifoorsszrnetjeed 使用不同的顺序进行编写和选择，可以得到各种不

18、同的路使用不同的顺序进行编写和选择，可以得到各种不同的路 线加密体制。对于同一明文消息矩阵，采用不同的抄写方线加密体制。对于同一明文消息矩阵，采用不同的抄写方 式，得到的密文也是不同的。式，得到的密文也是不同的。 当明文超过规定矩阵的大小时，可以另加一矩阵。当需要当明文超过规定矩阵的大小时，可以另加一矩阵。当需要 加密的字母数小于矩阵大小时，可以在矩阵中留空位或以加密的字母数小于矩阵大小时，可以在矩阵中留空位或以 无用的字母来填满矩阵。无用的字母来填满矩阵。 移位法密码移位法密码 的的破译破译 对窃听到的密文进行分析时对窃听到的密文进行分析时 ，穷举法穷举法和和统计法统计法是最基本的是最基本的

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

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

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

22、h,r; II. e; III. d,l; IV. c,u,m,w,f,g,y,p,b; V. 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,a s,or,ti,is,er,it,ar,te,se,hi,of 使用最多的三字母按频率大小排列如下：使用最多的三字母按频率大小排列如下： The,ing,and,her

23、,ere,ent,tha,nth,was,eth,for,dth 统计的章节越长，统计结统计的章节越长，统计结 果就越可靠。对于只有几果就越可靠。对于只有几 个单词的密文，统计是无个单词的密文，统计是无 意义的。意义的。 下面介绍一下统计观察的三个结果：下面介绍一下统计观察的三个结果： a)单词单词the在这些统计中有重要的作用；在这些统计中有重要的作用； b)以以e，s，d，t为结尾的英语单词超过了一半；为结尾的英语单词超过了一半； c)以以t，a，s，w为起始字母的英语单词约为一半。为起始字母的英语单词约为一半。 对于对于a) ，如果，如果 将将the从明文中删除，那从明文中删除，那 么么

24、t的频率将要降的频率将要降 到第二组中其他字母之后，到第二组中其他字母之后， 而而h将降到第三组中，并将降到第三组中，并 且且th和和he就不再是最众多的字母了。就不再是最众多的字母了。 以上对英语统计的讨论是在仅涉以上对英语统计的讨论是在仅涉 及及26个字母的假设条件个字母的假设条件 下进行的。实际上消息的构成还包括间隔、标点、数字下进行的。实际上消息的构成还包括间隔、标点、数字 等字符。总之，破译密码并不是件很容易的事。等字符。总之，破译密码并不是件很容易的事。 希尔密码希尔密码 移位密码的一个致命弱点移位密码的一个致命弱点 是是明文字符明文字符和和密文字符密文字符有相同有相同 的的使用频

25、率使用频率,破译者可从统计出来的字符频率中找到规律，破译者可从统计出来的字符频率中找到规律， 进而找出破译的突破口。要克服这一缺陷，提高保密程度进而找出破译的突破口。要克服这一缺陷，提高保密程度 就必须改变字符间的一一对应。就必须改变字符间的一一对应。 1929年，希尔利用线性代数中的矩阵运算，打破了字符间的年，希尔利用线性代数中的矩阵运算，打破了字符间的 对应关系，设计了一种被称为希尔密码的代数密码。为了便对应关系，设计了一种被称为希尔密码的代数密码。为了便 于计算，希尔首先将字符变换成数，例如，对英文字母，我于计算，希尔首先将字符变换成数，例如，对英文字母，我 们可以作如下变换：们可以作如

26、下变换： 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去乘每一向量，即可起到加密的效果，解密也不去乘每一向量，即可起到加密的效果，解密也不 麻烦，将密文也分麻烦，将密文也分

27、成成n个一组，同样变换个一组，同样变换 成成n维向量，只需用维向量，只需用 A逆去乘这些向量，即可将他们变回原先的明文。逆去乘这些向量，即可将他们变回原先的明文。 Hill密码的加密过程 选择一个n阶可逆矩阵A作为加密矩阵； 将明文字符按顺序排列分组； 将明文字符对应一个整数，组成一组列 向量； 用加密矩阵左乘每一列向量； 将新向量的每个分量关于模m取余运算； 将新向量的每个整数对应于一个字符。 解密过程相反。 定理定理1 ,若若 使得使得 (mod26)，则必有，则必有 =1，其，其 中中 为为 与与26的最大公因子。的最大公因子。 0 0, ,. . . ., ,2 25 5 a a0,2

28、50,25a a 1 1 1 1a aa aa aa a 1 11 1 g 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 k26a26ap p26k)26k)(ap(apa aq qa aapapa a 1 11 11 11 1 ，故，故 k k26a26a1)p1)pa a(a(a 1 11 1 ，由，由 p p 的任意性可知必有的任意性可知必有 1 1a aa a 1 1 (mod26) 即即 1 126k26k

29、a aa a, ,k k 1 1 上式说明必有上式说明必有1 1g gc cd d a a, ,2 26 6 ，不然它将整，不然它将整 除除1，而这是不可能的。，而这是不可能的。 在具体实施时在具体实施时 ，我们很快会发现一些困，我们很快会发现一些困 难：难： (1) 为了使数字与字符间可以互换，必须为了使数字与字符间可以互换，必须 使用取自使用取自025之间的整数之间的整数 (2)由线性代数知识，由线性代数知识， ，其中，其中 为为A的伴随矩阵。由于使用了除法，的伴随矩阵。由于使用了除法， 在在 求求A的逆矩阵时可能会出现分数。不的逆矩阵时可能会出现分数。不 解决这些困难，上述想法仍然无法实

30、现。解决这些困难，上述想法仍然无法实现。 解决的办法是引进同余运算，并用乘法解决的办法是引进同余运算，并用乘法 来代替除法，（如同线性代数中用逆矩来代替除法，（如同线性代数中用逆矩 阵代替矩阵除法一样）。阵代替矩阵除法一样）。 det(A)det(A) A A A A 1 1 A A 例例 取取A = 则则 (具体求法见具体求法见 后后),用用A加密加密THANK YOU,再用再用 对密文解密对密文解密 0 0 1 1 3 3 2 2 0 0 1 1 A A 1 1 9 9 8 8 1 1 A A 8 8 2 20 0 1 14 4 1 1 2 25 5 1 11 1 2 21 1 1 15

31、5 用矩阵用矩阵A左乘各向量加密（关左乘各向量加密（关 于于26取余）得取余）得 24 10 16 3 23 9 11 5 得到密文得到密文 JXCPI WEK 解解:(希尔密码加希尔密码加 密密)用相应数字代替字符，划分为两个元素一用相应数字代替字符，划分为两个元素一 组并表示为向量：组并表示为向量： （希尔密码解密希尔密码解密） 用用A-1左乘求得的向量，即可还原为原来的向量。左乘求得的向量，即可还原为原来的向量。 (自行验证自行验证) 希尔密码是以希尔密码是以矩阵矩阵 法法为基础的，明文与密文的对为基础的，明文与密文的对 应由应由n阶矩阶矩 阵阵A确定。矩阵确定。矩阵A的阶数是事先约定的

32、，与明文分组时每组字的阶数是事先约定的，与明文分组时每组字 母的字母数量相同，如果明文所含字数母的字母数量相同，如果明文所含字数 与与n不匹配，则最后不匹配，则最后 几个分量可任意补足。几个分量可任意补足。 A-1的求法的求法 方法方法 利用公式利用公式 ，例如，若取，例如，若取 ， 则则 , , (mod26) ，即，即 )det( 1 A A A 0 1 A 3 2 3)det( A 9 )det( 1 A 0 3 9A 1 1 2 0 1 1 A 9 8 希尔密码体系为破译者设置了多道关口，加大了破译难度。破希尔密码体系为破译者设置了多道关口，加大了破译难度。破 译和解密是两个不同的概念

33、，虽然两者同样是希望对密文加以译和解密是两个不同的概念，虽然两者同样是希望对密文加以 处理而得到明文的内容，但是他们有一个最大的不处理而得到明文的内容，但是他们有一个最大的不 同同破破 译密码时，解密必需用到的钥匙未能取得，破译密码的一方需译密码时，解密必需用到的钥匙未能取得，破译密码的一方需 要依要依 据据密文的长度密文的长度，文字的本身特征文字的本身特征，以及，以及行文习惯行文习惯 等等各等等各 方面的信息进行破译。破译密码虽然需要技术，但更加重要的方面的信息进行破译。破译密码虽然需要技术，但更加重要的 是是“猜测猜测”的艺术。的艺术。“猜测猜测”的成功与否直接决定着破译的结的成功与否直接

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

35、可确定A，并将密码破译。，并将密码破译。 在实际计算中，可以利用以下方法：在实际计算中，可以利用以下方法： 令令 则则 T n pppP),.,( 21 ， T n T APpppAQ ),.,( 21 1 )(, TT AQPPAQ 取矩阵取矩阵Q | P,经过一系列初等行变换，将由密文决定经过一系列初等行变换，将由密文决定 的的n 维矩阵维矩阵Q化为化为n阶单位阵阶单位阵 I的时候，由明文决定的矩的时候，由明文决定的矩 阵阵P自自 动化为动化为 (A-1)T，即，即 ： ),)(, ()(, 1111 1 TT T AIAQQQQ AQQPQ （ 初等行变换）初等行变换） 例例 有密文如下

36、有密文如下:goqbxcbuglosnfal;根据英文的行根据英文的行 文习惯以及获取密码的途径和背景，猜测是两个字文习惯以及获取密码的途径和背景，猜测是两个字 母为一组的希尔密码，前四个明文字母母为一组的希尔密码，前四个明文字母 是是dear， 试破译这段秘文。试破译这段秘文。 解解： 前两组明文字前两组明文字 母母de和和ar 对应的二维向量是：对应的二维向量是： 按同一对应整数表，密文中对应这两组的二维向量是：按同一对应整数表，密文中对应这两组的二维向量是： TT PP)18, 1(,)5 , 4( 21 T Apq)15, 7( 11 ， T Apq)2 ,17( 22 ， T qqQ),( 21 由此可得由此可得 )( ,)26(mod(,