MT19937预测随机数

一、基本介绍

mt19937 ，又称梅森旋转算法，是一个伪随机数生成算法，由松本与西村设计于 1998 年提出，可以快速产生高质量的伪随机数。19937这个名字来源于周期长度为梅森素数。

Python的“random”标准库使用mt19937，因此我们可以很容易地破解它，以此来预测要生成的随机数。

二、算法

MT19937主要分为三部分：
1.生成一个seed，通过seed初始化624个32位的状态向量
2.根据状态向量生成随机数(这里说的随机数都是32位的)
3.每生成624个随机数，状态向量旋转

所以，只要知道至少连续的624个32位随机数，就能预测此状态之前和之后的随机数。

若随机数不是32位，可以分成32位的整数倍，按照先生成低32位，再生成高位的原则。

三、函数

1.mersenne-twister-recover[]eboda/mersenne-twister-recover: Given at least 624 outputs of a Mersenne Twister PNRG we can restore its internal state. (github.com)

r1 = random.Random(31337)
outputs = [r1.getrandbits(32) for _ in range(625)]

mtr = MT19937Recover()
r2 = mtr.go(outputs)

assert r1.getrandbits(32) == r2.getrandbits(32)

2.Extend MT19937 Predictor[extend-mt19937-predictor · PyPI]

import random
from extend_mt19937_predictor import ExtendMT19937Predictor

predictor = ExtendMT19937Predictor()

for _ in range(624):
    predictor.setrandbits(random.getrandbits(32), 32)

for _ in range(1024):
    assert predictor.predict_getrandbits(32) == random.getrandbits(32)
    assert predictor.predict_getrandbits(64) == random.getrandbits(64)
    assert predictor.predict_getrandbits(128) == random.getrandbits(128)
    assert predictor.predict_getrandbits(256) == random.getrandbits(256)