How to write a random number generator and is it possible to predict Math.random?

Have you ever wondered how Math.random () works? What is a random number and how does it work? And submit a question at the interview - write your random number generator in a couple of lines of code. And so, what is it, an accident and is it possible to predict it?

I am very fascinated by various IT puzzles and puzzles, and a random number generator is one such task. Usually in my telegram channel I parse all sorts of puzzles and different tasks from interviews. The task about the random number generator gained great popularity and I wanted to perpetuate it in the depths of one of the authoritative sources of information - I mean, here, on Habré.
')
This material will be useful to all those frontendors and Node.js developers who are at the cutting edge of technology and want to get into the project / startup blockchain, where questions about security and cryptography, even at a basic level, are asked even from front-end vendors.

Pseudorandom number generator and random number generator

In order to get something random, we need a source of entropy, a source of some chaos from which we will use to generate randomness.

This source is used to accumulate the entropy and then obtain from it the initial value (initial value, seed), which is necessary for random number generators (RNG) to generate random numbers.

The Pseudo-Random Number Generator uses a single initial value, from which its pseudo-randomness follows, while the Random Number Generator always generates a random number, having a high-quality random variable at the beginning, which is taken from various sources of entropy.

Entropy is a measure of disorder. Informational entropy is a measure of uncertainty or unpredictability of information.

It turns out that in order to create a pseudo-random sequence we need an algorithm that will generate some sequence based on a certain formula. But such a sequence can be predicted. Nevertheless, let's imagine how we could write our own random number generator if we didn’t have Math.random ()

PRNG has some algorithm that can be played.
RNG is getting numbers completely from any noise, the ability to calculate which tends to zero. At the same time in the RNG there are certain algorithms for leveling the distribution.

We invent our algorithm PRNG

The pseudorandom number generator (PRNG, pseudorandom number generator, PRNG) is an algorithm that generates a sequence of numbers whose elements are almost independent of each other and obey a given distribution (usually uniform).

We can take a sequence of some numbers and take from them the modulus of a number. The simplest example that comes to mind. We need to think about which sequence to take and the module from what. If just in the forehead from 0 to N and module 2, then we get the generator 1 and 0:

function* rand() { const n = 100; const mod = 2; let i = 0; while (true) { yield i % mod; if (i++ > n) i = 0; } } let i = 0; for (let x of rand()) { if (i++ > 100) break; console.log(x); } 

This function generates the sequence 01010101010101 ... and it is impossible to call it even a pseudo-random. For a generator to be random, it must pass the test for the next bit. But we are not worth such a task. Nevertheless, even without any tests, we can predict the next sequence, which means that such an algorithm does not fit in the forehead, but we are in the right direction.

And what if we take some well-known, but non-linear sequence, for example, the number PI. And as a value for a module, we’ll take something else 2 rather than 2. You can even think about the changing value of the module. The sequence of digits in the number Pi is considered random. The generator can work using Pi numbers, starting from some unknown point. An example of such an algorithm, with a sequence based on PI and with a variable module:

 const vector = [...Math.PI.toFixed(48).replace('.','')]; function* rand() { for (let i=3; i<1000; i++) { if (i > 99) i = 2; for (let n=0; n<vector.length; n++) { yield (vector[n] % i); } } } 

But in JS the PI number can only be displayed up to 48 characters and no more. Therefore, it is still as easy to predict such a sequence, and each launch of such a generator will always give the same numbers. But our generator has already started to show numbers from 0 to 9.

We received a number generator from 0 to 9, but the distribution is very uneven and each time it will generate the same sequence.

We can take not the number Pi, but time in the numerical representation and consider this number as a sequence of numbers, and in order that the sequence does not repeat each time, we will read it from the end. Overall, our algorithm of our PRNG will look like this:

 function* rand() { let newNumVector = () => [...(+new Date)+''].reverse(); let vector = newNumVector(); let i=2; while (true) { if (i++ > 99) i = 2; let n=-1; while (++n < vector.length) yield (vector[n] % i); vector = newNumVector(); } } // TEST: let i = 0; for (let x of rand()) { if (i++ > 100) break; console.log(x) } 

This is similar to a pseudo-random number generator. And the same Math.random () is PRNG, we'll talk about it a bit later. In this case, each time we get the first number is different.

Actually on these simple examples one can understand how more complex random number generators work. And there are even ready-made algorithms. For example, consider one of them - this is a linear congruent PRNG (LCPRNG).

Linear congruent PRNG

Linear congruent PRNG (LCPRNG) is a common method for generating pseudo-random numbers. It does not possess cryptographic security. This method consists in calculating the members of a linear recurrent sequence modulo some natural number m given by the formula. The resulting sequence depends on the choice of the starting number - i.e. seed. For different values ​​of seed, different sequences of random numbers are obtained. An example of the implementation of such an algorithm on JavaScript:

 const a = 45; const c = 21; const m = 67; var seed = 2; const rand = () => seed = (a * seed + c) % m; for(let i=0; i<30; i++) console.log( rand() ) 

Many programming languages ​​use LPRNG (but not just such an algorithm (!)).

As mentioned above, such a sequence can be predicted. So why do we need GPSU? If we talk about security, the PRNG is a problem. If we talk about other tasks, then these properties can play a plus. For example, for various special effects and graphics animations you may need to frequently call random. And here the distribution of values ​​and performance are important! Secural algorithms can not boast speed.

Another property is reproducibility. Some implementations allow you to set a seed, and this is very useful if the sequence is to be repeated. Reproduction is needed in tests, for example. And many more things exist that do not need a safe RNG.

How Math.random () works

The Math.random () method returns a pseudo-random floating-point number from the range [0, 1), that is, from 0 (inclusive) to 1 (but not including 1), which can then be scaled to the desired range. The implementation itself chooses the initial seed for the random number generation algorithm; it cannot be selected or reset by the user.

How the Math.random () algorithm works is an interesting question. Until recently, namely up to 49 Chrome, the MWC1616 algorithm was used:

 uint32_t state0 = 1; uint32_t state1 = 2; uint32_t mwc1616() { state0 = 18030 * (state0 & 0xffff) + (state0 >> 16); state1 = 30903 * (state1 & 0xffff) + (state1 >> 16); return (state0 << 16) + (state1 & 0xffff); } 

It is this algorithm that generates a sequence of pseudo-random numbers between 0 and 1.

Predict Math.random ()

What was it fraught with? There is a quest: alf.nu/ReturnTrue

It has a task:

 { let rand = Math.random(); function random4(x) { return rand === x; } } random4(???) 

What needs to be entered instead of questions so that the function returns true? It seems that this is impossible. But, this is possible if you looked into the spec and saw the PRNG V8 algorithm. Roman Dvornov showed me the solution of this problem at one time:

 random4(function(){var A=18030,B=36969,F=65535,Z=16,M=Math,I=M.imul,c=M.random,M=M.pow(2,32),k,d,g=c()*M,h=c()*M;for(k=0;F^k&&(c=I(A,g>>>Z)+k++)&F^h>>>Z;);for(k=0;F^k&&(d=I(B,g&F)+k++)&F^h&F;);for(k=2;k—;g=c<<Z|d&F)c=c/A|c%A<<Z,d=d/B|d%B<<Z;return(g<0?g+M:g)/M}()) 

This code worked 70% of the time for Chrome <49 and Node.js <5. Roma Dvornov, as always, showed the wonders of magic, which is nothing but a deep understanding of the internal mechanisms of browsers. I'm still waiting for Roman to make a report based on these events or write a more detailed article.

What's going on here? The fact is that the algorithm can be predicted. To make it clearer, you can generate a random pixel image. The site has such a generator. This is what happened when the browser had the MWC1616 algorithm:



See these uniformities on the left slide? The image shows a problem with the distribution of values. The image on the left shows that the values ​​in places are strongly grouped, and in some places large fragments fall out. As a consequence, the numbers can be predicted.

It turns out that we can reverse Math.random () and predict what the number was made up on the basis of what we received at the given time. To do this, we get two values ​​via Math.random (). Then we calculate the internal state of these values. Having the internal state, we can predict the following values ​​of Math.random () without changing the internal state. We change the code so that the previous value is returned instead of the next one. Actually all this is described in the code-solution for the random4 task. But then the algorithm was changed (read the specs for details). It can be broken as soon as we have normal work with 64-bit numbers in JS. But it will be another story.

The new algorithm looks like this:

 uint64_t state0 = 1; uint64_t state1 = 2; uint64_t xorshift128plus() { uint64_t s1 = state0; uint64_t s0 = state1; state0 = s0; s1 ^= s1 << 23; s1 ^= s1 >> 17; s1 ^= s0; s1 ^= s0 >> 26; state1 = s1; return state0 + state1; } 

It can still be calculated and predicted. But so far we have no “long mathematics” in JS. You can try using TypedArray to make or use special libraries. Maybe someone will write the predictor once again. Perhaps it will be you, the reader. Who knows ;)

rypto Random Values

The Math.random () method does not provide cryptographically secure random numbers. Do not use it for anything related to security. Instead, use the Web Crypto API (a cryptography API on the Web) and the more accurate method window.crypto.getRandomValues ​​().

Example of generating a random number:

 let [rvalue] = crypto.getRandomValues(new Uint8Array(1)); console.log( rvalue ) 

But, unlike the PRNG Math.random (), this method is very resource intensive. The fact is that this generator uses system calls in the OS to access the entropy sources (mac address, CPU, temperature, etc ...).