MT19937

MT19937是一种周期很长的的伪随机数生成算法，可以快速的产生高质量的伪随机数，主要分为三部分：

  1. 利用seed初始化624的状态
  2. 对状态进行旋转
  3. 根据状态提取伪随机数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:
    # 根据seed初始化624的state
    def __init__(self, seed):
        self.mt = [0] * 624
        self.mt[0] = seed
        self.mti = 0
        for i in range(1, 624):
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

    # 提取伪随机数
    def extract_number(self):
        if self.mti == 0:
            self.twist()
        y = self.mt[self.mti]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18
        self.mti = (self.mti + 1) % 624
        return _int32(y)

    # 对状态进行旋转
    def twist(self):
        for i in range(0, 624):
            #y是当前数的第1位和下一个数的最后31位
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            #先将y右移一位，再与第397位数异或
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
			#如果y为奇数，则与0x9908b0df异或
            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df

python 中内置的 Random 类就是采用了 MT19937 算法， getrandbits(32) 方法可以获得一个 32 位随机数。

题型1 逆向 extract_number

首先分析extract_number函数，可以发现输出的伪随机数是对state[i]进行了异或，位运算后的结果。

逐步分析 extract_number

1
y = y ^ (y >> 18)

可以发现 y 的高 18 位没有变化。所以y1 = y ^ ( y>> 18)，y1 的高 18 位就是 y 的高 18 位，y 的 18-36 位能通过异或出来。也就是说我们可以在有限步内，获得y的所有信息，即我们可以根据y1逆向y。代码如下：

1
2
3
4
5
6
o = 2080737669
y = o ^ o >> 18
# 控制位移的次数
for i in range(32 // 18):
    y = y ^ (y >> 18)
print(y == o)

继续分析

1
y = y ^ y << 15 & 4022730752

可以看到这一步位移的方向发生改变，而且增加了掩码，根据运算符的优先级，可以得到

y1 = y ^ ((y<<15) & 4022730752)，实际上增加的掩码并没有太大的作用，因为 y1 的低 15 位实际上就是 y 的低 15 位和4022730752 的低 15 位异或运算的结果，我们只需要 y1^4022730752 便可以得到y的低 15 位，于是得到y<<15的低 30 位，同理可以得到 y1 的低 30 位，经过有限步，最终可以得到y 的全部信息。代码如下：

1
2
3
4
5
6
7
o = 2080737669
y = o ^ o << 15 & 4022730752
tmp = y
for i in range(32 // 15):
    # (y<<15)&40022730752 每次可以恢复y的15位
    y = tmp ^ y << 15 & 4022730752
print(y==o)

剩下的两步操作，可以采用同样的分析方法进行逆行。最终完整的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
o = 2080737669

# right shift inverse
def inverse_right(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift
    return tmp

# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp >> shift & mask
    return tmp

# left shift inverse
def inverse_left(res, shift, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift
    return tmp

# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
    tmp = res
    for i in range(bits // shift):
        tmp = res ^ tmp << shift & mask
    return tmp

def extract_number(y):
    y = y ^ y >> 11
    y = y ^ y << 7 & 2636928640
    y = y ^ y << 15 & 4022730752
    y = y ^ y >> 18
    return y&0xffffffff

def recover(y):
    y = inverse_right(y,18)
    y = inverse_left_mask(y,15,4022730752)
    y = inverse_left_mask(y,7,2636928640)
    y = inverse_right(y,11)
    return y&0xffffffff

y = extract_number(o)
print(recover(y) == o)

题型2 预测随机数

题型3 逆向twist

题型4 逆向init