数学建模
§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。A????12??，求这段明文的Hill密码。 ??03?将明文相邻2个字母分为一组：YI CH UF AA。最后一个字母是哑字母，它是为使最后一组的字母数为2而添加的，无实际意义。查出每对字母的表值，并构造2维列向量：
?25???9??,???43? ??27??,???3???8??,???19???24??,???21???6??,???33???18??,???1?? ?1?? （1）???3??（2） ?3?? ??将上述4个列向量左乘矩阵A，得到4个新的列向量：
在反查这4个向量对应的字母时，遇到了问题：第1个向量与第三个向量中的43与33不是表值，处理的办法是加减26的整数倍，使其化为0—25之间的一个整数，这称为模26运算，记为：
???43??17???(mod26)???1??,27?????33??7???? (mod26)??18??18?? （3）????这样，这4个新的二维列向量对应的字母为：QA SX GR CC。它就是明文“YI CHU FA”的密文。
二、解密
解密过程即为上述过程的逆过程。这是在模运算下如何解方程组A???的问题。一般一个
数学建模
数学建模
n阶方阵A可逆的充要条件是detA?0。在模26运算下矩阵可逆与一般的矩阵可逆有所不同。记整数集合Z={0，1，2，…，m-1}，m为一正整数，模m可逆定义如下：
定义1 对于一个元素属于集合Z的n阶方阵A，若存在一个元素属于集合Z的方阵B，使得
AB?BA?E(modm)
称A为模m可逆，B为A的模m逆矩阵，记为B?A?1(modm)。
E（mod m）的意义是，每一个元素减去m的整数倍后，可以化成单位矩阵。例如：
?2752???2627??(mod26)?E ??定义2 对Z的一个整数a，若存在Z的一个整数b，使得ab=1（mod m），称b为a的模m倒数，记作b?a?1(modm)。
15 7 17 23 19 11 21 5 23 17 25 25 Z中有模26倒数的整数及其倒数见下表： a 1 3 5 7 9 11 9 21 15 3 19 a?1 1 可以证明，如果a与m无公共素数因子，则a有唯一的模m倒数。利用这点，可以证明下述命题：
命题 元素属于Z的方阵A模m可逆的充要条件是m和det A没有公共素数因子。 显然，所选加密矩阵必须符合该命题的条件。
这里所选项的明文字母共26个，m=26，26的素数因子为2和13，所以Z上的方阵A可逆的充要条件是det A (mod m)不能被2和13整除。 设A????ab??，若A满足命题的条件，不难验证： ??cd??d?b?A?(ad?bc)???ca??(mod26)
???1?1其中(ad?bc)是(ad?bc)(mod26)的倒数。显然(ad?bc)(mod26)为Z中的数。
这样，在模26意义下，求解方程组A???的问题即可解决：
?1??A?1?(mod26) （4）
例 要将一段密文QA SX GR CC解密，只要将上述加密过程逆转回去，即将密文按同样方式分组，
查它们的表值即得：
?17???1??,???19???24??,???7???18??,???3?? ?3?? （5）??根据上述命题与表值，所选加密矩阵A的行列式det A=3没有2与13这两个素数因子，所以A模26可逆。
数学建模
数学建模
?3?2??3?2??27?18??18??????? A?1(mod26)?3?1?(mod26)?9(mod26)????01??01??0???9??09??????这样，由（4）和（5）中的向量可得到（1）中的向量，明文为YI CH UF AA。
三、密码的破译
密码破译实际上就是破译加密矩阵A及A?1，前面的加密与解密过程类似于在二维向量空间进行线性变换与其逆变换。每个明文向量都是一个Z上的二维向量，乘以加密矩阵A后仍为一个Z上的二维向量。由于A为可逆矩阵，所以，如果知道了两个线性无关的二维明文向量与其对应的密文向量，就可以求出它的加密矩阵A及A?1。
下面以一个具体例子说明这种方法。
有一段密文：QJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH。经分析是用Hill密码编译的，且这段密文的字母UCRS依次代表字母TACO（通常这是由破译部门通过大量的统计分析与语言分析确定的），这样密文与明文的对应为
?U??T??????C??A??,?????R??C??????S??O?? ?????U??21??20??T?于是有 ??C????1???3???A?1??1???1?????A??
?????????R??18??3??C????????????A?????222?S??19??15??O?? ????????在模26意义下，det(?1,?2)?2118319(mod26)?345(mod26)?7，它有模26倒数，所以，
?1,?2在模26意义下线性无关。类似地，也可以验证?1,?2在模26意义下线性无关。
记P?(?1,?2)，C?(?1,?2)，则P?AC,A?PC。这样，可以利用模26意义下的初
?1等行变换求得(A)，因而可以求出A。初等行变换的过程如下：
?1T?1?213?201??10?10?(PC)???1819?315?????01?179??
????TT故(A?1)T???17?1?0??117??1?1???，。利用即可将密文解密，得到这段密文的明文： AA????9??09?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 Hill密码的数学模型数学建模案例分析.doc
