线性同余生成器（LCG）-原理及攻击方式（一）

2021-12-30

线性同余方法（LCG）是个产生伪随机数的方法。

它是根据递归公式：Sn+1 = (A*Sn + B) mod M 进行实现，

其中A,B,M是产生器设定的常数。我们常说的种子数seed其实就是初始的S0的值。

实现算法：

class prng_lcg: 
    m = 672257317069504227 # "乘数" 
    c = 7382843889490547368 # "增量" 
    n = 9223372036854775783 # "模数" 
    
    def __init__(self, seed): 
        self.state = seed # the "seed" 
        
    def next(self): 
            self.state = (self.state * self.m + self.c) % self.n 				return self.state 
        
    def test(): gen = prng_lcg(123) # seed = 123 
        print gen.next() # 第一个生成值 
        print gen.next() # 第二个生成值 
        print gen.next() # 第三个生成值

基本攻击方式有四种，基本都基于初等数学计算方法，还有基于格理论的攻击方法以后再更新。

1.对于A、B、M以及N0已知的情况

假设我们观察到有一个LCG系统产生了以下三组连续的值，并且知道内部的参数如下:

# 三组连续的值
s0 = 2300417199649672133
s1 = 2071270403368304644
s2 = 5907618127072939765
# 内部的参数
m = 672257317069504227   # the "multiplier"
c = 7382843889490547368  # the "increment"
n = 9223372036854775783  # the "modulus"

在已知了这些参数之后可以通过递推关系很快推算出未来的数值或者之前的某个数值。

2.增量未知

不清楚增量，但是知道以下信息:

m = 81853448938945944
c = # unknown
n = 9223372036854775783
# 初值和第一个计算值
s0 = 4501678582054734753
s1 = 4371244338968431602

稍稍改写下公式就可以将目标c计算出来

1
2
3

s1 = s0*m + c   (mod n)

c  = s1 - s0*m  (mod n)

3.增量和乘数都未知

虽然不知道增量和乘数但是知道以下数值：

m = # unknown
c = # unknown
n = 9223372036854775783
# LCG生成的初值和后面生成的两个值
s0 = 6473702802409947663
s1 = 6562621845583276653
s2 = 4483807506768649573

解决办法很简单，想想怎么解线性方程组就好了

s_1 = s0*m + c  (mod n)
s_2 = s1*m + c  (mod n)

s_2 - s_1 = s1*m - s0*m  (mod n)
s_2 - s_1 = m*(s1 - s0)  (mod n)
m = (s_2 - s_1)/(s_1 - s_0)  (mod n)

4.增量、乘数和模数均未知

现在内部状态基本是都不知道了，但是知道初值和随后LCG产生的连续的几个值。

m = # unknown
c = # unknown
n = # unknown
s0 = 2818206783446335158
s1 = 3026581076925130250
s2 = 136214319011561377
s3 = 359019108775045580
s4 = 2386075359657550866
s5 = 1705259547463444505
s6 = 2102452637059633432

用线性方程式无法解决了，因为未知数太多，引入多个随机数值都会给每个方程引入新的未知量：

s1 = s0*m + c  (mod n)
s2 = s1*m + c  (mod n)
s3 = s2*m + c  (mod n)
s1 - (s0*m + c) = k_1 * n
s2 - (s1*m + c) = k_2 * n
s3 - (s2*m + c) = k_3 * n

这就相当于六个未知数和三个方程，线性方程组不可能行得通。考虑利用gcd: 如果有几个随机数分别乘以n，那么这几个数的欧几里德算法(gcd)就很可能等于n。

1
2
3

In [944]: n = 123456789
In [945]: reduce(gcd, [randint(1, 1000000)*n, randint(1, 1000000)*n, randint(1, 1000000)*n])
Out[945]: 123456789

某些非0值取模运算是会等于0的：

1	X = 0 (mod n)

然后，根据定义，这相当于：

X = k*n

这种X != 0但是X = 0 (mod n)的情况可以加以利用。我们只需要取几个这样的值进行gcd运算，我们就可以解出n的值。这是在模数未知的情况下十分常用的方法。

在此引入一个序列 – T(n) = S(n+1) - S(n):

t0 = s1 - s0
t1 = s2 - s1 = (s1*m + c) - (s0*m + c) = m*(s1 - s0) = m*t0 (mod n)
t2 = s3 - s2 = (s2*m + c) - (s1*m + c) = m*(s2 - s1) = m*t1 (mod n)
t3 = s4 - s3 = (s3*m + c) - (s2*m + c) = m*(s3 - s2) = m*t2 (mod n)

之后就可以得到想要的效果了:

1	t2t0 - t1t1 = (mmt0 * t0) - (mt0 m*t0) = 0 (mod n)

可以生成几个这样模是0的随机数算式，进而利用上文讲述的技巧。