LFSR

在介绍LFSR（线性反馈移位寄存器）之前，我们先对它的归属有一个大致的了解，LFSR是属于FSR（反馈移位寄存器）的一种，除了LFSR之外，还包括NFSR（非线性反馈移位寄存器）。

基本介绍

下面在有限域FpF_{p}下讨论n级LFSR：

反馈函数

ai+n=∑j=1ncjai+n−ja_{i+n} = \sum_{j=1}^{n} c_j a_{i+n-j}

既然反馈函数是一个线性变换，我们可以得知这个线性变换为

[ai+1,ai+2,…,ai+n]=[ai,ai+1,…,ai+n−1][00⋯0cn10⋯0cn−101⋯0cn−2⋮⋮⋱⋮⋮00⋯1c1][ai+1,ai+2,…,ai+n]=[a0,a1,…,an−1][00⋯0cn10⋯0cn−101⋯0cn−2⋮⋮⋱⋮⋮00⋯1c1]i+1\begin{array}{rcl} [a_{i+1}, a_{i+2}, \ldots, a_{i+n}] & = & [a_i, a_{i+1}, \ldots, a_{i+n-1}] \begin{bmatrix} 0 & 0 & \cdots & 0 & c_n \\ 1 & 0 & \cdots & 0 & c_{n-1} \\ 0 & 1 & \cdots & 0 & c_{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_1 \end{bmatrix} \\[10pt] \phantom{[a_{i+1}, a_{i+2}, \ldots, a_{i+n}]} & = & [a_0, a_1, \ldots, a_{n-1}] \begin{bmatrix} 0 & 0 & \cdots & 0 & c_n \\ 1 & 0 & \cdots & 0 & c_{n-1} \\ 0 & 1 & \cdots & 0 & c_{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_1 \end{bmatrix}^{i+1} \end{array}

特征多项式

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

f(x)=xn−∑i=1ncixn−if(x) = x^n - \sum_{i=1}^n c_i x^{n - i}

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

f‾(x)=xnf(1x)=1−∑i=1ncixi\overline{f}(x) = x^n f\left(\frac{1}{x}\right) = 1 - \sum_{i=1}^n c_i x^i

p=2的特殊情况

当p=2时，只有{0，1}两种情况，此时用异或代替原来的模p加法运算。
其中ci∈{0,1}c_{i} \in \{0,1\}即表示取或不取
反馈函数变成：

f(a1,a2,⋯ ,an)=cna1⊕cn−1a2⊕⋯⊕c1anf(a_{1}, a_{2}, \cdots, a_{n}) = c_{n} a_{1} \oplus c_{n-1} a_{2} \oplus \cdots \oplus c_{1} a_{n}

进一步得到特征多项式：

f(x)=xn−∑i=1ncixn−i=xn+c1xn−1+c2xn−2+⋯+cn−1x+cnf(x) = x^n - \sum_{i=1}^n c_i x^{n - i}=x^{n}+c_{1}x^{n-1}+c_{2}x^{n-2}+\cdots+c_{n-1}x+c_{n}

这里为什么减法变成加法(?)：在模2意义下加减是一样的。
下面根据F2F_{2}模拟LFSR工作
图片描述
如图我们可以知道，这是一个5级的LFSR，由5个二元存储器和一个反馈函数组成。
反馈函数为：

f(a1,a2,a3,a4,a5)=a1⊕a4f(a_{1}, a_{2}, a_{3},a_{4}, a_{5}) = a_{1} \oplus a_{4}

规定初始状态为(a1,a2,a3,a4,a5)=(1,0,0,1,1)(a_{1}, a_{2}, a_{3},a_{4}, a_{5})=(1,0,0,1,1)
第一次工作时输出a1=1a_{1}=1，根据反馈函数f计算得到0。此时更新(a1,a2,a3,a4,a5)=(0,0,1,1,0)(a_{1}, a_{2}, a_{3},a_{4}, a_{5})=(0,0,1,1,0)
第一次工作时输出a1=0a_{1}=0，根据反馈函数f计算得到1。此时更新(a1,a2,a3,a4,a5)=(0,1,1,0,1)(a_{1}, a_{2}, a_{3},a_{4}, a_{5})=(0,1,1,0,1)
重复上述过程31次得到长度为31的序列：1001101001000010101110110001111
为什么写到31(?)因为如果继续下去会得到重复的序列也就是说序列的周期为31。

周期

对于有限域FpF_{p}下的n级LFSR可以知道最大周期为pn−1p^{n}-1。我们把取到最大周期的LFSR的特征多项式叫做本原多项式。
为什么是pn−1p^{n}-1(?)因为n位p进制数最多能表示pnp^{n}个数字，但是这里要舍去全为0的情况，如果初始情况全取0，那么将得到全是0的序列，这是没有意义的。故n级LFSR最多能够存储pn−1p^{n}-1的信息量。
这里要引入多项式阶的概念：假设f(x)f(x)是FpF_{p}下的多项式，使得f(x)∣(xk−1)f(x) \mid (x^{k}-1)成立的最小的k叫做f(x)f(x)的阶，这里的阶往往也可以叫做周期。
下面考虑p=2。
对于上面的举例可以写出特征多项式为：

f(x)=x5+x2+1f(x)=x^{5}+x^{2}+1

而

f(x)∣x31−1f(x) \mid x^{31}-1

可以得到上面举例的LFSR的周期是31，符合我们遍历的结果。也可以看出这个周期是5级LFSR的最大周期，故特征多项式是本原的。

本原多项式

设 f(x)f(x) 是定义在有限域 GF(p)\mathrm{GF}(p) 上的一个不可约多项式，次数为 nn，即：

f(x)=xn−c1xn−1−c2xn−2−⋯−cnf(x) = x^n - c_1 x^{n-1} - c_2 x^{n-2} - \cdots - c_n

若 f(x)f(x) 的一个根 α\alpha 在扩域 GF(pn)\mathrm{GF}(p^n) 中是该域的一个本原元，即：

αpn−1=1且αk≠1对所有 1≤k<pn−1\alpha^{p^n - 1} = 1 \quad \text{且} \quad \alpha^k \ne 1 \quad \text{对所有 } 1 \le k < p^n - 1

那么称 f(x)f(x) 为 GF(p)\mathrm{GF}(p) 上的一个本原多项式。

换句话说：f(x)f(x) 是本原的当且仅当它是不可约的，并且它的一个根能够生成 GF(pn)\mathrm{GF}(p^n) 中所有非零元素。

总结

左移型

(a0,a1,a2,⋯ ,an−1)⋅[00⋯0c010⋯0c101⋯0c2⋮⋮⋱⋮⋮00⋯1cn−1]=(a1,a2,a3,⋯ ,an)(a_0,a_1,a_2,\cdots,a_{n-1}) \cdot \begin{bmatrix} 0 & 0 & \cdots & 0 & c_0 \\ 1 & 0 & \cdots & 0 & c_{1} \\ 0 & 1 & \cdots & 0 & c_{2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_{n-1} \end{bmatrix} =(a_1,a_2,a_3,\cdots,a_n)

[a0a1⋯an−1a1a2⋯an⋮⋮⋮an−1an−2⋯a2n−2]⋅[c0c1⋮cn−1]=[anan+1⋮a2n−1]\begin{bmatrix} a_{0} & a_{1} & \cdots & a_{n-1} \\ a_1 & a_{2} & \cdots & a_{n} \\ \vdots & \vdots & & \vdots \\ a_{n-1} & a_{n-2} & \cdots & a_{2n-2} \end{bmatrix} \cdot \begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_{n-1} \end{bmatrix}= \begin{bmatrix} a_n \\ a_{n+1} \\ \vdots \\ a_{2n-1} \end{bmatrix}

对应脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def recover_c(output,n,p=2):
    M=[]
    for i in range(n):
        M.append(output[i:i+n])
    M=matrix(GF(p),M)
    vec=vector(GF(p),output[n:2*n])
    c=M.solve_right(vec)
    return list(c)
def solve_lfsr_left(output,n,d,p=2):
    c_list=recover_c(output,n)
    a_list=output[:n]
    vec=vector(GF(p),a_list)
    M=matrix(GF(p),n,n)
    for i in range(n):
        M[i,n-1]=c_list[i]
    for i in range(n-1):
        M[i+1,i]=1
    res=vec*M^(-d)
    print(long_to_bytes(int(''.join(str(x) for x in res),2)))

右移型

(an−1,an−2,,⋯ ,a1,a0)⋅[cn−11⋯00cn−20⋯00⋮⋮⋱⋮⋮c10⋯01c00⋯00]=(an,an−1,⋯ ,a2,a1)(a_{n-1},a_{n-2},,\cdots,a_1,a_{0}) \cdot \begin{bmatrix} c_{n-1} & 1 & \cdots & 0 & 0 \\ c_{n-2} & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ c_{1} & 0 & \cdots & 0 & 1 \\ c_0 & 0 & \cdots & 0 & 0 \end{bmatrix} =(a_n,a_{n-1},\cdots,a_2,a_1)

[an−1an−2⋯a0anan−1⋯a1⋮⋮⋮a2n−2a2n−3⋯an−1]⋅[cn−1cn−2⋮c0]=[anan+1⋮a2n−1]mod  2\begin{bmatrix} a_{n-1} & a_{n-2} & \cdots & a_0 \\ a_n & a_{n-1} & \cdots & a_1 \\ \vdots & \vdots & & \vdots \\ a_{2n-2} & a_{2n-3} & \cdots & a_{n-1} \end{bmatrix} \cdot \begin{bmatrix} c_{n-1} \\ c_{n-2} \\ \vdots \\ c_{0} \end{bmatrix}= \begin{bmatrix} a_n \\ a_{n+1} \\ \vdots \\ a_{2n-1} \end{bmatrix} \mod 2

对应脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def recover_c(output,n,p=2):
    M=[]
    for i in range(n):
        M.append(output[i:i+n:][::-1])
    M=matrix(GF(p),M)
    vec=vector(GF(p),output[n:2*n])
    c=M.solve_right(vec)
    return list(c)
def solve_lfsr_right(output,n,d,p=2):
    c_list=recover_c(output,n)
    a_list=output[:n][::-1]
    vec=vector(GF(p),a_list)
    M=matrix(GF(p),n,n)
    for i in range(n):
        M[i,0]=c_list[i]
    for i in range(n-1):
        M[i,i+1]=1
    res=vec*M^(-d)
    print(long_to_bytes(int(''.join(str(x) for x in res),2)))

例题

moectf2024-EzMatrix

题目

Can you break my LFSR?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from secret import FLAG,secrets,SECERT_T
assert len(secrets) == 16
assert FLAG == b'moectf{' + secrets + b'}'
assert len(SECERT_T) <= 127
class LFSR:
    def __init__(self):
        self._s = list(map(int,list("{:0128b}".format(bytes_to_long(secrets)))))
        for _ in range(8*len(secrets)):
            self.clock()
    def clock(self):
        b = self._s[0]
        c = 0
        for t in SECERT_T:c ^= self._s[t]
        self._s = self._s[1:] + [c]
        return b
    def stream(self, length):
        return [self.clock() for _ in range(length)]
c = LFSR()
stream = c.stream(256)
print("".join(map(str,stream))[:-5])
# 11111110011011010000110110100011110110110101111000101011001010110011110011000011110001101011001100000011011101110000111001100111011100010111001100111101010011000110110101011101100001010101011011101000110001111110100000011110010011010010100100000000110

分析

题目构造了在F2F_{2}下的128级LFSR并通过secrets构造出128位的初始序列，而SECERT_T则是cic_i列表。
题目的难点在于输出的序列是经过128次操作之后的序列，经过了一层混淆，另外一点在于隐藏了后5bit位的数字，所以需要简单的爆破枚举。
下面说说如何还原，根据前面的知识我们可以知道：

[ai+1,ai+2,…,ai+n]=[ai,ai+1,…,ai+n−1][00⋯0cn10⋯0cn−101⋯0cn−2⋮⋮⋱⋮⋮00⋯1c1][ai+1,ai+2,…,ai+n]=[a0,a1,…,an−1][00⋯0cn10⋯0cn−101⋯0cn−2⋮⋮⋱⋮⋮00⋯1c1]i+1\begin{array}{rcl} [a_{i+1}, a_{i+2}, \ldots, a_{i+n}] & = & [a_i, a_{i+1}, \ldots, a_{i+n-1}] \begin{bmatrix} 0 & 0 & \cdots & 0 & c_n \\ 1 & 0 & \cdots & 0 & c_{n-1} \\ 0 & 1 & \cdots & 0 & c_{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_1 \end{bmatrix} \\[10pt] \phantom{[a_{i+1}, a_{i+2}, \ldots, a_{i+n}]} & = & [a_0, a_1, \ldots, a_{n-1}] \begin{bmatrix} 0 & 0 & \cdots & 0 & c_n \\ 1 & 0 & \cdots & 0 & c_{n-1} \\ 0 & 1 & \cdots & 0 & c_{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_1 \end{bmatrix}^{i+1} \end{array}

但是我们这里并不知道cic_{i}所以我们应该先还原cic_{i},思路如下：
线性反馈移位寄存器（LFSR）产生的输出序列满足如下线性关系：

at=c1at−1⊕c2at−2⊕⋯⊕cnat−na_t = c_1 a_{t-1} \oplus c_2 a_{t-2} \oplus \cdots \oplus c_n a_{t-n}

其中，ata_t 表示第 tt 个输出比特，c1,c2,…,cn∈F2c_1, c_2, \dots, c_n \in \mathbb{F}_2 是反馈系数，⊕\oplus 表示在二元有限域 F2\mathbb{F}_2 上的加法（异或）。

假设已知长度为 2n2n 的输出序列 (a0,a1,…,a2n−1)(a_0, a_1, \dots, a_{2n-1})，可以构造如下的线性方程组：

[an−1an−2⋯a0anan−1⋯a1⋮⋮⋮a2n−2a2n−3⋯an−1]⋅[c1c2⋮cn]=[anan+1⋮a2n−1]mod  2\begin{bmatrix} a_{n-1} & a_{n-2} & \cdots & a_0 \\ a_n & a_{n-1} & \cdots & a_1 \\ \vdots & \vdots & & \vdots \\ a_{2n-2} & a_{2n-3} & \cdots & a_{n-1} \end{bmatrix} \cdot \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix}= \begin{bmatrix} a_n \\ a_{n+1} \\ \vdots \\ a_{2n-1} \end{bmatrix} \mod 2

即矩阵形式为：

M⋅c⃗=v⃗mod  2M \cdot \vec{c} = \vec{v} \mod 2

通过求解这个方程组，可以还原 LFSR 的反馈系数 c⃗=(c1,c2,…,cn)\vec{c} = (c_1, c_2, \dots, c_n)，进而确定特征多项式。

脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Util.number import *
for i in range(32):
    output = "11111110011011010000110110100011110110110101111000101011001010110011110011000011110001101011001100000011011101110000111001100111011100010111001100111101010011000110110101011101100001010101011011101000110001111110100000011110010011010010100100000000110"
    brutebits = bin(i)[2:].zfill(5)
    output += brutebits
    F = GF(2)
    n = 128
    V = VectorSpace(F,n)
    vec = V(list(map(int, list(output[n:]))))
    M = []
    for i in range(n-1,2*n-1):
        m = []
        for j in range(n):
            m.append(output[i-j])
        M.append(m)
    M = Matrix(F,M)
    try:
        sol = M.solve_right(vec)
    except ValueError:
        continue
    poly = list(sol)
    B = Matrix(F,n,n)
    for i in range(n):
        B[i,n-1] = poly[n-1-i]
    for i in range(n-1):
        B[i+1,i] = 1
    try:
        B_inv = B**(-1)
        t = V(list(map(int,list(output[:n]))))
        print(long_to_bytes(int("".join(map(str,t*B_inv**(n))),2)))
    except ZeroDivisionError:
        continue
#b'e4sy_lin3ar_sys!'

ciscn2018-oldstreamgame

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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()
#key=20FDEEF8A4C9F4083F331DA8238AE5ED083DF0CB0E7A83355696345DF44D7C186C1F459BCE135F1DB6C76775D5DCBAB7A783E48A203C19CA25C22F60AE62B37DE8E40578E3A7787EB429730D95C9E1944288EB3E2E747D8216A4785507A137B413CD690C

分析

题目构造了在F2F_{2}下的32级LFSR，flag里面是长度为8的十六进制数，折算也是32bit。
再来分析lfsr的实现过程：

1
2
output = (R << 1) & 0xffffffff
i=(R&mask)&0xffffffff

这里首先把R像左移1位，然后&0xffffffff把首位去掉，得到末尾是0的output。关键是这里的i的构造过程，R和mask都是32位，后面&0xffffffff其实没什么用处。在F2F_{2}的有限域下，&的作用相当于按位乘法，得到

(i1,i2,⋯ ,i32)=(r1a1,r2a2,⋯ ,r32a32)(i_{1},i_{2},\cdots,i_{32})=(r_{1}a_{1},r_{2}a_{2},\cdots,r_{32}a_{32}) 

1
2
3
4
5
lastbit=0
while i!=0:
    lastbit^=(i&1)
    i=i>>1
output^=lastbit

while循环内的过程就是模拟r1a1⊕r2a2⊕⋯⊕r32a32r_{1}a_{1} \oplus r_{2}a_{2} \oplus \cdots \oplus r_{32}a_{32}。最后在把结果加到前面的末尾是0的output上就是一个完整的LFSR过程。

1
2
3
4
5
6
7
8
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()

这里执行了100*8次LFSR过程，其中每8次得到一个8位字符然后打印在文件里，过程重复100次。但是我们解决这道题目肯定不需要这么多次，只需要前32次就够我们得到一个序列然后还原得到明文即可。这里的key是网上摘的别人的数据，不清楚为什么不是ASCII字符串而是十六进制字符，神秘。
总的来说这道题目的LFSR的阅读难度很大，但是解密其实很简单。

脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
mask="10100100000010000000100010010100"
key='00100000111111011110111011111000'
F=GF(2)
V = VectorSpace(F,32)
vec = V(list(map(int, list(key))))
mask=list(map(int, list(mask)))
M=matrix(F,32,32)
for i in range(32):
    M[i,31]=mask[i]
for i in range(31):
    M[i+1,i]=1
M_inv=M**(-1)
vec=vec*M_inv**32
vec=[1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1]
res=0
for i in vec:
    res=res*2+i
print(hex(res))
#flag{926201d7}