参考文献：

ctf竞赛密码学之lfsr

ctfwiki crpto lfsr（线性反馈移位寄存器)

简单认识一下lfsr

lfsr可以直接看作下面这个公式，对于我来说还是公式比较好理解，网上很多题解直接对于lfsr函数进行分析，还是没有公式来的舒服，更好理解，我是理解了公式之后才看懂他们在做什么

下面结合具体例题来解释lfsr的逆推方法

强网杯 streamgame1

from flag import flagassert flag.startswith("flag{")assert flag.endswith("}")assert len(flag)==25def lfsr(R,mask):output = (R << 1) & 0xffffffi=(R&mask)&0xfffffflastbit=0while i!=0:lastbit^=(i&1)i=i>>1output^=lastbitreturn (output,lastbit)R=int(flag[5:-1],2)mask = 0b1010011000100011100f=open("key","ab")for i in range(12):tmp=0for j in range(8):(R,out)=lfsr(R,mask)tmp=(tmp << 1)^outf.write(chr(tmp))f.close()

已知flag是19位得二进制，可以直接爆破

这道题貌似和lfsr没什么关系。。。？

decrypt:

mask = 0b1010011000100011100def lfsr(R,mask):output = (R << 1) & 0xffffffi=(R&mask)&0xfffffflastbit=0while i!=0:lastbit^=(i&1)i=i>>1output^=lastbitreturn (output,lastbit)key=[85,56,247,66,193,13,178,199,237,224,36,58]for R in range(2**19):judge=0for i in range(12):tmp=0for j in range(8):(R,out)=lfsr(R,mask)tmp=(tmp << 1)^outif key[i]!=tmp:judge=1breakif judge==0:print(bin(R)[2:])break

当然这个题可以有另一种更好的做法，对于lfsr可以有更深刻的认识：

key就是flag传入lfsr之后不断生成的序列，也就是我们知道初始值后面的输出序列要逆推初始值

key = 0101010100111000111(只需要取前19位就可)

我们假设我们已经知道了19位，那么我们想要用lfsr求下一位，公式参考上面的公式,得到

a20=a19^a17^a14^a13^a9^a5^a4^a3

刚刚好a19在这个表里，我们可以让a19为唯一未知量来求a19

那么我们把1个未知量放到这个式子里，让其他量已知，我们发现，当flag经过lfsr运算了18次时候符合条件。每一次运算结果都会保存到key里，也就是flag经过的18次lfsr运算都储存到了key里，此时flag还剩下1位，下一次lfsr运算他将被当作a19参加运算，得到a20也就是key[-1]=1

突然明了了，这个时候就只有a19不知道了：

1=$a_{19}$^(R[-3])^(R[-4])^(R[-5])^(R[-9])^(R[-13])^(R[-14])^(R[-17])

a19也就是flag的最后一位求出来了，用这个方法继续往下求直到flag全部求出来

mask = '1010011000100011100' #顺序 c_n,c_n-1,。。。,c_1key = '0101010100111000111'R = ''for i in range(19):output='x'+key[:18]#我们就是要求这个xout = int(key[-1])^int(output[-3])^int(output[-4])^int(output[-5])^int(output[-9])^int(output[-13])^int(output[-14])^int(output[-17])R+=str(out)key=str(out)+key[:18]print('flag{'+R[::-1]+'}')

强网杯 streamgame2

源码:

from flag import flagassert flag.startswith("flag{")assert flag.endswith("}")assert len(flag)==27def lfsr(R,mask):output = (R << 1) & 0xffffffi=(R&mask)&0xfffffflastbit=0while i!=0:lastbit^=(i&1)i=i>>1output^=lastbitreturn (output,lastbit)R=int(flag[5:-1],2)mask=0x100002f=open("key","ab")for i in range(12):tmp=0for j in range(8):(R,out)=lfsr(R,mask)tmp=(tmp << 1)^outf.write(chr(tmp))f.close()

弱弱的问一句，这个streamgame1有什么区别吗？

key = '101100101110100100001'mask= '100000000000000000010'R = ''for i in range(21):output='?'+key[:20]ans=int(key[-1])^int(output[-2])R+=str(ans)key=str(ans)+key[:20]print(R[::-1])

再来看 CISCN 初赛 oldstreamgame

原来ctf会遇到这么多一样的题吗！就跟考原题是的

flag = "flag{xxxxxxxxxxxxxxxx}"assert flag.startswith("flag{")assert flag.endswith("}")assert len(flag)==14def lfsr(R,mask):output = (R << 1) & 0xffffffffi=(R&mask)&0xfffffffflastbit=0while i!=0:lastbit^=(i&1)i=i>>1output^=lastbitreturn (output,lastbit)R=int(flag[5:-1],16)mask = 0b10100100000010000000100010010100f=open("key","w")for i in range(100):tmp=0for j in range(8):(R,out)=lfsr(R,mask)tmp=(tmp << 1)^outf.write(chr(tmp))f.close()

和上面的同理，貌似也是能爆破的，有兴趣的小伙伴可以尝试一下

decrypt：

import os,sysos.chdir(sys.path[0])from Crypto.Util.number import*key = '00100000111111011110111011111000'#只需要用前32位mask = '10100100000010000000100010010100'R = ''tem = keyfor i in range(32):output = '?' + key[:31]ans = int(tem[-1-i]) ^ int(output[-3]) ^ int(output[-5]) ^ int(output[-8]) ^ int(output[-12]) ^ int(output[-20]) ^ int(output[-27]) ^ int(output[-30])R += str(ans)key = str(ans) + key[:31]# R = format(int(R[::-1],2),'z')R = str(hex(int(R[::-1],2))[2:])print(R)

wiki上还给出了一中用矩阵来解的方法，等我学习一下后续补充