​ LFSR 属于 FSR(反馈移位寄存器)的一种,除了 LFSR 外,还有 NFSR (非线性反馈移位寄存器);FSR 是流密码产生密钥流的一个重要组成部分,在 GF (2) 上的一个 n 级 FSR 通常由 n 个二元存储器一个反馈函数组成,如:img 如果这里的反馈函数是线性的,就是LFSR

反馈函数可以表示为:ci=0 或 1,⊕表示异或。

f(a1,a2,,an)=(cna1)(cn1a2)...(c1an)f(a_1,a_2,…,a_n)=(c_na_1)\oplus (c_{n-1}a_2)\oplus ...(c_1a_n)

5 级 LFSR 例子:初始状态(a1 到 a5 五个二元存储器的值)和 反馈函数设为

(a1,a2,a3,a4,a5)=(1,0,0,1,1)f(a1,a2,a3,a4,a5)=a4a1(a_1,a_2,a_3,a_4,a_5)=(1,0,0,1,1)\\f(a_1,a_2,a_3,a_4,a_5)=a_4\oplus a_1

过程可以表示为下图所示的形式:

jpg 所以前五位是 10011,第 6 位输出如下:

a6=a4q1=11=07,a7=a5a2=10=1a_6=a_4\oplus q_1=1\oplus 1=0\\7,a_7=a_5\oplus a_2=1\oplus 0=1

前 31 位为:1001101001000010101110110001111

而对于一个 n 级的 lfsr 来说,最大周期为 2**n-1, 因此上述周期为 31 后面就都是循环的了

因此,我们需要关心的部分为:初始状态反馈函数输出序列

大多数情况下,需要我们观察反馈函数和、输出序列,反推出初始状态。

反馈函数一般为 $$a_i+n}=\sum(n_{j=1)a_ja_{i+n-j}$$

可得出特征多项式: $$f (x)=xn-\sumn}_{i=1}c_ix({n-i)$$

同时,定义其互反多项式为: $$\bar f (x)=xnf(\frac{1}{x})=1-\sum^n_{i=1}c_ixi$$

# Characteristic Polynomial & Generating Function :

已知某个 n 级线性反馈移位寄存器的特征多项式,序列对应的生成函数为 $$A (x)=\fracp(x)}{f(x)},in \ it,p(x)=\sum(n_{i=1)(c_n-i}x({n-i)\sum^i_j=1}a_jx({j-1))$$

# Sequence Period & Generating Function :

序列的周期为其生成函数的既约真分式的分母的周期。对于 n 级线性反馈移位寄存器,最长周期为 2**n-1. 达到最长周期的序列一般称为 m 序列

# Special Natures:

  • 将两个序列累加得到新的序列的周期是两个序列的周期的和
  • 序列是 n 级 m 序列,当且仅当序列的极小多项式是 n 次本原多项式

# E.G. :

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

分析已知条件:

已知初始状态长度为 32 位;已知反馈函数;已知输出序列

#已知 R 是 32 位初始状态,mask 是 32 位掩码已知
def lfsr(R,mask):
    output=(R<<1)&0xffffffff#把 R 左移一位后低 32 位,最后一位是 0
    i=(mask&R)&0xffffffff#R 和 mask 按位与运算,同时也是取低 32 位 // 个人认为没有必要取低 32 位?,因为它本身就是 32 位的数
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1#从 i 的最低位向最高位做异或运算,运算结果赋值给 lastbit
    output^=lastbit#把 output 最后一位变为 lastbit
    return (output,lastbit)#返回 output 和 lastbit

进一步分析:

mask 只有 3,5,8,12,20,27,30,32 位为 1,其他都是 0;mask 与 R 按位与运算得到 i,当且仅当 R 的 3,5,8,12,20,27,30,32 位为 1,i 中才可能出现 1,否则 i 中为 0;lastbit 是由 i 的最低位向最高位依次做异或运算得到的,过程中,所有为 0 的位忽略不计,因此 lastbit 的值仅取决于 i 中含有多少个 1:奇数个 1,lastbit=1 否则为 0;当 R 的 3,5,8,12,20,27,30,32 位这几位依次异或结果为 1 时,即 R 中有奇数个 1,因此将导致 i 中有奇数个 1;因此 —>lastbit 等于 R 的第 3、5、8、12、20、27、30、32 这几位依次异或的结果

lastbit=R3R5R8R12R20R27R30R32lastbit=R_3\oplus R_5\oplus R_8\oplus R_{12}\oplus R_{20}\oplus R_{27}\oplus R_{30}\oplus R_{32}

这就是我们所需要的线性关系,就可以得出

img

因此可以推出 R 的全部 32 位:

mask =  '10100100000010000000100010010100'
key  =  '00100000111111011110111011111000'
tmp  =  key
R    =  ''
for i in range(32):
    output='?'+key[:31]
    ans = int(key[31])^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)
#flag{926201d7}

# 分组码

分组码是对每段长度为 k 的信息,以一定的规则增加 r=n-k 个校验元,组成长为 n 的序列,我们称这个序列为码字

请我喝[茶]~( ̄▽ ̄)~*

De3B4to 微信支付

微信支付

De3B4to 支付宝

支付宝