线性同余生成器

线性同余方器（LCG）可以产生伪随机数。

它根据递归公式生成新的数：

si=(si−1a+b) mod ns_i = (s_{i-1} a + b) \bmod n

其中 aa、bb、nn 是生成器设定的常数，s0s_0 相当于一个种子。

可以用 python 简单实现一下 LCG：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *

class LCG():
    def __init__(self, s0=getRandomInteger(128)):
        self.a = getPrime(128)
        self.b = getPrime(128)
        self.n = getPrime(256)
        self.s = s0

    def next(self):
        self.s = (self.s * self.a + self.b) % self.n
        return self.s

lcg = LCG()
print lcg.next()
print lcg.next()
print lcg.next()

LCG 在数学表达实现上十分优雅，非常容易理解并且容易设计实现。但是它在安全性方面十分弱。接下来将从以下几种情况对其进行攻击。

攻击 LCG

全都已知

已知全部的内部参数，再知道随便一个输出，就可以推算未来或者倒退之前的输出。

假如知道 s2，可以求之后和之前的输出：

si−1=a−1(si−b) mod ns_{i-1} = a^{-1} (s_i - b) \bmod n 

1
2
3
4
5
6
a = 227534804674212294373456976878991674591
b = 218174184596792028429991024115182554493
n = 103062888820337978910105855710820590574814030029886609905720019096651060712461
s2 = 29312131474314770241680760398669700939670692727273348413246711409796444883599
s3 = (s2 * a + b) % n
s1 = ((s2 - b) * gmpy2.invert(a, n)) % n

b 未知

已知乘数 a、模数 n，但不知增量 b，但知道连续两个输出，就能推算出 b：

b=(si−si−1a) mod nb = (s_i - s_{i-1}a) \bmod n 

1
2
3
4
5
a = 192588738683067832869240203685434639117
n = 98050903778398182124874337920935505944420404837269997836081281971360568748291
s1 = 56877403406926375972348286664767936935900247160292261457124625361059643277984
s2 = 81044863851407226329153956857965274264068864480980462430979569542522955371451L
b = (s2 - s1 * a) % n

a、b 未知

只知模数 n，不知乘数 a 和 增量 b，但知道连续三个输出，就能推算出 a 和 b：

由：

{si+1=(sia+b) mod nsi+2=(si+1a+b) mod n\begin{cases} s_{i+1} = (s_{i}a + b) \bmod n \\ s_{i+2} = (s_{i+1}a + b) \bmod n \end{cases}

得：

si+2−si+1=a(si+1−si) mod na=(si+1−si)−1(si+2−si+1) mod ns_{i+2} - s_{i+1} = a (s_{i+1} - s_i) \bmod n\\ a = (s_{i+1} - s_i)^{-1} (s_{i+2} - s_{i+1}) \bmod n 

1
2
3
4
5
n = 92013576770645791378768990394128181282635078497671261559009254989701587973989
s1 = 60880122533680572874218523434449512865056441979647433804698757756501421133461
s2 = 78556744799434854594411626681897469161797844824631708003278266665419173379561
s3 = 51792442792801060013114854273780228326195005987417858969968176470919682885233
a = (gmpy2.invert((s2 - s1), n) * (s3 - s2)) % n

全都未知

内部参数全都未知，但知道若干个输出（至少 5 个），就能推算出 n、 a 和 b：

令：

ti=si−si−1t_{i} = s_i - s_{i-1}

则：

ti=si−si−1=(si−1a+b) mod n−(si−2a+b) mod n=a(si−1−si−2) mod n=ati−1 mod n\begin{aligned} t_i & = s_i - s_{i-1} \\ & = (s_{i-1} a + b) \bmod n - (s_{i-2} a + b) \bmod n \\ & = a (s_{i-1} - s_{i-2}) \bmod n\\ & = a t_{i-1} \bmod n \end{aligned}

则：

ti+2×ti−ti+12=a2ti2−a2ti2 mod n=0 mod nt_{i+2} \times t_{i} - {t_{i+1}}^2 = a^2{t_i}^2 - a^2{t_i}^2 \bmod n = 0 \bmod n\\

因此 (t3×t1−t22)(t_{3} \times t_{1} - {t_{2}}^2) 、 (t4×t2−t32)…(t_{4} \times t_{2} - {t_{3}}^2) \dots 模 nn 同余，即：

t3×t1−t22=knt4×t2−t32=tnt_{3} \times t_{1} - {t_{2}}^2 = kn \\ t_{4} \times t_{2} - {t_{3}}^2 = tn

knkn、tntn 的最大公因数很有可能就是 nn，更多的数据结果更准确。

1
2
3
4
s = [s1, s2, s3, s4, s5, s6]
t = [s[i] - s[i-1] for i in range(1, len(s))]
tt = [(t[i-2] * t[i] - t[i-1] * t[i-1]) for i in range(2, len(s)-2)]
print reduce(gmpy2.gcd, tt)

还可以根据 a 来减小 n 的差错。

求 a 中 要计算 si+1−sis_{i+1} - s_i 在模 nn 下的逆元，因此两者肯定互素。如果不互素，n 就除以从 2 开始的素数，直到可以整除，然后再判断 si+1−sis_{i+1} - s_i 与 nn 是否互素。

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import sieve_base

def check_n(s, n):
    for i in range(len(s)-1):
        if gmpy2.gcd(s[i+1] - s[i], n) != 1:
            return False
    return True

while not check_n(s, n):
    for i in sieve_base:
        if n % i == 0:
            n = n // i
            break