What Has A 17th Century French Friar Got To Do With Your Smart Phone Payment?

If you want to try the method defined in the article, click [here].

What Has A 17th Century French Friar Got To Do With Your Smart Phone Payment?

If you want to try the method defined in the article, click [here].

We increasingly exist in a world where random numbers are generated for our transactions, our network connections, and in our on-line accesses. If there was any weaknesses in the generation of these, we could leave large holes in the Internet. We might even be able to predict the weekly lottery, as here.

One of the most popular pseudorandom number generators (PRNGs) is the Mersenne Twister. It was created by Makoto Matsumoto and Takuji Nishimur in 1997 and it derives its name from its period length — which is the number of values before the sequence repeats — and which is a Mersenne prime. This article contains one of the most commonly used version of the Mersenne Twister algorithm which is MT19937 and generates a 32-bit word length (using the Mersenne prime of 2¹⁹⁹³⁷−1. The method is named after Marin Mersenne and who was a 17th Century French Minim friar. His main contribution included his investigation of prime numbers, along with being seen as the father of acoustics.

The Mersenne Twister method is by far the most popular method of creating random numbers, and is used extensively within many libraries including within mt_rand() in PHP and random.random() in Python.

A Mersenne prime is defined as a prime number that is one less than a power of two. The general form is M_n=2^{n−1} where n is an integer. The discovery of 2¹¹²¹²-1 was even given its own post mark:

The largest found is 2⁷⁷²³²⁹¹⁷-1, and which was discovered by Jonathan Paceon on Boxing Day in 2017 (and it only the 50th Mersenne prime to be ever found). Since 1997, the Great Internet Mersenne Prime Search (GIMPS) distributed system has been used to find new Mersenne primes.

To determine the Mersenne primes, we can try prime numbers (2,3,5,7,11…) :

The Mersenne sequence becomes:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281,
 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243,
 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 
3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 
32582657, 37156667, ..., 77232917 ...

A typical value used is 19,937.

The basic parameters are:

w: word size (in number of bits)
n: degree of recurrence
m: middle word, an offset used in the recurrence relation defining the series x, 1 ≤ m < n
r: separation point of one word, or the number of bits of the lower bitmask, 0 ≤ r ≤ w — 1
a: coefficients of the rational normal form twist matrix
b, c: TGFSR(R) tempering bitmasks
s, t: TGFSR(R) tempering bit shifts
u, d, l: additional Mersenne Twister tempering bit shifts/masks

and where 2^{nw−r−1} is a Mersenne prime. The details of the maths behind the method is [here]. The coefficients for MT19937 are:

(w, n, m, r) = (32, 624, 397, 31)
a = 9908B0DF16
(u, d) = (11, FFFFFFFF16)
(s, b) = (7, 9D2C568016)
(t, c) = (15, EFC6000016)
l = 18

The following code is taken from [here]:

class mersenne_rng(object):def __init__(self, seed = 5489):
        self.state = [0]*624self.f = 1812433253self.m = 397self.u = 11self.s = 7self.b = 0x9D2C5680self.t = 15self.c = 0xEFC60000self.l = 18self.index = 624self.lower_mask = (1<<31)-1self.upper_mask = 1<<31

        # update stateself.state[0] = seedfor i in range(1,624):
            self.state[i] = self.int_32(self.f*(self.state[i-1]^(self.state[i-1]>>30)) + i)

    def twist(self):for i in range(624):
            temp = self.int_32((self.state[i]&self.upper_mask)+(self.state[(i+1)%624]&self.lower_mask))
            temp_shift = temp>>1if temp%2 != 0:
                temp_shift = temp_shift^0x9908b0dfself.state[i] = self.state[(i+self.m)%624]^temp_shift
        self.index = 0

    def get_random_number(self):if self.index >= 624:
            self.twist()
        y = self.state[self.index]
        y = y^(y>>self.u)
        y = y^((y<<self.s)&self.b)
        y = y^((y<<self.t)&self.c)
        y = y^(y>>self.l)
        self.index+=1return self.int_32(y)

    def int_32(self, number):return int(0xFFFFFFFF & number)

rng = mersenne_rng(seed=123)
for i in range(10):
   print rng.get_random_number()

Here is a sample run with a seed value of 123:

If you want to try the method defined in the article, click [here].

Conclusions

Pseudorandom number generators — PRNGs — are deterministic and periodic. With their periodic nature, we repeat the random sequence for the length of all the possible outputs. So if you are watching a slot machine, you might guest that the sequence for the output will eventually repeat. With the Mersenne Twister the period is a massive 2¹⁹⁹³⁷-1, which means that it is unlikely to repeat in a reasonable time frame. An important element is thus the seed value, as, if this can be guessed, it may be possible to replicate the whole sequence.

Another possible attack is on the state machine for generating the sequence, as a PRNG is deterministic. If some of these values are discovered, it may be possible to recreate others from it.

A Cryptographically Secure PRNG (CSPNG) should never repeat its sequence (non-periodic), and uses randomness based on random events (such as the time between system interrupts). Examples of CSPNG include /dev/urandom and CryptGenRandom. A CSPNG should also be non-deterministic.