线性反馈移位寄存器（LFSR）的学习笔记

• 前言

LFSR（线性反馈移位寄存器）已经成为如今CTF中密码学方向题目的一个常见考点了，在今年上半年的一些 国内赛和国际赛上，也出现了非常多的这类题目，对其的说明解释也有几位大佬已经做过详细说明，但始终 网上针对这类考点的详细分析不多，因此接下来我将以更为简单的的介绍及分析带入门，后续将会附上大佬 的链接，若有总结不到位请见谅。

• LFSR简介

LFSR是属于FSR（反馈移位寄存器）的一种，除了LFSR之外，还包括NFSR（非线性反馈移位寄存器）。反馈移位就是可以通过前面已经存在的寄存器中的值反馈出后面的的寄存器的值，通过不断移位对应不同的前 寄存器值一直反馈出后面连续的后寄存器值。即类似于摸石过河的游戏，三块石头总量不变却能一直向前移动，你可以将石头看作是寄存器中的值，每次移动石头相当于进行一次位移操作，而你手中的石头则是通过反馈决定下一次移动的位置。

那么接下来正式带各位进入LFSR，由上文可知这是该一个不断反馈的过程，FSR是流密码产生密钥流的一个 重要组成部分，在GF(2)上的一个n级FSR通常由n个二元存储器和一个反馈函数组成，如下图所示：

在反馈移位寄存器（FSR)中，从第n项转移到第n+1项时，通过反馈函数将第1项的值反馈到第n+1项，从而 实现循环的效果。在这个过程中，从第n项开始到第2项的所有存储器的位置都将进行改变，而最后一项的值 会被反馈到第1项。

因此，通过从第n项指向第1项的箭头来表示反馈过程是为了更好地说明存储器值的位移和流动，以及整体循 环的效果。在这个过程中，每个存储器的值会不断地被反馈并移动到下一个位置，最终回到第1项的位置， 从而实现了循环。

请注意，实际上，反馈值不直接影响第一项存储器的值。第一项存储器的值是由初始状态或初始向量决定 的，而不是通过反馈值计算得到的。箭头的指向并不意味着反馈值直接影响第一项存储器的值，而只是简单 地展示存储器值的流动和位移过程。

因此，箭头从第n项指向第1项的表述方式在图解中是为了更好地说明存储器值的位移和流动方向，并不代表 反馈值对第一项的直接影响。

如果这里的反馈函数是线性的，我们则将其称为LFSR，此时该反馈函数可以表示为，其中ci=0或1，⊕表示 异或（模二加)。

我们接下来通过一个例子来更直观的明确LFSR的概念，假设给定一个5级的LFSR，其初始状态（即a1到a5这 5个二元存储器的值)为：

其反馈函数为：

整个过程可以表示为下图所示的形式：

接下来我们来计算该LFSR的输出序列，输出序列的前5位即为我们的初始状态10011，第6位的计算过程如 下:

第7位的计算过程如下：

由此类推，可以得到前31位的计算结果如下： 

1001101001000010101110110001111 

对于一个n级的LFSR来讲，其最大周期为2^n-1，因此对于我们上面的5级LFSR来讲，其最大周期为2^5- 1=31，再后面的输出序列即为前31位的循环。 

通过上面的例子我们可以看到，对于一个LFSR来讲，我们目前主要关心三个部分：初始状态、反馈函数和输出序列，那么对于CTF中考察LFSR的题目来讲也是如此，大多数情况下，我们在CTF中的考察方式都可以概括为：给出反馈函数和输出序列，要求我们反推出初始状态，初始状态即为我们需要提交的flag，另外大多数情况下，初始状态的长度我们也是已知的。 

显然，这个反推并不是一个容易的过程，尤其当反馈函数十分复杂的时候，接下来我们就通过一些比赛当中 出现过的具体的CTF题目，来看一下在比赛当中我们应该如何解决这类问题，由于不同题目之间难度差异会 很大，所以我们先从最简单的题目开始，同样如果有错误的地方请谅解，而我挑选的也是经典比赛题目，网 络上有着详尽的wp，在此我将尽可能的用最通俗的语言和脚本来进行演示。

flag = "flag{xxxxxxxxxxxxxxxx}"assert flag.startswith("flag{")assert flag.endswith("}")assert len(flag)==14def lfsr(R,mask):output = (R << 1) & 0xffffffffi=(R&mask)&0xfffffffflastbit=0while i!=0:lastbit^=(i&1)i=i>>1output^=lastbitreturn (output,lastbit)R=int(flag[5:-1],16)mask = 0b10100100000010000000100010010100f=open("key","w")for i in range(100):tmp=0for j in range(8):(R,out)=lfsr(R,mask)tmp=(tmp << 1)^outf.write(chr(tmp))f.close()

下面我将进行逐行分析该题代码：

分析完毕后，我们可以看出在这道题的情境下，lfsr函数本质上就是一个输入R输出lastbit的函数，虽然我们 现在已经清楚了R是如何经过一系列运算得到lastbit的，但是我们前面的反馈函数都是数学表达式的形式， 我们能否将上述过程整理成一个表达式的形式呢？这就需要我们再进一步进行分析： 

mask只有第3、5、8、12、20、27、30、32这几位为1，其余位均为0。

mask与R做按位与运算得到i，当且仅当R的第3、5、8、12、20、27、30、32这几位中也出现1时，i中才可 能出现1，否则i中将全为0。 

lastbit是由i的最低位向i的最高位依次做异或运算得到的，在这个过程中，所有为0的位我们可以忽略不计 （因为0异或任何数等于任何数本身，不影响最后运算结果），因此lastbit的值仅取决于i中有多少个1：当i中 有奇数个1时，lastbit等于1；当i中有偶数个1时，lastbit等于0。注意，这里的lastbit是一个数字，仅为1或 0。

在代码中，lastbit 变量在循环中通过异或运算逐步计算得到，并最终用于更新output的最后一位。异或运算 符^用于按位异或操作，当两个操作数的对应位不同时，结果为 1；当两个操作数的对应位相同时，结果为 0。在每次循环中，将i的最右端位与i进行异或运算，并将结果存储到lastbit 变量中。由于i 只能取整数值， 每次对其进行右移操作后，最右端位的值只能是 1 或 0。因此，lastbit只能取 1 或 0。当lastbit 为 0 时，则 表示当前的i的最右端位为 0；当lastbit为 1 时，则表示当前的i的最右端位为 1。根据lastbit的值，可以影响 下一次迭代中output的最后一位是保持不变还是进行翻转。因此，lastbit 变量仅能取到 1 或 0，用于在 LFSR 的循环中标识当前的寄存器位状态，并根据其值来调整下一次迭代中的输出位。

当R的第3、5、8、12、20、27、30、32这几位依次异或结果为1时，即R中有奇数个1，因此将导致i中有奇 数个1；当R的第3、5、8、12、20、27、30、32这几位依次异或结果为0时，即R中有偶数个1，因此将导致 i中有偶数个1。因此我们可以建立出联系：lastbit等于R的第3、5、8、12、20、27、30、32这几位依次异或的结果。 

将其写成数学表示式的形式，即为我们要求的反馈函数，反馈函数的形式也说明了初始位数要32位：

那么对于明文key的输出，最后八行代码，对flag，它做了一百次循环，每次循环都产生一个结果，并将这个 结果写到key里面去，所以key里面总共有一百个ASCII字符，共两百个16进制数。题目之所以会出现 100 个 ASCII字符是因为 4 循环次加内嵌的 8 位一次共 32 位循环往后产生的 4 个flag生成的加密字符共 8个 16进制数后，继续用这 4 个加密后的 flag 字符继续新一轮加密，就是多层加密。所以我们取 32 位即可，结果 flag 也是 4 个ASCII字符拆分出的 8 个 16 进制数。

显然，lastbit和R之间满足线性关系，那么接下来我们就可以开始求解了，而且从这里我们可以知道，这种移 位的CTF题目类型要反推32位的初始值要多少位输出序列呢，答案就是32位，因为这种移位的题目是32位为 一个循环，这就和我们前面说的2^32-1的循环不太同了，因为这里是移位操作。

我们想象这样一个场景，当即将输出第32位lastbit时，此时R已经左移了31位，根据上面的数学表达式，我们有：

我们要明确我们是解题，需要的是逆过程，输出值output的不断左移导致右边不断补充由反馈函数生成的 lastbit。当右边补满31位lastbit后，最左边的第32位就是原始标志（flag）的第1位。在这个过程中，由于反馈函数的计算是基于当前的R值，所以前31位的R值是已知的，可以利用这些已知位来计算出第32位的值。

这样我们就可以求出R的第1位，同样的方法，我们可以求出R的第2位

那么解题脚本就是：

原文始发于微信公众号（火炬木攻防实验室）：线性反馈移位寄存器（LFSR）的学习笔记