流密码

线性反馈移位寄存器

拜访harry0597

LFSR

即线性反馈移位寄存器

  • 作用：
    生成长伪随机序列，（二进制）

  • 存储元件（触发器）：
    可以存数据的就是

  • 反馈路径：
    计算移位寄存器触发器的XOR和，并传递

  • 度
    LFSR由若干时钟存储元件（触发器）组成，存储器元件个数就是LFSR的度

简单LFSR

当m=3

  1. 假设初始状态为：S2=1, S1=0, S0=0 ；最右位的FF0往外输出

  2. 在每一个时间单位下，内部状态位向右移动一位

    从左往右看

    • 原先S2的值（1）给到 FF1
    • 原先S1的值（0）给到 FF0
    • 原先S0的值（0）和 原先S1的值（0）异或后（得到0）给到 FF2
    • 原先S0的值（0）输出，LFSR得到数据 0

  3. 多次移位后，得到数据

    Clk FF2 FF1 FF0=si
    0 1 0 0
    1 0 1 0
    2 1 0 1
    3 1 1 0
    4 1 1 1
    5 0 1 1
    6 0 0 1
    7 1 0 0
    8 0 1 0

其中 Si 就是第i次输出的数据，i从0开始

而这里的S3其实就是第2步中FF2获得的值，右移了几次所输出的

不难归纳出输出位的计算公式为：
$$
S_{i+3}\equiv S_{i+1}+S_i \pmod 2
$$
其中，i = 0, 1, 2…

LFSR通用模式

度为m

  • 反馈系数（多乘一个系数P可以这么理解）

    某条反馈路径是否活跃取决于反馈系数P0, P1, …, Pm-1

    • 若Pi = 1，此反馈是活跃的
    • 若Pi = 0，对应触发器的输出将不会被反馈

比简单LFSR多了一条路

归纳直接截个图：

还有一些拓展可以的harry0597师傅博客上看