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

任务目标

实现仿射密码的加密与解密函数。仿射密码将明文中的每个字母 \( x \)（0~25）映射为密文 \( y = (a \cdot x + b) \bmod 26 \)，解密为 \( x = a^{-1} \cdot (y - b) \bmod 26 \)。要求密钥 \( (a, b) \) 满足 \( \gcd(a, 26) = 1 \)，否则抛出异常。输入仅处理大写字母 A-Z，其他字符原样保留。

核心实现

def egcd(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):
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError(f"密钥 a={a} 与 26 不互质，无法解密")
    return x % m

def encrypt(plaintext, a, b):
    if gcd(a, 26) != 1:
        raise ValueError(f"密钥 a={a} 与 26 不互质，非法密钥")
    result = []
    for ch in plaintext:
        if 'A' <= ch <= 'Z':
            x = ord(ch) - ord('A')
            y = (a * x + b) % 26
            result.append(chr(y + ord('A')))
        else:
            result.append(ch)
    return ''.join(result)

def decrypt(ciphertext, a, b):
    if gcd(a, 26) != 1:
        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')
            x = (a_inv * (y - b)) % 26
            result.append(chr(x + ord('A')))
        else:
            result.append(ch)
    return ''.join(result)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

运行与验证

# 测试用例
plain = "HELLO WORLD"
a, b = 5, 8   # gcd(5,26)=1，合法密钥

cipher = encrypt(plain, a, b)
print("密文:", cipher)          # 预期输出: RCLLA OAPLX
print("解密:", decrypt(cipher, a, b))  # 预期输出: HELLO WORLD

# 非法密钥测试
try:
    encrypt("HELLO", 4, 8)  # gcd(4,26)=2，非法
except ValueError as e:
    print("异常捕获:", e)

运行后观察：合法密钥下解密结果与明文完全一致；非法密钥 \( a=4 \) 时抛出 ValueError。满足以上两点即验证通过。

关键说明

• 加密与解密前均检查 \( \gcd(a,26)=1 \)，不满足直接抛异常，避免产生不可逆密文。
• 解密依赖 \( a \) 在模 26 下的乘法逆元，由扩展欧几里得算法计算。
• 非字母字符（如空格）在加解密中原样保留，不参与变换。