2. 仿射密码的加密与解密

任务目标

实现仿射密码的加密与解密函数。密钥由整数对 (a, b) 构成，其中 a 与 26 互质（即 gcd(a, 26) = 1），b 为任意整数。输入为小写英文字母组成的明文字符串，输出为对应密文；解密函数需根据同一密钥恢复明文。

核心实现

def egcd(a, b):
    """扩展欧几里得算法，返回 (g, x, y) 使得 a*x + b*y = g = gcd(a, b)"""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def mod_inverse(a, m=26):
    """求 a 在模 m 下的乘法逆元，要求 gcd(a, m) = 1"""
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError(f"{a} 与 {m} 不互质，无法求逆元")
    return x % m

def is_valid_key(a, b):
    """检查密钥是否合法：a 与 26 互质"""
    from math import gcd
    return gcd(a, 26) == 1

def encrypt(plaintext, a, b):
    """仿射加密：E(x) = (a*x + b) mod 26，x 为字母序号 (a=0, b=1, ..., z=25)"""
    if not is_valid_key(a, b):
        raise ValueError(f"密钥 a={a} 与 26 不互质，加密失败")
    result = []
    for ch in plaintext:
        if 'a' <= ch <= 'z':
            x = ord(ch) - ord('a')
            result.append(chr((a * x + b) % 26 + ord('a')))
        else:
            result.append(ch)  # 非小写字母原样保留
    return ''.join(result)

def decrypt(ciphertext, a, b):
    """仿射解密：D(y) = a_inv * (y - b) mod 26，y 为密文字母序号"""
    if not is_valid_key(a, b):
        raise ValueError(f"密钥 a={a} 与 26 不互质，解密失败")
    a_inv = mod_inverse(a, 26)
    result = []
    for ch in ciphertext:
        if 'a' <= ch <= 'z':
            y = ord(ch) - ord('a')
            result.append(chr((a_inv * (y - b)) % 26 + ord('a')))
        else:
            result.append(ch)
    return ''.join(result)

# 最小调用示例
if __name__ == "__main__":
    a, b = 5, 8   # gcd(5,26)=1，合法密钥
    plain = "hello"
    cipher = encrypt(plain, a, b)
    decrypted = decrypt(cipher, a, b)
    print(f"明文: {plain}")
    print(f"密文: {cipher}")
    print(f"解密: {decrypted}")
    print(f"验证: {plain == decrypted}")

运行与验证

运行方式：将上述代码保存为 affine.py，在终端执行 python affine.py。

预期输出：（由代码逻辑直接推出）

明文: hello
密文: rcllo
解密: hello
验证: True

验证方法：

• 观察输出中“验证: True”，说明解密结果与原始明文一致，加解密闭环正确。
• 手动测试非法密钥：将 a 改为 4（gcd(4,26)=2），调用 encrypt("test", 4, 8)，应抛出 ValueError，提示不互质。
• 自行更换合法密钥（如 a=7, b=3）和不同明文，确认解密始终能还原明文。

关键说明

• 字母序号映射为 a=0, b=1, …, z=25，加密公式 E(x) = (a·x + b) mod 26，解密公式 D(y) = a⁻¹·(y − b) mod 26。
• mod_inverse 使用扩展欧几里得算法计算模逆元，是解密函数的必要依赖，已在代码中完整实现。
• 非小写字母（如空格、数字、大写字母）在加解密中原样保留，不参与变换，便于处理含标点的文本。