反馈移位寄存器

type

Post

status

Published

date

Jul 22, 2022

slug

LFSR

summary

LFSR

在GF(2)上的一个n级FSR通常由n个二元存储器和一个反馈函数组成

当反馈函数是线性的我们则将其称为LFSR

反馈函数可表示为

举个栗子

给定一个5级的LFSR，其初始状态为

反馈函数

过程图

输出序列前5位已知10011

第六位则为

接下来

以此推类

对于一个n级的LFSR来讲，其最大周期为

因此对于我们上面的5级LFSR来讲，其最大周期为

从上面可以看出，LFSR主要关心三个部分，初始状态，反馈函数和输出序列

一般遇到题目都是已知反馈函数和输出序列，求初始状态

题目

[第七章 CTF之CRYPTO章]LFSR


seed = 0x00000000 # you need to solve this
flag = 'n1book{seed}'

state = seed
mask = 0b10000000000000000000000001010111

def lfsr():
    global state, mask
    output = state & 1
    now = state & mask
    new = 0
    while now:
        new ^= now & 1
        now >>= 1
    state = (new << 31) | (state >> 1)
    return output


for i in range(32):
    lfsr()

print '%x' % state # 155a796b

当最后一次lfsr()时

而s2, s3, s5, s7, s32, new已知

exp


state = seed
mask = 0b10000000000000000000000001010111

sts=0x155a796b
key=bin(sts)[2:].zfill(32)
print(key)

mask = '10000000000000000000000001010111'
key='00010101010110100111100101101011'
R = ''
for i in range(32):
    output = key[1:32]+'?'
    out = int(key[0]) ^ int(output[-32]) ^ int(output[-2]) ^ int(output[-3]) ^ int(output[-5]) ^ int(
        output[-7])
    R += str(out)
    key = key[1:32]+ str(out)
print('flag{' + hex(eval('0b' + R)) + '}')

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

exp


mask = '10100100000010000000100010010100'
key = '00100000111111011110111011111000'

tmp=key

R = ''
for i in range(32):
    output = '?' + key[:31]
    ans = int(key[-1])^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),'x')
flag = "flag{" + R + "}"
print (flag)