线性反馈移位寄存器

线性反馈移位寄存器

在正式介绍线性反馈移位寄存器(LFSR)之前，先来看一个小故事，相传在遥远的古代，住着4个奇怪的人。

四个奇怪的人

上图表示了他们居住的相对的位置，上面说到他们是奇怪的人，这里来简单说一下，他们每天出门的人有一个简单的规律：

1. 李四明天是否出门取决于张三昨天是否出门
2. 王五明天是否出门取决于李四昨天有没有出门
3. 赵六明天是否出门取决于王五有没有出门
4. 张三明天是否出门呢? 可不是取决于赵六有没有出门，而是有王五和赵六共同决定的，如果王五和赵六其中有且只有一个人昨天出门了，张三才出门，也就是说只有王五昨天出门而赵六不出门，或者，赵六昨天出门而王五昨天没出门，张三才出门。

于是，咱们假设王五昨天出门了，来看一下接下来几天这四个人的出门情况。

出门情况

简单解释一下前面几天的出门情况，后面类似就不挨个去描述一遍了。

• 第一天: 这个是基本的假设，只有王五出门，这个就是假设，没有原因，任性
• 第二天: 由于昨天王五出门了，所以第二天赵六出门，并且根据第四条, 王五出门并且赵六没出门，因此张三这一天出门
• 第三天: 由于张三昨天出门了，因此今天李四出门，而由于赵六昨天出门了，并且王五昨天没出门，因此张三今天依然出门
• 第四天: 由于张三昨天出门了，因此李四今天出门，而由于李四昨天也出门了，所以王五今天出门

好了，后面几天读者自行推导一下吧，这里我就不描述了，规则是一致的。

接下来，我们来看一下，赵六这几天的出门情况。

watermark

好了，故事讲完了，在这里问一下各位读者，有没有发现赵六出门有什么规律呢?

这个问题，等我讲完这一篇文章之后再做解答，大家也可以暂停思考一下。

反馈移位寄存器(FSR)

FSR的构造比较简单，包含一个指定大小的寄存器，里面有一些比特构成，以及一个更新反馈函数(f), 每次执行，通过f函数并产生一个新的比特。假设FSR的初始状态是, 它的下一个状态是由左移一个比特之后，最后侧空位有f()补充得到，这里左移出去的那一个比特就是输出的比特，通用公式如下:

这么描述，可能读者不太理解，来看一个具体的例子吧，假设咱们有一个初始的4bit的寄存器, 然后f函数就定义为每个bit进行异或，也就是, 然后下一个输出状态也就是1000, 下一个周期, 接下来的状态输出为0001, 然后重复上述的步骤，整体过程如下:

1. 1100
2. 1000
3. 0001
4. 0011
5. 0110
6. 1100

我们发现，经过5次迭代更新，这个状态又回到了最原始的状态，这就接下来，这个也就会按照5为周期来重复这个操作。

FRS图示

这里FSR就基本介绍完了，接下来介绍一下本篇文章的主角LFSR(线性反馈移位寄存器)了。

线性反馈移位寄存器(LFSR)

线性反馈移位寄存器是具有线性反馈函数的FSR, 也就是说，反馈函数仅仅是当前状态的某些比特位异或，上面介绍的那个FSR实际上就是一个线性反馈移位寄存器，通过数学可以证明，LFSR是会有周期的，影响LFSR周期的关键因素是那些比特进行了异或，这里采用线性反馈移位寄存器的好处是可以通过数学的方法去挑选特殊的比特位置进行异或，使得寄存器的周期达到最大也就是。

你们看这个寄存器只有0/1这两种状态的长度组合，它像不像之前我们提到的有限域GF(), 因此我们可以用域当中的多项式来表示反馈函数，假设最右边比特的位置记为1， 最左边比特的位置记为n, 将位置信息可以转换为多项式其中项存在当且仅当该比特参与反馈函数的计算，如果要想使得LFSR出现它的最大周期，这要求这个多项式是本原的，在这里不过多介绍本原多项式的概念了，有兴趣的读者可以自行查阅相关资料。

好了，简单介绍了LFSR的概念，我们来回到文章刚开始所介绍的小故事，实际上这4个人实际上构成了一个4位的LFSR。

文章开始的例子

这里参与异或的实际上也就是后面两个比特，然后到了现在，就可以回答在文章故事结束之后提出的问题了，赵六的出行规律是什么，这里上图这个反馈寄存器的周期实际上是15, 因此在15以内，实际上赵六出行是没有规律的，哈哈。

总结

本文简单介绍了一下线性反馈移位寄存器的相关知识，由于这个产生的随机比特是具有周期性的，因此在密码学当中并不安全，输出序列和寄存器状态之间可以建立简单的方程，从而利用线性代数的知识求解，但是如果多个不同长度的线性反馈移位寄存器组合或者在里面添加非线性反馈移位寄存器，那么这个安全性就会达到要求，不少密码体制也是这么设计的。

个人水平有限，讲解过程当中如果有哪些疏漏或者错误的地方，还请各位读者指正。