MT19937 即梅森旋转算法（Mersenne twister）由松本眞（日语：松本真）和西村拓士在 1997 年开发，基于二进制有限域 $\mathbb{F}_2$​上的矩阵线性递归，可以快速产生高质量的伪随机数。

该算法的周期为$2^{19937}−1$，故名为 MT19937。该算法具有以下优点

  • 周期非常长，达到$2^{19937}−1$。
  • 在$1≤k≤623$都满足$k-$分布。
  • 能比硬件实现的方法更快产生伪随机数。

$k-$分布：一个周期为$P$的$\omega$位整数的伪随机序列$x_i$，如果下列成立则称$v-$比特精度的$k-$分布成立：

令$trunc_v(x)$表示由$x$的前$v$位形成的数，考虑$P$中$k$个$v$向量，然后$2^{kv}$个组合中每一个都在一个周期内出现次数相同（全0组合次数较少除外）。
$$
(trunc_v(x_i),trunc_v(x_{i+1}),…,trunc_v(x_{i+k-1}))~(0≤i＜P)
$$

MT19937

  • 对于MT19937的介绍，已经在前面的一篇文章中介绍过了，接下来就具体学习一下MT19937具体的算法过程。这里简单讲一下前面没讲的：

    • 对于MT19937的应用，其实很多语言的random这个库都使用的是MT19937这个算法，比如python、PHP和Matlab，并且从C++11开始，C++也可以使用梅森旋转算法（MT19937）,对应的命名空间为std::mt19937_64。

    • MT19937这个伪随机数生成器，目前被视为最好的随机数算法。

    • 做个统一：以下文章中的内容都以MT19937来表示该算法。

    • 该版本其实就是使用32位的整数作为该算法的种子。之后的64位是后来的一个变种版本，初学的时候一开始只要学原始版本即可。

    • 注意：自己写好的MT19937算法代码不要使用Python的random库验证，因为使用Python自带的random库传入seed的时候可能还会对seed做一些处理。

  • 接下来我们一步一步介绍一下MT19937的具体过程，采用的是该博客的方式：https://hasegawaazusa.github.io/mersenne-twister-note.html，先分布介绍，最后再将算法有个整体概念。

  • 代码采用的是这篇博客的代码，实现的比较简洁：https://huangx607087.online/2021/07/10/Explore-MT19937/

  • 这个算法其实总的来说有三个部分，分别就是初始化操作、获得伪随机数(提取伪随机数)、梅森旋转操作

初始化

代码如下，这里主要就是利用用户传入的种子，对该MT19937中的初始状态寄存器做一个初始化操作，使得624个初始化状态寄存器都有对应的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 由于Python中支持无限长度的整型,所以我们需要定义一个函数来实现32位整型的提取
def _int32(x):
    return 0xFFFFFFFF & x

# 创建一个MT19937的类
class MT19937:
    def __init__(self,seed):
        """
        先对数据进行初始化操作,并且定义一些固定的值以及用户传进来的值
        1.mt:表示624个初始状态的寄存器,这里使用长度为624的列表表示
        2.seed:表示用户传入的随机数种子,并将该种子赋值给mt[0],即第一个寄存器
        3.mtinit: 是用于初始化的一个常数,该数可以用于提高初始种子的扩散效果
        4.mti:这里先设定一个初值0,在初始化的时候用不到
        5.最后进行623次的for循环,通过递推的方式为每一个初始状态寄存器都进行初始化
        (也就是说初始状态寄存器的值与seed关联性是比较强的)
        """
        self.mt = [0]*624
        self.mt[0] = seed
        self.mti=0
        self.mtinit = 0x6c078965
        for i in range(1,624):
            self.mt[i] = _int32(self.mtinit * (self.mt[i-1] ^ self.mt[i-1] >> 30) + i)

提取伪随机数

  • 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def getrandbits(self):
    """
    1.这个步骤就是利用之前生成的624个初始状态寄存器的值,通过梅森旋转以及位运算
      从而计算出这一次触发时我们得到的伪随机数的值
    2.mti其实这里就是记录用户获取随机数的此时,以624为一个周期,每获取一个周期后就会触发梅森旋转(也被称为回火策略)
    3.一开始mti为0的时候就会先触发一次梅森旋转
    4. 2636928640(即0x9D2C5680)和4022730752(即0xEFC60000)都是常量。前者混合中位，掩盖模式特征;后者混合高位，增强熵
    5. 这些常数保证了输出的质量和周期长度,并不能随意修改
    :return: 返回值就是一个32位的整数
    """
    if self.mti >= 624:
        self.twist()
    y = self.mt[self.mti]
    y ^= (y >> 11)
    y ^= (y << 7) & 0x9D2C5680
    y ^= (y << 15) & 0xEFC60000
    y ^= (y >> 18)
    self.mti = (self.mti + 1) % 624
    return _int32(y)

状态旋转

  • 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def twist(self):
    """
    直接将624个初始状态寄存器进行一个梅森旋转操作，
    旋转过程涉及位运算以及与当前初始状态寄存器i以及第i+397个寄存器的状态有关
    :return: 无返回值
    """
    for i in range(0,624):
        # 主要就是与一个固定的0x80000000 和 0x7fffffff
        # 这里就表示用第i个初始状态寄存器的最高位 + 第i+1个初始状态寄存器的第1-31位
        y = _int32(((self.mt[i]) & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
        # 之后就是更新当前初始状态寄存器的的值
        self.mt[i] = _int32((y >> 1) ^ self.mt[(i+397) % 624])
        if y % 2 != 0:
            self.mt[i] = self.mt[i] ^ 0x9908b0df
    self.mti = 0

总体代码

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
54
55
56
57
58
59
60
def _int32(x):
    return int(0xFFFFFFFF & x)

# 创建一个MT19937的类
class MT19937:
    def __init__(self,seed):
        """
        先对数据进行初始化操作,并且定义一些固定的值以及用户传进来的值
        1.mt:表示624个初始状态的寄存器,这里使用长度为624的列表表示
        2.seed:表示用户传入的随机数种子,并将该种子赋值给mt[0],即第一个寄存器
        3.mtinit: 是用于初始化的一个常数,该数可以用于提高初始种子的扩散效果
        4.mti:这里先设定一个初值0,在初始化的时候用不到,
        5.最后进行623次的for循环,通过递推的方式为每一个初始状态寄存器都进行初始化
        (也就是说初始状态寄存器的值与seed关联性是比较强的)
        """
        self.mt = [0]*624
        self.mt[0] = seed
        self.mti=624
        self.mtinit = 0x6c078965
        for i in range(1,624):
            self.mt[i] = _int32(self.mtinit * (self.mt[i-1] ^ self.mt[i-1] >> 30) + i)

    def getrandbits(self):
        """
        1.这个步骤就是利用之前生成的624个初始状态寄存器的值,通过梅森旋转以及位运算
          从而计算出这一次触发时我们得到的伪随机数的值
        2.mti其实这里就是记录用户获取随机数的此时,以624为一个周期,每获取一个周期后就会触发梅森旋转(也被称为回火策略)
        3.一开始mti为0的时候就会先触发一次梅森旋转
        4. 2636928640(即0x9D2C5680)和4022730752(即0xEFC60000)都是常量。前者混合中位，掩盖模式特征;后者混合高位，增强熵
        5. 这些常数保证了输出的质量和周期长度,并不能随意修改
        :return: 返回值就是一个32位的整数
        """
        if self.mti >= 624:
            self.twist()
        y = self.mt[self.mti]
        y ^= (y >> 11)
        y ^= (y << 7) & 0x9D2C5680
        y ^= (y << 15) & 0xEFC60000
        y ^= (y >> 18)
        self.mti = (self.mti + 1) % 624
        return _int32(y)

    def twist(self):
        """
        直接将624个初始状态寄存器进行一个梅森旋转操作，
        旋转过程涉及位运算以及与当前初始状态寄存器i以及第i+397个寄存器的状态有关
        :return: 无返回值
        """
        for i in range(0,624):
            # 主要就是与一个固定的0x80000000 和 0x7fffffff
            # 这里就表示用第i个初始状态寄存器的最高位 + 第i+1个初始状态寄存器的第1-31位
            y = _int32(((self.mt[i]) & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
            # 之后就是更新当前初始状态寄存器的的值
            self.mt[i] = _int32((y >> 1) ^ self.mt[(i+397) % 624])
            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df
        self.mti = 0
mt = MT19937(0)
print(mt.getrandbits())
# 2357136044

MT19937破解

状态破解

矩阵状态破解

旋转破解

MT19937常见题型

题型1_预测随机数

  • 给了足够多的数据后其实可以预测随机数的，并且有在Python中其实有现成的库可以使用，当然其实也可以自己逆向以下MT19937的算法，自己预测破解。

题目1_XYCTF2025_Division

题目2_

题型2_恢复随机数

  • 这类题型其实就是选用一开始生成的随机数对flag等密文进行加密，之后给你后续一大堆随机数，让你恢复出随机数种子和初始状态寄存器
  • 恢复出随机数种子和初始状态寄存器，从而可以得到一开始生成的随机数值，从而获得密钥，对flag的密文进行解密操作。

题目1_XYCTF2025_choice

题型3_给一定量任意的bit

  • 这种情况是题目给你一定量任意的伪随机数的bit，从而让你恢复这个伪随机数。这种情况其实就是要进行一定量的操作了。
  • 有些情况他会给你足够的bit也就是19968个bit或者超过19968个bit，此时还是比较好恢复初始状态寄存器的。
  • 但是有些情况题目不会给你足够数量的bit位，此时可能就需要对MT19937的旋转过程或者其他过程进行破解。从而恢复初始状态寄存器。

题目1_Random game

题目2_never enough

相关库分析

python中random库

C++中std::mt19937_64