跳转至

线性反馈移位寄存器 - LFSR

介绍

线性反馈移位寄存器的反馈函数一般如下

a_{i+n}=\sum\limits_{j=1}^{n}c_ja_{i+n-j}

其中,c_j 均在某个有限域 F_q 中。

既然线性空间是一个线性变换,我们可以得知这个线性变换为

\begin{align*} &\left[ a_{i+1},a_{i+2},a_{i+3}, ...,a_{i+n} \right]\\\\=&\left[ a_{i},a_{i+1},a_{i+2}, ...,a_{i+n-1} \right]\left[ \begin{matrix} 0 & 0 & \cdots & 0 & c_n \\ 1 & 0 & \cdots & 0 & c_{n-1} \\ 0 & 1 & \cdots & 0 & c_{n-2}\\\vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & c_1 \\ \end{matrix} \right]\\\\=&\left[ a_{0},a_{1},a_{2}, ...,a_{n-1} \right]\left[ \begin{matrix} 0 & 0 & \cdots & 0 & c_n \\ 1 & 0 & \cdots & 0 & c_{n-1} \\ 0 & 1 & \cdots & 0 & c_{n-2}\\\vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & c_1 \\ \end{matrix} \right]^{i+1} \end{align*}

进而,我们可以求得其特征多项式为

f(x)=x^n-\sum\limits_{i=1}^{n}c_ix^{n-i}

同时,我们定义其互反多项式为

\overline f(x)=x^nf(\frac{1}{x})=1-\sum\limits_{i=1}^{n}c_ix^{i}

我们也称互反多项式为线性反馈移位寄存器的联结多项式。

这里有一些定理需要我们记一下,感兴趣的可以自行推导。

特征多项式与生成函数

已知某个 n 级线性反馈移位寄存器的特征多项式,那么该序列对应的生成函数为

A(x)=\frac{p(x)}{\overline f(x)}

其中,p(x)=\sum\limits_{i=1}^{n}(c_{n-i}x^{n-i}\sum\limits_{j=1}^{i}a_jx^{j-1})。可以看出 p(x) 完全由初始状态和反馈函数的系数决定。

序列周期与生成函数

序列的的周期为其生成函数的既约真分式的分母的周期。

对于 n 级线性反馈移位寄存器,最长周期为 2^{n}-1(排除全零)。达到最长周期的序列一般称为 m 序列。

特殊性质

  • 将两个序列累加得到新的序列的周期为这两个序列的周期的和。
  • 序列是 n 级 m 序列,当且仅当序列的极小多项式是 n 次本原多项式。

B-M 算法

一般来说,我们可以从两种角度来考虑 LFSR

  • 密钥生成角度,一般我们希望使用级数尽可能低的 LFSR 来生成周期大,随机性好的序列。
  • 密码分析角度,给定一个长度为 n 的序列 a,如何构造一个级数尽可能小的 LFSR 来生成它。其实这就是 B-M 算法的来源。

一般来说,我们定义一个序列的线性复杂度如下

  • 若 s 为一个全零序列,则线性复杂度为0。
  • 若没有 LFSR 能生成 s,则线性复杂度为无穷。
  • 否则,s 的线性复杂度为生成 L(s) 的最小级的 LFSR。

BM 算法的要求我们需要知道长度为 2n 的序列。其复杂度

  • 时间复杂度:O(n^2) 次比特操作
  • 空间复杂度:O(n) 比特。

关于 BM 算法的细节,后续添加,目前处于学习过程中。

但是其实如果我们知道了长度为 2n 的序列,我们也可以一种比较笨的方法来获取原先的序列。不妨假设已知的序列为a_1,...,a_{2n},我们可以令

S_1=(a_1,...,a_n)

S_2=(a_2,...,a_{n+1})

....

S_{n+1}=(a_{n+1},...,a_{2n})

那么我们可以构造矩阵 X=(S_1,...,S_n),那么

S_{n+1}=(c_n,...,c_1)X

所以

(c_n,...,c_1)=S_{n+1}X^{-1}

进而我们也就知道了 LFSR 的反馈表达式,进而我们就可以推出初始化种子。

2018 强网杯 streamgame1

简单看一下题目

from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==25

def lfsr(R,mask):
    output = (R << 1) & 0xffffff
    i=(R&mask)&0xffffff
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)



R=int(flag[5:-1],2)
mask    =   0b1010011000100011100

f=open("key","ab")
for i in range(12):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()

可以发现,flag 的长度为25-5-1=19,所以可以暴力枚举。结果

2018-强网杯-streamgame1 git:(master) ✗ python exp.py
12
0b1110101100001101011

因此 flag 为 flag{1110101100001101011}。

2018 CISCN 初赛 oldstreamgame

简单看一下题目

flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14

def lfsr(R,mask):
    output = (R << 1) & 0xffffffff
    i=(R&mask)&0xffffffff
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)

R=int(flag[5:-1],16)
mask = 0b10100100000010000000100010010100

f=open("key","w")
for i in range(100):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()

程序很简单,仍然是一个 LFSR,但是初态是 32 比特位,当然,我们也可以选择爆破,但是这里不选择爆破。

这里给出两种做法。

第一种做法,程序输出的第 32 个比特是由程序输出的前 31 个比特和初始种子的第 1 个比特来决定的,因此我们可以知道初始种子的第一个比特,进而可以知道初始种子的第 2 个比特,依次类推。代码如下

mask = 0b10100100000010000000100010010100
b = ''
N = 32
with open('key', 'rb') as f:
    b = f.read()
key = ''
for i in range(N / 8):
    t = ord(b[i])
    for j in xrange(7, -1, -1):
        key += str(t >> j & 1)
idx = 0
ans = ""
key = key[31] + key[:32]
while idx < 32:
    tmp = 0
    for i in range(32):
        if mask >> i & 1:
            tmp ^= int(key[31 - i])
    ans = str(tmp) + ans
    idx += 1
    key = key[31] + str(tmp) + key[1:31]
num = int(ans, 2)
print hex(num)

运行

2018-CISCN-start-oldstreamgame git:(master) ✗ python exp1.py
0x926201d7

第二种做法,我们可以考虑一下矩阵转换的过程,如果进行了 32 次线性变换,那么就可以得到输出流前 32 个比特。而其实,我们只需要前 32 个比特就可以恢复初始状态了。

mask = 0b10100100000010000000100010010100

N = 32
F = GF(2)

b = ''
with open('key', 'rb') as f:
    b = f.read()

R = [vector(F, N) for i in range(N)]
for i in range(N):
    R[i][N - 1] = mask >> (31 - i) & 1
for i in range(N - 1):
    R[i + 1][i] = 1
M = Matrix(F, R)
M = M ^ N

vec = vector(F, N)
row = 0
for i in range(N / 8):
    t = ord(b[i])
    for j in xrange(7, -1, -1):
        vec[row] = t >> j & 1
        row += 1
print rank(M)
num = int(''.join(map(str, list(M.solve_left(vec)))), 2)
print hex(num)

运行脚本

2018-CISCN-start-oldstreamgame git:(master) ✗ sage exp.sage
32
0x926201d7

从而 flag 为 flag{926201d7}。

还有一种做法是 TokyoWesterns 的,可以参考对应的文件夹的文件。

题目

参考文献

  • 密码学讲义,李超,屈龙江编著