前言

在此记录一下用python脚本解决希尔密码的方法。

加密原理

首先必须要有一个NxN（一般为2×2或者3×3）的可逆矩阵，这个矩阵称为密钥矩阵KEY，然后再把明文按照字母编码A=0，B=1，C=2，D=3………（官方的编码形式，还有其他不常见的编码形式），然后再写成矩阵M（从第一列开始由上到下写，这是官方的顺序），通过KEY*M可以得到一个新的矩阵，该矩阵中的每一个元素进行mod26，即为密文矩阵C，再按原来的字母编码转化为字母形式，即可得到密文。

解密原理

如果我们已知密钥矩阵KEY和密文矩阵C，则由加密原理的C=KEYM，根据线性代数知识可以得到：M=KEY^(-1)C，因此通过求出密钥矩阵KEY的逆矩阵，按照原先加密步骤往回推导可以得到明文矩阵M。

代码实现

一开始还在犹豫，思维还停留在C语言上，对如何实现矩阵的相乘，矩阵的求逆感到绝望，然而python的numpy库便很好地解决了这个问题，直接对两个矩阵连上乘号*就可以实现矩阵的相乘，而sympy库直接Matrix类.inv()即可实现矩阵求逆。只能仰天长叹python大法好啊。
先把总的过程分开来，然后逐个解决并用代码来实现：

第一步

将字母进行编码，这里会用到string库中的alphabet_uppercase，先把26个大写字母以字符串的形式列出来，然后通过index函数，比对出明文的字母所对应的是第几个字母编号，即可实现字母编码。

alphabet=string.ascii_uppercase  #alphabet='ABCDEFGHIJKLMNOPQRSTUVWXYZ'

第二步

将字符串按每一列从上到下写出矩阵，参照网上大佬的思路，将该操作编写成一个函数：

def convertmatrix(m,dimension):   #传入的参数为目标字符串和所要矩阵的行数
    for index,i in enumerate(m):      #利用enumerate函数与for循环的结合
        value=[]
        if index % dimension == 0:
            for j in range(0,dimension):
                value.append([alphabet.index(m[index+j])])  #第一步中index函数的应用
          if index == 0:
                m_mat = np.matrix(value)  #np.matrix()作用是将列表转化为矩阵
            else:
                m_mat = np.hstack((m_mat,value))  #np.hstack()作用是将两个矩阵在水平方向上平铺
                                  #也就是把几个列给连起来
    return m_mat

第三步

KEY矩阵的求逆并进行解密操作，通过sympy库中的inv()即可实现矩阵求逆（前提是将矩阵转为Matrix类才可用该方法），重点还是在于解密函数的构造：

def hilldecrypt(c,key,dimension):
    c=convertmatrix(c,dimension);  #将密文转化为密文矩阵C
    m=(key*c)(%26)  #得到明文矩阵M
    m=m.T   #为了方便查看明文矩阵对应的字符串，在此利用矩阵的转置将明文对应的字符按下标顺序排出来
    size=np.size   #np.size:计算矩阵的元素有多少个
    m=m.tolist()    #将转置后的矩阵转化为列表形式，方便之后的操作
    m=[y for x in m for y in x]    #列表推导式，作用是将二维列表转化为一维
    for i in range(0,size):
        m[i]=chr(m[i]+65)   #根据0对应A，1对应B....可以通过ASCII将他们联系起来
    m = ''.join(m)    #将列表形式转化成字符串形式，方便查看结果
    return m

结合加密原理和解密原理可以发现，在hilldecrypt函数中，如果传的值不是KEY的逆矩阵和密文，而是传入KEY矩阵和明文，则可以得到密文，也就是说，hilldecrypt可以同时用于加密和解密。

应用

2018 hgame上的一道题目：

hill密码，秘钥是3×3矩阵，flag的密文是TCSHXZTCXAPBDKJVJDOHJEAE，flag中含有BABYSHILL，flag是有意义的英文，最终提交格式: hgame{有意义的英文}

思路

目标就是要把密钥给求出来，而我们已知的是密文中存在BABYSHILL，但不知道是对应密文的哪九个字母，根据M=KEYC有：KEY=MC^(-1)，所以可以通过穷举这九个字母，结合矩阵的运算求解KEY，进而得到明文,找到有意义的那句话。

最终得到代码：

import numpy as np
from sympy import Matrix
import string

alphabet = string.ascii_uppercase


# 将字符串生成对应的矩阵
def convert2matrix(m, dimension):
    for index, i in enumerate(m):
        value = []
        if index % dimension == 0:
            for j in range(0, dimension):
                value.append([alphabet.index(m[index + j])])
            if index == 0:
                m_mat = np.matrix(value)
            else:
                m_mat = np.hstack((m_mat, value))
    return m_mat


# 希尔解密函数，前提已知密钥矩阵的逆矩阵，与密文
def hillencrypt(unknown_c, dec_key, dimension):
    unknown_c = convert2matrix(unknown_c, dimension)
    m = (dec_key * unknown_c) % 26
    m = m.T
    size = np.size(m)
    m = m.tolist()
    m = [y for x in m for y in x]
    for i in range(0, size):
        m[i] = chr(m[i] + 65)
    return m


if __name__ == '__main__':
    m = 'BABYSHILL'
    c = 'HXZTCXAP'
    dimension = 3
    unknown_c = 'TCSHXZTCXAPBDKJVJDOHJEAE'
    c = convert2matrix(c, dimension)
    c = Matrix(c)
    # 求密文矩阵C的逆矩阵，再mod26，注意，只有Matrix类才有inv_mod方法可以用！
    c_inv = c.inv_mod(26)

    c_inv = c_inv.tolist()
    m = convert2matrix(m, dimension)
    m = np.matrix(m)
    dec_key = m * c_inv
    dec_key %= 26
    print(dec_key)
    m = hillencrypt(unknown_c, dec_key, dimension)
    print(m)