3.7 针对单个 LFSR 的已知明文攻击

LFSR 是线性的，线性系统是由其输入和输出之间的线性关系来决定的。由于线性依赖易于分析，使得 LFSR 在诸如通信系统的应用中具有很大的优势。然而，如果一个密钥体制中的密钥位置只呈现线性关系，那么该密钥会相当不安全。现在我们将探讨 LFSR 的线性行为如何导致强大的攻击。
如果 LFSR 作为序列密钥使用，密钥 k 就是反馈系数向量$(p_{m-1}, …, p_1, p_0)$。如果攻击者 Oscar 知道某些明文和对应的密文，他就可能发起攻击。进一步假设 Oscar 知道 LFSR 的度 m, 那么攻击将非常高效，他可以尝试很多可能的 m 的值，因此这个假设并不是一个很重要的限制条件。假设已知的铭文表示为$x_0, x_1,…,x_{2m-1}$，他们对应的密文表示为$y_0, y_1, …,y_{2m-1}$。Oscar 利用这 2m 对明文和密文位，就可以重构 2m 个密钥序列位：

$s_i\equiv x_i + y_i\ mod\ 2;i = 0, 1, ..., 2m-1$

现在的目标就是找出由反馈系数$p_i$ 给出的密钥。

$\displaystyle s_{i+m}\equiv\sum_{j=0}^{m-1}p_j\cdot s_{i+j}\ mod\ 2;s_i,p_j\epsilon\{0,1\};\\ i = 0, 1, 2, ...$

注意：每个 i 值都会得到不同的等式；此外，此等式都是线性无关的。有了这些知识，Oscar 就可以生成 i 开头 m 个值对应的 m 个等式。

$i = 0, s_m\equiv p_{m-1}s_{m-1} + ... + p_1s_1 + p_0s_0\ \ \ \ mod\ 2\\ i = 1, s_{m+1}\equiv p_{m-1}s_m + ... + p_1s_2 + p_0s_1\ \ \ \ mod\ 2\\ .\\ .\\ .\\ i = m-1, s_{2m-1}\equiv p_{m-1}s_{2m-2} + ... + p_1s_m + p_0s_{m-1}\ \ \ \ mod\ 2$

Oscar 现在得到了拥有 m 个未知数$p_0, p_1, …p_{m-1}$ 的 m 个线性等式。Oscar 利用高斯消去、矩阵求逆或其他任何方法来求解次等式系统。即使 m 的值非常大，使用标准 PC 也很容易做这点。
这种情况的后果非常严重：只要 Oscar 知道度为 m 的 LFSR 的 2m 个输出位，他就可以通过仅求解一个线性等式系统来精确地构建系数$p_i$。一旦 Oscar 知道了这些反馈系数，他就可以构建 LFSR 并加载他已知道的任意 m 个连续的输出位。现在，Oscar 可以计时 LFSR，并得到整个输出序列。正是因为这种强大的攻击，LFSR 本身就是极其不安全的。这是一个很好的拥有良好统计属性但密码属性非常差的 PRNG 示例。然而，它并没有丧失所有密码属性。有不少序列密码都是使用多个 LFSR 的组合构建强健的密码体制。Trivium 就是一个例子。