如何修改Vigenere密码破解Python代码以正确获取明文与密钥？

原代码存在的核心问题 #

• Kasiski检验未过滤非字母字符，导致重复序列包含空格、数字等无效字符，计算的距离无法正确反映密钥长度
• 密钥长度猜测逻辑错误：直接将出现次数最多的距离作为密钥长度，正确做法是计算所有距离的公约数，取最可能的公约数作为密钥长度候选
• 频率分析未过滤非字母字符，统计了空格等无效字符，导致最常见字母判断错误
• 解密函数将所有字母转为大写，未保留原密文的大小写格式

修改后的完整代码 #

import re
import collections
from math import gcd
from functools import reduce

def vigenere_decrypt(ciphertext, key):
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    plaintext = ''
    key_index = 0
    for char in ciphertext:
        if char.isalpha():
            # 循环使用密钥字符
            key_char = key[key_index % len(key)].upper()
            key_idx = alphabet.index(key_char)
            char_upper = char.upper()
            char_idx = alphabet.index(char_upper)
            decrypted_idx = (char_idx - key_idx) % 26
            # 保留原字符大小写
            plaintext += alphabet[decrypted_idx].lower() if char.islower() else alphabet[decrypted_idx]
            key_index += 1
        else:
            plaintext += char
    return plaintext

def kasiski_examination(ciphertext):
    # 过滤非字母字符，仅处理纯字母序列
    cleaned_cipher = re.sub(r'[^a-zA-Z]', '', ciphertext)
    repeating_sequences = {}
    # 查找3-5长度的重复字母序列
    for length in range(3, 6):
        for i in range(len(cleaned_cipher) - length + 1):
            sequence = cleaned_cipher[i:i+length]
            if sequence in repeating_sequences:
                repeating_sequences[sequence].append(i)
            else:
                repeating_sequences[sequence] = [i]

    distances = []
    for sequence, indices in repeating_sequences.items():
        if len(indices) > 1:
            for i in range(len(indices) - 1):
                distance = indices[i + 1] - indices[i]
                if distance > 0:
                    distances.append(distance)
    return distances

def guess_key_length(distances):
    if not distances:
        return 3  # 默认候选长度
    
    # 计算所有距离对的公约数，统计最常见的公约数
    gcd_counts = collections.Counter()
    for i in range(len(distances)):
        for j in range(i+1, len(distances)):
            current_gcd = gcd(distances[i], distances[j])
            if current_gcd > 1:
                gcd_counts[current_gcd] += 1
    
    if gcd_counts:
        key_length_guess = gcd_counts.most_common(1)[0][0]
    else:
        # 所有距离的最大公约数
        key_length_guess = reduce(lambda x, y: gcd(x, y), distances)
    
    return max(key_length_guess, 2)  # 确保密钥长度至少为2

def frequency_analysis(grouped_text):
    # 过滤非字母字符，仅统计字母频率
    cleaned_group = [c.upper() for c in grouped_text if c.isalpha()]
    if not cleaned_group:
        return 'A'
    
    most_common_letter = collections.Counter(cleaned_group).most_common(1)[0][0]
    # 基于英文最常见字母E计算密钥字符
    key_offset = (ord(most_common_letter) - ord('E')) % 26
    key_char = chr(key_offset + ord('A'))
    return key_char

def vigenere_break(ciphertext):
    distances = kasiski_examination(ciphertext)
    key_length = guess_key_length(distances)

    key = ''
    # 提取纯字母序列用于分组
    cleaned_cipher = [c for c in ciphertext if c.isalpha()]
    for i in range(key_length):
        group = cleaned_cipher[i::key_length]
        key_char = frequency_analysis(group)
        key += key_char

    plaintext = vigenere_decrypt(ciphertext, key)
    return key, plaintext

# 测试示例
ciphertext = "Vyc fnqkm spdpv nqo hjfxa qmcg 13 eiha umvl."
key, plaintext = vigenere_break(ciphertext)
print("Ciphertext:", ciphertext)
print("Decrypted Plaintext:", plaintext)
print("Key:", key)

关键修改说明 #

1. Kasiski检验优化：先过滤密文中的非字母字符，仅处理纯字母序列，避免无效重复序列干扰，同时统一收集所有有效距离。
2. 密钥长度猜测修正：计算所有距离对的公约数，统计出现次数最多的公约数作为密钥长度，符合Kasiski检验的核心逻辑，同时增加边界判断避免无效长度。
3. 频率分析优化：过滤分组中的非字母字符，仅统计字母频率，确保最常见字母的判断准确。
4. 解密函数优化：保留原密文的大小写格式，仅在处理字母字符时递增密钥索引，避免非字母字符占用密钥位置。

内容的提问来源于stack exchange，提问作者megan