线性反馈移位寄存器(LFSR)密码学教学文档<\/h1>

一、LFSR基础概念<\/h2>

线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)是一种在密码学中广泛使用的伪随机序列生成器。它由以下几个核心组件构成：<\/p>

寄存器状态(R)<\/strong>: 一个n位的二进制序列，表示当前状态<\/li>
反馈函数(mask)<\/strong>: 决定哪些位参与反馈计算<\/li>

输出序列<\/strong>: 每次移位后输出的比特序列<\/li> <\/ol>
LFSR的工作原理是：每次操作时，寄存器右移一位，最右边的位作为输出，新的最左边的位由反馈函数计算得出。<\/p>
二、LFSR的数学表示<\/h2>
对于一个n级LFSR，其反馈函数可以表示为：<\/p>
f(aₙ,aₙ₋₁,...,a₂,a₁) = cₙaₙ ⊕ cₙ₋₁aₙ₋₁ ⊕ ... ⊕ c₂a₂ ⊕ c₁a₁ <\/code><\/pre> 其中：<\/p> aᵢ表示寄存器第i位的值<\/li> cᵢ ∈ {0,1}表示该位是否参与反馈计算(由mask决定)<\/li> ⊕表示异或(XOR)操作<\/li> <\/ul> 反馈多项式(特征多项式)可以表示为：<\/p> P(x) = xⁿ + cₙ₋₁xⁿ⁻¹ + ... + c₁x + c₀ <\/code><\/pre> 三、LFSR的密码学应用<\/h2> 在CTF密码学题目中，LFSR通常以两种形式出现：<\/p> 第一类：已知输出序列和mask，求初始状态(seed)<\/h3> 例题：CISCN2018 oldstreamgame<\/strong><\/p> 题目给出：<\/p> 输出序列(key)：798位二进制(实际应为800位，前面补0)<\/li> mask：32位二进制数(0x100002)<\/li> <\/ol> 解题步骤：<\/p> 理解LFSR正向工作流程<\/li> 根据输出序列前32位逆向推导初始状态<\/li> 通过矩阵运算求解初始状态<\/li> <\/ol> 正向推导示例<\/strong>：对于8位初始状态R=10010001和mask=10101000：<\/p> 计算反馈位：1⊕0⊕0⊕0⊕0⊕0⊕0⊕0 = 1<\/li> 右移后新状态：11001000<\/li> 输出最右位：1<\/li> <\/ol> 逆向推导方法<\/strong>：<\/p> 设已知输出序列为s₁,s₂,...,sₙ<\/li> 初始状态R = [s₁,s₂,...,sₙ]<\/li> 对于后续输出sₙ₊₁，有：sₙ₊₁ = c₁s₁ ⊕ c₂s₂ ⊕ ... ⊕ cₙsₙ<\/li> 建立方程组求解<\/li> <\/ol> 第二类：已知初始状态和输出序列，求mask<\/h3> 解题方法<\/strong>：<\/p> B-M算法<\/strong>：需要知道2n长的输出序列<\/p> 适用于当输出序列足够长时<\/li> 算法介绍参考：https:\/\/ctf-wiki.org\/crypto\/streamcipher\/fsr\/lfsr\/<\/li> <\/ul> <\/li> 矩阵逆运算方法<\/strong>：<\/p> 建立线性方程组<\/li> 通过矩阵求逆解mask<\/li> <\/ul> <\/li> <\/ol> 示例题目<\/strong>：<\/p> 已知初始状态R(seed)<\/li> 已知128位输出序列<\/li> 求mask(即flag)<\/li> <\/ul> 解题脚本逻辑<\/strong>：<\/p> 根据输出序列建立线性方程组<\/li> 使用高斯消元法求解mask各比特位<\/li> 验证解的合理性<\/li> <\/ol> 四、LFSR的重要性质<\/h2> 最大周期<\/strong>：<\/p> n级LFSR的最大周期为2ⁿ-1<\/li> 达到最大周期的条件是反馈多项式是本原多项式<\/li> <\/ul> <\/li> 本原多项式<\/strong>：<\/p> 定义：在有限域GF(2)上不可约且阶数为2ⁿ-1的多项式<\/li> 示例：x⁴ + x + 1是4阶本原多项式，对应周期为15<\/li> <\/ul> <\/li> 循环特性<\/strong>：<\/p> 当使用本原多项式时，输出序列达到最大周期后才开始循环<\/li> 非本原多项式产生的序列循环周期会缩短<\/li> <\/ul> <\/li> <\/ol> 五、实践测试与验证<\/h2> 测试一：正向测试验证<\/h3> 使用特定初始状态和mask，验证输出序列与手工计算一致。<\/p> 测试二：循环特性测试<\/h3> 验证不同反馈多项式下的循环周期：<\/p> 使用本原多项式x⁴ + x + 1： 4级LFSR<\/li> 输出序列周期应为15<\/li> <\/ul> <\/li> 使用非本原多项式：观察循环周期缩短现象<\/li> <\/ul> <\/li> <\/ol> 六、解题脚本示例<\/h2> 第一类问题解题脚本（已知输出和mask求初始状态）<\/h3> def<\/span> reverse_lfsr<\/span>(output, mask): <\/span><\/span> length =<\/span> mask.<\/span>bit_length() <\/span><\/span> # 补全输出序列前面的0<\/span> <\/span><\/span> if<\/span> len(output) <<\/span> length: <\/span><\/span> output =<\/span> [0<\/span>]*<\/span>(length-<\/span>len(output)) +<\/span> output <\/span><\/span> <\/span><\/span> # 取前length位作为初始状态<\/span> <\/span><\/span> state =<\/span> output[:length] <\/span><\/span> <\/span><\/span> # 验证后续输出是否匹配<\/span> <\/span><\/span> for<\/span> i in<\/span> range(length, len(output)): <\/span><\/span> feedback =<\/span> 0<\/span> <\/span><\/span> tmp =<\/span> mask &<\/span> ((1<\/span> <<<\/span> length) -<\/span> 1<\/span>) <\/span><\/span> for<\/span> j in<\/span> range(length): <\/span><\/span> if<\/span> (tmp >><\/span> j) &<\/span> 1<\/span>: <\/span><\/span> feedback ^=<\/span> state[i-<\/span>length+<\/span>j] <\/span><\/span> if<\/span> feedback !=<\/span> output[i]: <\/span><\/span> return<\/span> None<\/span> # 不匹配<\/span> <\/span><\/span> <\/span><\/span> return<\/span> state[:length] <\/span><\/span><\/code><\/pre>第二类问题解题脚本（已知初始状态和输出序列求mask）<\/h3> def<\/span> find_mask<\/span>(initial_state, output_sequence): <\/span><\/span> n =<\/span> len(initial_state) <\/span><\/span> # 建立方程组<\/span> <\/span><\/span> equations =<\/span> [] <\/span><\/span> for<\/span> i in<\/span> range(n, len(output_sequence)): <\/span><\/span> equation =<\/span> [] <\/span><\/span> for<\/span> j in<\/span> range(n): <\/span><\/span> equation.<\/span>append(initial_state[j] if<\/span> i ==<\/span> n else<\/span> output_sequence[i-<\/span>n+<\/span>j-<\/span>1<\/span>]) <\/span><\/span> equations.<\/span>append((equation, output_sequence[i])) <\/span><\/span> <\/span><\/span> # 高斯消元求解mask<\/span> <\/span><\/span> mask =<\/span> 0<\/span> <\/span><\/span> for<\/span> bit in<\/span> range(n): <\/span><\/span> # 收集所有涉及该bit的方程<\/span> <\/span><\/span> # ... 具体实现省略 ...<\/span> <\/span><\/span> pass<\/span> <\/span><\/span> <\/span><\/span> return<\/span> mask <\/span><\/span><\/code><\/pre>七、参考资料<\/h2> CTF Wiki - LFSR: https:\/\/ctf-wiki.org\/crypto\/streamcipher\/fsr\/lfsr\/<\/li> 本原多项式相关介绍<\/li> B-M算法详细说明<\/li> <\/ol> 八、总结<\/h2> LFSR在密码学题目中常见且重要，掌握以下关键点：<\/p> 理解LFSR的工作原理和数学表示<\/li> 掌握两类常见问题的解决方法<\/li> 了解LFSR的周期特性和本原多项式的作用<\/li> 能够编写正向和逆向的解题脚本<\/li> <\/ol> 通过实际例题练习和测试验证，可以深入理解LFSR在密码学中的应用。<\/p>