密码学-Hill密码实现（python）-学习笔记

飛翔意大利

一、原理要素

1. 加密

如下图所示，并给公式：
C = (C_1\ C_2\ ... \ C_n)\\ C_i=P_iK\mod\ 26\\ C_i: 一段密文\\ P_i: 一段明文


这里选用的字符和数字的映射关系是："a": 0, "b": 1, ... , "z": 25

2. 解密

求得秘钥矩阵逆按理说即可，但这里与寻常求逆有所不同，这里是求矩阵关于 mod 的逆。公式总结如下：
K_! = yK^*\ mod\ m\\ y: |K| （行列式）在模 m 下的乘法逆元\\ K^*: K 的伴随矩阵\\ K_!：解密秘钥（相当于要求的K^{-1}）

2.1  x 关于 m 的乘法逆元 y

其中求 x 关于 m 的乘法逆元 y 的伪代码如下：（即满足公式 (x×y) mod m = 1）
y = 0
while(y < m) do
    y += 1
    if (x * y) mod m = 1 then
        return y
    end if
end while
return -1python 封装实现如下：
def modInv(x: int, m: int):
        """
        求 x 逆元 y，需满足：(x×y) mod m = 1
        :param x:
        :returns: 存在返回逆元 y，否则返回 -1
        """
        y = 0
        while y < m:
            y += 1
            if (x * y) % m == 1:
                return y
        return -1
2.2 K 的伴随矩阵 Kstar（模 m）

K^{-1}=\frac{K^*}{|K|}
import numpy as np


K_inv = np.linalg.inv(key)                                   # K 的逆（矩阵）
K_det = np.linalg.det(key)                                   # K 的行列式（数）
K_star = np.around(K_inv * K_det % m).astype(np.int64)       # K 的伴随
2.3 组合以上部分实现求秘钥

import numpy as np


def getKsigh(K: np.ndarray, m) -> np.ndarray:
    y = modInv(np.linalg.det(K))
    K_inv = np.linalg.inv(key)
    K_det = np.linalg.det(key)
    K_star = np.around(K_inv * K_det  % 26).astype(np.int64)
    return y * K_star % m

二、Code

这里把整个加密解密过程封装成类来使用：
import numpy as np
        

class HillEncryption:
    """
    :method __init__:
        设置秘钥维度 m；
        可选传入秘钥 key；
        解密秘钥 key_1；
        设置填充字符 fillchar（默认"z"）；
        数字字符映射字典 dic_num_char：{0: "a", ..., 25: "z"}；
        字符数字映射字典 dic_char_num：{"a": 0, ..., "z": 25}；
    :method setM: 设置秘钥维度
    :method setKey: 设置秘钥
    :method modInv: 求 x 关于模 m 的逆元 y
    :method _loopCrypt: 循环加密、循环解密
    :method encrypt: 加密
    :method decrypt: 解密
    :method translate: 把字符串转数字序列，数字序列转字符串
    """
    def __init__(self, m: int, fillchar: str="z", key: np.ndarray=None):
        self.m = m                  # 秘钥的维度
        self.key = key              # 秘钥
        self.key_1 = None           # 解密秘钥
        self.dic_num_char = {i: chr(ord("a") + i) for i in range(26)}  # {0: "a", ...}
        self.dic_char_num = dict(zip(self.dic_num_char.values(), self.dic_num_char.keys()))
        self.fillchar = self.dic_char_num[fillchar]    # 填充字符
   
    def setM(self, m: int) -> None:
        """设置秘钥的维度"""
        assert m > 0, "秘钥维度应当大于0！"
        self.m = m
   
    def setKey(self, key: np.ndarray=None) -> None:
        """
        设置秘钥，并进一步计算出解密秘钥 key_1
        :param key: 设置的秘钥，若不传参那么将根据维度 m 自动生成秘钥
        """
        if key is None:  # 生成直到行列式有逆元为止
            while key is None or HillEncryption.modInv(np.linalg.det(key)) == -1:
                key = np.random.randint(0, 27, size=(self.m, self.m))
            print("随机生成的秘钥是：\n", key)
        else:
            assert HillEncryption.modInv(np.linalg.det(key)) != -1, "此秘钥无逆元，请重新输入！"
        # 求得解密秘钥
        y = HillEncryption.modInv(np.linalg.det(key))
        K_inv = np.linalg.inv(key)
        K_det = np.linalg.det(key)
        K_star = np.around(K_inv * K_det  % 26).astype(np.int64)
        self.key_1 = y * K_star % 26
        self.key = key
   
    @staticmethod
    def modInv(x: int):
        """
        求 x 逆元 y，需满足：(x×y) mod 26 = 1
        :param x:
        :returns: 存在返回逆元 y，否则返回 -1
        """
        y = 0
        while y < 26:
            y += 1
            if (x * y) % 26 == 1:
                return y
        return -1
   
    def _loopCrypt(self, long: np.ndarray, K: np.ndarray) -> np.ndarray:
        """
        用来完成滑动矩阵乘积，以及拼接答案数组
        :param long: 长文
        :param K: 做乘积的方阵
        :returns:
        """
        ans = np.array([])
        for i in range(long.shape[0] // self.m):
            ans = np.mod(np.hstack((
                ans,
                np.dot(long[i*self.m:i*self.m+self.m], K)
            )), 26)
        return ans.astype(np.int64)
   
    def encrypt(self, plaintext: np.ndarray):
        assert self.m !=None and self.key is not None, "请检查补充秘钥维度 m 和秘钥 key！"
        # 明文长度和加密长度不符，填充字符
        if plaintext.shape[0] % self.m:
            plaintext = np.hstack((
                plaintext,
                [self.fillchar] *(self.m - plaintext.shape[0] % self.m)
            ))
        # 循环加密
        return self._loopCrypt(plaintext, self.key)
   
    def decrypt(self, ciphertext: np.ndarray):
        """解密"""
        assert self.key is not None, "Please input a key!"
        # 循环解密
        return self._loopCrypt(ciphertext, self.key_1)
   
    def translate(self, s, to: str):
        """
        :param to: "text"把数字数组 ndarray(dim 1) 转化成字符串 str；"num"把字符串转化成数字数组
        :param s: 需要转化的序列，可以是字符串、列表、ndarray(dim 1)
        :returns: 翻译的字符串，或是数值 ndarray
        """
        if to == "text":
            return "".join([self.dic_num_char[si] for si in s])
        elif to == "num":
            # 删除空格
            s = s.replace(" ", "")
            return np.array([self.dic_char_num[si] for si in s])


### 测试 ###
he = HillEncryption(m=3)                            # 创建 Hill 加密对象，秘钥维度为 m = 3
he.setKey()                                         # 设置秘钥，不传入秘钥则随机生成
print("\n解密秘钥是:\n", he.key_1, "\n")            # 打印解密秘钥
text = "hello the world"                            # 明文，这里空格采取去除的方式
print("明文是：\n", text, "\n")                     
nums = he.translate(text, "num")                    # 把字符串转化成对应的数值数组 ndarray
print("翻译成数字的明文是：\n", nums, "\n")
res = he.encrypt(nums)                              # 加密
print("加密后的数字密文是：\n", res, "\n")
nums = he.decrypt(res)                              # 解密
print("解密后的数字明文是：\n", nums, "\n")         
res = he.translate(nums, "text")   
print("解密后的明文是：\n", res)

天天超市

带佬！[赞同]  [爱心]

幸福一生一世

学习[思考]

玄之又璇

万水千山总是情，数科没你不能行[惊喜][惊喜][惊喜]