5. 希尔（Hill）密码

• 基本思想：将n个明文字母通过线性变换，将它们转换为n个密文字母，解密只需做一次逆变换即可。

• 密钥$K=\{Z_{26}\text{上}\text{的}n\times n\text{可}\text{逆}\text{矩}\text{阵}\}$$K=\{Z_{26}上的n\times n可逆矩阵\}$

• M与C均是n维向量

• 计为： $\begin{array}{c}M=\left(\begin{array}{c}{m}_1\\ m_2\\ m_3\\ ⋮\\ m_n\end{array}\right),C=\left(\begin{array}{c}{c}_1\\ c_2\\ c_3\\ ⋮\\ c_n\end{array}\right),K=(k_{ij}{)}_{n\times n}=\left(\begin{array}{cccc}{k}_{11}& k_{12}& \cdots & k_{1n}\\ k_{21}& k_{22}& \cdots & k_{2n}\\ k_{31}& k_{32}& \cdots & k_{3n}\\ ⋮& ⋮& \ddots & ⋮\\ k_{n1}& k_{n2}& \cdots & k_{nn}\end{array}\right)\end{array}$$M=\begin{pmatrix}m_1\\m_2\\m_3\\\vdots\\m_n\end{pmatrix},C=\begin{pmatrix}c_1\\c_2\\c_3\\\vdots\\c_n\end{pmatrix},K=(k_{ij})_{n\times n} = \begin{pmatrix}k_{11}&k_{12}&\cdots&k_{1n}\\k_{21}&k_{22}&\cdots&k_{2n}\\k_{31}&k_{32}&\cdots&k_{3n}\\\vdots&\vdots&\ddots&\vdots\\k_{n1}&k_{n2}&\cdots&k_{nn}\end{pmatrix}$

• $C=K\cdot M(mod26)$$C=K\cdot M(mod 26)$

• $M=K^{-1}\cdot C(mod26)$$M=K^{-1}\cdot C(mod26)$ 注:$K^{-1}\text{为}K\text{在}mod26\text{上}\text{的}\text{逆}\text{矩}\text{阵}，\text{满}\text{足}K\cdot K^{-1}=K^{-1}\cdot K=I(mod26)$$K^{-1}为K在mod26上的逆矩阵，满足K\cdot K^{-1}=K^{-1}\cdot K=I(mod26)$

• 例：

  设M=good,n=2,$\begin{array}{c}K=\left(\begin{array}{cc}11& 8\\ 3& 7\end{array}\right)\end{array}$$K=\begin{pmatrix}11&8\\3&7\end{pmatrix}$

加密： $\left(\begin{array}{c}{c}_1\\ c_2\end{array}\right)=K\left(\begin{array}{c}{m}_1\\ m_2\end{array}\right)=\left(\begin{array}{cc}11& 8\\ 3& 7\end{array}\right)\left(\begin{array}{c}6\\ 14\end{array}\right)(mod26)\equiv \left(\begin{array}{c}22\\ 12\end{array}\right)\Rightarrow \left(\begin{array}{c}w\\ m\end{array}\right)$$\begin{pmatrix}c_1\\c_2\end{pmatrix}=K\begin{pmatrix}m_1\\m_2\end{pmatrix}=\begin{pmatrix}11&8\\3&7\end{pmatrix}\begin{pmatrix}6\\14\end{pmatrix}(mod26)\equiv\begin{pmatrix}22\\12\end{pmatrix} \Rightarrow \begin{pmatrix}w\\m\end{pmatrix}$

$\left(\begin{array}{c}{c}_3\\ c_4\end{array}\right)=K\left(\begin{array}{c}{m}_3\\ m_4\end{array}\right)=\left(\begin{array}{cc}11& 8\\ 3& 7\end{array}\right)\left(\begin{array}{c}14\\ 3\end{array}\right)(mod26)\equiv \left(\begin{array}{c}22\\ 11\end{array}\right)\Rightarrow \left(\begin{array}{c}w\\ l\end{array}\right)$$\begin{pmatrix}c_3\\c_4\end{pmatrix}=K\begin{pmatrix}m_3\\m_4\end{pmatrix}=\begin{pmatrix}11&8\\3&7\end{pmatrix}\begin{pmatrix}14\\3\end{pmatrix}(mod26)\equiv\begin{pmatrix}22\\11\end{pmatrix} \Rightarrow \begin{pmatrix}w\\l\end{pmatrix}$

得C=wmwl

易知：

$\begin{array}{c}{K}^{-1}=\left(\begin{array}{cc}7& 18\\ 23& 11\end{array}\right)\end{array}$$K^{-1}=\begin{pmatrix}7&18\\23&11\end{pmatrix}$

解密：

$\left(\begin{array}{c}{m}_1\\ m_2\end{array}\right)=K^{-1}\left(\begin{array}{c}{c}_1\\ c_2\end{array}\right)=\left(\begin{array}{cc}7& 18\\ 23& 11\end{array}\right)\left(\begin{array}{c}22\\ 12\end{array}\right)(mod26)\equiv \left(\begin{array}{c}6\\ 14\end{array}\right)\Rightarrow \left(\begin{array}{c}g\\ o\end{array}\right)$$\begin{pmatrix}m_1\\m_2\end{pmatrix}=K^{-1}\begin{pmatrix}c_1\\c_2\end{pmatrix}=\begin{pmatrix}7&18\\23&11\end{pmatrix}\begin{pmatrix}22\\12\end{pmatrix}(mod26)\equiv\begin{pmatrix}6\\14\end{pmatrix} \Rightarrow \begin{pmatrix}g\\o\end{pmatrix}$

$\left(\begin{array}{c}{m}_3\\ m_4\end{array}\right)=K^{-1}\left(\begin{array}{c}{c}_3\\ c_4\end{array}\right)=\left(\begin{array}{cc}7& 18\\ 23& 11\end{array}\right)\left(\begin{array}{c}22\\ 11\end{array}\right)(mod26)\equiv \left(\begin{array}{c}14\\ 3\end{array}\right)\Rightarrow \left(\begin{array}{c}o\\ d\end{array}\right)$$\begin{pmatrix}m_3\\m_4\end{pmatrix}=K^{-1}\begin{pmatrix}c_3\\c_4\end{pmatrix}=\begin{pmatrix}7&18\\23&11\end{pmatrix}\begin{pmatrix}22\\11\end{pmatrix}(mod26)\equiv\begin{pmatrix}14\\3\end{pmatrix} \Rightarrow \begin{pmatrix}o\\d\end{pmatrix}$

得M=good