文件列表:

code (0, 2020-03-31)
code\clone_mt19937.py (1173, 2020-03-31)
code\crack_seed_mt19937.py (1186, 2020-03-31)
code\implement_mt19937.py (1210, 2020-03-31)

# MT19937 Implementing and breaking the MT19937 Mersenne Twister pseudorandom number generator; based on the challenges #21 to #23 of [cryptopals](https://github.com/anneouyang/cryptopals) - [Part I: Implement the MT19937 Mersenne Twister RNG](https://github.com/anneouyang/MT19937#part-i-implement-the-mt19937-mersenne-twister-rng) - [Part II: Crack an MT19937 seed](https://github.com/anneouyang/MT19937#part-ii-crack-an-mt19937-seed) - [Part III: Clone an MT19937 RNG from its output](https://github.com/anneouyang/MT19937#part-iii-clone-an-mt19937-rng-from-its-output)
## Overview The Mersenne Twister is a pseudorandom number generator using a Mersenne prime (a prime number one less than a power of two: ) as its period length. MT19937 uses the Mersenne prime . C++11 provides an implementation of [`std::mt19937`](http://www.cplusplus.com/reference/random/mt19937/) designed to replace `rand()` for several reasons: 1. MT19937 provides better pseudorandomness. 2. MT19937 has a longer period, which is . 3. MT19937 is able to generate random numbers from a larger range.
## Part I: Implement the MT19937 Mersenne Twister RNG ### A Simplified Explanation of the Algorithm #### High Level Overview A state of a Mersenne Twister is an array of *n* values of *w* bits each. The array is initialized with a *w*-bit seed value to obtain *state_0*. Note that *state_0* does not produce any outputs. State transitions are achieved by a twist function. At each state, an output (a random number) can be obtained by . A state allows you to output *n* numbers before transitioning to the next state. In the 32-bit MT19937, *w* = `32` and *n* = `624`. #### Initialization The initialization function takes in a seed and generates the first state. Let - *f* be a constant parameter; *f* = `1812433253` - *X* be the state array  = seed = lowest *w* bits of () for  #### Twist Function The twist function is called every *n* numbers to achieve the state transition. Let - *m* be an offset where 1 <= *m* < *n*; *m* = `397` - *r* be the number of bits of the lower bitmask where 0 <= *r* <= *w* - 1; *r* = `31` - *a* be the coefficients of the rational normal form twist matrix; a = `0x9908B0DF` - *A* be the twist transformation in the rational normal form  The series is defined by the recurrence relation  where Note because *A* is in the rational normal form, the multiplication can be efficiently expressed as  where  Is the lowest order bit of x #### Temper Function The tempering function returns a random number from a state and calls the twist function every *n* numbers. Let - *y* be a temporary intermediate value - *x* be the next value from the series - *z* be the value returned from the algorithm - *d, b, c* be TGFSR(R) tempering bitmasks; *d* = `0xFFFFFFFF`, *b* = `0x9D2C5680`, *c* = `0xEFC60000` - *u, s, t, l* be TGFSR(R) tempering bit shifts; *u* = `11`, *s* = `7`, *t* = `15`, l = `18` The tempering operations are defined as *y* = *x* ((*x* >> *u*) & *d*) *y* = *y* ((*y* << *s*) & *b*) *y* *=* y ((*y* << *t*) & *c*) *z* = *y* (*y* >> *l*) ### Implementation The code can be found [here](/code/implement_mt19937.py).
## Part II: Crack an MT19937 seed ### The Setup - Wait a random number of seconds between `min_sleep_time` and `max_sleep_time`. - Seeds the RNG with the current Unix timestamp. - Waits a random number of seconds again. - Returns the first 32 bit output of the RNG. Guess the seed from the output of the RNG. ### Idea Try all the possible seed values from (current time - max time) to (current time - min time). If the seed produces an RNG that generates the same output as the given RNG, it's likely that the seed has been recovered. This example illustrates a vulnerability from using an imprecise clock as the seed, and it has an easy fix by seeding with a more precise clock. In C++, for example, the use of`std::chrono::system_clock::now().time_since_epoch().count()` is preferable to `time(NULL)` as the seed of an RNG. ### Implementation See code [here](/code/crack_seed_mt19937.py) for an implementation of the set up and a comparison of the two seeds (actual & guessed).
## Part III: Clone an MT19937 RNG from its output ### Idea After observing *n* numbers, it is possible to predict all future iterations by reconstructing the internal state of the RNG, since the tempering function used to produce outputs is bijective and *invertible*. (However, this wouldn't work for the cryptographically secure variant CryptMT) Inverting the temper transform involves applying the inverse of each operation of the tempering function in reverse order. Examine the code segment from the tempering function: ```python y = y ^ ((y >> MT19937.u) & MT19937.d) y = y ^ ((y << MT19937.s) & MT19937.b) y = y ^ ((y << MT19937.t) & MT19937.c) y = y ^ (y >> MT19937.l) ``` Note that there are essentially two types of operations: - Shift left + bitwise and - Shift right + bitwise and ### Inverting the (shift left + bitwise and) operation For an operation  rewrite the forward operation in terms of individual bits . There are two cases: - Case 1, *if i + a >= w*:  - Case 2, *if i + a < w:*  The inverses for the two cases are then: - Case 1:  - Case 2:  Inverse the operation bit by bit starting from the trivial bits in Case 1. ### Inverting the (shift right + bitwise and) operation The inverse of the right shift operation  is symmetrical: - Case 1, *if i < a*:  - Case 2, *if i >= a*:  ### Implementation See an efficient implementation that uses the symmetry and operations on bits [here](/code/clone_mt19937.py).
## References - https://en.wikipedia.org/wiki/Mersenne_Twister - http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：