LFSR基本原理和简单题型

2022-01-26

序列密码最重要的就是以某种规律产生大量密钥，而产生密钥流最重要的部件之一是反馈移位寄存器。其中反馈移位寄存器又分为线性反馈移位寄存器和非线性反馈移位寄存器，本篇主要介绍线性反馈移位寄存器（LFSR）的原理和基本题型。

一.LFSR的优点

1.LFSR适合硬件实现，代价小，收益大

2.它们能产生大的周期序列

3.它们能产生好的统计特性的序列

4.它们的结构能够应用代数方法进行分析

二.n级反馈移位寄存器的结构和原理

LFSR的结构如图所示：

其工作原理比较简单，移位寄存器用来存储数据，并受到系统时钟脉冲驱动。每一存储器称为移位存储器的一级，移位存储器中的个数称为移位存储器的级数。在某一时刻，所有寄存器的内容构成该反馈移位寄存器的一个状态，共有2^n种可能的状态，每一个状态对应于域GF（2）上的一个n维向量，用（a1，a2，…，an-1，an）表示，其中ai是当前时刻第i级存储器的内容。

在一个时间单位内，第i级寄存器ai的内容被传递给第i-1级寄存器ai-1（i=2，3，…），并根据寄存器当前的状态计算f(a1，a2，…，an)作为寄存器an下一个时刻的内容，其中f称为反馈函数，该函数是个n元布尔函数。

若f（a1，a2，…，an）是a1，a2等的线性函数，则这样的移位寄存器称为线性反馈移位寄存器，否则位非线性反馈移位寄存器。

若f为线性移位寄存器，则可以表示为：

f（a1，a2，…，an）=Cn .a1+Cn-1 .a2+…+C1 .an

其中，Ci为0或者1，+为模2加法（异或运算），并且要满足Ci不全为0。举个例子如下：

三.基本题型举例

[CISCN2018]oldstreamgame

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

def lfsr(R,mask):
    output = (R << 1) & 0xffffffff #R进行左移，说明R即为初始状态
    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()

#输出（16进制序列）#20FDEEF8A4C9F4083F331DA8238AE5ED083DF0CB0E7A83355696345DF44D7C186C1F459BCE135F1DB6C76775D5DCBAB7A783E48A203C19CA25C22F60AE62B37DE8E40578E3A7787EB429730D95C9E1944288EB3E2E747D8216A4785507A137B413CD690C

LFSR类型的题目首先要确定移位周期，其实也就是寄存器的个数。题目中的R = int(flag[5:-1],16)，其长度为14-6 = 8 （个16进制数），说明寄存器的个数为8*4 = 32。

下一步要搞清楚移位寄存器的线性函数表达式，所以需要研究lfsr函数：

output = (R << 1) & 0xffffffff：R（32位）循环左移一位

i=(R&mask)&0xffffffff：i为R与mask与运算的结果，由于mask大部分为0，所以i可能为1的位数只能为mask非0的位数，即mask从右向左第3、5、8、12、20、27、30、32位

lastbit^=(i&1)：lastbit实际上等于i的每一位相异或，由于与0异或值不变，所以只考虑i中的1的数量，若1的数量为偶数，lastbit为0，若为奇数，则为1。又由于i可能为1的位数为以上几位，所以lastbit = 3^5^8^12^20^27^30^32（线性表达式）。

再分析输出流：

	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()

每8位lastbit组成一个字节，即一个字符，循环一百次，获得100个字符。

解题：综合以上分析，可以发现欲获得初始R的序列，需要找到R左移31次以后的状态，此时R的最低位在反馈寄存器的最高位，其他位都是由f连续生成的31位lastbit，那么可以通过异或的可逆性，获得R的最低位，依次可以获得R的倒数第二位…直到获得R的完整序列。

exp：

c = "00100000111111011110111011111000"
s = ''
for i in range(32):

    m = str(int(c[-4])^int(c[-6])^int(c[-9])^int(c[-13])^int(c[-21])^int(c[-28])^int(c[-31])^int(c[-1])) #这里需要仔细思考
    s = s + m
    l = s[::-1]
    c = l + '00100000111111011110111011111000'[0:31-i]


s = s[::-1]
print(s)
d = int(s,2)
print('flag{'+str(hex(d))[2:]+'}')
#flag{926201d7}