单表替换后接列置换的两步密码破解Python脚本优化求助

现有代码核心问题 #

当前实现的流程存在两个核心逻辑错误：

1. 解密顺序不匹配加密流程：加密顺序为「明文→替换加密→列置换加密→密文」，解密必须反过来先解列置换、再解替换，你当前代码中替换解密直接传入原始密文计算频率，完全无法得到有效结果
2. 适配度指标太弱：替换解密用单字母频率差作为判断标准，抗干扰性极差，很容易陷入局部最优

可行优化方案 #

• 首先修正解密流程链路：所有替换解密操作的输入，必须是当前候选置换密钥解密后的文本，不能直接用原始密文
• 预筛选置换密钥长度：不用暴力遍历所有可能的长度，先通过重合指数（IC）筛选候选长度。正确密钥长度下，按密钥长度拆分的每一列的IC值接近自然英文的0.0667，错误长度下IC会落在0.038左右，可快速筛掉90%以上无效长度
• 升级适配度函数：把单字母频率差替换为4元组（quadgram）对数概率得分，基于标准英文语料的n元组统计结果计算，判断准确率会提升数倍
• 优化爬山迭代逻辑：不要割裂置换和替换的优化流程，改为联合迭代：
  1. 用当前候选置换密钥解密密文，得到置换后文本
  2. 对置换后文本跑替换爬山算法，得到当前最高适配度
  3. 微调置换密钥（交换任意两列的顺序），重新执行前两步，只要适配度上升就保留新的置换密钥
  4. 重复迭代直到适配度不再上升
• 加入模拟退火逻辑：常规爬山算法容易卡在局部最大值，模拟退火允许迭代初期接受小幅得分下降的修改，随着迭代次数增加逐步降低接受坏修改的概率，可大幅提升找到全局最优解的概率
• 修复多n元组混跑问题：你当前代码中同时用2/3/4元组跑置换优化，不同n元组的得分数值范围差异很大，不能共用同一个阈值和密钥变量，固定用4元组作为统一适配度指标即可

参考修正代码片段 #

import math
import random

besttext = text
# 先通过IC预筛选最可能的3种密钥长度
candidate_keylens = filter_keylen_by_ic(text, top_k=3)

# 仅遍历候选密钥长度
for keylength in candidate_keylens:
    print("当前测试密钥长度", keylength)
    highest_fit = -9999
    # 多轮随机重启避免局部最优
    for restart in range(15):
        transpositionkey = list(range(keylength))
        random.shuffle(transpositionkey)
        # 模拟退火参数
        temperature = 20
        while temperature > 0.1:
            # 生成微调后的置换密钥
            new_transkey = transpositionkey.copy()
            a, b = random.sample(range(keylength), 2)
            new_transkey[a], new_transkey[b] = new_transkey[b], new_transkey[a]
            # 先解置换
            transposed_text = decrypt_transposition(text, new_transkey)
            # 再解替换，用4元组算得分
            sub_result = HillClimbingSubstitution(transposed_text)
            current_fit = sub_result[2]
            # 退火判断逻辑
            if current_fit > highest_fit or random.random() < math.exp((current_fit - highest_fit)/temperature):
                highest_fit = current_fit
                transpositionkey = new_transkey
                besttext = sub_result[0]
                best_subkey = sub_result[1]
            temperature *= 0.995
    print("当前长度最优得分", highest_fit)
    print("当前最优明文片段", besttext[:100])

return(besttext, best_subkey, transpositionkey, highest_fit)

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