Mersenne Twister (MT) is one of the most widely used general-purpose pseudorandom number generator (PRNG). Its name derives from the fact that its period length is chosen to be a Mersenne prime.
The most commonly used version of the MT algorithm is based on the Mersenne prime MT19937
). The standard implementation of MT19937 uses a MT19937-64
).
In this project, we will reimplement MT19937 algorithm using C/C++ (comparing correctness with C++ built-in functions: std::mt19937
, std::mt19937_64
) Then we will suggest some methods to attack Mersenne Twister (included C/C++ or Python scripts).
IMPORTANT: Mersenne Twister is not cryptographically secure.
In this section, we will recall three main parts in MT algorithm.
The state needed for a Mersenne Twister implementation is an array of seed
value is used to supply
The MT algorithm generates a sequence of word vectors, which are considered to be uniform pseudorandom integers between
We have several constants:
- An integer
$n$ : the degree of the recurrence. -
$x_{k}^{u}$ : the upper$w - r$ bits of$x_{k}$ . -
$x_{k+1}^{l}$ : the lower$r$ bits of$x_{k+1}$ . -
$x_{k}^{u} \vert x_{k+1}^{l}$ : is just concatenation. -
$A$ : is a chosen matrix so that multiplication by$A$ is very fast:
then the calculation of
where
The tempering operation to tamper a state register to the produced
where
IMPORTANT: Tempering step is reversible.
Update latter...