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