Mersenne Twister Predictor
Predict MT19937 PRNG, from preceding 624 generated numbers.
usage
install
$ pip install mersenne-twister-predictoras a library
This library has the special feature for CPython's standard random.
Try below one:
import random
from mt19937predictor import MT19937Predictor
predictor = MT19937Predictor()
for _ in range(624):
x = random.getrandbits(32)
predictor.setrandbits(x, 32)
assert random.getrandbits(32) == predictor.getrandbits(32)This is useful for some CTF tasks, e.g. TokyoWesterns CTF 4th 2018: mixed cipher, Tokyo Westerns CTF 3rd: 2017, etc.
For more details, see mt19937predictor.py and tests/random_py.py.
as a command
Give the 624 32-bit integers, as unsigned decimal integers, line by line.
$ wc data.txt
624 624 6696 data.txt
$ head -n 4 data.txt
734947730
363401994
806921074
790218357
$ cat data.txt | mt19937predict > predicted.txt
example (same as tests/cplusplus.py)
This is an example of a pseudorandom number generator using the Mersenne Twister.
// generator.cpp
#include <iostream>
#include <random>
using namespace std;
int main() {
random_device seed_gen;
mt19937 mt(seed_gen());
for (int i = 0; i < 1000; ++i) {
cout << mt() << endl;
}
return 0;
}Compile it and let it generate 1000 numbers.
$ g++ -std=c++11 generator.cpp
$ ./a.out > data.txt
$ head data.txt
734947730
363401994
806921074
790218357
1766244801
680628322
1972477509
4015123394
2848130362
3481789813Take the 624 consecutive numbers. We will predict the rest, 376 numbers.
$ head -n 624 data.txt > known.txt
$ tail -n 376 data.txt > correct.txt
$ wc known.txt
624 624 6696 known.txtPredict.
$ cat known.txt | mt19937predict | head -n 376 > predicted.txtCompare the predict numbers and the original ones.
If diff outputs nothing, it means the prediction was succeeded.
$ diff predicted.txt correct.txtreference
thanks to
