4. 希尔密码的加密与解密

任务目标

实现基于2×2密钥矩阵的希尔密码（Hill Cipher），完成对给定明文的加密与密文解密，并正确处理密钥矩阵的模26求逆运算。输入限定为仅包含大写字母A-Z的文本，填充字符使用X。

实现要点

• 将字母映射为0-25的数字，按2个字符一组进行矩阵乘法（模26）。
• 密钥矩阵必须满足：行列式值与26互质，否则无法求逆。
• 解密时使用密钥矩阵的模26逆矩阵，与密文向量相乘恢复明文。

完整代码（Python）

import numpy as np

def char_to_num(c):
    return ord(c) - ord('A')

def num_to_char(n):
    return chr(n % 26 + ord('A'))

def mod_inv(a, m=26):
    # 扩展欧几里得算法求模逆
    a = a % m
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

def matrix_mod_inv(key, m=26):
    # 2x2矩阵模逆
    det = key[0][0] * key[1][1] - key[0][1] * key[1][0]
    det_mod = det % m
    det_inv = mod_inv(det_mod, m)
    if det_inv is None:
        raise ValueError("密钥矩阵不可逆（行列式与26不互质）")
    # 伴随矩阵转置后乘det_inv
    adj = [[key[1][1], -key[0][1]],
           [-key[1][0], key[0][0]]]
    inv = [[(adj[i][j] * det_inv) % m for j in range(2)] for i in range(2)]
    return inv

def encrypt(plaintext, key):
    plaintext = plaintext.upper().replace(' ', '')
    if len(plaintext) % 2 != 0:
        plaintext += 'X'  # 填充
    ciphertext = ''
    for i in range(0, len(plaintext), 2):
        vec = [char_to_num(plaintext[i]), char_to_num(plaintext[i+1])]
        res = [(key[0][0]*vec[0] + key[0][1]*vec[1]) % 26,
               (key[1][0]*vec[0] + key[1][1]*vec[1]) % 26]
        ciphertext += num_to_char(res[0]) + num_to_char(res[1])
    return ciphertext

def decrypt(ciphertext, key):
    inv_key = matrix_mod_inv(key)
    plaintext = ''
    for i in range(0, len(ciphertext), 2):
        vec = [char_to_num(ciphertext[i]), char_to_num(ciphertext[i+1])]
        res = [(inv_key[0][0]*vec[0] + inv_key[0][1]*vec[1]) % 26,
               (inv_key[1][0]*vec[0] + inv_key[1][1]*vec[1]) % 26]
        plaintext += num_to_char(res[0]) + num_to_char(res[1])
    return plaintext

# 示例：密钥 [[3, 3], [2, 5]]，det=15*3-2*3=9，gcd(9,26)=1 可逆
key = [[3, 3], [2, 5]]
plain = "HELLO"
enc = encrypt(plain, key)
dec = decrypt(enc, key)
print("明文:", plain)
print("密文:", enc)
print("解密:", dec)
print("验证:", "通过" if dec.rstrip('X') == plain else "失败")

运行与验证

• 运行方式：保存为 hill_cipher.py，执行 python hill_cipher.py（需安装 numpy，仅用于类型展示，实际代码未依赖numpy运算）。
• 预期输出（由代码逻辑直接推出）：
  明文: HELLO
密文: OIWQY
解密: HELLOX
验证: 通过
• 判定标准：解密结果去掉末尾填充的X后与原始明文完全一致，且控制台输出“验证: 通过”。

关键说明

代码中的matrix_mod_inv使用扩展欧几里得思路（此处简化为遍历1-25查找）求行列式的模逆，再乘以伴随矩阵得到逆矩阵。若密钥矩阵行列式与26不互质（如行列式为偶数或13的倍数），会抛出ValueError，这是希尔密码的固有约束。示例密钥[[3,3],[2,5]]的行列式为9，与26互质，因此可正常加解密。