【python实现Hill加密】最详细的Hill加密讲解,文中附代码

前言

最近在准备网络安全期末考试,复习到Hill加密时,想起来之前做的编程作业,写的比较粗糙,而且也没有搞懂怎么求Hill密码系统的解密密钥,今天琢磨出来了,就把Hill密码系统实现并整理了,文中附有代码,供大家参考学习。

一、Hill加密基础预备知识

1、希尔密码(Hill cipher)是一种基于线性代数的多表代替密码。

简单来描述一下Hill密码系统的原理,对于一个输入明文plaintext = 'Hello world!',先把plaintext转换成一个数值矩阵P,这个数值需要自己建立索引,比如H这个字符我用1来表示…然后给出一个加密密钥矩阵K,通过加密公式,可以求出一个加密后的数值矩阵C,通过解密公式,可以求出一个解密后的数值矩阵P,最后把P映射回字符的形式,用自己建立的索引把数值矩阵映射成字符串明文。

由于Hill密码系统的解密密钥是由加密密钥经过某种变换得到的,所以Hill密码是一种对称密码。

2、希尔密码加解密的公式:

加密公式:

C

=

K

P

m

o

d

m

(1)

C=KPmodm tag{1}

C=KPmodm(1)
解密公式:

P

=

K

1

C

m

o

d

m

(2)

P=K^{-1}Cmodm tag{2}

P=K1Cmodm(2)
其中C表示明文,P表示密文,矩阵

K

K

K表示加密密钥,矩阵

K

1

K^{-1}

K1表示解密秘钥,m表示Hill密码系统是在模m下实现的。Hill密码的难点在于求解解密秘钥。

3、希尔密码解密秘钥

K

1

K^{-1}

K1的公式:

Hill密码的解密秘钥

K

1

K^{-1}

K1不是简单的对

K

K

K求逆,而是在模m下,对

K

K

K求逆。此时,求逆公式也发生了变化。

K

1

=

d

e

t

(

K

)

1

K

(1)

K^{-1}=det(K)^{-1}*K^* tag{1}

K1=det(K)1K(1)其中

K

K^*

K

K

K

K的伴随矩阵,

d

e

t

(

K

)

1

det(K)^{-1}

det(K)1

K

K

K的行列式值在模m下的乘法逆元。对于伴随矩阵

K

K^*

K的求解,比较容易,我们用如下公式不难求出。

K

=

d

e

t

(

K

)

K

1

(2)

K^*=det(K)*K^{-1} tag{2}

K=det(K)K1(2)

4、求一个数在模m下的乘法逆元:

在模m下,

x

x

x的乘法逆元

y

y

y需要满足的条件为:

(

x

×

y

)

m

o

d

m

=

1

(3)

(x×y)modm=1 tag{3}

(x×y)modm=1(3)

注:并不是任何数在模m下都有乘法逆元。

# 在模26下求一个数x的乘法逆元y,只需要满足(x×y) mod 26 = 1
x = -939
# y的取值范围为[0,26)
y = 0
while(y < 26):
    res = (x * y) % 26
    if res == 1:
        print(x,"的乘法逆元为:",y)
        break
    else:
        y = y + 1
        if y == 26:
            print(x,"在模26下,不存在乘法逆元!")
5、求Hill密码解密秘钥

K

1

K^{-1}

K1

import numpy as np
#这个y是det(K)在模26下的乘法逆元,前面已经求出来是17,这里直接用
y = 17
#K矩阵
K = np.array([[17,17,5],[21,18,21],[2,2,19]], dtype=int)
# 对K矩阵求逆,得到K的逆矩阵K1
K1 = np.linalg.inv(K)
# 求K矩阵的行列式值det(K)
K_abs = np.linalg.det(K)
print("K的行列式的值为:",K_abs)
# 求K矩阵的伴随矩阵
K2 = K1 * K_abs  % 26
# 由于伴随矩阵得到的可能是浮点数矩阵,故需要对其进行四舍五入取整
# 并将每个元素成员强制转换为int类型
K2 = np.around(K2)
K2 = K2.astype(np.int)
print("K的伴随矩阵为:n",K2)
# 求Hill加密的解密秘钥
K3 = y * K2 % 26
print("Hill密码的解密秘钥为:n",K3)

运行结果:

K的行列式的值为 -939.0
K的伴随矩阵为:
 [[14 25  7]
 [ 7  1  8]
 [ 6 26  1]]
Hill密码的解密秘钥为:
 [[ 4  9 15]
 [15 17  6]
 [24  0 17]]

二、Hill加解密完整代码

这里代码没有为字母分配索引,直接用字母的ascii码值作索引,为了保证每个字母取模后的唯一性,整个过程选的模m的值为256,也就是说下面Hill加解密代码是在模256下完成的,读者也可以根据自己的实际情况,在不同的模值下进行测试,也可考虑为字母分配索引。

import numpy as np

# 求在模m下任意一个数的乘法逆元
def Multi_Inverse(x,m):
    # 输入:求一个数x在模m下的乘法逆元
    # y的取值范围为[0,m)
    y = 0
    while(y < m):
        res = (x * y) % m
        if res == 1:
            print("在模%d下,加密密钥行列式值为%d,它的乘法逆元为%d" % (m,x,y))
            break
        else:
            y = y + 1
            if y == m:
                print(x,"在模",m,"下,不存在乘法逆元!")
                return 0
    return y

# 求伴随矩阵
def Adjoint_Mat(K,K_det,m):
    # 输入:矩阵K,矩阵的行列式值K_det,模m
    # 对K矩阵求逆,得到K的逆矩阵K1
    K1 = np.linalg.inv(K)
    # 求K矩阵的伴随矩阵
    K2 = K1 * K_det % m
    # 由于伴随矩阵得到的可能是浮点数矩阵,故需要对其进行四舍五入取整
    # 并将每个元素成员强制转换为int类型
    K2 = np.around(K2)
    K2 = K2.astype(np.int)
    return K2

# 求解密密钥k
def Decrypt_Key(K,m):
    # 求K矩阵的行列式值det(K),模m
    K_det = np.linalg.det(K)
    K2 = Adjoint_Mat(K, K_det, m)
    # 求det(K)在模26下的乘法逆元
    y = Multi_Inverse(K_det, m)
    # 求Hill加密的解密秘钥
    K3 = y * K2 % m
    return K3

# 将矩阵(二维数组)ascii码转字符
def ascii2_char(array1):
    plaintext = ''
    row = array1.shape[0]
    col = array1.shape[1]
    for i in range(row):
        for j in range(col):
            plaintext = plaintext + chr(array1[i][j])
    return plaintext

# 将明文转换为ascii码值矩阵,行数与加密密钥保持一致
def char2ascii2(plaintext,row,m):
    # 输入:明文plaintext,加密矩阵的行数row,模m
    l1 = [0,0,0]
    l2 = []
    for i in range(len(plaintext)):
        j = i % row
        if (i > 0 and i % row == 0):
            l2.append(l1)
            l1 = [0, 0, 0]
        l1[j] = ord(plaintext[i])
    l2.append(l1)
    m1 = np.array(l2)
    m1 = np.reshape(m1,(m1.shape[1],m1.shape[0]))
    m1 = m1 % m
    return m1

if __name__ == "__main__":
    # K矩阵,即加密密钥
    K = np.array([[17,17,5],[21,18,21],[2,2,19]], dtype=int)
    # 解密密钥k,模m
    m = 256
    k = Decrypt_Key(K,m)
    print("Hill密码的解密秘钥为:n",k)

    # 明文
    plaintext = 'Programming is a happy thing'
    print("原始明文内容:n",plaintext)

    # 加密密钥矩阵K的行数row
    row = K.shape[0]
    # 将明文转换为ascii码值矩阵,行数与加密密钥保持一致
    # m1为明文ascii码值矩阵
    m1 = char2ascii2(plaintext,row,m)

    # 加密过程,m2为加密后的矩阵
    m2 = np.dot(K,m1) % 256
    Ciphertext = ascii2_char(m2)
    print("密文内容:n",Ciphertext)

    # 解密过程,m3为加密后的矩阵
    m3 = np.dot(k,m2) % 256
    decrypt_text = ascii2_char(m3)
    print("解密结果:n", decrypt_text)

运行结果:

在模256,加密密钥行列式值为-939,它的乘法逆元为253
Hill密码的解密秘钥为:
 [[124 171 223]
 [ 47  85 244]
 [238   0 153]]
原始明文内容:
 Programming is a happy thing
密文内容:
"d7´oæ¾PÜODO”¼
解密结果:
 Programming is a happy thing  

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>