序言

LFSR（线形反馈移位寄存器）早已变成现如今CTF中密码算法方位题目的一个普遍考试点了，在2020年上半年度的一些中国赛和国际赛上，也出現了十分多的这种题目，可是在其中绝大部分题目现阶段也没有writeups（或是writeups并沒有做crypt *** ysis，只是根据工程爆破的方式处理，这类构思只适用一部分相近上年强网杯出現的几个十分基本的LFSR类题目合理，针对绝大部分国际赛上的题目不但是沒有一切实际效果的，也是沒有一切实际意义的，仅有真实把握了LFSR的密码算法基本原理，才有可能在国际赛上处理一道高得分的LFSR类题目），在网上对于这类考试点的深入分析也很少，因而下面我将根据2~3篇文章内容，对这种知识要点开展一个详尽的剖析。

LFSR介绍

在详细介绍LFSR以前，大家先对它的所属有一个大概的掌握，LFSR是归属于FSR（反馈移位寄存器）的一种，除开LFSR以外，还包含NFSR（离散系统反馈移位寄存器）。

FSR是流登陆密码造成密钥流的一个关键构成部分，在GF(2)上的一个n级FSR一般 由n个二元储存器和一个反馈函数构成，如下图所显示：

假如这儿的反馈函数是线形的，大家则将其称之为LFSR，这时该反馈函数能够表明为：

在其中ci=0或1，⊕表明异或（模二加）。

大家下面根据一个事例来更形象化的确立LFSR的定义，假定给出一个5级的LFSR，其初始状态（即a1到a5这五个二元储存器的值）为：

其反馈函数为：

全部全过程能够表明为下面的图所显示的方式：

下面大家来测算该LFSR的輸出序列，輸出序列的前5位即是大家的初始状态10011，第六位的测算全过程以下:

第7位的测算全过程以下:

从而推导，能够获得前31位的数值以下：

1001101001000010101110110001111

针对一个n级的LFSR而言，其较大 周期时间为2^n-1，因而针对大家上边的5级LFSR而言，其较大 周期时间为2^5-1=31，再后边的輸出序列即是前31位的循环系统。

根据上边的事例我们可以见到，针对一个LFSR而言，大家现阶段关键关注三个一部分：初始状态、反馈函数和輸出序列，那麼针对CTF中调查LFSR的题目而言也是这般，大部分状况下，我们在CTF中的调查 *** 都能够归纳为：得出反馈函数和輸出序列，规定大家反发布初始状态，初始状态即是大家必须递交的flag，此外大部分状况下，初始状态的长短大家也是已经知道的。

显而易见，这一推算并并不是一个非常容易的全过程，特别是在当反馈函数十分复杂的情况下，下面大家就根据一些赛事之中出現过的实际的CTF题目，看来一下在赛事之中大家应当如何解决这类难题，因为不一样题目中间难度系数差别会非常大，因此 大家先从非常简单的题目逐渐，我将尽量的用最通俗化的語言和脚本 *** 来开展演试，在后面会慢慢提高题目的难度系数，另外填补相对的解析几何专业知识。

CTF练习题演试

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

剖析一下大家的已经知道标准：

已经知道初始状态的长短为4个十六进制数，即32位系统，初始状态的值即我们要去求的flag。

已经知道反馈函数，只不过是这儿的反馈函数是编码的方式，大家必须获取出它的数学课关系式。

已经知道輸出序列。

那麼大家的每日任务很确立，便是根据剖析lfsr函数，梳理成数学课关系式的方式求得就可以，下面大家一行一行的来剖析这一函数：

#接受2个主要参数，R是32位系统的初始状态(即flag)，mask是32位系统的掩码，因为mask已经知道，因此 大家就立即把他作为一个参量就可以。