作者: 人生若只如初见

• 计算机产生随机数在概率算法设计中，随机数分为真随机数和伪随机数，计算机只能产生伪随机数。
• 真随机数：类似放射性元素的衰变等无法控制的且无法复制数据
• 伪随机数：通过较为容量大的数学公式产生的数字，具有可猜测性。在得到生成器的随机数种子之后，可以通过计算得到伪随机数序列。
• 通用性伪随机数生成器：s0=seed,s[i+1]=f(s[i])，推广形式：s[i+1]=f(s[i],s[i-1],……,s[i-t])，其中t是固定整数。
• 满足通用性伪随机数的推广的例子，线性同余生成器：s0=seed,s[i+1]=a*s[i]+b mod m,(i=0,1,2……)

线性同余生成器

线性同余序列的周期

• 在线性同余序列中存在自封闭特性，具有以下性质

1、存在递推关系：x[i+1]=f(x[i])
2、其中的任意元素x[i]都在[0,m-1]范围内
3、f(x)的值也在[0,m-1]范围内

• 性质证明及周期计算

1、假设两个集合s={0,1,2,3,……,m-2,m-1} size(s)=m
    T={} size(T)=0
    将产生的伪随机数挪到集合T中
2、先生成第一个伪随机数x1
    s={0,1,2,3,……,m-2,m-1} size(s)=m
    T={x1} size(T)=1
3、根据第一个伪随机数x1生成第二个伪随机数x2，判断x2的归属，若x2属于集合s则一个周期还未结束，若x2属于集合T此处正好等于x1则一个周期产生，周期p=1

推论到x[i]即生成的每个x都属于s，都转移到T
此时：s={0,1,2,3,……,m-2,m-1} size(s)=m
      T={x1,x2,x3,……,x[i-2],x[i-1]} size(T)=i-1
若x[i]=f(x[i-1])∈s，则未能完成一周期
若x[i]=f(x[i-1])∈T，则已完成一个周期，周期p≤i-1

周期p也可能等于m，也就是最终s为空集，T中包含0到m-1的所有元素，且f(X[m])=x1
因此一定存在一个周期p≤m
推论：
    1) 当周期p＜m时，选取不同的随机数种子也就是x0(初始值)产生的周期可能会不同。
    2) 当周期p=m时，序列的周期与初始值x0无关，周期必定为p。

参数选择

m的选择

• 一般来说，模数应该尽可能大，这样可以产生较长的周期，常见的模数挑选一般为2**w（常用的为2^32或者2^64，产生结果直接截断最右边的32bit或者64bit）
• 当模数为2**w的时候，最后产生未模之前的数字与最后的结果相比，是该数字的比特位向右边减w位的结果，这种形式在低位上的随机性并不是很好。可以在产生随机数后截取高位比特，将随机性不好的低位比特直接舍弃。

a的选择（0≤a<m）

• a的取值会很大程度上影响整个生成器的安全性，应该使周期尽量长（最长为m），但是周期长的序列随机性比较差。
• 当a=1时，生成器的公式为s[i+1]=s[i]+b mod m
• 当a=0时，生成器的公式为s[i+1]=b mod m，安全性为0.
• 当a取值其他数字时，影响随机数生成器生成数字的周期。

选取参数的总结

• 模数m尽可能大，一般大于2**30
• 当m选取为2的幂次方时，应该满足a mod 8=5
• 当m和a选取都合理时，b需要在与m互质的条件下选取。

最大周期符合的条件：

• m和b互质
• m的所有质因子的积能整除a-1
• 如果m是4的倍数，a-1也是
• a,b,seed都比m小
• a,b是正整数

例题

• 根据线性同余生成器lcg可得：lcg=(a*x+c)%m
• 根据题目，当输入数字时，可以得到多个连续随机数，根据伪随机数生成的机制，可以了解到，随机数的生成只要知道随机数种子就可以破解
• 类推到线性同余方程组，也就是说当知道a,c,m时即可知道随机数的整个序列
• 例如：假设我们知道lcg0,那么lcg1=(alcg0+c)%m,同理lcg2=(alcg1+c)%m
• 此时我们随意提交多次，可以从中得到连续的随机数，类比于lcg0,lcg1,lcg2的关系
• lcg0=32081 lcg1=23815 lcg2=1237 lcg3=2387
• 爆破模数module，每次moudle值改变时，都进行下面的操作：

lcg1=(a*lcg0+c)%m       lcg2=(a*lcg1+c)%m

两式相减   左边为:lcg2-lcg1   右边为:(a*lcg1+c)-(a*lcg0+c)

化简为: [lcg2-lcg1=a*(lcg1-lcg0) ] %m

根据求余运算规则可知  
[a=(lcg2-lcg1)*gmpy2.invert(lcg1-lcg0,m)]%m

此时代入lcg0,lcg1,lcg2之后可求得a

代入lcg1=(a*lcg0+c)%m,把c当作未知数放到等式左边后，式子为：
c=[lcg1-(a*lcg0)]%m

类推lcg3_guess=(a*lcg2+c)%m
将求得地lcg3_guess与lcg3比较，如果相等，证明求得的a,c,m为正确值
否则，m=m+1，继续验证

注意：
1、这个式子成立条件是两边同时对m求余
2、gmpy2.invert(x1,x2)是求与x1%x2同余的最小数，二者在求余操作后等价，因为余数相等，该式表示余数，类似7%5=2%5

• 求得正确的a,c,m之后，线性同余方程为 lcg[i]=(a*lcg[i-1]+c)%m
• 多次提交成功之后，获得flag

本文始发于微信公众号（星盟安全）：lcg线性同余随机数生成器