LCG
发现自己没有整过线性同余生成器的东西，今天专门来总解一下
参考资料
1、线性同余生成方法
设A,B,M是一定常数，按照递推公式 $state_{i+1}=(A\times state_i+B)\pmod{M}$ ，其中A称为乘数(multiplier)，B称为增量(increment)，M称为模数(modulus)
LCG的生成周期理论上应该是M，但大部分情况下会小于M，如果想要追求LCG的最大周期，应符合以下几个条件：
- A与B都是正整数
- A、B、N[0]都比M要小
- B与M互质
- M的所有质因数都能整除A-1
2、攻击方法
我们把state均简称为s
1、B未知
只需获取中间的两个状态值
显然 $B = s_1 - s_0\times a\pmod{M}$
2、A与B未知
只需获取中间的三个状态值
1
2
| s_1 = (s_0*A+B)%M
s_2 = (s_1*A+B)%M
|
线性方程，解起来还是挺简单的
显然 $A = \frac{s_2-s_1}{s_1-s_0}\pmod{M}$ ，于是就转化成了问题1了
3、A、B、M都不知道 一问三不知
如果获取中间的7个状态值，就很有可能能够成功，数论里：如果有几个随机数分别乘以n，那么这几个数的欧几里德算法(gcd)就很可能等于n
1
2
3
| x = 114514
print(reduce(gcd, [randint(1, 1000000)*x, randint(1, 1000000)*x, randint(1, 1000000)*x, randint(1, 1000000)*x]))
|
所以我们可以利用这个性质，来尝试得到M，于是问题就被转化成了问题2
整合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class lcg_attack:
def lcgattack1(self, states, modulus, multiplier):
if(len(states)<2):
raise Exception("#####Invalid lenth of states! The lenth should be 2 at least!##### - Dawn_whisper")
increment = (states[1] - states[0] * multiplier) % modulus
return {'multiplier':int(multiplier), 'increment':int(increment), 'modulus':int(modulus)}
def lcgattack2(self, states, modulus):
if(len(states)<3):
raise Exception("#####Invalid lenth of states! The lenth should be 3 at least!##### - Dawn_whisper")
multiplier = (states[2] - states[1]) * inverse(states[1] - states[0], modulus) % modulus
return self.lcgattack1(states, modulus, multiplier)
def lcgattack3(self, states):
if(len(states)<6):
raise Exception("#####Invalid lenth of states! The lenth should be 6 at least!##### - Dawn_whisper")
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
return self.lcgattack2(states, modulus)
|
wechat
