MT19937 - Zsm's blog

算法描述#

主要步骤#

利用 seed 初始化寄存器状态
对寄存器状态进行旋转
根据寄存器状态提取伪随机数

初始化可能用的是固定的种子，也有可能是服务器时间戳，生成一个长度为624的状态数组，填充完后作为初始状态

旋转的目的是增加不确定性还有均匀性，主要是位运算实现的线性变换

提取伪随机数这一步会从状态数组中依次提取一个整数，并对其进行位运算和异或运算，生成的数即为输出的伪随机数。当所有数组全被遍历过之后，就会对状态数组再次进行一次旋转，重新生成新的状态数组。

python代码实现#

这是一个简单的实现代码

1
def _int32(x):
2
    return int(0xFFFFFFFF & x)
3

4
class MT19937:
5
    # 初始化
6
    def __init__(self, seed):
7
        self.mt = [0] * 624
8
        self.mt[0] = seed
9
        self.mti = 0
10
        for i in range(1, 624):
11
            self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)
12

13
    # 提取伪随机数
14
    def extract_number(self):
15
        if self.mti == 0:
16
            self.twist()
17
        y = self.mt[self.mti]
18
        y = y ^ y >> 11
19
        y = y ^ y << 7 & 2636928640
20
        y = y ^ y << 15 & 4022730752
21
        y = y ^ y >> 18
22
        self.mti = (self.mti + 1) % 624
23
        return _int32(y)
24

25
    # 旋转状态
26
    def twist(self):
27
        for i in range(0, 624):
28
            y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
29
            self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
30

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

为什么说是简单的生成方法呢？可能知道python的random库也是MT19937生成伪随机数，但是它对 seed 的传入经过了两步处理 init_genrand和 init_by_array，因此和上面的实现是有区别的，也就是说两者产生的状态矩阵和伪随机数是不一样的。

逆向extract_number#

这里跟随xenny老师的思路走，就拿y = y ^ y << 7 & 2636928640举例
那么整个式子就是

y=x \oplus ((x\ll7)\&2636928640)\\ \quad\quad\quad\quad\quad\quad =x \oplus ((x\ll7)\&10011101001011000101011010000000)

注意后七位都是0，那么最后结果的后七位和最初状态的后七位就是相同的，在y已知的情况下，我们就可以步步回推了，比如倒数8~14位就是

(后七位 \& 0101101) \oplus y的倒数8到14位

其他的类似，用代码实现如下

1
def invert(res, shift, right=True, mask=0xffffffff, bits=32):
2
    tmp = res
3
    if right:
4
        for i in range(bits // shift):
5
            tmp = res ^ tmp >> shift & mask
6
        return tmp
7
    else:
8
        for i in range(bits // shift):
9
            tmp = res ^ tmp << shift & mask
10
        return tmp
11

12
def inv_extract_number(y):
13
    y = invert(y,18,True)
14
    y = invert(y,15,False,4022730752)
15
    y = invert(y,7,False,2636928640)
16
    y = invert(y,11,True)
17
    return _int32(y)

逆向twist#

在上文中我们提到如果得到了某一轮 state 的全部信息便可以向后预测随机数，那么如果我们需要向前恢复随机数，则需要对 twist 函数进行逆向。

1
def twist(self):
2
    for i in range(0, 624):
3
        y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
4
        self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
5

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

先关注旋转的后几步操作，能注意到由于 y>>1的最高位一定为 0，所以最终 self.mt[i]的最高位一定由 self.mt[(i + 397) % 624]或 self.mt[(i + 397) % 624] ^ 0x9908b0df控制，所以可以判断出是否经历了xor 0x9908b0df 操作。然后由于是否异或操作同时受最低位控制，那么逆向的时候即可，通过是否异或来恢复因为就右移而丢失的最低位。于是我们就得到了 y

然后分析旋转的第一步，y 是由 self.mt[i]的最高位和 self.mt[(i + 1) % 624]的除最高位部分组合得到的。所以我们只要计算 self.mt[i]和 self.mt[(i - 1) % 624]两个位置的 y 就能得到 self.mt[i]的值了

1
def inv_twist(state):
2
    high = 0x80000000
3
    low = 0x7fffffff
4
    mask = 0x9908b0df
5

6
    def _recover(i):
7
        y = state[i] ^ state[(i + 397) % 624]
8
        if y & high == high:
9
            y ^= mask
10
            y <<= 1
11
            y |= 1
12
        else:
13
            y <<= 1
14
        return y
15

16
    for i in range(len(state)-625, -1, -1):
17
        state[i] = _recover(i) & high
18
        state[i] |= _recover(i-1) & low
19
    return state

逆向init#

这玩意的主要操作是

self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

你可以发现，里面主要是乘法加法和self.mt[i - 1] ^ self.mt[i - 1] >> 30，前两者可逆运算，后面这个和前面的类似，通过invert逐位还原即可

1
def inv_init(last):
2
    n = 1<<32
3
    inv = pow(1812433253,-1,n)
4
    for i in range(623,0,-1):
5
        last = ((last-i)*inv)%n
6
        last = invert(last,30)
7
    return last

给出任意19937个bit#

这个类型是看鸡块神的博客学到的，主要的地方还是在于构建矩阵，直接上脚本吧

1
Dall=list(map(int,open('data3.txt','r').readlines()))
2
from Crypto.Util.number import *
3
from random import *
4
from tqdm import *
5
n=1250
6
D=Dall[:n]
7
rng=Random()
8
def getRows(rng):
9
    #这一部分根据题目实际编写，必须和题目实际比特获取顺序和方式完全一致，且确保比特数大于19937，并且请注意zfill。
10
    row=[]
11
    for i in range(n):
12
        row+=list(map(int, (bin(rng.getrandbits(16))[2:].zfill(16))))
13
    return row
14
M=[]
15
for i in tqdm_notebook(range(19968)):#这一部分为固定套路，具体原因已经写在注释中了
16
    state = [0]*624
17
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
18
    for j in range(624):
19
        state[j] = int(temp[32*j:32*j+32],2)
20
    rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
21
    M.append(getRows(rng))
22
M=Matrix(GF(2),M)
23
y=[]
24
for i in range(n):
25
    y+=list(map(int, (bin(D[i])[2:].zfill(16))))
26
y=vector(GF(2),y)
27
s=M.solve_left(y)
28
#print(s)
29
G=[]
30
for i in range(624):
31
    C=0
32
    for j in range(32):
33
        C<<=1
34
        C|=int(s[32*i+j])
35
    G.append(C)
36
import random
37
RNG1 = random.Random()
38
for i in range(624):
39
    G[i]=int(G[i])
40
RNG1.setstate((int(3),tuple(G+[int(624)]),None))
41

42
print([RNG1.getrandbits(16) for _ in range(75)])
43
print(D[:75])

常用脚本#

原始版本#

最经典的款式，速度慢，不好用

1
def construct_a_row(RNG):
2
    row = []
3
    for _ in range(19968//32):
4
        tmp = RNG.getrandbits(32)
5
        row += list(map(int, bin(tmp)[2:].zfill(32)))
6
    return row
7

8
# 构造线性方程组的矩阵
9
L = []
10
for i in trange(19968):
11
    state = [0]*624  # MT19937使用624个32位整数作为状态
12
    # 构造一个只有一位为1,其他都为0的序列
13
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
14
    # 将这个序列分成624段,每段32位,转换为整数
15
    for j in range(624):
16
        state[j] = int(temp[32*j:32*j+32], 2)
17

18
    RNG = Random()
19
    RNG.setstate((3,tuple(state+[624]),None))
20
    L.append(construct_a_row(RNG))
21

22
# 将L转换为GF(2)上的矩阵（二进制域）
23
L = Matrix(GF(2),L)
24
print(L.nrows(), L.ncols())
25

26
def MT19937_re(state):
27
    try:
28
        # 构造目标向量R
29
        R = []
30
        for i in state:
31
            R += list(map(int, bin(i)[2:].zfill(32)))
32

33
        R = vector(GF(2), R)
34
        s = L.solve_left(R)  # 这里可能会抛出异常
35

36
        # 将解转换为二进制字符串
37
        init = "".join(list(map(str,s)))
38
        state = []
39
        # 将解重新分割成624个32位整数
40
        for i in range(624):
41
            state.append(int(init[32*i:32*i+32],2))
42

43
        # 创建新的RNG并设置恢复出的状态
44
        RNG1 = Random()
45
        RNG1.setstate((3,tuple(state+[624]),None))
46

47
        return RNG1
48

49
    except Exception as e:
50
        print(f"[-]{e}")
51
        pass
52

53
RNG = MT19937_re()

randcrack#

一个无脑的方法？直接利用这个库进行预测，但是只能是624*32，要不然不行

1
import random
2
from randcrack import  RandCrack
3

4
rc = RandCrack()
5
for i in range(624):
6
    rc.submit(random.getrandbits(32))
7
print(random.getrandbits(64))
8
print(rc.predict_getrandbits(64))

github上有一个优化后的版本，但是还没有用过，可以看看链接

gf2bv#

maple神写的一个库，本质是接GF(2)方程组的，MT19937刚刚好满足，所以可以拿来使用，传送门。TGCTF的那个题就可以用这个库去写，非常的好用。

示例代码

1
from gf2bv import LinearSystem
2
from gf2bv.crypto.mt import MT19937
3
from tqdm import *
4
import random
5
from Crypto.Util.number import *
6
def mt19937(bs, out):
7
    lin = LinearSystem([32] * 624)
8
    mt = lin.gens()
9

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

15
    sol = lin.solve_one(zeros)
16

17
    rng = MT19937(sol)
18
    pyrand = rng.to_python_random()
19
    for i in range(2496):
20
        out.append(pyrand.getrandbits(8))
21
    print(pyrand.getrandbits(8))
22
import random
23
random.seed(1)
24
out=[]
25
for i in range(2496):
26
    out.append(random.getrandbits(8))
27
mt19937(8, out)

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

关于安装：

mac直接去github下m4ri的包，然后本地编译后sudo make install
如果像我一样在pyenv这种虚拟环境里面跑python的，把环境注入进去 export CFLAGS="-I/usr/local/include" export LDFLAGS="-L/usr/local/lib"然后再pip install .

a ctfer on the load