【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=K?1Cmodm(2)
其中C表示明文，P表示密文，矩陣 K K K表示加密密鑰，矩陣 K ? 1 K^{-1} K?1表示解密秘鑰，m表示Hill密碼系統是在模m下實作的，Hill密碼的難點在于求解解密秘鑰，

3、希爾密碼解密秘鑰 K ? 1 K^{-1} K?1的公式：

Hill密碼的解密秘鑰 K ? 1 K^{-1} K?1不是簡單的對 K K K求逆，而是在模m下，對 K K K求逆，此時，求逆公式也發生了變化，
K ? 1 = d e t ( K ) ? 1 ? K ? (1) K^{-1}=det(K)^{-1}*K^* \tag{1} K?1=det(K)?1?K?(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)?K?1(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} K?1：

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