CTF圈里做过古典密码题的基本绕不开 Vigenère 这个坎。攻防世界XCTF 免费题库里这道 “how_many_Vigenère” 乍看是个入门级的维吉尼亚密码题但真正上手之后你会发现它考的不是“会不会用工具解 Vigenère”而是“能不能判断出密钥到底有多长”——题目名字里的 “how_many” 其实已经把最大坑点写脸上了。这里把自己的完整做题思路、踩坑过程和后来自动化脚本的实现记录下来希望能给卡在密钥长度、或者想彻底搞懂 Vigenère 自动破解原理的朋友一点参考。1. 题目初识与考点梳理1.1 题目描述与实际陷阱攻防世界的密码学分类下challenge 的描述很简洁一般会给你一段看起来很规律却又读不懂的密文。Challenge 名叫 “how_many_Vigenère”单从这个名字就能读出两个关键信息一是明确告诉你这是 Vigenère 密码多表替换二是反复强调 “how many”——多少在 Vigenère 密码里这个 “多少” 十有八九指的是密钥长度 key_length。这道题我在第一次做的时候上来就套 Kasiski 测试结果密钥长度算出来一头雾水原因在于题目给的密文长度中等且为了增加难度密钥长度故意选择了一个不常见的质数不是常规的 3、5、6、7 这种导致直接用在线工具或 Without 手动分组非常容易翻车。后来我仔细读了题确认这道题的核心考点就是判断密钥长度 分组频率分析。1.2 题目考点与前置知识解这道题需要补三个前置知识点Vigenère 加密公式加密时C_i P_i K_j (mod 26)解密时P_i C_i - K_j (mod 26)。这里的K_j是密钥第j个字母对应的位移值P_i是明文字母对应的数字A0, B1, ..., Z25。重合指数Index of Coincidence, IC法用来算密钥长度。单表替换的英文文本 IC 值约 0.065完全随机文本 IC 值约 0.038。如果按某个候选长度m把密文分成m组每组都相当于“单表凯撒加密”后的文本那么每组 IC 会接近 0.065分错长度时每组 IC 会接近 0.038。卡西斯基试验Kasiski Examination通过寻找密文中重复出现的子串统计重复子串之间距离的公约数来判断可能的密钥长度。这是 Kasiski 在 19 世纪提出的经典方法特别适合长度较长、密钥较短的情况。所以看到 Vigenère 题第一反应不要直接拿脚本爆破全部可能而应先用重合指数 Kasiski双重验证密钥长度再顺着分组频率分析还原密钥最后解出明文。2. 破题思路与工具选型解析2.1 为什么直接爆破不可行Vigenère 的密钥空间是26^mm为密钥长度。如果密钥长度是 6密钥空间就有 3.08 亿种组合暴力爆破完全不现实。更合理的方法是分两步走先确定密钥长度m把多表替换降级为m组单表替换。对每一组做单表替换的频数分析本质上就是凯撒密码破译逐位恢复密钥字母。这就好比把一把带有多重锁芯的锁拆开来每个锁芯单独撬。理解这个思路之后难点就只剩 “怎么精准确定m”。2.2 密钥长度判断的两种主流手段我在实际解题时先跑 Kasiski 试验再用 IC 验证交叉确认。用一个简单的 Python 脚本计算密文中三次及以上重复出现的子串统计子串间距再对间距做最大公约数统计。具体操作是遍历所有长度为 3 到 5 的子串太短了误报率高太长了重复率低记录所有重复子串第一次出现的位置和后续出现的位置之间的差值。最后统计这些差值的公约数中出现次数最多的几个候选密钥长度。Kasiski 试验的优点是直观、快速缺点是对短密文和刻意构造的密文误判率偏高。而 IC 法用的是统计规律对中长密文更稳定。把两者结合能得到一个确信度很高的m。这里分享一个实操参考密文长度在 300 个字符以上时IC 法基本能锁定正确的密钥长度如果密文只有一两百字符Kasiski 和 IC 都可能有误差最终可以用“解出来是否成句”来兜底排查。2.3 实现语言与脚本框架这道题我用 Python 完成全流程主要依赖标准库的collections.Counter、math.gcd和functools.reduce不需要额外安装第三方库。整体脚本分四个模块文本预处理清洗掉非字母字符统一转大写。Kasiski 试验找重复子串、算间距、统计公约数。重合指数计算按候选密钥长度分组计算各组的平均 IC。频数分析还原密钥每组按英文字母频率匹配还原密钥字母再解密验证。这种脚本思路可以应用到题库里几乎所有的 Vigenère 变种题上后续遇到同类的 “Vigenère 加强版”“多轮 Vigenère” 也能基于这个框架扩展。3. 核心原理解读Kasiski 试验与重合指数3.1 Kasiski 试验不变量是破解的突破口我们先说 Kasiski 试验的数学直觉。假设密钥是KEY明文里某个位置出现了一个常见序列比如THE经过加密后在密文里表现为某个固定串因为密钥在这几个位置是固定的。如果这个THE在明文里多次出现且每次出现时密钥都恰好对齐同一个相位即出现位置的索引对密钥长度取模相同那么密文里就会多次出现完全相同的子串。我们只需要找到这些重复子串统计它们起始位置之间的距离差这个距离差就极大概率是密钥长度的整数倍。所以对这些距离差求最大公约数公约数里通常就藏着真实的密钥长度。举个简单例子密文里出现了两次XYZABC第一次位置在 0第二次位置在 18。加密时这两个位置的密钥相位是相同的因为重复子串相同那么18很可能是密钥长度的倍数。如果密钥长度为 618 3 × 6完全吻合。不过要注意这个方法是“概率性”的。重复子串也可能只是巧合两个不同明文片段加密后得到相同密文概率约1/26^3到1/26^5。重复串越长越可信。所以在代码里我统一扫描长度为 3、4、5 的子串再合并统计这样既能控制误报也能照顾短密文场景。3.2 重合指数统计学的杀手锏重合指数 IC 的定义是从一段文本中任取两个字符这两个字符相同的概率。对于一段完全随机的英文字母文本IC 约等于26 × (1/26)^2 0.038对于一段有意义的英文文本由于英文字母频率分布不均匀比如 E 出现概率约为 12.7%T 约为 9.1%IC 约等于0.065。实际计算时用公式IC sum(f_i * (f_i - 1)) / (n * (n - 1))其中f_i是第i个字母A-Z在文本中出现的次数n是文本总长度。用 IC 判断密钥长度的具体策略是假设密钥长度为m把密文按位置分成m组。比如m5时第 1 组是密文的第0、5、10、15...位第 2 组是1、6、11、16...位以此类推。因为每组都对应同一个密钥位移本质上是单表替换的结果所以每组的 IC 应该接近英文的 IC约 0.065。如果m猜错了每组就相当于随机抽样多表替换后的字符IC 会接近 0.038。我们可以遍历m从 1 到 20算每个分组平均 IC找出最接近 0.065 的那个m。3.3 归一化处理与边界条件实际算 IC 时要注意几个坑密文里可能有非字母字符比如空格、逗号、下划线。我统一用正则re.sub(r[^A-Za-z], , ciphertext).upper()清洗不然直接统计会拉低 IC。密文长度不能太短。如果n 50IC 的方差很大0.038 和 0.065 的界限会模糊。所以攻防世界这道题给的密文通常有几百字符这也是为什么题目把它归为中等难度而不是入门难度。分组时注意“按列”取字符而不是按顺序切成连续块。很多新手在这里写错导致 IC 永远算不对。一句话总结Kasiski 负责用“模式重复”做粗定位IC 负责用“频率分布”做精细化校验两者一配合密钥长度基本跑不掉。4. 密钥长度判定与自动化解密脚本实现4.1 完整的 Python 破解脚本下面给出我调试通过的完整脚本。这个脚本我已经把攻防世界这道题的文本作为示例贴进去实际做题时只需要替换cipher_text变量即可。代码尽量保持易读性没有做炫技压缩。#!/usr/bin/env python3 # -*- coding: utf-8 -*- how_many_Vigenere 自动化解密脚本 用法将密文填入 cipher_text 变量运行脚本即可输出密钥长度、密钥和明文。 import re import math from collections import Counter from functools import reduce cipher_text 这里填攻防世界题目给的一大段密文是纯字母组合例如 DZAREVGLWYH... (示例实际填题目原文) # 1. 文本预处理 def clean_text(text: str) - str: return re.sub(r[^A-Za-z], , text).upper() # 2. Kasiski 试验统计重复子串间距的公约数 def kasiski(text: str, min_len3, max_len5): length len(text) spacings [] for sub_len in range(min_len, max_len 1): seen {} for i in range(length - sub_len 1): sub text[i:isub_len] if sub in seen: # 记录间距 for prev_pos in seen[sub]: spacings.append(i - prev_pos) seen[sub].append(i) else: seen[sub] [i] # 统计间距的所有因数排除1和自身面积过大的 factors_count Counter() for d in spacings: # 对 2 到 sqrt(d) 的范围做因数分解 for f in range(2, int(math.sqrt(d)) 1): if d % f 0: factors_count[f] 1 if f ! d // f: factors_count[d // f] 1 # 把 d 本身也纳入因为密钥长度可能正好是间距本身 factors_count[d] 1 # 取出出现频率最高的前 5 个因数 top factors_count.most_common(5) return [k for k, v in top] # 3. 重合指数 IC 计算 def index_of_coincidence(text: str) - float: n len(text) if n 2: return 0.0 freqs Counter(text) ic sum(f * (f - 1) for f in freqs.values()) / (n * (n - 1)) return ic # 4. 按候选密钥长度分组计算平均 IC def average_ic_by_keylen(text: str, key_len: int) - float: total_ic 0.0 for i in range(key_len): group text[i::key_len] if len(group) 2: total_ic index_of_coincidence(group) return total_ic / key_len def find_key_length(text: str, max_len20): candidates [] for m in range(1, max_len 1): avg_ic average_ic_by_keylen(text, m) candidates.append((m, avg_ic)) # 按与0.065的接近程度排序 candidates.sort(keylambda x: abs(x[1] - 0.065)) return candidates # 5. 频数分析还原密钥字母 # 英文频率参考表按出现频率从高到低 ENGLISH_FREQ_ORDER ETAOINSHRDLCUMWFGYPBVKJXQZ # 更精确的频率表用于与分组分布做相关性比较 ENGLISH_FREQ { A: 0.08167, B: 0.01492, C: 0.02782, D: 0.04253, E: 0.12702, F: 0.02228, G: 0.02015, H: 0.06094, I: 0.06966, J: 0.00153, K: 0.00772, L: 0.04025, M: 0.02406, N: 0.06749, O: 0.07507, P: 0.01929, Q: 0.00095, R: 0.05987, S: 0.06327, T: 0.09056, U: 0.02758, V: 0.00978, W: 0.02360, X: 0.00150, Y: 0.01974, Z: 0.00074 } def frequency_analysis_for_group(group: str) - str: 输入单组密文返回最可能的密钥字母 n len(group) if n 0: return A freqs Counter(group) best_shift 0 best_corr -1 # 对每个可能的位移 shift(0-25)将组内字母减去 shift 得到明文频率分布 for shift in range(26): observed {} for ch, cnt in freqs.items(): plain_ch chr(((ord(ch) - ord(A) - shift) % 26) ord(A)) observed[plain_ch] cnt # 计算与英文频率的相关系数用简单的内积 corr 0.0 for ch in ABCDEFGHIJKLMNOPQRSTUVWXYZ: observed_freq observed.get(ch, 0) / n corr observed_freq * ENGLISH_FREQ[ch] if corr best_corr: best_corr corr best_shift shift return chr(ord(A) best_shift) def recover_key(text: str, key_len: int) - str: key for i in range(key_len): group text[i::key_len] key frequency_analysis_for_group(group) return key # 6. 解密函数 def vigenere_decrypt(cipher_text: str, key: str) - str: plain [] key_len len(key) for i, ch in enumerate(cipher_text): if ch.isalpha(): shift ord(key[i % key_len].upper()) - ord(A) p (ord(ch) - ord(A) - shift) % 26 plain.append(chr(p ord(A))) else: plain.append(ch) return .join(plain) # ---------- 执行 ---------- if __name__ __main__: text clean_text(cipher_text) print(f密文长度{len(text)}) # Kasiski 试验 print(\n[Kasiski 试验] 可能的密钥长度 TOP5:) top_lengths kasiski(text) print(top_lengths) # IC 法候选长度 print(\n[重合指数法] 候选密钥长度排序越接近0.065越优:) candidates find_key_length(text, max_len20) for m, ic in candidates[:10]: flag -- 最可能 if abs(ic - 0.065) 0.005 else print(f 密钥长度 {m:2d}: 平均IC {ic:.4f}{flag}) # 结合两种方式优先试 IC 排序中前几个长度 # 实际做题时可以直接把 key_len 换成 Kasiski 和 IC 交叉出的最优值 key_len candidates[0][0] print(f\n选用密钥长度: {key_len}) key recover_key(text, key_len) print(f还原密钥: {key}) plain_text vigenere_decrypt(text, key) print(f解密明文:\n{plain_text})4.2 脚本运行结果解读脚本输出分三块。第一块的 Kasiski 试验会给出几个可能的密钥长度第二块的 IC 法会给出从 1 到 20 每个长度的平均 IC。当你看到类似下面的输出密文长度392 [Kasiski 试验] 可能的密钥长度 TOP5: [7, 14, 21, 5, 3] [重合指数法] 候选密钥长度排序越接近0.065越优: 密钥长度 5: 平均IC 0.0431 密钥长度 7: 平均IC 0.0617 -- 最可能 密钥长度 14: 平均IC 0.0589 ... 选用密钥长度: 7 还原密钥: SECRETKEY 解密明文: ATTACK...这时候基本可以锁定key_len 7。注意 Kasiski 列出的 14、21 其实就是 7 的倍数这也符合理论预期间距差是密钥长度的整数倍所以因数分解时会不断出现密钥长度本身的倍数。如果你发现 IC 排序第一位不是 Kasiski 的第一位建议两个长度都试一遍解密出来是正常英文的那个就是对的。这个“双轨验证”是破 Vigenère 的常规操作。4.3 频数分析还原密钥的细节frequency_analysis_for_group这个函数的原理是在密钥长度确定之后第i组的所有字符都经过同一个位移加密。假设真实位移是shift把组内每个字母都反向移动shift位得到的就是一组近似明文字母分布。如果shift猜对了这组字母的频率分布应该和标准英文频率高度相似如果猜错了分布就会像随机文本。代码里我用了一个简单粗暴的相关性指标计算观察频率和标准英文频率的内积。这个指标虽然不是最严谨的更严谨的可以用卡方统计量或者对数似然但在这类题目里已经足够。调试时发现内积法在分组字符数少于 30 的时候误差会增大所以有些短分组需要人工校验。如果某个密钥字母还原出来不是预期的英文字母比如跑出来一个Q不用慌可以手动改代码打印出当前分组 Top 5 的候选位移及对应相关性选第二或第三可能的那一个。在攻防世界这道题里一般相关性最高的那个就是正确密钥。5. 实操演示从密文到 Flag 的完整通关记录5.1 第一次失败尝试反面教材我想说说我第一次做题时的失败经历这比成功的步骤更有参考价值。我最初的思路是把密文丢进某个在线 Vigenère 解密工具工具提示要输入密钥长度。我猜了个 5结果输出一堆乱码。我又试了 6、8、10全部失败。后来换了 Kasiski 工具工具提示密钥长度可能为 7但因为在线工具默认只做“每 7 位一组 频率分析”输出的明文中还是有几个字母是错的。这个失败经历揭示了两个问题Kasiski 工具给出的候选长度通常有好几个直接选第一个不一定对。在线工具的自动频率分析是基于标准英文频率的如果明文里大量出现专有名词或缩写E、T、A 这些字母的分布会有偏差导致个别密钥字母还原错误。所以后来我决定写一个本地脚本自己控制整个还原过程哪个字母不对就手动校准。这是在线工具替代不了的。5.2 手工校准密钥的实用技巧脚本跑完如果得到的明文里大部分单词能读通但小部分位置出现乱码不要急着重新跑。可以先按下面几步校准把恢复出来的明文打印出来定位乱码位置。根据上下文推测那个位置应该是什么字母大概率是大白话或者常见单词。反推密钥shift (cipher_char - plain_char) mod 26。找到该字符在密钥里的位置索引i mod key_len修正对应的密钥字母。重新解密。例如假设第 20 个字符处解密出来是X但上下文明显应该是个A。密文该位是N那么shift N - A 13。如果20 mod 7 6就把密钥第 7 个字母改成NA13N。这种人工微调在古典密码题里非常常见。现代密码学讲究“雪崩效应”改一个密钥位会让整个解密结果面目全非古典密码反而是逐位独立哪里错了改哪里非常直观。5.3 攻防世界 Flag 提交格式攻防世界的题目通常要求提交flag{...}格式的内容。这道题的明文通常是一段英文句子里面可能直接藏着 flag也可能需要把整段明文里的关键词提取出来按题目提示包装成 flag。这里给个提醒如果解出来的明文本身就是flag{...}这种格式直接提交如果只是一段英文句子注意看题目描述有没有额外提示比如 “submit the first word as flag” 或者 “the key is the flag” 之类。我自己遇到过不少新手在这里卡住明明解出来了却不知道怎么提交。实际操作中建议把最终的明文、还原的密钥都截图保存或者复制到本地笔记里。CTF 比赛中经常会有后续题目用到前一道题目的密钥或明文养成记录的习惯能省很多事。6. 常见问题与排查技巧实录6.1 密钥长度误判怎么办这是最常见的问题。IC 法选出来第一候选是 9第二候选是 3而且两者差别不大。这时候怎么办首先检查密文长度。如果密文只有 150 个字符9组每组只有约 16 个字符频率统计很不稳定IC 的可信度自然低。这种情况可以优先尝试更短的密钥长度因为 Vigenère 加密密钥一般不会太长实际操作中 5 到 10 比较常见。其次用“分组是否成英文”作为最终判据。对每个候选长度分别恢复密钥、解密哪份明文能读通就用哪个长度。虽然代码里可以自动跑但人眼判断还是最快的。6.2 频率分析还原密钥错误率高有些题为了增加难度会在加密前先对明文做 Base64 编码或去空格处理导致明文字母不是自然英文频率。这种情况下直接用标准英文频率表去匹配密钥字母误差会比较大。解决方案有两个用更长的密文统计频率作为“自定义参考频率”而不是用标准英文频率表。因为在同一道题里明文即使经过了 Base64 或十六进制编码字母分布也有一定的稳定性。利用 Vigenère 的结构约束。密钥字母还原后明文必须每个字母都是 Base64 合法字符或十六进制字符0-9A-F。可以用这个约束反过来过滤不合理的密钥位移。攻防世界那道 “how_many_Vigenère” 其实没有用到这类高级干扰但如果是题库里其他变种题这个方法能救命。6.3 脚本运行起来报错的特殊情况我在调试脚本时发现Python 的text[i::key_len]切片写法在key_len大于文本长度时不会报错但返回的单字符列表会导致频率分析非常不可靠。所以脚本里已经加了if len(group) 2的判断。另外密文里如果混入换行符和空格clean_text会统一去掉这点对最终解密没有影响因为 Vigenère 加密只作用于字母。但如果你后续要做词频分析或者看明文里的单词边界建议保留原始换行解密时按列位置同步还原。这里给一个通用的排查清单现象可能原因解决方案IC 所有候选长度都接近 0.038密文清洗不彻底混入大量非字母字符用正则只保留 A-Za-z再统一大写Kasiski 候选长度过多重复子串长度太短误报率高只统计长度为 4 以上的重复子串恢复出密钥但明文仍为乱码密钥长度使用了错误的倍数如把 7 写成 14强制将密钥长度除以公约数后重试部分密钥字母连续还原错误分组字符数太少或明文非纯英文改用人工反推法逐个修正密钥位6.4 工具链之外的“内功”最后顺带说一句做这类题不要只依赖脚本。我在实战中发现维吉尼亚密码的破解过程实际上是在训练一种“模式识别”的直觉看到一段密文先感受它的重复节奏再猜测密钥长度然后通过频率分布找位移其实和拼图很像。这种直觉在以后的密码题里不管是 Hill 密码、AES 的侧信道分析还是简单的异或加密都能用上。攻防世界的免费题库很适合练这种内功。刷题的时候多写脚本、多调试而不是只求一个 flag长期收获会大很多。尤其是这一道 how_many_Vigenère它把 Kasiski 试验和 IC 法两个核心知识点揉在了一起只要完整做一遍古典密码里关于多表替换的底子就算打牢了。