希尔密码详解

大家好，欢迎来到IT知识分享网。

本文翻译自《Learn Hill Cipher with 3×3 Matrix Multiplicative Inverse Example》，英文水平有限，如有不足之处还请指正。

希尔密码是什么？

希尔密码是一种基于线性代数的多表替换密码。使用希尔密码需要对矩阵的有基本的了解。希尔密码也是一种分块加密算法（block cipher），它接受输入的明文，并生成一个密文块。希尔密码是由Lester S在1929年发明的。是第一个同时处理三个及以上符号或字母的多表密码。下面的公式用于加密和解密：

$$\begin{gathered} Cipher=(Plain\times Key)\mathrm{mod}N \\ Plain=(Cipher\times Ke{y}^{-1})\mathrm{mod}N \end{gathered}$$

其中，$Plain$是加密前的明文矩阵，$Cipher$是加密后的密文矩阵，$Key$是密钥矩阵（要求是一个方阵），$N$是字符集的大小，，$Ke{y}^{-1}$是密钥矩阵在模N空间上的逆矩阵。

希尔密码的加密步骤

接下来让我们通过下面的例子来理解希尔密码加密解密的流程。

加入我们要加密如下信息：“ATTACK IS TONIGHT”，密钥矩阵$K$如下：
$$K=\left(\begin{array}{ccc}3& 10& 20\\ 20& 9& 17\\ 9& 4& 17\end{array}\right)$$
加密这一段明文的步骤如下：

1 将明文转化为数字矩阵

第一步是将给定的明文转化为明文数字矩阵，首先按照A-Z分别映射到0-25的方式，将原文字母映射为数字，并且将得到的数字序列根据密钥的维度排列成明文矩阵$P$（在我们的教程中采用的是按行排列的方法）。
$$P=\left(\begin{array}{ccc}A& T& T\\ A& C& K\\ I& S& T\\ O& N& I\\ G& H& T\end{array}\right)=\left(\begin{array}{ccc}0& 19& 19\\ 0& 2& 10\\ 8& 18& 19\\ 14& 13& 8\\ 6& 7& 19\end{array}\right)$$

由于加密过程中使用了矩阵乘法运算，因此对于维度为$M\times M$的密钥矩阵，我们需要将明文序列排列成一个$R\times M$的矩阵，当序列长度不够时，可以用我们预先设定的方式进行填充。

2 计算矩阵乘法

第二步，做矩阵模$N$乘法，即现将两矩阵相乘，再将所得结果每个元素均除$N$取余，由于教程中加密字符集仅涉及26个字母，因此$N=26$，如下
$$C=P\times K\mathrm{mod}N=\left(\begin{array}{ccc}0& 19& 19\\ 0& 2& 10\\ 8& 18& 19\\ 14& 13& 8\\ 6& 7& 19\end{array}\right)\times \left(\begin{array}{ccc}3& 10& 20\\ 20& 9& 17\\ 9& 4& 17\end{array}\right)\mathrm{mod}26$$

将上一步计算得到得密文矩阵$C$按照字母到数字的映射表转化为字母序列并展开得到密文“FNWAGWJGJKDNRRQ”。
$$C=\left(\begin{array}{ccc}5& 13& 22\\ 0& 6& 22\\ 9& 6& 9\\ 10& 3& 13\\ 17& 17& 16\end{array}\right)=\left(\begin{array}{ccc}F& N& W\\ A& G& W\\ J& G& J\\ K& D& N\\ R& R& Q\end{array}\right)$$

希尔密码的解密

1 计算密钥矩阵的模N行列式

计算给定的密钥矩阵$K$的行列式，然后将所得行列式的值除以$N$取余。

$$\det K=\left|\begin{array}{ccc}3& 10& 20\\ 20& 9& 17\\ 9& 4& 17\end{array}\right|=-1635$$
之后再除26取余，则$\det K=-1635\mathrm{mod}26=3$，（这是因为$-1635=26\times (-63)+3$）

2 计算行列式模N乘法逆元

模n乘法逆元是指，对于整数$a$，$n$，如果存在整数$b$满足$ab\mathrm{mod}n=1$，则说$b$是$a$模$n$的乘法逆元，记为$a^{-1}\mathrm{mod}n=b$。其中，$a$存在模$n$乘法逆元的充要条件是$a$与$n$互质。

上一步中解出的行列式的模26乘法逆元为，$|K{|}^{-1}\mathrm{mod}26=3^{-1}\mathrm{mod}26=9$

3 计算密钥矩阵的伴随矩阵

计算伴随矩阵，可以直接使用伴随矩阵的定义计算，也可以使用公式$A{A}^{\ast }=|A|E$计算，如果手工计算的话，我们的例子中的密钥矩阵$K$的伴随建议按照定义计算，因为$K$的逆矩阵很不好计算，计算得$K$的伴随矩阵为
$$K^{\ast }=\left(\begin{array}{ccc}85& -90& -10\\ -187& -129& 349\\ -1& 78& -173\end{array}\right)$$

4 计算密钥矩阵的模N逆矩阵

矩阵的模N逆矩阵是指，对于方阵$A$，整数$n$，如果存在方阵$B$满足$AB\mathrm{mod}n=BA\mathrm{mod}n=E$，$E$为$n$阶单位矩阵，则说$B$是$A$模$n$逆矩阵，记为$A^{-1}\mathrm{mod}n=B$。其中，$A$存在模$n$逆矩阵的充要条件是$\det A$与$n$互质。这里直接给出一个模N逆矩阵的一个计算公式：
$$A^{-1}\mathrm{mod}n=(|A{|}^{-1}\mathrm{mod}n\times A^{\ast })\mathrm{mod}n$$

5 解密

希尔密码的安全性

希尔密码的基本实现很容易受到已知明文攻击，因为它是线性的。对于拦截到明文/密文对的攻击者来说，希尔密码是一个易于激活成功教程的线性系统。如果系统是不确定的，有必要添加更多的明文/密文对，因为用标准线性代数算法计算反解出加密过程只需要花费很少的时间。

矩阵乘法不能单独产生安全密码，但当与应用在矩阵上的其他非线性操作结合时，它仍然是一个必不可少的步骤，因为它导致扩散。例如，如果一个矩阵被明智而恰当地选择，它可能会保证很小的差异，但在执行矩阵乘法时，矩阵将导致很大的差异。一些现代密码，如AES，使用矩阵乘法来提供扩散。

受限于本人的英文水平，这里给出原文，以免读者被我蹩脚的翻译误导。

The basic implementation of the Hill cipher was vulnerable to a known plaintext attack because it was linear. An attacker who will intercept plaintext or ciphertext alphabet pairs forms a linear system that can be easily solved. If the system is indeterminate, it’s necessary to add a few more plaintext/ciphertext pairs because calculating the solution by the standard linear algebra algorithms consumes a minute amount of time.

Matrix multiplication does not result in a secure cipher solely but is still an essential step when combined with other non-linear operations applied on the matrix as it leads to diffusion. For example, if a matrix is chosen wisely and appropriately, it might guarantee small differences, but the matrix will result in large differences in performing matrix multiplication. A few modern ciphers such as AES use matrix multiplication to provide diffusion.

Python 实现

import numpy as np key = np.array( [[3, 10, 20], [20, 9, 17], [9, 4, 17]], dtype=np.int16 ) dim_key = 3 # 字母转化为数字（不区分大小写） def char2int(c): a = ord(c) if ord('a') <= a <= ord('z'): return a-97 else: return a-65 # 数字转化为大写字母 def int2char(c): return chr(c+65) def encrypt(s): col_p = dim_key row_p = len(s) // dim_key if len(s) % dim_key != 0: row_p += 1 # 转化为矩阵，不足补零 p = np.zeros((row_p, col_p), dtype=np.int16) for i in range(len(s)): p[i//col_p, i%col_p] = char2int(s[i]) c = np.matmul(p, key) % 26 result = "" for i in range(row_p): for j in range(col_p): result += int2char(c[i, j]) return result def modular_inv(a, p): x, y, m = 1, 0, p while a > 1: q = a // m t = m m = np.mod(a, m) a = t t = y y, x = x - np.int64(q) * np.int64(y), t if x < 0: x = np.mod(x, p) return np.mod(x, p) def decode(s): col_c = dim_key row_c = len(s) // dim_key # 转化为矩阵，不足补零 c = np.zeros((row_c, col_c), dtype=np.int16) for i in range(len(s)): c[i // col_c, i % col_c] = char2int(s[i]) det_k = np.linalg.det(key) det_k_inv = modular_inv(det_k % 26, 26) k_ = np.linalg.inv(key) k_ = np.around(k_ * det_k).astype(np.int64) k_inv = (det_k_inv * k_) % 26 p = np.matmul(c, k_inv) % 26 result = "" for i in range(row_c): for j in range(col_c): result += int2char(p[i, j]) return result if __name__ == "__main__": c = encrypt("ATTACKISTONIGHT") print(c) # FNWAGWJGJKDNRRQ p = decode(c) print(p) # ATTACKISTONIGHT