线性同余生成器

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

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

si=(si1a+b)modns_i = (s_{i-1} a + b) \bmod n

其中 aabbnn 是生成器设定的常数,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,可以求之后和之前的输出:

si1=a1(sib)modns_{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=(sisi1a)modnb = (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)modnsi+2=(si+1a+b)modn\begin{cases} s_{i+1} = (s_{i}a + b) \bmod n \\ s_{i+2} = (s_{i+1}a + b) \bmod n \end{cases}

得:

si+2si+1=a(si+1si)modna=(si+1si)1(si+2si+1)modns_{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=sisi1t_{i} = s_i - s_{i-1}

则:

ti=sisi1=(si1a+b)modn(si2a+b)modn=a(si1si2)modn=ati1modn\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×titi+12=a2ti2a2ti2modn=0modnt_{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×t1t22)(t_{3} \times t_{1} - {t_{2}}^2)(t4×t2t32)(t_{4} \times t_{2} - {t_{3}}^2) \dotsnn 同余,即:

t3×t1t22=knt4×t2t32=tnt_{3} \times t_{1} - {t_{2}}^2 = kn \\ t_{4} \times t_{2} - {t_{3}}^2 = tn

knkntntn 的最大公因数很有可能就是 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+1sis_{i+1} - s_i 在模 nn 下的逆元,因此两者肯定互素。如果不互素,n 就除以从 2 开始的素数,直到可以整除,然后再判断 si+1sis_{i+1} - s_inn 是否互素。

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