lcg线性同余随机数生成器

  1. 随机数
  2. 线性同余生成器
    1. 线性同余序列的周期
    2. 参数选择
      1. m的选择
      2. a的选择(0≤a<m)
      3. 选取参数的总结
      4. 最大周期符合的条件:
  3. 例题

随机数

  • 计算机产生随机数在概率算法设计中,随机数分为真随机数和伪随机数,计算机只能产生伪随机数。
  • 真随机数:类似放射性元素的衰变等无法控制的且无法复制数据
  • 伪随机数:通过较为容量大的数学公式产生的数字,具有可猜测性。在得到生成器的随机数种子之后,可以通过计算得到伪随机数序列。
  • 通用性伪随机数生成器: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
2
3
1、存在递推关系:x[i+1]=f(x[i])
2、其中的任意元素x[i]都在[0,m-1]范围内
3、f(x)的值也在[0,m-1]范围内
  • 性质证明及周期计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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值改变时,都进行下面的操作:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 1259742453@qq.com

💰

×

Help us with donation