是否有可能只对LFSR进行密文攻击？

Question

阅读LFSR，我知道通过知道LFSR的设计和拥有足够多的(明文，密文)对来打破LFSR是一项相对容易的任务，但我们假设我们知道LFSR的设计和一个长的密文，这是通过链接明文和LFSR输出的结果。有办法解密密文吗？

例如，假设我们有一个原始特征多项式$x^{51}+x^{9}+1$和5600位密文，我们已经知道的明文是英语纯文本？

一种强力方法是尝试所有$2^{51}可能的种子值，用LFSR输出对密文进行拼接，并检查产生的明文是否具有正常的英文字母熵，但是这种方法越来越难获得更大的LFSR程度。

Answer 1

对于已知的ASCII编码为八位字节的文本，其高阶位为零，这显示了LFSR输出的8位中的一位。它仅通过求解一个线性布尔方程组，就可以从(比方说)前51位密文中找到LFSR的原始状态；然后破译其余的部分。不涉及任何猜测。

对于7位加奇偶(其中每个八位的高阶位是其他7位的外接或或，或它的补充)，线性代数也是有效的。

随着明文变得不那么冗馀，事情变得更加困难。使用7位ASCII，注意到空格、数字、普通标点符号和所有小写字母都在范围$\cup$中，我们知道每个这样的7位符号都有权重5集的位，在800个字符的明文中有51个这样的字符出现在一行中。根据英语文本的特点，可以在哪里对其他内容进行解码，这样就很容易发现猜测是否正确。

更普遍的是，如果几乎任何位置的51位都可以猜测，那么剩下的就由基本线性代数唯一确定，并且通过检查产生的明文是否适当冗馀来验证猜测。一个LFSR是这样的，一个糟糕的猜测被淘汰，使用非常简单的测试非常高的可能性，不可能错误地排除一个错误的猜测。我们甚至可以使用一个宽松的X-平方检验，猜测产生的明文是随机的，当它不是，它将是正确的。这具有不分语言工作的优点。

只要能够猜测到足够多的比特，这些技术就可以与数百位的LFSR一起工作，包括使用未知的反馈多项式(只需将抽头作为附加未知数添加即可)。