LFSR（线性反馈移位寄存器）

发表于 更新于 分类于

生成序列

LFSR是一种流密码，加密方式

加密方式如下 \[ mask=(c_0,c_1,\dots,c_m)\\ a_n=c_ma_{n-1}+c_{m-1}a_{n-2}+\dots+c_0a_{n-m-1}\ mod\ 2 \] 用矩阵表示有 \[ \begin{pmatrix} &1\\\\ &&1\\\\ &&&\ddots&\\\\ &&&&1\\\\ c_0&c_{1}&\dots&&c_m \end{pmatrix} \begin{pmatrix} a_{n-m-1}\\\\ a_{n-m}\\\\ \vdots\\\\ a_{n-1} \end{pmatrix}= \begin{pmatrix} a_{n-m}\\\\ a_{n-m+1}\\\\ \vdots\\\\ a_{n} \end{pmatrix} \]

可以看出，右边的矩阵是一般线性群 \(G=GL_{m+1}(Z_2)\) 的一个元素，群 \(G\) 的阶为 \(\prod_{i=0}^{m+1}(2^{m+1}-2^i)\) ，所以该 LFSR 在经过最多与阶相等的周期后就会重复序列（矩阵非群的生成元可以有更短的周期）

逆推序列

注意到，该矩阵是满秩矩阵，所以一定会有逆，从而回推序列 \[ \begin{pmatrix} &1\\\\ &&1\\\\ &&&\ddots&\\\\ &&&&1\\\\ c_0&c_{1}&\dots&&c_m \end{pmatrix}^{-1} \begin{pmatrix} a_{n-m}\\\\ a_{n-m+1}\\\\ \vdots\\\\ a_{n} \end{pmatrix} = \begin{pmatrix} a_{n-m-1}\\\\ a_{n-m}\\\\ \vdots\\\\ a_{n-1} \end{pmatrix} \]

计算掩码

我们可以通过序列连续2(m+1)个元素计算出mask掩码 \[ \begin{pmatrix} a_n&a_{n+1}&\dots&a_{n+m}\\\\ a_{n+1}&a_{n+2}&\dots&a_{n+m+1}\\\\ \vdots&&\ddots&\vdots\\\\ a_{n+m}&a_{n+m+1}&\dots&a_{n+2m} \end{pmatrix} \begin{pmatrix} c_{0}\\\\ c_{1}\\\\ \vdots\\\\ c_{m} \end{pmatrix} = \begin{pmatrix} a_{n+m+1}\\\\ a_{n+m+2}\\\\ \vdots\\\\ a_{n+2m+1} \end{pmatrix} \] 解上面方程得到掩码 \(mask=(c_0,c_1,\dots,c_m)\)

sage代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def lfsr(R,mask,n):
    output = (R << 1) & (2**n-1)
    i=(R&mask)&(2**n-1)
    lastbit=0
    while i!=0:
        lastbit^^=(i&1)
        i=i>>1
    output^^=lastbit
    return (output,lastbit)

def lfsr_matrix(R,mask,n):
    F=GF(2)
    mask=[int(i) for i in bin(mask)[2:]]
    mask_bits=len(mask)
    id=matrix.identity(31)
    M=matrix(F,mask_bits-1,1).augment(id).stack(vector(F,mask))
    R=[int(i) for i in bin(R)[2:].rjust(mask_bits,'0')]
    R=vector(F,R)
    r=M^n*R
    r=''.join([str(i) for i in r])
    return r
    

def lfsr_inv(R,mask,n):
    key=R
    for i in range(n):
        l=key&1
        key=key>>1
        key=key|l<<(n-1)
        R,lastbit=lfsr(key,mask,n)
        key=key^^l<<(n-1)|lastbit<<(n-1)
    return key

def lfsr_matrix_inv(R,mask,n):
    F=GF(2)
    mask=[int(i) for i in bin(mask)[2:]]
    mask_bits=len(mask)
    id=matrix.identity(31)
    M=matrix(F,mask_bits-1,1).augment(id).stack(vector(F,mask))
    R=[int(i) for i in bin(R)[2:].rjust(mask_bits,'0')]
    R=vector(F,R)
    r=M^-n*R
    r=''.join([str(i) for i in r])
    return r

def BM(s, N):
    F = GF(2)
    A = [[0]*N for i in range(N)]
    B = [0]*N
    for j in range(N):
        for i in range(N):
            k =(s >> (2*N-1-(i+j)) & 1)
            A[j][i] = k
    for j in range(N):
        k =(s >> (2*N-1-(j+N)) & 1)
        B[j]=k
    A,B=Matrix(F, A),vector(F, B)
    if A.rank()<A.augment(B).rank():
            return 0,False
    M=A.solve_right(B)
    MM=[int(i) for i in M]
    M=MM[0]
    for i in range(1,256):
            M=M<<1
            M=M|MM[i]
    return M,True