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未知

只需获取中间的两个状态值

1
s_1 = (s_0*A+B)%M

显然 $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]))
# 114514

所以我们可以利用这个性质，来尝试得到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:
    # unknown B (increment)
    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)}

    # unknown A (multiplier)
    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)
    
    # unknown M (modulus)
    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)