2. 古典密码算法：原理、实现与攻击

古典密码是密码学的基石，虽然其安全性在现代计算能力面前已不堪一击，但其中蕴含的替换与换位思想至今仍被广泛借鉴。本章将深入剖析凯撒密码、维吉尼亚密码的原理与Python实现，并演示如何通过频率分析攻破它们。

2.1 凯撒密码：最简单的替换密码

凯撒密码（Caesar Cipher）是一种单表替换密码，通过将字母表中的每个字母按固定位数进行移位来实现加密。例如，移位量为3时，A→D，B→E，……，Z→C。

2.1.1 加密与解密公式

2.1.2 Python实现

def caesar_encrypt(plaintext: str, shift: int) -> str:
    """凯撒加密"""
    result = []
    for char in plaintext.upper():
        if char.isalpha():
            shifted = (ord(char) - ord('A') + shift) % 26
            result.append(chr(shifted + ord('A')))
        else:
            result.append(char)
    return ''.join(result)

def caesar_decrypt(ciphertext: str, shift: int) -> str:
    """凯撒解密"""
    return caesar_encrypt(ciphertext, -shift)

# 示例
plain = "HELLO WORLD"
shift = 3
cipher = caesar_encrypt(plain, shift)
print(f"密文: {cipher}")          # KHOOR ZRUOG
print(f"解密: {caesar_decrypt(cipher, shift)}")  # HELLO WORLD

2.2 维吉尼亚密码：多表替换的里程碑

维吉尼亚密码（Vigenère Cipher）使用一个关键词作为密钥，每个明文字母根据关键词对应位置的字母决定移位量，从而实现了多表替换，有效抵抗了简单的频率分析。

2.2.1 加密流程

1. 密钥扩展：将关键词重复至与明文等长。
2. 逐位加密：对每个位置i，密文字母 = (明文字母索引 + 密钥字母索引) mod 26。
3. 输出密文：将转换后的字母拼接。

2.2.2 Python实现

def vigenere_encrypt(plaintext: str, key: str) -> str:
    """维吉尼亚加密"""
    plaintext = plaintext.upper()
    key = key.upper()
    result = []
    key_index = 0
    for char in plaintext:
        if char.isalpha():
            shift = ord(key[key_index % len(key)]) - ord('A')
            shifted = (ord(char) - ord('A') + shift) % 26
            result.append(chr(shifted + ord('A')))
            key_index += 1
        else:
            result.append(char)
    return ''.join(result)

def vigenere_decrypt(ciphertext: str, key: str) -> str:
    """维吉尼亚解密"""
    ciphertext = ciphertext.upper()
    key = key.upper()
    result = []
    key_index = 0
    for char in ciphertext:
        if char.isalpha():
            shift = ord(key[key_index % len(key)]) - ord('A')
            shifted = (ord(char) - ord('A') - shift) % 26
            result.append(chr(shifted + ord('A')))
            key_index += 1
        else:
            result.append(char)
    return ''.join(result)

# 示例
plain = "ATTACKATDAWN"
key = "LEMON"
cipher = vigenere_encrypt(plain, key)
print(f"密文: {cipher}")          # LXFOPVEFRNHR
print(f"解密: {vigenere_decrypt(cipher, key)}")  # ATTACKATDAWN

2.2.3 凯撒 vs 维吉尼亚：核心差异

2.3 频率分析攻击方法

频率分析（Frequency Analysis）利用自然语言中字母出现频率的不均匀性来破解替换密码。英语中，字母E、T、A、O、I、N、S、H、R的出现频率远高于其他字母。

2.3.1 攻击凯撒密码：暴力枚举

由于密钥空间极小，直接尝试所有25种移位量，通过词频评分或人工识别即可快速找到正确结果。

def caesar_brute_force(ciphertext: str):
    """暴力破解凯撒密码"""
    for shift in range(26):
        decrypted = caesar_decrypt(ciphertext, shift)
        print(f"Shift {shift:2d}: {decrypted[:50]}...")  # 只显示前50字符

# 示例
cipher = "KHOOR ZRUOG"
caesar_brute_force(cipher)
# 输出中 Shift 3 对应 "HELLO WORLD" 即为正确结果

2.3.2 攻击维吉尼亚密码：两步走

1. 确定密钥长度：使用卡西斯基测试（Kasiski Examination）或重合指数（Index of Coincidence）。卡西斯基测试寻找密文中重复出现的片段，其间距的最大公约数很可能就是密钥长度。
2. 逐组频率分析：将密文按密钥长度分组，每组对应一个凯撒密码，分别进行频率分析即可恢复每个密钥字母。

2.4 古典密码安全启示

通过本章学习，我们应深刻理解以下安全原则：

• 密钥空间必须足够大：凯撒密码的25种可能在现代计算机面前形同虚设。
• 算法公开不降低安全性：Kerckhoffs原则指出，密码系统的安全性应仅依赖于密钥的保密性，而非算法的隐秘。
• 统计特征不可忽视：任何保留原始语言统计模式的加密方案都易受频率分析攻击。