CTF竞赛密码学 之 LFSR

目录

概述:

解决LFSR问题

Part(1)  2018 强网杯 Streamgame1

第一种方法

第二种方法

第三种方法

Part(1)  2018 强网杯 Streamgame2

Part(3) [CISCN2018]oldstreamgame

Part(4) [De1CTF2019]Babylfsr考点：B-M 算法

  概述:

线性反馈移位寄存器（LFSR）归属于移位寄存器（FSR）,除此之外还有非线性移位寄存器（NFSR）。移位寄存器是流密码产生密钥流的一个主要组成部分。

上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数组成，如下图所示。

移位寄存器的三要素：

• 初始状态：由用户确定

• 反馈函数：是n元布尔函数，即函数的自变量和因变量只取0和1这两个可能值

• 输出序列

如果反馈函数是线性的，那么我们称其为 LFSR,如下图所示：

LFSR的输出序列{ }满足:

•  
•  

• .....

• (i = 1,2,3,...)

举例：

下面是一个5级的线性反馈移位寄存器，其初始状态为

反馈函数为：，(i = 1,2,...) 可以得到输出序列为：

1001101001000010101110110001111 100110…

周期为31。

对于 n 级线性反馈移位寄存器，最长周期为（排除全零）。达到最长周期的序列一般称为 m 序列

本文涉及相关实验:CTFCrypto练习之替换密码 （本实验主要介绍了CTFCrypto练习之替换密码，通过本实验的学习，你能够了解CTF竞赛中的密码学题型，掌握凯撒密码破解方法，学会基于频率的替换密码破解方法。）

解决LFSR问题 Part(1)  2018 强网杯 Streamgame1

考点：已知反馈函数，输出序列，求逆推出初始状态

题目：

from flag import flag
assert flag.startswith("flag{")
assert flag.endswith("}")
# 作用：判断字符串是否以指定字符 开头或结尾
assert len(flag)==25

def lfsr(R,mask):
    output = (R 1
    output^=lastbit              #将输出值写入 output的后面
    return (output,lastbit)

R=int(flag[5:-1],2)  #flag为二进制数据
mask    =   0b1010011000100011100

f=open("key","ab")   #以二进制追加模式打开
for i in range(12):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp