两次维吉尼亚加密同一明文:差分周期恢复密钥流并解 flag
ctf/crypto · verified
一句话结论
两段密文的单词数、标点、换行结构完全一致,说明是同一明文被两次维吉尼亚加密;去掉非字母后逐字符做 Δ=(c2-c1) mod 26,差分严格以 41 为周期,结合已知 texsaw 前缀恢复密钥短语 askanditshallbegivenyouseekandyeshallfind 的不同循环位移,即可解出两段 flag。
原理
- 维吉尼亚:
c_i = (p_i + k_i) mod 26。同一明文用两套密钥流加密时,c2_i - c1_i = k2_i - k1_i mod 26,明文被消掉,只剩两套密钥流的差。 - 周期检测:若密钥流周期为
p,差分序列也以p为周期。本题对两段正文去空格/标点后做差分,发现严格按 41 个字母循环,说明是周期多表替换且密钥长度 41。 - 已知前缀恢复密钥片段:flag 格式为
texsaw{...},两串 flag 密文前缀twhsnz/brassg与明文texsaw逐位相减,得到askand/indask。这两个片段拼起来指向一句 41 字母的英文短语:askanditshallbegivenyouseekandyeshallfind(“Ask and it shall be given you; seek and ye shall find”)。 - 相位:不同密文块的起始位置不同,密钥流要循环位移。flag 两块分别用
rot(key,0)和rot(key,38);正文两块用rot(key,15)和rot(key,12)(可枚举 41 个相位找可读英文)。 - 结果:flag 解密为
texsaw{luojmfsgmkqltenaemdqlxgtyrfdlzxdmqmxysvdettsxpatcq};正文是可读英文。
触发条件
- 有两段密文,长度/词数/标点/换行结构高度一致,疑似同一明文。
- 加密是周期性多表替换(维吉尼亚/博福特/格朗斯费尔德等)。
- 已知明文前缀或格式(如
flag{、texsaw{)。 - 密钥流长度可通过差分周期、Kasiski 或重合指数确定。
利用步骤
- 把两段密文去掉非字母、转小写,确认长度一致。
- 逐字符算
Δ=(c2-c1) mod 26,找最小周期p(本题 41)。 - 用已知明文前缀反推密钥片段;搜索/联想出完整密钥短语。
- 对每个密文块枚举密钥流的 41 个循环位移,解出可读文本。
- 用 flag 格式和英文语义验证;必要时对多段分别求相位。
PoC
import string
ALPHA = string.ascii_lowercase
flag_ct1 = "twhsnz{tngqmqdhqqygxrloyehuvxtwwvxklkiiudpxqcvqhbmkepledu}"
flag_ct2 = "brassg{lhrrfxzgxvrpzmierkrkdbkdyeibpredxbrflvvvotgvfisacb}"
def only_letters(s):
return ''.join(ch for ch in s.lower() if ch in ALPHA)
def rot(s, n):
return s[n:] + s[:n]
def vig_dec(text, key):
out, j = [], 0
for ch in text.lower():
if ch in ALPHA:
out.append(ALPHA[(ALPHA.index(ch) - ALPHA.index(key[j % len(key)])) % 26])
j += 1
else:
out.append(ch)
return ''.join(out)
base = "askanditshallbegivenyouseekandyeshallfind"
assert len(base) == 41
print(vig_dec(flag_ct1, rot(base, 0)))
print(vig_dec(flag_ct2, rot(base, 38)))
差分周期检测(正文两段):
def diff_period(a, b):
ds = [(ALPHA.index(y) - ALPHA.index(x)) % 26 for x, y in zip(a, b)]
for p in range(1, len(ds) + 1):
if all(ds[i] == ds[i % p] for i in range(len(ds))):
return p
# period = 41
变体与关联
- 同明文变体:两段正文是同一明文的不同语言/不同密钥/不同相位;差分周期就是密钥长度。
- 密码变体:维吉尼亚、博福特(
k-p)、格朗斯费尔德(数字密钥)、自动密钥;差分公式不同但思路相同。 - 密钥恢复变体:已知前缀、Kasiski、重合指数、字典短语;密钥可能是名言/歌词。
- 关联卡片:[[ctf-crypto-vigenere-caesar-digit-letter-branch-counter-scope]](维吉尼亚+凯撒复合)、[[ctf-crypto-aes-gcm-nonce-reuse-ghash-subkey-root]](复用/差分思想)、[[crypto-classical-hill-cipher-3x3-matrix-inverse-mod26]](古典多表/矩阵还原)。
- 边界:若两段不是同一明文、密钥非周期、或差分周期不唯一,需要更多密文/已知明文;相位枚举要结合语言模型。
检测与防御
- 防御:不要用同一明文配相关密钥重复加密;使用带随机 nonce/IV 的认证加密(AES-GCM/ChaCha20-Poly1305)。
- 检测信号:两段密文结构完全一致;差分序列呈短周期;同一密钥流被不同相位复用。
- CTF 技巧:先做差分找周期,再用已知前缀锁定密钥片段,最后枚举相位。