本节作为流密码第一篇科普性文章，首先介绍一下什么是流密码。
在介绍流密码之前，我们先引入OTP（One-time Password，一次性密码）这样一个概念。
所谓一次性密码，是一次加密使用一次密钥，这次加密过程中使用的密钥不能在下一次加密中继续使用，密钥是一次性的，使用一次当即作废。
例如：
我们想加密 abcdefg 这串字符。想要加密所有明文，就要用与明文等长的密钥来加密。比如利用密钥1234567加密，1代表在字母表的顺序向后移动一位，2代表移动2位，等等，和凯撒的原理相同，只不过这里使用了多个密钥。
但是，我们会遇到这样一个问题，我们需要用和明文长度相同的密钥来去加密明文，然后需要将密文与密钥一同发送给对方，对方才能用密钥来解密密文，在这个过程中，密钥是不可泄露的，因此我们又需要一个十分安全的方式来护送密钥。
那么，既然密钥长度和明文一样，也就是护送的难度一样大，如果真的有一种方法可以安全的护送密钥，为什么不直接用这种安全的方式来护送明文呢？
显然，OTP在实际操作中效率并不高，我们也许可以用一个比较短的密钥来加密明文呢？
例如，我们选择123作为密钥，加密的时候，可以重复使用密钥，例如1231231作为密钥来加密abcdefg。但是，这样的重复列太容易被破解了，我们需要让123生成的7位密钥看似杂乱无章一点，无序一点，比如1239782，看起来像随机数一样，这样既减小了护送密钥的难度，也能提高其加密的安全性。
流密码，应运而生。
LCG既属于伪随机数发生器，也属于流密码。因为他的生成既达到了随机数生成的要求，又能按照需求将一定长度的内容扩展到需要的长度。
LCG原理：
S
n
+
1
=
a
∗
S
n
+
b
(
m
o
d
m
)
S_{n+1}=a*S_n+b~(mod~m)\\
Sn+1=a∗Sn+b (mod m)
其中，m表示模量、a表示乘数、b表示增量。
同时要求
g
c
d
(
m
,
a
)
=
1
gcd(m,a)=1
gcd(m,a)=1
周期
T
=
O
r
d
m
(
a
)
T=Ordm(a)
T=Ordm(a)
为了让周期尽可能的大，我们需要让a尽可能的是m的一个原根，这时周期最大，为
ϕ
(
m
)
\phi{(m)}
ϕ(m)。
有关原根的理解可以参考下面这篇博客：
https://blog.csdn.net/qq_44109982/article/details/111324293
当我们知道了由LCG生成的连续三个随机数时，就可以破解LCG
S
n
=
a
∗
S
n
−
1
+
b
(
m
o
d
m
)
S
n
+
1
=
a
∗
S
n
+
b
(
m
o
d
m
)
S_n=a*S_{n-1}+b~(mod~m)\\ S_{n+1}=a*S_n+b ~(mod~m)
Sn=a∗Sn−1+b (mod m)Sn+1=a∗Sn+b (mod m)
下式减上式，得到：
S
n
+
1
−
S
n
=
a
∗
(
S
n
−
S
n
−
1
)
(
m
o
d
m
)
S_{n+1}-S_n=a*(S_n-S_{n-1})~(mod~m)
Sn+1−Sn=a∗(Sn−Sn−1) (mod m)
只有a已知，我们可以求出来a，带入上面的式子求出b，那么我们只要知道一个随机数，就可以知道它的下一个随机数是多少了。
当然，结合到数学问题，再ctf中还会存在多种解题姿势。
例如，给出给出四个连续的已知随机数：
T
n
=
S
n
+
1
−
S
n
(
m
o
d
m
)
T
n
+
1
=
S
n
+
2
−
S
n
+
1
(
m
o
d
m
)
=
a
(
S
n
+
1
−
S
n
)
(
m
o
d
m
)
=
a
T
n
(
m
o
d
m
)
T
n
+
2
=
S
n
+
3
−
S
n
+
2
(
m
o
d
m
)
=
a
T
n
+
1
(
m
o
d
m
)
=
a
2
T
n
(
m
o
d
m
)
T_{n}=S_{n+1}-S_{n}~(mod~m)\\ T_{n+1}=S_{n+2}-S_{n+1}~(mod~m)=a(S_{n+1}-S_{n})~(mod~m)=aT_n~(mod~m)\\ T_{n+2}=S_{n+3}-S_{n+2}~(mod~m)=aT_{n+1}~(mod~m)=a^2T_n~(mod~m)
Tn=Sn+1−Sn (mod m)Tn+1=Sn+2−Sn+1 (mod m)=a(Sn+1−Sn) (mod m)=aTn (mod m)Tn+2=Sn+3−Sn+2 (mod m)=aTn+1 (mod m)=a2Tn (mod m)
所以：
T
n
∗
T
n
+
2
=
a
2
T
n
2
=
T
n
+
1
2
T_n*T_{n+2}=a^2T_n^2=T_{n+1}^2
Tn∗Tn+2=a2Tn2=Tn+12
所以
T
n
+
2
∗
T
n
−
T
n
+
1
2
=
k
∗
m
T_{n+2}*T_n-T_{n+1}^2=k*m
Tn+2∗Tn−Tn+12=k∗m
则易找到m