LFSR

badmonkey的博客

最开始了解到LFSR的时候是在学习MT19937伪随机数生成器的时候，当时也是初步了解。也没有用代码实现过，最近做了几道相关的题，在这里记录一下。

原理

证明过程不太会，简单说一下大致的原理。LFSR是用于生成随机数序列的，每一个LFSR都是有级数的，级数决定了潜在的循环周期（即随机数序列的周期）。对于每个LFSR还需要有一个线性函数，用于生成随机数。比如

这里的线性函数必须是二元域上的n阶不可约多项式，线性函数的作用有点类似掩码的功能，对上面的线性函数相当于mask 1011（x的系数非零则为1，不考虑常数项，从左到右次数依次递减）

对上面的例子，选取一个4位的seed用于生成随机数，假设seed为1010

step1

线性函数充当掩码的功能选取seed的对应位，即 seed & mask => 1010 & 1011 选取了第1，3，4位分别为 1，1，0 ，则有 1 xor 1 xor 0 => 0

step2

将上一步得到的结果和seed后三位进行拼接，所以新的随机数就是0100

同理下一个随机数为1000，若经过k次迭代后生成了和seed一样的的数，则称k为为循环周期，显然周期越长为好，MT19937的周期就很长可以达到2^19937-1。

题目

CISCN oldstreamgame

# coding=utf-8flag = "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()

相信看过原理之后应该可以理解代码，关键代码为

for i in range(100):tmp=0for j in range(8):(R,out)=lfsr(R,mask)tmp=(tmp << 1)^outf.write(chr(tmp))

初始的时候tmp为0，经过8次变化得到的新的tmp，将其转成字符写到文件中去。来看一下文件中的第一个字符的二进制形式00100000，其实仔细想想只有当每次的out为1的时候才能改变tmp的值，下一次tmp又会左移一位，所以8位的tmp对应8次lfsr的out。

也就是所根据文件的二进制可以知道每一次lfsr的out，而每一次的out其实就是对应生成的随机数的最低位，而且随机数的生成是每次左移+out构成的！

因此文件的前32位二进制数，是由seed生成的一个随机数。而且是第32个生成的随机数，而且我们能根据第32个随机数猜测第31个随机数，因为第31个随机数的低31位是第32个随机数的高31位。猜测32次后可以得到原始seed，即flag，exp脚本如下：

cipher = open('key','rb').read()bin_out = ''.join([bin(ord(i))[2:].zfill(8) for i in cipher])R = int(bin_out[0:32],2)mask = 0b10100100000010000000100010010100def lfsr(R,mask):output = (R << 1) & 0xffffffffi=(R&mask)&0xfffffffflastbit=0while i!=0:lastbit^=(i&1)i=i>>1output^=lastbitreturn (output,lastbit)def decry():cur = bin_out[0:32]res = ''for i in range(32):if lfsr(int('0'+cur[0:-1],2),mask)[0] == int(cur,2):res += '0'cur = '0'+cur[0:-1]else:res += '1'cur = '1' + cur[0:-1]return int(res[::-1],2)r = decry()print hex(r)[2:].strip('L')

AFCTF TinyLFSR

# coding=utf-8import sysfrom binascii import unhexlifyif(len(sys.argv)<4):print("Usage: python Encrypt.py keyfile plaintext ciphername")exit(1)def lfsr(R, mask):output = (R << 1) & 0xffffffffffffffffi=(R&mask)&0xfffffffffffffffflastbit=0while i!=0:lastbit^=(i&1)i=i>>1output^=lastbitreturn (output,lastbit)R = 0key = ""with open(sys.argv[1],"r") as f:key = f.read()R = int(key,16)f.closemask = 0b1101100000000000000000000000000000000000000000000000000000000000a = ''.join([chr(int(b, 16)) for b in [key[i:i+2] for i in range(0, len(key), 2)]])f=open(sys.argv[2],"r")ff = open(sys.argv[3],"wb")s = f.read()f.close()lent = len(s)for i in range(0, len(a)):ff.write((ord(s[i])^ord(a[i])).to_bytes(1, byteorder='big'))for i in range(len(a), lent):tmp=0for j in range(8):(R,out)=lfsr(R,mask)tmp=(tmp << 1)^outff.write((tmp^ord(s[i])).to_bytes(1, byteorder='big'))ff.close()

考点貌似不在LFSR,只是加密的时候用到了，seed就是key的int值，key也可以通过爆破来找，exp脚本如下：

# coding=utf-8import binasciipt = open('Plain.txt', 'rb').read()et = open('cipher.txt', 'rb').read()fl = open('flag_encode.txt', 'rb').read()def lfsr(R, mask):output = (R << 1) & 0xffffffffffffffffi = (R & mask) & 0xfffffffffffffffflastbit = 0while i != 0:lastbit ^= (i & 1)i = i >> 1output ^= lastbitreturn (output, lastbit)def find_part():tmp = ''# 被密钥异或的公共部分for i, j in zip(et, fl):tmp += chr(i ^ j)tmp = bytes(tmp, encoding='utf-8')ans = ''# 异或明文恢复部分明文for i, j in zip(pt, tmp):ans += chr(i ^ j)return ansdef str_to_hexStr(string):str_bin = string.encode('utf-8')return binascii.hexlify(str_bin).decode('utf-8')def guess_key(size):key = ''for i,j in zip(pt[0:size],et[0:size]):key += chr(i ^ j)key = str_to_hexStr(key)return int(key, 16)def find_key():mask = 0b1101100000000000000000000000000000000000000000000000000000000000t = open('Plain.txt','r').read()for i in range(1,len(pt)):key = guess_key(i)cur = t[0:i]for j in range(i, len(pt)):tmp = 0for k in range(8):(key, out) = lfsr(key, mask)tmp = (tmp << 1) ^ outcur += chr(et[j] ^ tmp)# print(cur)if cur == t:return keyreturn -1def decry():flag = find_part()R = find_key()mask = 0b1101100000000000000000000000000000000000000000000000000000000000for i in range(104, len(fl)):tmp = 0for j in range(8):(R, out) = lfsr(R, mask)tmp = (tmp << 1) ^ outflag += chr(fl[i]^tmp)print(flag)decry()

强网杯

先挖个坑。。5道题。。😶 😶