代数方程在密码学中的应用

周晓燕

摘 要：线性代数主要是以向量和矩阵为对象，以实向量空间为背景的一种抽象数学工具，它广泛应用于数学的各个分支以及物理、化学和科学技术中。该篇通过Hill密码的数学模型阐述以线性代数为主要工具建立数学模型的一般方法和步骤。Hill密码是基于矩阵的线性变换，其最大的好处就是隐藏了字符的频率信息，使得传统的通过字频来破译密文的方法失效。该篇主要介绍了明文的加密、加密后的密文的解密以及密码的破译。

关键词：矩阵 Hill密码 数学模型

中图分类号：TP309 文献标识码：A 文章编号：1672-3791（2015）08（a）-0207-02

Hill密码是一种常见的传统密码体系，它加密过程为：

明文→加密器→密文→普通信道→解密器→明文

矩阵运算是完成这个加密过程的基本工具，具体过程如下：

1 加密

（1）根据明文字母的所对应得表值，把明文信息转换成数字，通常Hill密码加密是使用26个字母表 A—Z见表1（也可以不只26个，如还有数字、标点符号等）。

（2）通信双方选择一个二阶可逆整数方阵，这个方阵就称为Hill密码的加密矩阵，它是整个加密过程的“密钥”（ 只有通信双方掌握，是加密的关键）。

（3）把明文字母按照文字的顺序逐对分组。若Hill密码的加密矩阵为二阶矩阵，则明文字母2个一组（可以按照实际情况扩大至每n个明文字母为一组）。若最后一组只有一个字母，则补充一个没有实际意义的哑字母，这样使得每一组都由2个明文字母组成.查出每个明文字母的表值，构成一个二维列向量。

（4）乘以，得到一个新的二维列向量，由的两个分量反查字母表值得到的两个字母即为密文字母。

以上4步即为Hill密码的加密过程。

例如：对于明文为MI MA XUE；加密矩阵，求这段明文的Hill密码。

将明文相邻2个字母分为一组：MI MA XU EE.最后一个字母是哑字母，它是为使最后一组的字母数为2而添加的，无实际意义。查出每对字母的表值，并构造2维列向量：

把加密矩阵分别乘以这4个列向量，得到：

对这4个列向量反查字母表，但是这4个列向量中存在着一些数不是表值（大于25），无法在26个字母表中查到，我们可以Hill密码6运算，即：对这不在表中的数，加减26的整数倍，使其能够转化为0—25之间的一个整数，从而进行查表对应，如：

通过查表，这4个新的二维列向量对应的字母为：EA OC NK OO.它就是明文“MI MA XUE”的密文。

2 解密

顾名思义，解密过程就是上述加密过程的逆过程。这就涵盖了在模运算下如何解方程组这一问题。我们知道，对于一个n阶方阵可逆的充要条件是。在模m运算的条件下矩阵的可逆与一般意义的矩阵可逆略有不同。

在模m的运算下，单位矩阵E（mod m）也与通常的单位矩阵E有所不同：

E（mod m）表示，矩阵里的每一个元素减去m的整数倍后，就可以化成单位矩阵。例如：

记整数集合Z={0，1，2，…，m-1}，m为一正整数，模m可逆定义如下：

定义1 对于n阶方阵，其中中的元素均属于属于集合Z，如果存在一个方阵，中的元素也均属于集合Z，满足：

则称为模m可逆，称为为方阵的模m逆矩阵，记作：。

定义2 对于集合Z中的一个元素，为整数，如果存在集合Z中的一个元素b，满足，就把b称为a的模m倒数，记作.容易知道：Z中存在着模26倒数的整数以及其相应的倒数如下表2所示：

定理：元素属于Z的方阵模可逆的充要条件是和det没有公共素数因子。

推论：元素均属于集合Z的方阵模26可逆的充分必要条件是det不能被2和13整除。

定理：设，且模26可逆，则：

其中是的倒数。显然为Z中的数。

这样，在模26意义下，求解方程组的问题即可解决：

例：要将上述加密后的密文EA OC NK OO解密，只要把这个加密过程逆转回去，即将密文按同样方式分组，查它们的表值即得下列列向量：

上例所选取的加密矩阵，det=3不能被2和13整除，所以加密矩阵模26可逆。它对应的模26逆矩阵可以通过以下运算得到：

查表知：

这样，利用上面描述的方法，破译出明文为MI MA XU EE。

3 密码的破译

密码破译的过程顾名思义，就是找到加密矩阵及，前面讨论的加密与解密过程，可以看作是在二维向量空间内进行线性变换与其逆变换。每个明文对应的向量都是一个Z上的二维向量，该向量乘以加密矩阵后仍然是一个Z上的二维向量。由于我们要求所选取的加密矩阵应该为可逆矩阵，所以，有线性代数的知识可以知道，如果知道了两个明文对应的二维线性无关向量以及它们各自对应的密文向量，就能通過运算找出它的加密矩阵及。

例如：某军截获敌方的一份密文，破译部门通过大量的统计分析与语言分析确认为Hill密码体系，观察其中出现频数最高的双字母是CD和LW，而在明文语言中，出现频数最高的双字母是AZ和BC.试找出该密文相应的加密矩阵。

因为，密文与明文的对应如下：

于是有

，它有模26倒数，所以，在模26意义下线性无关。

同样地，它有模26倒数，所以，在模26意义下线性无关。

记，，

因此，找出加密矩阵后即可以完整地破译截获的密文。

参考文献

[1] 姜启源.数学模型[M].北京：高等教育出版社，1993.

[2] 胡章柱.密码转换问题的探究[J].数学通讯，2004（2m）：23.

[3] 王庚.现代数学建模方法[M].北京：科学出版社，2008.