CTF实战：如何精准判断Vigenère密钥长度并自动化解密

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是明文字母对应的数字（A=0, B=1, ..., Z=25）。
• 重合指数（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^m（m为密钥长度）。如果密钥长度是 6，密钥空间就有 3.08 亿种组合，暴力爆破完全不现实。更合理的方法是分两步走：

1. 先确定密钥长度m，把多表替换降级为m组单表替换。
2. 对每一组做单表替换的频数分析（本质上就是凯撒密码破译），逐位恢复密钥字母。

这就好比把一把带有多重锁芯的锁拆开来，每个锁芯单独撬。理解这个思路之后，难点就只剩 “怎么精准确定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很可能是密钥长度的倍数。如果密钥长度为 6，18 = 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组。比如m=5时，第 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 < 50，IC 的方差很大，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_len=3, max_len=5): 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:i+sub_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_len=20): 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(key=lambda 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_len=20) 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 手工校准密钥的实用技巧

脚本跑完，如果得到的明文里大部分单词能读通，但小部分位置出现乱码，不要急着重新跑。可以先按下面几步校准：

1. 把恢复出来的明文打印出来，定位乱码位置。
2. 根据上下文推测那个位置应该是什么字母（大概率是大白话或者常见单词）。
3. 反推密钥：shift = (cipher_char - plain_char) mod 26。
4. 找到该字符在密钥里的位置索引i mod key_len，修正对应的密钥字母。
5. 重新解密。

例如，假设第 20 个字符处解密出来是X，但上下文明显应该是个A。密文该位是N，那么shift = N - A = 13。如果20 mod 7 = 6，就把密钥第 7 个字母改成N（A+13=N）。

这种人工微调在古典密码题里非常常见。现代密码学讲究“雪崩效应”，改一个密钥位会让整个解密结果面目全非；古典密码反而是逐位独立，哪里错了改哪里，非常直观。

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 加密只作用于字母。但如果你后续要做词频分析或者看明文里的单词边界，建议保留原始换行，解密时按列位置同步还原。

这里给一个通用的排查清单：

6.4 工具链之外的“内功”

最后顺带说一句，做这类题不要只依赖脚本。我在实战中发现，维吉尼亚密码的破解过程实际上是在训练一种“模式识别”的直觉：看到一段密文，先感受它的重复节奏，再猜测密钥长度，然后通过频率分布找位移，其实和拼图很像。这种直觉在以后的密码题里，不管是 Hill 密码、AES 的侧信道分析，还是简单的异或加密，都能用上。

攻防世界的免费题库很适合练这种内功。刷题的时候多写脚本、多调试，而不是只求一个 flag，长期收获会大很多。尤其是这一道 how_many_Vigenère，它把 Kasiski 试验和 IC 法两个核心知识点揉在了一起，只要完整做一遍，古典密码里关于多表替换的底子就算打牢了。