流密码综述

流密码又称为序列密码，它是密码学的一个重要部分。在CTF的密码学中，流密码一般都以以下的几种情形出现：

• 线性同余发生器（LCG）

• MT19937（python随机数库的预测）

• 线性反馈移位寄存器（LFSR）和非线性反馈移位寄存器（NFSR）

• RC4

  其中，重点和难点应该是在LFSR和它所衍生出的一系列算法。下面总结一下流密码。

  线性同余发生器（LCG）

  形如$X_{n+1}\equiv aX_n+b\ (mod\ m)$（$X_0为已知种子$），若$gcd(a,m)=1$，则LCG可以取得最大周期（遍历所有可能结果）。

  一般题型

  对于LCG的一般情况下的攻击可分为两类，一类是a,b未知，另一类是a,b,m都未知。

  对于前者，我们只需要知道连续的三个生成值，即可通过解模线性方程组求解。

  对于后者，已知连续的五个生成值，我们可以通过构造模等比数列，再通过求gcd的方法求得m的值，接下来的过程就很好办了。

  参考链接：攻击线性同余生成器(LCG) (zeroyu.xyz)

  创新题型

  在Van1sh神的blog里面，有一篇介绍HNP（Hidden Number Probem）的文章,题目给出了a,b,m的值，生成了20个128位的随机数，但是只给出了每个数的高64位，然后题目的重点是恢复原来的seed。关于HNP问题的内容仍在学习中，等学明白了再将这一块更新。先给出V神文章链接：

  浅尝lattice之HNP

  python随机数——MT19937

  CTF一般随机数攻击方法：爆破或者预测

  预测python随机数的库：randcrack

  可在泄露624个连续随机数后进行预测

  线性反馈移位寄存器（LFSR）

  这一块一般题型都不难，但是水比较深，涉及到很多代数知识和分析方法如Galois理论还有GF（2）域上的多项式代数以及相关攻击、快速相关攻击、B-M算法，这段时间把这些都学会。

  待更新。

  非线性反馈移位寄存器（NFSR）

  待更新。

  RC4

  待更新。