希尔密码(Hill)

# write by 2021/7/6
# 希尔密码
from math import sqrt
import numpy as np
from scipy import linalg
DIC = "abcdefghijklmnopqrstuvwxyz"
# 使用列表创建空矩阵, 用0填充
def create_matrix(n, m):
    matrix = []
    for i in range(n):
        matrix.append([])
        for j in range(m):
            matrix[i].append(0)
    # print(matrix)
    return matrix
# 输入矩阵
def input_matrix(matrix):
    n, m = len(matrix), len(matrix[0])
    for i in range(n):
        for j in range(m):
            matrix[i][j] = int(input(f"输入{i}行{j}列数据: "))
    return matrix
# 矩阵相乘
def matrix_multiply(matrix_a, matrix_b):
    a_n, a_m = len(matrix_a), len(matrix_a[0])
    b_n, b_m = len(matrix_b), len(matrix_b[0])
    if a_m != b_n:
        return -1
    matrix_c = create_matrix(a_n, b_m)
    num = 0
    for i in range(a_n):
        for j in range(b_m):
            num = 0
            for k in range(a_m):
                num += matrix_a[i][k]*matrix_b[k][j]
            matrix_c[i][j] = num
    return matrix_c
# 辗转相除法
def gcd(a, b):
    a, b = b, a % b
    # print(a, b)
    if b == 0:
        return a
    else:
        return gcd(a, b)
# 判断秘钥的行列式是否与26互质, 以及秘钥是否可逆
def judge_key(key):
    a = np.array(key)
    det = int(np.linalg.det(a))
    if det == 0:
        return 0
    if 26 > det:
        max_gcd = gcd(26, det)
    else:
        max_gcd = gcd(det, 26)
    # print(f"26,{det}最大公约数: ", max_gcd)
    if max_gcd == -1 or max_gcd == 1:
        return 1
    return 0
def encrypt_hill(string, key):
    # 判断秘钥的行列式是否与26互质, 以及秘钥是否可逆
    if not judge_key(key):
        return -1
    ciphertext = ""
    n = len(key)
    str_len = len(string)
    plaintext_lis = []
    ciphertext_lis = []
    # 转为数字
    for i in string.lower():
        if DIC.find(i) != -1:
            plaintext_lis.append(DIC.index(i)+1)
        else:
            return -1
    # 补"0"
    if str_len % n != 0:
        for i in range(n-len(plaintext_lis) % n):
            plaintext_lis.append(0)
    m = len(plaintext_lis)//n   # m 为新矩阵的列数
    # 转为列表形式矩阵
    plaintext_matrix = create_matrix(n, m)
    for i in range(m):
        for j in range(n):
            plaintext_matrix[j][i] = plaintext_lis[i*n+j]
    # print("原位置=", plaintext_matrix)
    matrix_key = np.matrix(np.array(key))
    matrix_plaintext = np.matrix(np.array(plaintext_matrix))
    matrix_c = matrix_key*matrix_plaintext
    ciphertext_lis = matrix_c.tolist()
    # print("加密后的位置=", ciphertext_lis)
    for i in range(m):
        for j in range(n):
            ciphertext += DIC[ciphertext_lis[j][i] % 26-1]
    # print("ciphertext=", ciphertext)
    return ciphertext
def decrypt_hill(string, key):
    # 判断矩阵行列式是否与26互质, 以及秘钥是否可逆
    if not judge_key(key):
        return -1
    plaintext = ""
    n = len(key)
    m = len(string)//n
    # inv_key = np.matrix(np.array(key)).I
    inv_key = linalg.inv(np.array(key))
    # print("原矩阵=", np.array(key))
    # print("逆矩阵=", inv_key)
    # print("乘积=", inv_key*np.array(key))
    ciphertext_matrix = create_matrix(n, m)
    # 注意：这里的矩阵是一列一列放置，并不是一行一行放置
    for i in range(m):
        for j in range(n):
            ciphertext_matrix[j][i] = DIC.index(string[i*n+j])+1
    # print("密文位置=", ciphertext_matrix)
    matrix_ciphertext = np.matrix(np.array(ciphertext_matrix))
    # print(f"{matrix_ciphertext}")
    matrix_c = inv_key*matrix_ciphertext
    ciphertext_lis = matrix_c.tolist()
    # print("解密后位置=", ciphertext_lis)
    for i in range(m):
        for j in range(n):
            # if ciphertext_lis[i][j] % 26 != 0:
            # print(round(ciphertext_lis[j][i]) % 26)
            plaintext += DIC[round(ciphertext_lis[j][i]) % 26 - 1]
    return plaintext
if __name__ == '__main__':
    key_ = [[1, 2], [0, 1]]
    # print(matrix_multiply(key_, inv_key))
    print(judge_key(key_))
    ciphertext_ = encrypt_hill("flagishillissoeapy", key_)
    # ciphertext_ = "dloguszijluswogany"
    plaintext_ = decrypt_hill(ciphertext_, key_)
    print(f"{plaintext_}: {ciphertext_}")