Hed9eh0g

前进的路上总是孤独的

Hill Cipher And Python

本文共计有2297个字

希尔密码

经过一星期断断续续的理解,终于完成了对希尔密码解密的代码,不敢怠慢,马上在此做笔记总结一下。

加密原理

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

解密原理

如果我们已知密钥矩阵KEY和密文矩阵C,则由加密原理的C=KEY*M,根据线性代数知识可以得到: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可以同时用于加密和解密。

应用

hgame上的一道题目:

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

思路

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

最终得到代码:

import numpy as np
import string
import sympy
alphabet=string.ascii_uppercase()
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

def hilldecrypt(c,dimension)
点赞

发表评论

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