流密码与LFSR
流密码与LFSR
本文适合
已经掌握 XOR，准备处理 keystream 复用、LFSR 输出恢复和 bit 序列预测题的学习者。学完你能：从源码或密文中识别流密码结构，用已知明文恢复 keystream，并用 Berlekamp-Massey 或线性方程恢复 LFSR。
一句话判断
流密码题的关键是密钥流：只要密钥流被复用、可预测、线性生成或泄露足够多，就可以恢复明文、后续输出或内部状态。
题目中常见信号
说明：流密码或 OTP
说明：keystream 复用
说明：LFSR 或 bit PRNG
说明：LFSR 特征
说明：可恢复 keystream 片段
说明：Berlekamp-Massey 可能恢复递推
核心概念
流密码把 keystream 与明文 XOR 得到密文，安全前提是 keystream 不重复且不可预测。LFSR 的反馈是线性的，所以足够多的连续输出可以恢复最短线性递推；如果多个 LFSR 组合函数仍有偏差，也可能被相关攻击拆开。
不要把“输出看起来随机”当安全。CTF 中只要源码中出现线性反馈、短状态、固定 seed、重复 nonce，就要尝试状态恢复。
最小分析流程
- 把密文转成 bytes 或 bit 序列，确认 XOR 方向。
- 找已知明文：
flag{、文件头、协议头、JSON。 - 用
keystream = ciphertext xor known_plaintext得到局部密钥流。 - 如果是重复 key，按周期扩展；如果是 LFSR，收集连续 bit。
- 对 LFSR 输出跑 Berlekamp-Massey 或建立 GF(2) 线性方程。
- 用恢复出的状态生成后续 keystream，解密全文并验证 flag。
最小验证示例
def berlekamp_massey(bits):
c, b = [1], [1]
l, m = 0, 1
for n in range(len(bits)):
d = bits[n]
for i in range(1, l + 1):
d ^= c[i] & bits[n - i]
if d == 0:
m += 1
continue
t = c[:]
if len(c) < len(b) + m:
c += [0] * (len(b) + m - len(c))
for j in range(len(b)):
c[j + m] ^= b[j]
if 2 * l <= n:
l = n + 1 - l
b = t
m = 1
else:
m += 1
return l, c
bits = [1,0,0,1,1,0,1,1,1,0,0,1,0,1,1,0]
print(berlekamp_massey(bits))输出的 l 是最短 LFSR 阶数，c 是递推关系。真实题要用恢复出的递推生成后续 bit，再 XOR 密文验证。
常见利用 / 解题路线
路线总览：
- keystream 复用：
C1 xor C2 = P1 xor P2，结合 crib dragging。 - 已知明文恢复：用文件头或
flag{恢复 key/keystream 片段。 - 短周期 key：估计周期后按列做单字节 XOR 分析。
- LFSR 恢复：连续输出足够时用 Berlekamp-Massey。
- 组合 LFSR：先看组合函数是否线性或有相关偏差。
常见失败原因
排查动作：检查明文偏移、编码层和是否跳过了 nonce/header
排查动作：bit 顺序可能反了，或输出经过非线性过滤
排查动作：keystream 不是循环 key，可能是状态生成器
排查动作：先找空格和 flag 前缀，不要同时猜太多位置
排查动作：检查 tap 下标、移位方向、输出位是高位还是低位
迷你案例
题目给两个十六进制密文，并说明同一个 OTP key 加密两句话。先算 x = c1 xor c2，再把 flag{ 放在不同偏移 crib dragging。某个偏移得到另一条明文出现 the 和 _，说明该位置猜测可信。继续扩展 crib，恢复 keystream，再解出含 flag 的明文。
证据链是：同 key 流复用 -> 两密文互 XOR 消掉 keystream -> 已知明文拖拽 -> 恢复 keystream -> 解密验证。