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

3 Hill 密码的数学模型Hill 密码是一种传统的密码体系，它的加密过程可以描述如下：明文加密器密文普通信道解密器明文在这个过程中，运用的手段是矩阵运算，具体步骤如下：一、加密1、根据明文字母的表值，将明文信息用数字表示，设明文信息只需要26 个英文字母 AZ（也可以不只 26 个，如还有数字、标点符号等），通信双方给出这 26 个字母表值（见下表）。ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ14151617181920212223242502、选择一个二阶可逆整数方阵A，称为 Hill 密码的加密矩阵，加密矩阵，它是这个加密体制的“密钥”（是加密的关键，仅通信双方掌握）。3、将明文字母依次逐对分组。Hill 密码的加密矩阵为二阶矩阵，则明文字母2 个一组（可以扩充至每 n 个明文字母为一组）。若最后一组只有一个字母，则补充一个没有实际意义的哑字母，这样使得每一组都由 2 个明文字母组成。查出每个明文字母的表值，构成一个二维列向量。4、A乘以，得到一个新的二维列向量 A，由的两个分量反查字母表值得到的两个字母即为密文字母。以上 4 步即为 Hill 密码的加密过程。例例 明文为 YI CHU FA。A 12，求这段明文的 Hill 密码。03将明文相邻 2 个字母分为一组：YI CH UF AA。最后一个字母是哑字母，它是为使最后一组的字母数为 2 而添加的，无实际意义。查出每对字母的表值，并构造2 维列向量：259,（1）38,216,11 将上述 4 个列向量左乘矩阵A，得到 4 个新的列向量：43,271924,3318,33（2）在反查这 4 个向量对应的字母时，遇到了问题：第 1 个向量与第三个向量中的43 与 33 不是表值，处理的办法是加减 26 的整数倍，使其化为 025 之间的一个整数，这称为模模 2626 运算，运算，记为：4317(mod26),27133 7 18(mod26)18（3）这样，这 4 个新的二维列向量对应的字母为：QA SX GR CC。它就是明文“YI CHU FA”的密文。二、解密解密过程即为上述过程的逆过程。这是在模运算下如何解方程组A的问题。一般一个n 阶方阵A可逆的充要条件是det A 0。在模 26 运算下矩阵可逆与一般的矩阵可逆有所不同。记整数集合 Z=0，1，2，m-1，m 为一正整数，模 m 可逆定义如下：定义定义 1 1对于一个元素属于集合Z 的 n 阶方阵A，若存在一个元素属于集合Z 的方阵B，使得AB BA E(mod m)称A为模 m 可逆，B为A的模 m 逆矩阵，记为B A1(mod m)。E（mod m）的意义是，每一个元素减去m 的整数倍后，可以化成单位矩阵。例如：27522627(mod 26)E定义定义 2 2对 Z 的一个整数 a，若存在 Z 的一个整数 b，使得 ab=1（mod m），称 b 为 a 的模 m 倒数，记作b a1(mod m)。1571723191121523172525Z 中有模 26 倒数的整数及其倒数见下表：a135791192115319a11可以证明，如果 a 与 m 无公共素数因子，则 a 有唯一的模 m 倒数。利用这点，可以证明下述命题：命题命题元素属于 Z 的方阵A模 m 可逆的充要条件是 m 和 detA没有公共素数因子。显然，所选加密矩阵必须符合该命题的条件。这里所选项的明文字母共 26 个，m=26，26 的素数因子为 2 和 13，所以 Z 上的方阵A可逆的充要条件是 detA(mod m)不能被 2 和 13 整除。ab设A cd，若A满足命题的条件，不难验证：dbA1(ad bc)1ca(mod 26)其中(ad bc)是(ad bc)(mod 26)的倒数。显然(ad bc)(mod 26)为 Z 中的数。这样，在模 26 意义下，求解方程组A的问题即可解决：1 A1(mod 26)（4）例例 要将一段密文 QA SX GR CC 解密，只要将上述加密过程逆转回去，即将密文按同样方式分组，查它们的表值即得：171,1924,7 18,33（5）根据上述命题与表值，所选加密矩阵A的行列式 detA=3 没有 2 与 13 这两个素数因子，所以A模 26 可逆。3232271818A1(mod 26)31(mod 26)9(mod 26)01010909这样，由（4）和（5）中的向量可得到（1）中的向量，明文为 YI CH UF AA。三、密码的破译密码破译实际上就是破译加密矩阵A及A1，前面的加密与解密过程类似于在二维向量空间进行线性变换与其逆变换。每个明文向量都是一个Z 上的二维向量，乘以加密矩阵A后仍为一个Z 上的二维向量。由于A为可逆矩阵，所以，如果知道了两个线性无关的二维明文向量与其对应的密文向量，就可以求出它的加密矩阵A及A1。下面以一个具体例子说明这种方法。有一段密文：QJWPISWAZUXAUUISEABAUCRSUCRSIPLBHAAMMLPJJOTENH。经分析是用 Hill 密码编译的，且这段密文的字母UCRS 依次代表字母 TACO（通常这是由破译部门通过大量的统计分析与语言分析确定的），这样密文与明文的对应为U T CA,RCSOU 2120T 于是有C1 3 A11 1 AR18 3 C A222S1915O在模 26 意义下，det(1,2)21 18319(mod 26)345(mod26)7，它有模 26 倒数，所以，1,2在模 26 意义下线性无关。类似地，也可以验证1,2在模 26 意义下线性无关。记P (1,2)，C (1,2)，则P AC,A PC。这样，可以利用模模 2626 意义下的初意义下的初1等行变换等行变换求得(A)，因而可以求出A。初等行变换的过程如下：1T1213 201 10 10(PTCT)1819 315 01179故(A1)T 17 1011711，。利用即可将密文解密，得到这段密文的明文：AA099CL 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。注意最后一个字母是哑字母。