大佬教程收集整理的这篇文章主要介绍了Hill 密码，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

1. 原理介绍

希尔密码（Hill Cipher）是运用基本矩阵论原理的代替密码技术，由 Lester s. Hill 在 1929 年发明，26 个英文字母可表示成 0 ~ 25 的数字，将明文转化成 n 维向量，与一个 n × n 矩阵相乘后，得到的结果模 26，即可得到密文对应的值

假设对明文 act 加密：a 为 0，b 为 1，t 为 19，对其进行向量化得到 (M = [0,2,19]^T)。选取 3 × 3 阶矩阵密钥：

加密过程如下：

得到的密文为 pob

解密时，必须先算出密钥的逆矩阵，再根据加密的过程做逆运算

2. 矩阵求逆

对于矩阵求逆，常见的有 伴随矩阵 和 行变换 两种方法，不过需要注意的是，此处的逆矩阵为模 26 的逆矩阵，也就是所里面所有的运算（加减乘除）都是在模 26 下的运算

2.1 利用伴随矩阵

一个 (n times n) 矩阵 (A)，(A) 的逆矩阵 (A^{-1}) 为 (frac{1}{D} cdot (C_A)^T)。其中 d 是矩阵 (A) 的行列式，(C_A) 是 (A) 的伴随矩阵，((C_A)^T) 是 (C_A) 的转置矩阵

在求伴随矩阵的转置 ((C_A)^T) 的过程中，只使用了乘法与加减法运算， 并未使用特殊的除法运算，故算法过程与对一般矩阵求 ((C_A)^T) 无异，区别只在于每次运算时都需要模 26

在求矩阵行列式 (d) 的时候，若是采用余子式法，则也与一般矩阵无异。最后使用 扩展欧几里得 算法判断逆元的存在性：若不存在逆元，则矩阵在模 26 条件下不可逆；若存在逆元，则结合上述求解出的 ((C_A)^T) 可计算出 (A^{-1})

2.2 利用高斯行变换

(1) 先不考虑模 26 的条件

根据求伴随矩阵的过程，有 (A^{-1} = frac{1}{D} cdot (C_A)^T)，那么 ((C_A)^T = d A^{-1})。由于矩阵 (A) 为整数矩阵，故 ((C_A)^T) 也为整数矩阵（因为其计算过程中只使用了加减法与乘法）

也就是说，虽然通过 初等行变换 求解出的 (A^{-1}) 不是整数矩阵，但计算 (d A^{-1}) 的结果一定是整数矩阵。虽然使用初等行变换的过程会产生一些精度误差，但是可以通过四舍五入的方式避免

同时，在初等行变换的过程中可以很容易求出行列式 (d)，也就是说可以求出 (d A^{-1})，即 ((C_A)^T)

(2) 结合模 26 的条件

在通过上述方法求解出 ((C_A)^T) 和 (d) 后，采用类似的方式求解 (frac{1}{D} cdot (C_A)^T) 就可得到矩阵在模 26 条件下的逆矩阵

这种方式的优点在于时间复杂度少，但有可能产生一定的精度问题，在计算除法的过程中很可能会造成精度的丢失，在求解高阶矩阵时会产生错误

2.3 利用高斯行变换（另）

思考利用行变换求逆的过程，一般是将矩阵的某个元素变为 1 之后，再消去同一列上的其它元素。在没有模 26 条件下对矩阵求逆时，使用的是除法，但在模 26 条件下时，只有少数元素存在逆元，能够使用模 26 条件下的除法

回顾 扩展欧几里得 算法，思考是否存在其它的方式能够将元素变为 1。如果能够找到两个互素的元素 (a,b)，利用 扩展欧几里得 算法可以找到 (x,y)，使得 (xa+by=1)，通过这种方法也能让矩阵元素变成 1

那么在模 26 条件下，满足以下任意一个条件的元素能够化成 1：

稍微再细化一些，可以发现以下两个规律

那么在寻找能够化成 1 的元素时，可以分为以下几个步骤：

举例

例如要求解矩阵

的逆元

对其扩展矩阵同步执行上述变换，可以得到逆矩阵

就时间复杂度来说，该方法的耗时略高于上文提及的会照成精度损失的高斯行变换，但优点是不会产生精度误差，在求解高阶矩阵时依旧具有很好的效果

3. 代码实现(python)

3.1 模26求逆

def _ex_gcd(a: int, b: int) -> (int, int, int):
    """
    :return: gcd x y
    """
    if a == 0 and b == 0:
        return None
    else:
        x1, y1, x2, y2 = 1, 0, 0, 1  # 初始化x1,y1,x2,y2
        while b:
            q, r = divmod(a, b)
            a, b = b, r  # gcd(a,b)=gcd(b,a%b)
            x1, y1, x2, y2 = x2, y2, x1 - q * x2, y1 - q * y2
        return (a, x1, y1) if a > 0 else (-a, -x1, -y1)


def _opt1(matrix_r: list, col: int, n: int):
    """矩阵某行乘以一个数"""
    for c in range(col):
        matrix_r[c] = (matrix_r[c] * n) % 26


def _opt2(matrix_r1: list, matrix_r2: list, col: int, n: int):
    """某行加上另一行的倍数"""
    for c in range(col):
        matrix_r1[c] = (matrix_r1[c] + n * matrix_r2[c]) % 26


def _inverse(matriX):
    """模26求逆"""
    row, col = len(matriX), len(matrix[0])  # 矩阵的行列
    t_matrix = [[matrix[r][c] for c in range(col)] for r in range(row)]
    e_matrix = [[0 if c != r else 1 for c in range(col)] for r in range(row)]  # 扩展矩阵

    for i in range(row):
        # 寻找出符合条件的行
        odd, even, = None, None
        for r in range(i, row):
            if t_matrix[r][i] & 1:
                odd = r
            elif t_matrix[r][i] != 0:
                even = r
            # 找到对应元素为不等于13的奇数的行
            if odd is not None and t_matrix[odd][i] != 13:
                _, iv, _ = _ex_gcd(t_matrix[odd][i], 26)
                _opt1(t_matrix[odd], col, iv)
                _opt1(e_matrix[odd], col, iv)
                break
            # 找到对应元素分别为奇数和偶数的两行
            elif odd is not None and even is not None:
                _, x, y = _ex_gcd(t_matrix[odd][i], t_matrix[even][i])
                _opt1(t_matrix[odd], col, X)
                _opt2(t_matrix[odd], t_matrix[even], col, y)

                _opt1(e_matrix[odd], col, X)
                _opt2(e_matrix[odd], e_matrix[even], col, y)
                break
        else:  # 找不到对应的行
            return None
        # 交换行
        if odd != i:
            t_matrix[i], t_matrix[odd] = t_matrix[odd], t_matrix[i]
            e_matrix[i], e_matrix[odd] = e_matrix[odd], e_matrix[i]
        # 对其它行的变换
        for r in range(row):
            if r != i:
                temp = t_matrix[r][i]
                _opt2(t_matrix[r], t_matrix[i], col, -temp)
                _opt2(e_matrix[r], e_matrix[i], col, -temp)

    return e_matrix

3.2 矩阵乘法

def _mul(m1, m2):
    """矩阵乘法"""
    row1, col1 = len(m1), len(m1[0])
    row2, col2 = len(m2), len(m2[0])
    if col1 != row2:
        return None
    res = [[0 for _ in range(col2)] for _ in range(row1)]
    for row in range(row1):
        for col in range(col2):
            res[row][col] = sum([m1[row][k] * m2[k][col] for k in range(col1)]) % 26
    return res

3.3 Hill密码

此处将 Hill 密码写成一个类的形式

class HillCipher:
    def __init__(self, matriX):
        self.encrypt_key = matrix
        self.decrypt_key = _inverse(matriX)
        self._n = len(matriX)

    def encrypt(self, plaintext: str) -> str:
        return self._do(plaintext, self.encrypt_key)

    def decrypt(self, ciphertext: str) -> str:
        return self._do(ciphertext, self.decrypt_key)

    def _do(self, String: str, key) -> str:
        """矩阵乘法"""
        res = []
        for i in range(0, len(String), self._n):
            vector = self._to_vector(String[i:i + self._n])
            temp = _mul(key, vector)
            s = self._from_vector(temp)
            res.append(s)
        return ''.join(res)

    @staticmethod
    def _to_vector(String: str):
        """字符串转矩阵"""
        return [[ord(item) - 97] for item in String.lower()]

    @staticmethod
    def _from_vector(vector):
        """矩阵转字符串"""
        return ''.join([chr(97 + item[0]) for item in vector])

3.4 测试样例和结果

根据密钥矩阵是左乘还是右乘，会产生不同的结果。此处使用的是左乘密钥矩阵

# 样例一
key = [[5, 8], 
       [17, 3]]
plaintext = "loveyourself"

ciphertext = "lvhfyicbsgru"

# 样例二
key = [[6, 24, 1], 
       [13, 16, 10], 
       [20, 17, 15]]
plaintext = "ysezymxvv"

ciphertext = "iqokxwnno"

更多样例可以自己去网上的在线加解密网站构造

参考资料：《密码学实验教程》

大佬总结

以上是大佬教程为你收集整理的Hill 密码全部内容，希望文章能够帮你解决Hill 密码所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。