线性反馈移位寄存器(LFSR)密码学教学文档

一、LFSR基础概念

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

1. 寄存器状态(R): 一个n位的二进制序列，表示当前状态
2. 反馈函数(mask): 决定哪些位参与反馈计算
3. 输出序列: 每次移位后输出的比特序列

LFSR的工作原理是：每次操作时，寄存器右移一位，最右边的位作为输出，新的最左边的位由反馈函数计算得出。

二、LFSR的数学表示

对于一个n级LFSR，其反馈函数可以表示为：

f(aₙ,aₙ₋₁,...,a₂,a₁) = cₙaₙ ⊕ cₙ₋₁aₙ₋₁ ⊕ ... ⊕ c₂a₂ ⊕ c₁a₁

其中：

• aᵢ表示寄存器第i位的值
• cᵢ ∈ {0,1}表示该位是否参与反馈计算(由mask决定)
• ⊕表示异或(XOR)操作

反馈多项式(特征多项式)可以表示为：

P(x) = xⁿ + cₙ₋₁xⁿ⁻¹ + ... + c₁x + c₀

三、LFSR的密码学应用

在CTF密码学题目中，LFSR通常以两种形式出现：

第一类：已知输出序列和mask，求初始状态(seed)

例题：CISCN2018 oldstreamgame

题目给出：

1. 输出序列(key)：798位二进制(实际应为800位，前面补0)
2. mask：32位二进制数(0x100002)

解题步骤：

1. 理解LFSR正向工作流程
2. 根据输出序列前32位逆向推导初始状态
3. 通过矩阵运算求解初始状态

正向推导示例：
对于8位初始状态R=10010001和mask=10101000：

1. 计算反馈位：1⊕0⊕0⊕0⊕0⊕0⊕0⊕0 = 1
2. 右移后新状态：11001000
3. 输出最右位：1

逆向推导方法：

1. 设已知输出序列为s₁,s₂,...,sₙ
2. 初始状态R = [s₁,s₂,...,sₙ]
3. 对于后续输出sₙ₊₁，有：sₙ₊₁ = c₁s₁ ⊕ c₂s₂ ⊕ ... ⊕ cₙsₙ
4. 建立方程组求解

第二类：已知初始状态和输出序列，求mask

解题方法：

1. B-M算法：需要知道2n长的输出序列

   • 适用于当输出序列足够长时
   • 算法介绍参考：https://ctf-wiki.org/crypto/streamcipher/fsr/lfsr/

2. 矩阵逆运算方法：

   • 建立线性方程组
   • 通过矩阵求逆解mask

示例题目：

• 已知初始状态R(seed)
• 已知128位输出序列
• 求mask(即flag)

解题脚本逻辑：

1. 根据输出序列建立线性方程组
2. 使用高斯消元法求解mask各比特位
3. 验证解的合理性

四、LFSR的重要性质

1. 最大周期：

   • n级LFSR的最大周期为2ⁿ-1
   • 达到最大周期的条件是反馈多项式是本原多项式

2. 本原多项式：

   • 定义：在有限域GF(2)上不可约且阶数为2ⁿ-1的多项式
   • 示例：x⁴ + x + 1是4阶本原多项式，对应周期为15

3. 循环特性：

   • 当使用本原多项式时，输出序列达到最大周期后才开始循环
   • 非本原多项式产生的序列循环周期会缩短

五、实践测试与验证

测试一：正向测试验证

使用特定初始状态和mask，验证输出序列与手工计算一致。

测试二：循环特性测试

验证不同反馈多项式下的循环周期：

1. 使用本原多项式x⁴ + x + 1：
   • 4级LFSR
   • 输出序列周期应为15
2. 使用非本原多项式：
   • 观察循环周期缩短现象

六、解题脚本示例

第一类问题解题脚本（已知输出和mask求初始状态）

def reverse_lfsr(output, mask):
    length = mask.bit_length()
    # 补全输出序列前面的0
    if len(output) < length:
        output = [0]*(length-len(output)) + output
    
    # 取前length位作为初始状态
    state = output[:length]
    
    # 验证后续输出是否匹配
    for i in range(length, len(output)):
        feedback = 0
        tmp = mask & ((1 << length) - 1)
        for j in range(length):
            if (tmp >> j) & 1:
                feedback ^= state[i-length+j]
        if feedback != output[i]:
            return None  # 不匹配
    
    return state[:length]

第二类问题解题脚本（已知初始状态和输出序列求mask）

def find_mask(initial_state, output_sequence):
    n = len(initial_state)
    # 建立方程组
    equations = []
    for i in range(n, len(output_sequence)):
        equation = []
        for j in range(n):
            equation.append(initial_state[j] if i == n else output_sequence[i-n+j-1])
        equations.append((equation, output_sequence[i]))
    
    # 高斯消元求解mask
    mask = 0
    for bit in range(n):
        # 收集所有涉及该bit的方程
        # ... 具体实现省略 ...
        pass
    
    return mask

七、参考资料

1. CTF Wiki - LFSR: https://ctf-wiki.org/crypto/streamcipher/fsr/lfsr/
2. 本原多项式相关介绍
3. B-M算法详细说明

八、总结

LFSR在密码学题目中常见且重要，掌握以下关键点：

1. 理解LFSR的工作原理和数学表示
2. 掌握两类常见问题的解决方法
3. 了解LFSR的周期特性和本原多项式的作用
4. 能够编写正向和逆向的解题脚本

通过实际例题练习和测试验证，可以深入理解LFSR在密码学中的应用。