MT19937

发表于 更新于 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 8 分钟

owo

最近碰到蛮多涉及伪随机数预测的题目，顺便总结一下，常看常新。

基础知识

MT19937是一种周期很长的的伪随机数生成算法，该算法的周期为2$^{19937}$−1，故名为 MT19937。可以快速的产生高质量的伪随机数，主要分为三部分。

1.利用seed初始化624的状态
2.对状态进行旋转
3.根据状态提取伪随机数

其中 32 位的 MT19937 Python 代码实现为:

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
def _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:
    # 初始化
    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 = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df

更多详细关于该算法的知识可以参考MT19937 - Cryptography-Wiki

python中的

1
random.getrandbits()

实际上就是使用的梅森旋转(Mersenne Twister)。

对于不是32位的随机数生成，经过测试我们有以下发现

1，若生成位数小于32位，实际上是由生成的32位随机数在对应位上截断形成的。

举个栗子

1
2
3
4
5
6
7
8
9
import random
random.seed(1)#掷随机数种子为1从而确保随机数产生的一致性
print(hex(random.getrandbits(32)))
random.seed(1)#重新掷随机数种子
print(hex(random.getrandbits(16)))


0x2265b1f5
0x2265

这里我们生成了一个32位的随机数并将其转为16进制用来让我们观察规律，然后重置种子再生成一个16位的随机数。一眼看出其与上一个32位的前16位一致。验证了我们的结论。

2，若生成位数大于32位，本质是由多次生成的32位随机数拼接产生的。

同样举个栗子

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
random.seed(1)#掷随机数种子为1从而确保随机数产生的一致性
print(hex(random.getrandbits(32)))
print(hex(random.getrandbits(32)))
random.seed(1)#重新掷随机数种子
print(hex(random.getrandbits(64)))



0x2265b1f5
0x91b7584a
0x91b7584a2265b1f5

在这个样例中我们生成了2次32位的随机数然后又生成了一次64位随机数，我们观察64位随机数，我们发现，其高32位就是我们第二次生成的随机数，低32位是第一次生成的随机数。也就是说大于32位的随机数是以第一次生成的32位随机数作为低位向高位生长的。

再来看个例子

1
2
3
4
5
6
7
8
9
10
import random
random.seed(1)#掷随机数种子为1从而确保随机数产生的一致性
print(hex(random.getrandbits(32)))
print(hex(random.getrandbits(32)))
random.seed(1)#重新掷随机数种子
print(hex(random.getrandbits(36)))

0x2265b1f5
0x91b7584a
0x92265b1f5

因为每个十六进制位对应 4 位二进制，所以我们用36来便于观察，不难发现向高位生长时其实跟小于32位一样是从高位开始取。

关于预测

现在其实有蛮多的库能用了，不过还是先看看最基本的方法吧

1,基础脚本

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
47
48
49
50
51
52
53
def construct_a_row(RNG): 
    row = []
    for _ in range(19968//32):
        tmp = RNG.getrandbits(32)
        row += list(map(int, bin(tmp)[2:].zfill(32)))
    return row
 
# 构造线性方程组的矩阵 
L = [] 
for i in trange(19968): 
    state = [0]*624  # MT19937使用624个32位整数作为状态 
    # 构造一个只有一位为1,其他都为0的序列 
    temp = "0"*i + "1"*1 + "0"*(19968-1-i) 
    # 将这个序列分成624段,每段32位,转换为整数 
    for j in range(624): 
        state[j] = int(temp[32*j:32*j+32], 2) 
     
    RNG = Random() 
    RNG.setstate((3,tuple(state+[624]),None))
    L.append(construct_a_row(RNG)) 
 
# 将L转换为GF(2)上的矩阵（二进制域） 
L = Matrix(GF(2),L)
print(L.nrows(), L.ncols())
 
def MT19937_re(state): 
    try: 
        # 构造目标向量R 
        R = []
        for i in state:
            R += list(map(int, bin(i)[2:].zfill(32)))
         
        R = vector(GF(2), R)
        s = L.solve_left(R)  # 这里可能会抛出异常 
         
        # 将解转换为二进制字符串 
        init = "".join(list(map(str,s))) 
        state = [] 
        # 将解重新分割成624个32位整数 
        for i in range(624): 
            state.append(int(init[32*i:32*i+32],2)) 
 
        # 创建新的RNG并设置恢复出的状态 
        RNG1 = Random() 
        RNG1.setstate((3,tuple(state+[624]),None)) 
 
        return RNG1
         
    except Exception as e: 
        print(f"[-]{e}")
        pass
 
RNG = MT19937_re()

不过还是得根据具体情况来分析。不过这种方法在构造矩阵时花的时间其实挺长的，试了一下差不多得十分钟。

2,直接使用randcrack库进行预测

无脑调用库就行(bushi

1
2
3
4
5
6
7
8
import random #导入random库（Python内置了）
from randcrack import  RandCrack
#你可以掷随机数种子来确保预测的有效性， 不过random预测的时候默认以当前时间作为随机数种子
rc = RandCrack()#实例化randcrack类
for i in range(624):#循环624次
    rc.submit(random.getrandbits(32))#每次循环提交一个32位random生成的随机数
print(random.getrandbits(64))#利用random库获取一个64位的随机数（你可以修改为任意位数）
print(rc.predict_getrandbits(64))#利用randcrack获取的随机数

不过原版的randcrack仿佛只能特性针对“624”和“32位”对其他情况都没法打，不过有师傅做了优化（https://github.com/guoql666/pyrandcracker）可以了解一下。

3,gf2bv

无敌真神,maple师傅整的一个库。其实是maple佬写出来求解GF(2)上线性方程组的。恰好MT19937在GF(2)上关于初始状态也是线性递推，所以拿来搞MT也不是不行。

我们还是先生成足够的随机数来检验一下

1
2
3
4
5
6
7
8
9
import random
random.seed(1)
out=[]
for i in range(2496):
    out.append(random.getrandbits(8))
#print(out)
print(random.getrandbits(8))

#198

注意这里生成2496个是因为我选的是八位的随机数。

然后我们用gf2bv预测一下。

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
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from tqdm import *
import random
from Crypto.Util.number import *
def mt19937(bs, out):
    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    #rng.getrandbits(175)
    zeros = [rng.getrandbits(bs) ^ o for o in out] + [mt[0] ^ 0x80000000]
    print("solving...")

    sol = lin.solve_one(zeros)

    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    for i in range(2496):
        out.append(pyrand.getrandbits(8))
    print(pyrand.getrandbits(8))
import random
random.seed(1)
out=[]
for i in range(2496):
    out.append(random.getrandbits(8))
mt19937(8, out)

这里，zeros.append()的时候需要注意和题目中获取randbits的方式一致。生成的pyrand其实是它的初始状态，需要预测哪个就往后递推就行了。

(ps:这个库仿佛只能装到Linux系统里，它的一个依赖项没有windows的版本

例题分析