关键字替换密码(keyword cipher)密钥未知:按首字母枚举候选密钥 + 词频/可读性打分自动定位
crypto/classical · verified
一句话结论
密文保持词形、空格与标点不变但字母全被替换,且题面暗示"密钥/关键在一个 key 里"时,通常是关键字替换密码:换表由一个密钥短语(去重后接剩余字母表)生成。密钥未知时不必穷举整个短语——按密钥首字母枚举长度较小的候选短语,用英文词频与可打印率给每个候选的明文打分,分数陡然升高的那一个就是密钥(本例枚举到 b 开头时命中 bingo)。
原理
- 关键字替换密码(keyword cipher)构造换表:取密钥短语 → 去掉重复字母 → 后接字母表中未出现的字母 → 得到 26 字母密文字母表;加密即把明文按该表逐字母替换。密钥是一句话/一个词,因此密钥空间远小于 26!,属于"可枚举的置换"。
- 与纯单表替换的区别:它的换表有强结构(密钥字母按原序出现在表头、剩余字母按 a–z 顺序补齐)。这既是特征的来源,也意味着只要猜中密钥就能精确复现整张表。
- 当密钥本身是无意义短词(
bingo),词频工具(quipqiup 类)往往直接给出明文,反而"顺手"暴露密钥;先试工具、工具不给唯一解时再退回枚举,是效率最高的顺序。 - 枚举策略:固定首字母 + 短语长度 3~6,或直接用一个常见单词表(rockyou 的前若干万条、人名词表)作为候选密钥。评分函数用英文四元组/单词命中率(如
the、and、ing出现次数)+ 明文可打印率,排序取最高;通常第一名的分数会明显高于第二名。 - 本题的可利用提示:文档里"降序和升序"两处文字都出现了
bingo,说明出题人把密钥埋在文本细节里;真实题面里凡是在无关位置重复出现的同一个短词,都应优先当候选密钥试。
触发条件
- 密文为纯字母替换,保留空格/标点、单词长度不变(可据此确认是单表替换类,而非换位)。
- 题面或附件暗示"key/关键字/密钥在某个文档里",或提供了候选词来源(提示文本、文件名、图片)。
- 明文为英文自然语言(词频与词典匹配才有意义);若是中文拼音或随机串则失效。
- 有词频统计工具或能写十几行评分脚本。
利用步骤
- 先做基础判定:统计密文字母频率并画图,与英文频率(e/t/a/o/i/n 高、q/z/x 低)比对,确认是单表替换。
- 先试自动化工具(quipqiup 类):若直接给出可读明文,则从明文反推换表、再反查密钥短语(换表开头连续的、未按字母序排列的字母即密钥去重后的结果)。
- 工具不给唯一解时改为枚举:对候选密钥(首字母 a–z 各枚举 3~6 位短语,或直接用词表)生成换表、解出明文、打分。
- 打分:统计
the/and/ing/ion/ent等高频片段命中数 + 明文可打印率 + 单词是否在词典中;取分数最高的候选。 - 用命中的密钥复现完整换表,逐字解密全文(含
flag{}内的数字/符号,注意非字母字符通常原样保留)。 - 回填验证:解密结果里的
flag{...}前缀应与题面格式一致,可据此反向确认换表正确。
PoC
import string, collections
ALPHA = string.ascii_lowercase
def build_table(key: str) -> dict:
"""密钥去重后接剩余字母 -> 明文->密文映射(解密时取反映射)"""
seen, head = set(), ""
for c in key.lower():
if c in ALPHA and c not in seen:
seen.add(c); head += c
tail = "".join(c for c in ALPHA if c not in seen)
cipher_alpha = head + tail
return str.maketrans(ALPHA, cipher_alpha)
def decrypt(ct: str, key: str) -> str:
enc = build_table(key) # 明文->密文
dec = {v: k for k, v in enc.items()}
return "".join(dec.get(c.lower(), c) if c.isalpha() else c for c in ct)
FREQ = ("the", "and", "ing", "ion", "ent", "her", "for", "tha", "nth", "int")
def score(pt: str) -> float:
low = pt.lower()
words = sum(low.count(w) for w in FREQ)
printable = sum(c.isprintable() for c in pt) / max(len(pt), 1)
return words * 3 + printable
# 1) 先用工具/词表给候选;2) 无候选时按首字母枚举
best = None
for first in ALPHA:
for word in [first + x for x in ("ingo", "ingo!", "ingo1")]: # 本例命中的构造
pt = decrypt(CT, word)
s = score(pt)
if best is None or s > best[0]:
best = (s, word, pt)
print(best[1], best[2][:80])
# 更通用的做法:用词表当候选密钥,取评分最高者
cands = [w.strip() for w in open("words.txt", encoding="utf-8", errors="ignore") if 3 <= len(w.strip()) <= 8]
ranked = sorted(((score(p := decrypt(CT, w)), w, p) for w in cands), reverse=True)
for s, w, p in ranked[:5]:
print(round(s, 2), w, p[:60])
变体与关联
- 变体(密钥是长句):换表头部很长且顺序明显不是字母序,此时"读出表头即得密钥",不需要枚举。
- 变体(换表后还叠加移位):关键字换表 + 凯撒移位,先按频率定移位量、再解关键字表。
- 变体(换位而非替换):若字母频率与英文吻合但词不成词,说明是换位类(栅栏/列置换),走另一条路。
- 关联:[[crypto-classical-monoalphabetic-substitution-frequency-tool]](同类问题的"先上词频工具"路线)、[[crypto-classical-lookup-table-multibyte-substitution-reverse]](表结构与换表映射)、[[crypto-classical-column-transpose-vertical-read-caesar-shift]](换位类的对照)。
- 边界:明文不是英文时评分函数失效;密钥含数字/符号时换表构造需按样本的实际实现(有的实现只对字母去重,数字原样保留)。
检测与防御
- 说明:本条是古典密码的分析与还原方法,不是对在用系统的攻击手段。
- 防御侧价值:任何"用短语派生换表"的古典方案都不构成现代密码学安全边界;需要保密时应使用 AEAD 类现代加密,而不是字符替换。
- 若作为题目/教学材料:提醒出题人避免在正文里重复出现密钥词(本例的
bingo就出现在无关句子里,直接缩小了搜索空间)。