ctf-Crypto密码学-LFSR线性反馈移位寄存器-先知社区

在打比赛的过程中，已经遇到了好多lfsr（线性反馈移位寄存器）相关的题目，一直没有进行深入的学习，现在用一道经典的题目进行学习。

废话不多说，直接上题目和解题过程。

第一类、给出输出序列和掩码mask，求初始状态（或者说是种子seed）

例题-CISCN2018 oldstreamgame

题目代码

附件key的内容，这个内容是从其他博主的文章中拿来的，真实啥样也不知道≡(▔﹏▔)≡

还有一个，大家就看着用吧

还有一个版本 (我用这个)

这个key的2进制表示是第一个16进制key对每个字符转化为4位的2进制位表示的。最前面的第一个16进制数2转换为2进制后前面的两个0省略了，即本来是0b0010，省略后是0b10，文章后面也会进行解释。

已知的内容都列出来了，下面先分析代码

这是确定flag的格式，flag一共14长，除去flag{}这6个字符，中间应该包含8个字符

这个叫做

lfsr

的函数是实现

线性反馈移位寄存器

中的从

初始状态

根据

反馈函数

得到

输出序列

的过程的代码实现，每一行的解释已经注释了，本质上就是一个

输入R输出output和lastbit的函数

R为flag{}中的内容，即一个8长的16进制表示的字符串，将其转换为了十进制。

mask为定义的一个值，长32位的二进制数，长度对应了flag中的字符的值，8长16进制的内容，每一个字符占4位，8长即32位。

mask的二进制形式的值也确定了

线性反馈移位寄存器

中的

反馈函数

的形式（为什么确定，这里给出一段其他师傅写的解释）

这段话最重要的是根据

代码分析

得出

数学联系

，即：

个人理解，也就是得到了反馈函数的表达式，即

f(a32,a32,...a2,a1)=a32⊕a30⊕a27⊕a20⊕a12⊕a8⊕a5⊕a3=lastbit

到这里，以上代码就基本实现了

线性反馈移位寄存器

最重要的部分，后面的就是

循环使用

该函数，生成

输出序列

，然后将输出的内容转换成字符写到一个文件中

到这里，代码基本分析完成，下面列出已知的内容

mask即为得到

反馈函数

的值，key即为文件中的内容转换为二进制的内容，即为

输出序列

，但是这个key只有798位，按道理应该有800位，因为外循环100次，内循环8次，lfsr一共生成了800个二进制数，这是因为python在输出二进制数值时，会将最前面的0忽略，所以在前面添加2个0

目前已知

反馈函数

，

输出序列

，因为R的值为8个16进制数，转换为二进制即为32位，而mask也为32位，则可以根据key的

前32个二进制位

还原出

初始状态R

具体的原理如图，图为手画推导，以8位初始状态R=10010001和mask=10101000为例

先给出

正向

得出

输出序列

的推导，有一些草稿抱歉( ╯□╰ )

以上为

正向

根据

初始状态

和

反馈函数

得到

输出序列

的细节

下面给出

逆向推导

原始R的图片，字迹潦草抱歉了啊(;´༎ຶД༎ຶ`)

以上为

逆向推导

得出原始R的过程，字迹有些曲折，给大家两张其他师傅的图洗洗眼睛(￣y▽,￣)╭ (￣y▽,￣)╭ ，但是只有两张，给出我自己的推导过程，也是因为梳理整体思路

这张图表示了我们的题目中的内容，即生成序列的第32位是根据R的第1位，也就是从右往左的第1位和前面生成的31位lastbit组合生成的

同理，这是

输出序列

的第31位的生成过程

然后我们根据

逆向推导

的具体细节，就可以写出代码，然后得出原始的R了

解题脚本

代码具体的解释已经写到了注释中

最后得到flag，8位16进制的数

第二类、给出初始状态和输出序列，求掩码mask

可以使用B-M算法，对于算法的介绍：

https://ctf-wiki.org/crypto/streamcipher/fsr/lfsr/

但是使用B-M的前提是知道2n长的输出序列。B-M的具体使用还不懂

但这里使用矩阵的逆运算，是一种笨一点的方法，但胜在好理解

例题题目：

这题是某位师傅问我的，具体哪里来的不晓得，感觉挺不同就学了一下

可以看到第一次输出的R，即为

初始状态

，也就是种子seed，

第二次输出的R，是128个

输出序列

，看到这里只给出了n长的序列，所以不能使用B-M

而flag的即为mask，我们要反求出mask

解题脚本1：来自

https://www.cnblogs.com/naby/p/18487794

Naby师傅太强了┗|｀O′|┛ 嗷~~

这里给出一张GPT分析的过程

还没有手推过，先看看，后面手推一遍我再补充

解题脚本2：来自

https://blog.csdn.net/weixin_52640415/article/details/143099594

基本逻辑与脚本1相同，不过更简练。

一些简单的测试

简单介绍，lfsr，即

线性反馈移位寄存器

，简单来说就是根据

初始状态

和

反馈函数

得到一个

输出序列。

具体的实现过程这里就不给出了，可以查看其他师傅的文章了解学习。

测试一：正向测试

这里的正向测试，也就是手推正向过程之前使用代码进行了测试

最后得到的 l 与手推得到的 l 一致，都是11001010

测试二：循环测试

在查阅关于lfsr的资料的过程中，在其他师傅的文章中看到这样一句话

对于一个

n级

的LFSR来讲，其最大周期为

2^n-1

，因此对于我们上面的

5级

LFSR来讲，其最大周期为

2^5-1=31

，再后面的输出序列即为前31位的

循环

。

于是对于LFSR的

循环

进行了探索，发现只有当

反馈多项式

是一个本原多项式时，才会达到最大周期

2^n-1

，那么什么是

本原多项式

呢(⊙o⊙)？，哈哈，这里就不多解释了，因为我也还没特别清楚啊－O－

只是简单验证了一下在4级LFSR上，使用一个4阶的本原多项式x^4+x+1（在模2的有限域中），最大周期是否为2^4-1=15

对输出序列进行了验证，确实是以15长为循环，如下

当使用的

反馈多项式

不是

本原多项式

时，

输出序列

的循环大小就达不到最大循环了，但是也是循环的。

最后暂时完结，有需要再来补充啊ヾ(^▽^*)))

参考文章：

LFSR | DexterJie'Blog

CTF中的LFSR考点(一)_ctf lfsr-CSDN博客

深入分析CTF中的LFSR类题目（一）-安全客 - 安全资讯平台

线性反馈移位寄存器 - LFSR - CTF Wiki

[CISCN2018]oldstreamgame （考点: LFSR）-CSDN博客

攻防世界：streamgame1（考点：LFSR）_攻防世界简单的lfsr-CSDN博客