python与希尔密码

前言

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据