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

1、3 hill密码的数学模型hill密码是一种传统的密码体系，它的加密过程可以描述如下：明文加密器密文普通信道解密器明文在这个过程中，运用的手段是矩阵运算，具体步骤如下：一、加密1、根据明文字母的表值，将明文信息用数字表示，设明文信息只需要26个英文字母az（也可以不只26个，如还有数字、标点符号等），通信双方给出这26个字母表值（见下表）。abcdefghijklm12345678910111213nopqrstuvwxyz14151617181920212223242502、选择一个二阶可逆整数方阵，称为hill密码的加密矩阵，它是这个加密体制的“密钥”（是加密的关键，仅通信双方掌握）。3、

2、将明文字母依次逐对分组。hill密码的加密矩阵为二阶矩阵，则明文字母2个一组（可以扩充至每n个明文字母为一组）。若最后一组只有一个字母，则补充一个没有实际意义的哑字母，这样使得每一组都由2个明文字母组成。查出每个明文字母的表值，构成一个二维列向量。4、乘以，得到一个新的二维列向量，由的两个分量反查字母表值得到的两个字母即为密文字母。 以上4步即为hill密码的加密过程。例 明文为yi chu fa。，求这段明文的hill密码。将明文相邻2个字母分为一组：yi ch uf aa。最后一个字母是哑字母，它是为使最后一组的字母数为2而添加的，无实际意义。查出每对字母的表值，并构造2维列向量： （1）

3、将上述4个列向量左乘矩阵，得到4个新的列向量： （2）在反查这4个向量对应的字母时，遇到了问题：第1个向量与第三个向量中的43与33不是表值，处理的办法是加减26的整数倍，使其化为025之间的一个整数，这称为模26运算，记为： （3）这样，这4个新的二维列向量对应的字母为：qa sx gr cc。它就是明文“yi chu fa”的密文。二、解密解密过程即为上述过程的逆过程。这是在模运算下如何解方程组的问题。一般一个n阶方阵可逆的充要条件是。在模26运算下矩阵可逆与一般的矩阵可逆有所不同。记整数集合z=0，1，2，m-1，m为一正整数，模m可逆定义如下：定义1 对于一个元素属于集合z的n阶方阵，

4、若存在一个元素属于集合z的方阵，使得称为模m可逆，为的模m逆矩阵，记为。e（mod m）的意义是，每一个元素减去m的整数倍后，可以化成单位矩阵。例如：定义2 对z的一个整数a，若存在z的一个整数b，使得ab=1（mod m），称b为a的模m倒数，记作。z中有模26倒数的整数及其倒数见下表：13579111517192123251921153197231151725可以证明，如果a与m无公共素数因子，则a有唯一的模m倒数。利用这点，可以证明下述命题：命题 元素属于z的方阵模m可逆的充要条件是m和det 没有公共素数因子。 显然，所选加密矩阵必须符合该命题的条件。 这里所选项的明文字母共26个，m

5、=26，26的素数因子为2和13，所以z上的方阵可逆的充要条件是det (mod m)不能被2和13整除。 设，若满足命题的条件，不难验证：其中是的倒数。显然为z中的数。这样，在模26意义下，求解方程组的问题即可解决： （4）例 要将一段密文qa sx gr cc解密，只要将上述加密过程逆转回去，即将密文按同样方式分组，查它们的表值即得： （5）根据上述命题与表值，所选加密矩阵的行列式det =3没有2与13这两个素数因子，所以模26可逆。这样，由（4）和（5）中的向量可得到（1）中的向量，明文为yi ch uf aa。三、密码的破译 密码破译实际上就是破译加密矩阵及，前面的加密与解密过程类似

6、于在二维向量空间进行线性变换与其逆变换。每个明文向量都是一个z上的二维向量，乘以加密矩阵后仍为一个z上的二维向量。由于为可逆矩阵，所以，如果知道了两个线性无关的二维明文向量与其对应的密文向量，就可以求出它的加密矩阵及。 下面以一个具体例子说明这种方法。 有一段密文：qjwpiswazuxauuiseabaucrsiplbhaammlpjjotenh。经分析是用hill密码编译的，且这段密文的字母ucrs依次代表字母taco（通常这是由破译部门通过大量的统计分析与语言分析确定的），这样密文与明文的对应为于是有 在模26意义下，它有模26倒数，所以，在模26意义下线性无关。类似地，也可以验证在模26意义下线性无关。 记，则。这样，可以利用模26意义下的初等行变换求得，因而可以求出。初等行变换的过程如下：故，。利用即可将密文解密，得到这段密文的明文：cl in to ni sg oi ng to vi si ta co