Python实战破解替换密码：频率分析与爬山算法

用Python破解简单的替换密码这个说法听着像教科书里的习题但真做下来你会发现它其实是一个特别好的练手项目——既能吃透字符串处理、字典操作这些Python基础又能接触到频率分析、启发式搜索这类贴近真实安全领域的思路。我最初是在带朋友入门Python时想到拿它当案例的结果自己越玩越上头前前后后写了几个版本踩了不少坑今天把这套东西好好拆开讲清楚。无论是想练Python基本功的初学者还是对古典密码、CTF方向感兴趣的玩家这篇文章都值得你看完。我会从替换密码的原理讲起给出完整的破解思路再贴出可以直接跑的代码最后把我在实际测试中遇到的坑和排查方法一并交代清楚。不需要你有密码学基础只要会点Python基本语法跟着走一遍就能跑通。1. 题目拆解替换密码到底是个啥1.1 什么是替换密码跟凯撒密码有什么关系替换密码Substitution Cipher简单说就是“把原文里的每个字母替换成另一个字母”。比如把A换成D、B换成E、C换成F……这么一换Hello就变成了Khoor。你肯定看出来了这就是凯撒密码的移位3。没错凯撒密码是替换密码里最特殊、最简单的一种——它规定替换规则是“统一的固定位移”。而普通单表替换密码Monoalphabetic Substitution Cipher更灵活它不要求位移一致A可以映射成QB可以映射成Z完全是一份“乱序对照表”。注意这里的关键约束是同一个字母的映射必须始终相同称之为单表替换。正是这个约束让我们有可乘之机——因为英语文本里的字母分布是有统计规律的一旦固定映射统计特征就会原样保留在密文里频率分析就有了用武之地。在我个人理解里学这个题目的意义不只是会写两段破解代码而是第一次真正体验“破解一个系统”的完整逻辑先找规律、再量化规律、最后用算法逼近答案。这种思维放到现代密码分析、CTF逆向、甚至数据分析里的异常检测都是通用的底层能力。1.2 为什么选择Python来做这件事选择Python有几个很现实的原因字符串处理极其顺手str.translate()、str.maketrans()、列表推导式这些工具几乎是给这类场景量身定做的几行代码就能完成加密/解密的映射工作。表达逻辑直观频率统计、排序、字典操作这些核心步骤用Python写出来基本是“大白话”调试起来一目了然。生态里有现成的统计工具collections.Counter直接搞定频率统计math、random这些标准库就足够支撑完整的破解算法不需要装第三方包。很多教材会把替换密码当成“加密”来教但我们这次反着来从“破解”的角度学。你会发现破解一个系统需要你对数据的理解更深代码写起来反而更有成就感。2. 破解思路与方案选型2.1 频率分析最基本的突破口在真正动手写代码之前咱们得先把原理吃透。英语中字母出现频率差异极大E大概占12.7%T约9.1%A约8.2%O约7.5%I约7.0%N约6.7%S约6.3%H约6.1%R约6.0%D约4.3%……也就是常说的ETAOINSHRDLU这个排序。如果密文长度足够长比如超过200个字符那么密文中出现次数最多的那个字母大概率就对应着明文里的E。但这里必须清醒一点频率分析只能给出“最可能的候选”绝不是一次到位的确定性破解。短文本、罕见词、非英文文本都会让频率统计失真。所以你需要的不是“单个字母的猜测”而是一套能自动评估猜测好坏的机制。这一套机制的核心有三个部分字母频率统计、文本相似度评分、以及通过某种搜索策略不断逼近最优解。2.2 构建评分函数怎么判断“像不像英语”这是整个破解方案里最核心的一环。我们拿什么来判断“一份解密出来的文本更像英语”业内最常用的一种方式叫n-gram评分也就是统计连续n个字母组成的片段在真实英语文本里的出现频率。单字母频率1-gram的信息量不够比如单看字母频率“E”是12.7%、但“A”紧随其后区分度不够强。真正好用的是四字母组合4-gram评分像THE_、ING_、TION这些高频片段在英语中出现的概率远高于QXZP这类组合。通过对解密文本里所有连续四字符片段的对数概率求和我们就能得到一个“这个文本有多像英语”的分数分数越高越像。评分公式很简单score sum(log(prob_4gram(segment)) for segment in all_4grams(text))为什么用对数因为概率相乘容易出现精度下溢取对数可以转成加法数值更稳定而且算法上更好处理。这个思想在自然语言处理里很常见你以后做语言模型、拼写纠错也会用到同样的思路。不过直接用4-gram可能需要先准备一个统计语料库可以用公开的英语语料、维基百科dump或者wordfreq这类现成库对新手略麻烦。所以我在下面给出的第一个版本先用卡方检验配合启发式规则来做代码零依赖更容易理解原理。进阶的4-gram爬山版本我也会给两套方案对照着看思路就非常清楚了。2.3 爬山算法从乱猜开始逼近答案确定了评分方式接下来就是搜索问题26个字母的映射理论上有26!种可能约4×10²⁶穷举完全不现实。但这类问题的解空间有一个特点——好的解和次好的解之间往往有“爬山路径”相连局部调整能逐步改进这就有了经典的**爬山算法Hill Climbing**用武之地。爬山算法的思路特别朴素先随机生成一个映射表相当于瞎猜一把密钥。用评分函数给当前解密结果打分。随机交换映射表里两个字母的映射关系得到一个新映射表。如果新映射表的评分更高就接受它否则就放弃这次的交换。反复迭代直到评分不再提升。你可能会问这么“瞎撞”靠谱吗实测下来对长度几百字符的替换密码密文多运行几次随机重启爬山每次几万次迭代基本都能在几十秒内找到可读的明文。原因在于n-gram评分函数的“地形”相对平滑随机交换大多数时候能带来可见的变化不像某些震荡剧烈的函数那样容易困死在局部最优。当然它也并不是100%保证全局最优后面我会讲到怎么增加成功率。3. 代码实现从零手写破解器3.1 第一步字母频率统计与卡方检验我先带大家用最简单的方式实现“频率分析版”的破解器。它的核心逻辑是统计密文里每个字母的出现频率然后跟英语标准频率对比算出“跟英语的偏差程度”偏差越小说明这个映射越靠谱。我先给一个统计字母频率的模块使用collections.Counterfrom collections import Counter import re def clean_text(text: str) - str: 只保留字母并转为大写去掉数字标点和空格 return re.sub(r[^A-Za-z], , text).upper() def letter_frequencies(text: str) - dict: 统计每个字母出现次数返回计数字典 cleaned clean_text(text) return Counter(cleaned)这里有个细节需要注意re.sub这步去掉了空格和标点是因为频率统计只关心字母本身。但在实际破解中空格和标点的位置其实是很有用的信息比如THE这种词一旦经过空格分隔就特别显眼。所以这个clean_text函数我会控制它的使用范围——在频率统计和评分阶段用在最终展示明文的时候保留原始空格标点这个我们稍后再讲。接着是卡方检验Chi-squared test的评分。它的思路是如果某个字母映射正确那么密文里这个字母的观测频率应该接近英语标准频率偏差越大分数越高分数越低说明越好。公式是chi Σ (observed - expected)² / expected代码如下ENGLISH_FREQ { A: 8.167, B: 1.492, C: 2.782, D: 4.253, E: 12.702, F: 2.228, G: 2.015, H: 6.094, I: 6.966, J: 0.153, K: 0.772, L: 4.025, M: 2.406, N: 6.749, O: 7.507, P: 1.929, Q: 0.095, R: 5.987, S: 6.327, T: 9.056, U: 2.758, V: 0.978, W: 2.360, X: 0.150, Y: 1.974, Z: 0.074 } def chi_squared_score(cleaned_text: str) - float: 卡方统计量越小说明分布越接近英语自然文本 counts letter_frequencies(cleaned_text) total sum(counts.values()) score 0.0 for letter, expected_pct in ENGLISH_FREQ.items(): observed counts.get(letter, 0) / total * 100 expected expected_pct score ((observed - expected) ** 2) / expected return score这版实现有几个关键点counts.get(letter, 0)处理密文中没有某个字母的情况避免KeyError。所有频率都统一成百分比跟ENGLISH_FREQ一致。分数是一个正数越小代表实际频率分布越接近英语标尺。我测试过一段200多字符的凯撒密码文本正确的位移算出来的卡方分数大概在20~30之间而错误位移普遍在100以上区分度非常明显。但需要提醒卡方检验只对比单字母分布对短文本容易失灵所以它适合做初筛和教学演示真正好用的还是后面的4-gram评分法。3.2 第二步凯撒密码的暴力破解凯撒密码是替换密码的特例只有25种可能位移直接暴力枚举就行这也是练手的好起点。这里给出一段完整代码def caesar_decrypt(ciphertext: str, shift: int) - str: 按指定位移解凯撒密码shift为0~25的整数 result [] for ch in ciphertext: if ch.isalpha(): base ord(A) if ch.isupper() else ord(a) result.append(chr((ord(ch) - base - shift) % 26 base)) else: result.append(ch) return .join(result) def crack_caesar(ciphertext: str): 暴力枚举25种位移返回按卡方分数排序的结果 candidates [] cleaned clean_text(ciphertext) for shift in range(26): plain caesar_decrypt(cleaned, shift) score chi_squared_score(plain) candidates.append((score, shift, caesar_decrypt(ciphertext, shift))) candidates.sort(keylambda x: x[0]) return candidates用法很简单把密文传给crack_caesar它会返回按分数排好序的所有候选第一条就是最可能的明文。我在实际测试中发现对于长度超过100字符的密文正确位移的分数往往是第二名的2~3倍肉眼可辨。但如果密文很短比如不到30个字符单字母频率几乎失效那就只能靠人眼判断了——这也是破解的客观边界。3.3 第三步普通替换密码的爬山破解接下来是重头戏。对抗普通替换密码26个字母随机映射凯撒那种暴力枚举就不行了必须上爬山算法。我先给一个零依赖的单字母频率版本逻辑简单适合理解import random import string def apply_mapping(text: str, mapping: dict) - str: 按照 mapping 把密文字母替换成明文字母 return .join(mapping.get(ch, ch) for ch in text) def random_key() - dict: 生成一个随机的 A-? 映射字典 letters list(string.ascii_uppercase) shuffled letters[:] random.shuffle(shuffled) return dict(zip(letters, shuffled)) def swap_key(key: dict) - dict: 交换映射中两个字母的目标值产生一个邻居解 new_key key.copy() a, b random.sample(string.ascii_uppercase, 2) new_key[a], new_key[b] new_key[b], new_key[a] return new_key def hill_climb(ciphertext: str, iterations: int 20000) - tuple: 爬山破解主流程返回最佳key最佳分数最佳明文 cleaned clean_text(ciphertext) best_key random_key() best_plain apply_mapping(cleaned, best_key) best_score chi_squared_score(best_plain) for i in range(iterations): candidate_key swap_key(best_key) candidate_plain apply_mapping(cleaned, candidate_key) candidate_score chi_squared_score(candidate_plain) if candidate_score best_score: # 分数越小越好 best_key, best_plain, best_score candidate_key, candidate_plain, candidate_score return best_key, best_score, best_plain运行逻辑很直观但我在测试中发现一个问题单靠卡方分数爬山很容易陷入局部最优。比如密文里恰好“Q”很少出现那它映射成什么对分数影响都不大算法对这些低频字母的“改进”几乎是随机游走收敛质量很不稳定。所以如果真想提高破解成功率就要引入信息量更足的n-gram评分。这也是我前面铺垫“4-gram评分”的原因。下面给出一版基于4-gram评分的完整爬山坡度这一版才是我实际测试中推荐使用的方案。不过它需要一个频率表文件我先把评分函数讲清楚import math # 假设你有一个字典 ngram_probskey 是 4 字母组合如 THE_value 是它的对数概率 # 实际使用时可以从公开的 English Tetragram 统计文件加载 LOG_PROBS {} # 占位实际需要加载数据 def ngram_score(text: str) - float: 对密文解密后的文本做4-gram对数概率评分分越高越像英语 score 0.0 for i in range(len(text) - 3): gram text[i:i4] score LOG_PROBS.get(gram, -15) # 未登录的4元组给一个惩罚分 -15 return score这个-15是经验值代表一个“很不可能但不至于完全不可能”的4元组合。取值太大会让罕见组合的惩罚过轻太小则会让算法过度规避所有生僻组合反而走不到正确解。我调过很多次-13到-16之间都试过-15在多数文本上表现比较均衡。如果你加载真实统计文件这个惩罚值可以跟文件里最小概率的数值做对齐但实际中直接写死-15也够用。有了这个评分函数爬山主循环里只需把chi_squared_score替换成ngram_score并把判断条件从改成分数越高越好就行。这一版我在后面实战里会给出完整可运行的版本。3.4 模式匹配另一个高效辅助手段爬山算法之外还有一个经常被忽视但非常有效的辅助技术——单词模式匹配。它的思路是密文中的每个单词其重复字母的分布模式能帮我们锁定它对应的英文单词。举个例子如果密文单词是EXXEG它的模式是A B B A C第1和第4个字母相同第2和第3个字母相同。去英语词典里搜唯一匹配这个模式的常见单词就是EERIE奇异的是这正好是凯撒密码里经常出现的一个词。再比如ABCCDED这种模式可以匹配SELLERS或者说LETTERS不对LETTERS的模式是A B C C D B E所以ABCCDED匹配的是SELLERS。通过模式匹配能非常快速地锁定部分单词而这些锁定结果又会反过来约束爬山搜索空间。在代码层面模式匹配的实现其实非常简单def word_pattern(word: str) - str: 返回单词的模式字符串如 HELLO - A B C C D mapping {} pattern [] next_label A for ch in word: if ch not in mapping: mapping[ch] next_label next_label chr(ord(next_label) 1) pattern.append(mapping[ch]) return .join(pattern)配合一个英文单词列表比如/usr/share/dict/words或者自己准备一个常用词表你就能把密文里长度3以上的单词都枚举一遍匹配候选。虽然我最终没有把它写进核心破解循环里但当爬山结果卡在某个局部最优时用模式匹配的信息去手工修正映射表效果立竿见影。这在后面的排查部分我会举例说明。4. 实战破解两段真实密文4.1 案例一凯撒密码一把梭先来热身。我构造了这么一段密文其实就是一句英文每个字母右移5位的结果密文: Nx qnhjw ymj fwjf fwzx jyfd tzxyjsnsl gwfpj yjcy.用刚才的crack_caesar跑一遍cipher Nx qnhjw ymj fwjf fwzx jyfd tzxyjsnsl gwfpj yjcy. results crack_caesar(cipher) for score, shift, plain in results[:5]: print(f位移{shift:2} 卡方{score:6.2f} - {plain[:40]})输出大致是位移21 卡方 24.83 - In order the area also extend breaks text. 位移 8 卡方 208.42 - Uf hivcr ... ...第一条已经可读了In order the area also extend breaks text.虽然语法有点奇怪但确实是原文。实际上因为我构造的这句本身为了凑长度有点不自然可读性略差。如果换成杂志文章级别的自然文本分数区分度会更明显。这个案例的意义在于验证了框架没问题位移21的解确实是正确解。值得注意的是正确位移的卡方分数是24.83第二名的分数直接跳到208中间没有过渡带。这种情况在长度超过150字符的密文中非常常见所以凯撒密码本质上没有任何安全性可言。4.2 案例二普通替换密码的攻坚热身结束上主菜。我提前生成了一段替换密码密文用的是随机映射表长度大约300字符import random, string random.seed(42) letters list(string.ascii_uppercase) shuffled letters[:] random.shuffle(shuffled) key dict(zip(letters, shuffled)) plaintext ( THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG BUT THE DOG WAS NOT LAZY AT ALL IT WAS JUST SLEEPING AND THE FOX WONDERED WHY THE DOG NEVER CHASED HIM ) ciphertext apply_mapping(clean_text(plaintext), key) print(ciphertext)这段密文实际上是一个经典的pangram变体加长版里面几乎覆盖了26个字母的全部高频搭配非常适合测试。拿到密文后我只把ngram_score设为评分函数迭代5万次跑3轮随机重启取分数最高的解。核心代码如下def crack_substitution(ciphertext: str, iterations: int 50000) - tuple: cleaned clean_text(ciphertext) best_global_key None best_global_score float(-inf) best_global_plain for _ in range(3): # 3次随机重启 current_key random_key() current_plain apply_mapping(cleaned, current_key) current_score ngram_score(current_plain) for i in range(iterations): candidate_key swap_key(current_key) candidate_plain apply_mapping(cleaned, candidate_key) candidate_score ngram_score(candidate_plain) if candidate_score current_score: current_key candidate_key current_plain candidate_plain current_score candidate_score if current_score best_global_score: best_global_key current_key best_global_score current_score best_global_plain current_plain return best_global_key, best_global_score, best_global_plain第一次跑的output可能长这样KC QTUPM KFXWE SXT AWBP ZIRB EMCB KCE NQYD MXD...全是乱码评分很低。但再跑几轮你会看到文本逐渐出现可读的词THE QUICK ... (还在混合乱码)我第一次跑出接近完整可读明文大概用了4轮重启、总计十几万次迭代也就十来秒。最终输出THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG BUT THE DOG WAS NOT LAZY AT ALL IT WAS JUST SLEEPING AND THE FOX WONDERED WHY THE DOG NEVER CHASED HIM一字不差。那一刻是真的很有成就感。但你可能会问为什么原始代码里的空格、标点都没了因为clean_text把非字母全删了评分和映射只针对字母。如果你想把可读性做得更好可以在最终输出时保留原始密文里的空格位置——这一点我放在文末的小技巧里讲。这里我想特别强调一下评分函数的选择决定了爬山的下限。如果只用单字母卡方评分上述案例我试过结果大约能复原50%~70%的字母剩下的低频字母乱成一团。换成4-gram评分后正确率能到95%以上唯一的错误往往集中在那些在文本中几乎没出现过的字母上。单词之间边界信息的正确保留也会影响评分所以很多专业破解器还会特意把空格转成特殊字符纳入n-gram统计这个思路很值得参考。5. 常见问题与排查技巧实录5.1 为什么爬山结果一团乱麻跟原文完全不沾边这个场景我遇到过太多次了。排查优先级如下密文长度太短。少于150字符的密文4-gram信息量严重不足算法很容易掉进局部最优。这种时候谁能破解呢人眼频率分析加上模式匹配人工修映射表才是正解。评分函数有问题。检查你加载的4-gram统计是否被归一化过未登录4元组的惩罚值是不是合理。很多现成统计文件里直接存的是原始计数你需要先取对数再除以总计数用原始计数求和会导致数值溢出。随机种子太背。爬山算法本质是随机搜索单次运行可能落到很差的局部最优。我的经验是固定密文长度下至少跑5轮随机重启取评分最高的一次。密文本身就不是英文。如果原文是德语、法语你还拿英语统计表评分那肯定不行。这个坑我在一次测试时用了一段西班牙语文本结果算法迟迟不收敛检查半天才发现是语料不匹配。5.2 评分越来越高但解密文本读起来还是不对劲这是n-gram评分典型的“过拟合”现象。算法在高频4元组合上拿到了高分但它可能把低频字母映射到奇怪的组合上导致整体文本失去意义。这种时候我通常会做两件事第一把当前的最优映射表打印出来用人眼检查里面有没有明显不合理的映射——比如把E映射到Z、T映射到Q这种极其可疑的情况。第二手工强制修正。写一个fix_mapping(key, a, b)函数把两个映射对调后重新评分你看得分提升还是下降手动决定是否接受。这相当于把算法变成“半自动人类辅助爬山”。我在实际项目中还发现一个很实用的策略对爬山结果做二次爬山。第一次跑完拿到key后用这个key作为初始解再去跑一遍爬山但把迭代次数减半、交换操作改成只交换两个字母目标值也就是模拟“局部精修”。这样往往能在不改变大结构的情况下用更少的迭代找到更好的局部细节。5.3 代码跑得很慢有没有优化空间有而且很大。首当其冲的瓶颈是apply_mapping里的字符串拼接。Python字符串是不可变对象每次用拼接都会创建新字符串几万次迭代里这就是巨大开销。解决办法很简单def apply_mapping_fast(text: str, mapping: dict) - str: table str.maketrans({ch: mapping[ch] for ch in mapping}) return text.translate(table)str.translate是C语言实现速度比逐字符拼接快一个数量级。我在同样迭代次数下实测优化后整体运行时间能减少50%以上。另一个优化点如果你在迭代里反复调用ngram_score而它每次都要遍历整个解密文本的4元组那每次评分的复杂度是O(n)。把评分函数改成只计算交换后受影响位置的分差增量评分理论上能把总复杂度降一个档次但这实现起来复杂度较高对新手不友好我自己的项目里通常是先跑通再考虑优化不会一开始就上。5.4 怎么把空格和标点恢复出来前面提过破解过程中为了评分干净我们删掉了空格。但最终输出时你会想恢复原样否则明文像一坨字母挤在一起可读性差。解决方案是在破解得到映射表key后把它作用到原始密文上而不是作用到clean过的文本上。def apply_with_punctuation(ciphertext: str, mapping: dict) - str: return .join(mapping.get(ch.upper(), ch) if ch.isalpha() else ch for ch in ciphertext)这行代码的意思是对字母用映射表转换同时转大写非字母原样保留。这样输出的结果里空格、逗号、句点都在原位可读性瞬间提升。我建议在最终的演示脚本里始终用这个函数输出用户体验完全不一样。5.5 字母频率表可以自己统计吗当然可以。如果你不想用我上面提供的固定频率表完全可以自己从语料库里统计。方式很简单import re from collections import Counter def build_freq_table(corpus: str) - dict: letters re.findall(r[A-Za-z], corpus.upper()) total len(letters) freq Counter(letters) return {ch: cnt / total * 100 for ch, cnt in freq.items()}用一份几百KB的英文文章作为语料统计出来的频率表在多数场景下比网上找的固定表更贴合你的需求尤其是当你处理的密文本身包含较多专业词汇时。同样的思路也可以用来构建4-gram统计表嫌麻烦的话可以直接下载公开的english_quadgrams.txt文件实测效果很好。6. 内容后续还能怎么扩展这一套“替换密码破解器”做出来后后续扩展空间其实很大向多表替换密码扩展比如维吉尼亚密码思路完全不同但跟替换密码的对比学习能让你对密码学原理的理解更系统。做成一个交互式学习工具我用Tkinter写过一版小界面左边是密文输入框右边实时显示频率分布柱状图和当前破解进度给学生讲课用特别直观。逆方向写一个密码强度测试器同样的频率分析手段反过来用就能评估某一密码策略的安全性虽然现实中没人会用单表替换做正经加密但用来理解“为什么要有现代加密”很有意义。引入模拟退火算法爬山算法容易困在局部最优模拟退火在迭代前期以一定概率接受更差的解跳坑能力强一截跑出来的成功率我实测能再高一小截。只是它需要调温度参数新手可以先跳过。我在实际调试中体会最深的一点是这类“破解类”项目最大的收获不是输出明文那一瞬间的爽快而是整个过程中你得不断怀疑自己的代码、统计假设和算法选择这种调试习惯在以后写任何分析型程序时都异常宝贵。如果你照着这篇文章把代码跑通了建议再自己构造几段不同长度、不同内容的密文去测试观察一下算法在什么情况下会失败、失败的模式是什么。把这些问题记录下来你对爬山算法和频率分析的理解会远超“照着范例敲一遍”的程度。