2022年线性代数方法建模Hill密码的数学模型--数学建模案例分析实用 .pdf

数学建模数学建模3 Hill密码的数学模型Hill密码是一种传统的密码体系，它的加密过程可以描述如下：明文加密器密文普通信道解密器明文在这个过程中，运用的手段是矩阵运算，具体步骤如下：一、加密1、根据明文字母的表值，将明文信息用数字表示，设明文信息只需要26 个英文字母A Z（也可以不只 26 个，如还有数字、标点符号等），通信双方给出这26 个字母表值（见下表） 。A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 0 2、选择一个二阶可逆整数方阵A，称为 Hill密码的 加密矩阵， 它是这个加密体制的“密钥”（是加密的关键，仅通信双方掌握）。3、将明文字母依次逐对分组。Hill密码的加密矩阵为二阶矩阵，则明文字母2 个一组（可以扩充至每 n 个明文字母为一组） 。若最后一组只有一个字母，则补充一个没有实际意义的哑字母，这样使得每一组都由2 个明文字母组成。查出每个明文字母的表值，构成一个二维列向量。4、A乘以，得到一个新的二维列向量A，由的两个分量反查字母表值得到的两个字母即为密文字母。以上 4 步即为 Hill密码的加密过程。例 明文为 YI CHU FA。3021A，求这段明文的Hill密码。将明文相邻2 个字母分为一组：YI CH UF AA。最后一个字母是哑字母，它是为使最后一组的字母数为2 而添加的，无实际意义。查出每对字母的表值，并构造2 维列向量：11,621,83,925（1）将上述 4 个列向量左乘矩阵A，得到 4 个新的列向量：33,1833,2419,2743（2）在反查这 4 个向量对应的字母时，遇到了问题： 第 1 个向量与第三个向量中的43 与 33 不是表值，处理的办法是加减26 的整数倍，使其化为0 25 之间的一个整数，这称为模 26 运算， 记为：187)26(mod1833,117)26(mod2743（3）这样，这 4 个新的二维列向量对应的字母为：QA SX GR CC 。它就是明文“YI CHU FA”的密文。二、解密解密过程即为上述过程的逆过程。这是在模运算下如何解方程组A的问题。一般一个n 阶方阵A可逆的充要条件是0det A。在模 26 运算下矩阵可逆与一般的矩阵可逆有所不同。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 数学建模数学建模记整数集合Z=0 ，1，2， ，m-1 ，m 为一正整数，模m 可逆定义如下：定义 1对于一个元素属于集合Z 的 n 阶方阵A，若存在一个元素属于集合Z 的方阵B，使得)(mod mEBAAB称A为模 m 可逆，B为A的模 m 逆矩阵，记为)(mod1mAB。E（mod m）的意义是，每一个元素减去m 的整数倍后，可以化成单位矩阵。例如：E)26(mod27265227定义 2对 Z 的一个整数a，若存在 Z 的一个整数b，使得 ab=1（ mod m） ，称 b 为 a 的模 m 倒数，记作)(mod1mab。Z 中有模 26 倒数的整数及其倒数见下表：a1 3 5 7 9 11 15 17 19 21 23 25 1a1 9 21 15 3 19 7 23 11 5 17 25 可以证明， 如果 a 与 m 无公共素数因子，则 a有唯一的模m 倒数。利用这点，可以证明下述命题：命题元素属于 Z 的方阵A模 m 可逆的充要条件是m 和 det A没有公共素数因子。显然，所选加密矩阵必须符合该命题的条件。这里所选项的明文字母共26 个， m=26，26 的素数因子为2 和 13，所以 Z 上的方阵A可逆的充要条件是det A(mod m) 不能被 2 和 13 整除。设dcbaA，若A满足命题的条件，不难验证：)26(mod)(11acbdbcadA其中1)(bcad是)26(mod)(bcad的倒数。显然)26(mod)(bcad为 Z 中的数。这样，在模26 意义下，求解方程组A的问题即可解决：)26(mod1A（4）例 要将一段密文QA SX GR CC解密，只要将上述加密过程逆转回去，即将密文按同样方式分组，查它们的表值即得：33,187,2419,117（5）根据上述命题与表值，所选加密矩阵A的行列式 det A=3 没有 2 与 13 这两个素数因子，所以A模 26 可逆。9081901827)26(mod10239)26(mod10233)26(mod11A名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 数学建模数学建模这样，由（ 4）和（ 5）中的向量可得到（1）中的向量，明文为YI CH UF AA 。三、密码的破译密码破译实际上就是破译加密矩阵A及1A，前面的加密与解密过程类似于在二维向量空间进行线性变换与其逆变换。每个明文向量都是一个Z 上的二维向量， 乘以加密矩阵A后仍为一个Z 上的二维向量。由于A为可逆矩阵，所以，如果知道了两个线性无关的二维明文向量与其对应的密文向量，就可以求出它的加密矩阵A及1A。下面以一个具体例子说明这种方法。有一段密文：QJWPISWAZUXAUUISEABAUCRS IPLBHAAMMLPJJOTENH。经分析是用Hill密码编译的， 且这段密文的字母UCRS 依次代表字母TACO（通常这是由破译部门通过大量的统计分析与语言分析确定的），这样密文与明文的对应为OCSRATCU,于是有ATACU120321111OCASR1531918222在模 26 意义下，7)26(mod345)26(mod1931821),(det21，它有模 26 倒数， 所以，21,在模 26 意义下线性无关。类似地，也可以验证21,在模 26 意义下线性无关。记),(21P，),(21C，则1,PCAACP。这样，可以利用模 26 意义下的初等行变换 求得TA)(1，因而可以求出1A。初等行变换的过程如下：9171001011531918120321)(TTCP故91701)(1TA，901711A。利用1A即可将密文解密，得到这段密文的明文：CL IN TO NI SG OI NG TO VI SI TA CO UN TR YI NM ID DL EE AS TT 分析这段文字，可以理解为：Clinton is going visit a country in Middle East。注意最后一个字母是哑字母。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -