MT19937

  • 对于MT19937的介绍，已经在前面的一篇文章中介绍过了，接下来就具体学习一下MT19937具体的算法过程。
  • 对于MT19937的应用，其实很多语言的random这个库都使用的是MT19937这个算法，比如python、PHP和Matlab，并且从C++11开始，C++也可以使用梅森旋转算法（MT19937）,对应的命名空间为std::mt19937_64。
  • MT19937这个伪随机数生成器，目前被视为最好的随机数算法。
  • 做个统一：以下文章中的内容都以MT19937来表示该算法。

MT19937原始版本

初始化

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

提取伪随机数

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

梅森旋转操作

  • 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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] = (y >> 1) ^ self.mt[(i+397) % 624]
        if y % 2 != 0:
            self.mt[i] = self.mt[i] ^ 0x9908b0df

总体代码

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
# 由于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)

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

MT19937-64版本

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