Hill加密法
hill密码是古典密码中常见的多码加密法,是使用数学方法实现的,Hill加密是1929年提出的一种密码体制。
需要的知识:线性代数基础(矩阵乘法,逆矩阵)
该加密算法将含有m个字母的明文块加密成含有m个字母的密文块。每个明文字母被赋予一个数值,通常是a=0,b=1,……,z=25,但Hill加密使用的是随机赋值。快中每个字母的数值一起用来生成一组新的数值,这些数值就用来表示密文字母。例如,如果m=3,那么3个明文字母的数值(假设为p1,p2和p3)将通过如下的方程组转换成密文数值c1,c2和c3:
该加密法的秘钥是kij的值。
加上秘钥之后,方程组变成了这样:
字母对照表:
利用这3个方程,明文“now”转成数字为13 14 22,将这些数值代入方程组,得出密文的数值为23 25 4,将之转换为字母后,得到的“xze”就是密文了。
上边所使用的秘钥是一个矩阵,加密秘钥矩阵是M,而解密秘钥是M-1(逆矩阵),对于前面的示例,秘钥为:
要使这个过程可行,则秘钥矩阵必须是可逆的,因此秘钥值不可以随机选取。可以从m=3的示例中归纳出用数学方法表示Hill加密法的一般形式。秘钥写成一个的可逆矩阵形式:
将明文分成块,每个块含m个字母,用m*1的向量表示。例如,第i块含有字符p1,p2,......pm,写成如下形式:
那么密文就由如下计算结果确定:
加密:密文=明文*密钥矩阵
# coding:UTF-8
# hell0_w
import numpy as np
print "请输入秘钥:"
secret_key = input()
print "请输入需要加密的内容:"
pla = raw_input()
#秘钥的行数
hang_len = len(secret_key)
#取下标值
def pla_index(strs):
result = []
for i in strs:
result.append(ord(i)-97)
return result
#将明文根据秘钥长度分组,取下标,存入列表
pla_group = []
for i in range(0,len(pla),hang_len):
a = ""
a = pla[i:i+hang_len]
pla_group.append(list(pla_index(a)))
#矩阵相乘,结果存入result中,是一个二维数组
result = []
for i in pla_group:
result.append(list(np.dot(secret_key,i) % 26))
#遍历result,转成密文
cip = ""
for i in result:
for j in i:
cip += chr(j + 97)
print "加密后的结果为:"
print cip
运行示例:
解密:明文=密文*密钥矩阵的逆
看一道XMAN选拔赛的题目:
Hill
爬啊爬啊爬下了山坡
hrwd hrygc qwdb nklbk
1 2
4 7
flag: XMAN{---flag---}
看题目就是一个hill密码,给出了秘钥矩阵。
解密程序:
# coding:UTF-8
# hell0_w
import numpy as np
cip = "hrwdhrygcqwdbnklbk"
key = [[-7,2],[4,-1]]
#秘钥逆矩阵的行数
hang_len = len(key)
#取下标值
def pla_index(strs):
result = []
for i in strs:
result.append(ord(i)-97)
return result
#将密文根据秘钥逆矩阵长度分组,取下标,存入列表
cip_group = []
for i in range(0,len(cip),hang_len):
a = ""
a = cip[i:i+hang_len]
cip_group.append(list(pla_index(a)))
#矩阵相乘,结果存入result中,是一个二维数组
result = []
for i in cip_group:
result.append(list(np.dot(key,i) % 26))
#遍历result,转成明文
pla = ""
for i in result:
for j in i:
pla += chr(j + 97)
print "解密后的结果为:"
print pla
print pla[::-1]
题目中说:“爬啊爬啊爬下了山坡”,所以将最终结果逆序输出即可。
运行示例:
补充:求逆矩阵方法
方法一:使用python的numpy模块(需自行安装)
示例:
import numpy as np
a = np.matrix([[1,2],[4,7]])
print a.I
print a ** (-1)
print np.linalg.inv(a)
方法二:在线求解逆矩阵
http://www.yunsuanzi.com/matrixcomputations/solvematrixinverse.html