前言
在此记录一下用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)