Truly random numbers and pseudo-random numbers

In computer science, random numbers are divided into true random numbers and pseudorandom numbers.

Most random numbers in computers are pseudorandom. So what is a pseudo-random number?

It looks random, but its randomness has rules.

In general, a random number can be obtained by adding a set of algorithms to a random seed. One problem with this is that as long as you can get random seeds and algorithms, you can always get the same random numbers. In other words, pseudo-random numbers are also the product of some kind of mapping.

Anyone who knows a little about computers knows that a computer by itself cannot generate truly random numbers in any absolute sense.

True randomness has a premise that random samples cannot be reproduced, that is, random seeds and random algorithms cannot be reproduced to produce true randomness.

Computers have basic order and rules, and in a computer system, everything is predictable. The system itself will not generate variables, to generate true randomness usually requires variables outside the computer system, such as hardware noise as a random seed, or network IO, keyboard and mouse click speed, mouse movement speed and so on.

There is a website called Random that uses atmospheric noise to generate random numbers.

On the premise of “time is not traceable”, this can comply with the basic principle of truly random numbers: “Random samples cannot be reproduced”.

The philosophical statement that “no two leaves are exactly the same shape” can be applied to the concept of random numbers. This statement can be considered that there is no truly random number in the world. Even if the DNA is completely equal, there are still differences in latitude such as time and space. And this view is only in three dimensions. The differences are even greater in higher dimensions.

In fact, this question can be overturned, I think “there are two leaves of the same shape”. The universe itself is also a system, but the system is too complex for human beings to predict and interfere with. No one can say whether the universe moves in order or disorder. I believe, philosophically and physically, that the universe is orderly and that entropy has an end.

But the two views are not contradictory. I can also argue that there are no absolute truly random numbers in the world, only relative truly random numbers.

If technology reaches the point where it can manipulate time, space, and even higher dimensions, what we currently think of as “unrepeatable random samples” will become reproducible.

As they say in cryptography, there is no such thing as a perfectly secure password. It’s just that computers aren’t fast enough. If a password takes 100 years to crack, we can assume it’s relatively secure.

In general, what we call truly random numbers are numbers that conform to the requirements of cryptography, not absolute random numbers.

In fact, pseudo-random numbers work in most scenarios, so what’s the point of truly random numbers?

In addition to cryptography, lotteries, lotteries, games and other fields are the main application scenarios of true random numbers.

I remember playing a game around 2008. There was a set of forging equipment in the game. One item was rated 0-10 stars, and the success rate of forging decreased as the star rating increased. There were a lot of crafting tips on game forums at the time, like a few minutes or seconds tomorrow, where you could click continuously to increase your crafting rate. Later, there were a number of game merchants who relied on crafting equipment for revenue. I didn’t know what was going on. As it turned out, the group presumably had obtained the source code for the game’s crafting equipment and identified the random seeds and algorithms used in the program. Random seeds should be time-stamped, so they can test future times to predict when crafting will succeed at some point in the future.

In addition to crafting rates, there are many chests in the game that can spawn different items. There is also a random mechanic, which can be more complex and has a low success rate, so there are fewer tutorials. But there are still plenty of game merchants who monetize by opening treasure chests at a high rate through scripting. For example, spend 100 yuan to buy 100 treasure boxes, and use the script to automatically open the box at a specific time. Although it cannot guarantee the highest value of the props every time, it can also open the props worth 500-800 yuan on a high probability. Then go buy the chest and repeat the process.

As a result, game equipment and props are devalued, the gap between rich and poor is reduced, and everyone can buy top equipment at a very low cost. The ecology of the game was severely damaged, and the vicious circle eventually collapsed.

I had a discussion with a senior about the value and impact of technology on business.

He believes that for the most part, the success of a product does not depend on how good the technology is. I agree, but games are definitely an exception. Plugins can ruin a game.

The random seed in the game can be set more complex, more access to some random seed synthesis parameters, such as the role’s current coordinates, role ID, etc., can effectively prevent plugins, improve the threshold of being cracked.

Generating random number

Common programming languages usually provide a Random function for generating pseudo-random numbers and a Crypto function for generating truly Random numbers.

Random number in JavaScript

In JavaScript, math.random is provided to generate pseudorandom numbers that return floating point data in the range 0-1 (including 0, but not including 1).

console.log(Math.random());
Copy the code

To facilitate generating a range of integers, you can encapsulate them slightly.

function getRandomInt(min, max) {
  return Math.floor(Math.random() * Math.floor(max - min)) + min;
}
Copy the code

In addition to math. random, JavaScript also provides crypto. GetRandomValues to generate real random numbers.

const arr = new Uint32Array(2020);
crypto.getRandomValues(arr);
Copy the code

JavaScript does not provide the ability to set random seeds at the language level.

In v8’s source code for random numbers, it can be seen that random numbers are generated by MathRandom method, while random seeds are generated by MathImul method, but there is no parameter for setting the seed value.

var rngstate; // Initialized to a Uint32Array during genesis.
function MathRandom() {
  var r0 = (MathImul(18030, rngstate[0] & 0xffff) + (rngstate[0] > > >16)) | 0;
  rngstate[0] = r0;
  var r1 = (MathImul(36969, rngstate[1] & 0xffff) + (rngstate[1] > > >16)) | 0;
  rngstate[1] = r1;
  var x = ((r0 << 16) + (r1 & 0xffff)) | 0;
  // Division by 0x100000000 through multiplication by reciprocal.
  return (x < 0 ? x + 0x100000000 : x) * 2.3283064365386962890625 e-10;
}
Copy the code

Not being able to set random seeds can be uncomfortable in some situations, such as when you want to set random seeds to restore random data generation.

The solution is to rewrite Math.random and define your own algorithm for generating random numbers.

The following is an example of generating random numbers by taking the absolute value of the sine.

Math.random = function () {
  return +Math.abs(Math.sin(Math.random_seed++)).toFixed(8);
};
Math.random.seed = function (seed) {
  Math.random_seed = seed;
};
Copy the code

After setting the random seed, the ++ operation will be performed after each random operation to change the random seed.

Math.random.seed(2020);
for (let i = 0; i < 5; i++) {
  console.log(Math.random());
}
/ / 0.04406199
/ / 0.81684695
/ / 0.92675057
/ / 0.18460399
/ / 0.72726665
Copy the code

The random seed can be reset before each random run, and the random value obtained with the same random seed is always the same.

for (let i = 0; i < 5; i++) {
  Math.random.seed(2020);
  console.log(Math.random());
}
/ / 0.04406199
/ / 0.04406199
/ / 0.04406199
/ / 0.04406199
/ / 0.04406199
Copy the code

In addition, you can use the Seedrandom library.

Random number in Golang

In Golang, both math/ RAND and Crypto/RAND packages are provided.

Use Math/RAND to generate pseudo-random numbers.

package main

import (
	"fmt"
	"math/rand"
)

func main(a) {
	for i := 0; i < 5; i++ {
		fmt.Println(rand.Int())
	}
}
Copy the code

Each time you rerun the GO program, the output is always the same.

5577006791947779410
8674665223082153551
6129484611666145821
4037200794235010051
3916589616287113937
Copy the code

Rand.Int Sets the random seed as the default Source, i.e. 1.

To make the pseudo-random number more random, it is a good idea to set the random seed to some variable every time the pseudo-random number is generated. For example, it is a good idea to seed the Unix nanosecond timestamp as a variable. In addition, UUID is also a good choice, but the performance is lower. Uuid is actually a random number.

package main

import (
	"fmt"
	"math/rand"
)

func main(a) {
	for i := 0; i < 5; i++ {
        rand.Seed(time.Now().UnixNano())
		fmt.Println(rand.Int())
	}
}
Copy the code

As long as the change speed of random seed is greater than the running speed of CPU, random pseudo-randomness can be realized. While CPU clock cycles can currently be less than 1 nanosecond, code is not instruction.

If it’s seconds, it’s different.

func main(a) {
	for i := 0; i < 5; i++ {
		rand.Seed(time.Now().Unix())
		fmt.Println(rand.Int())
	}
}
Copy the code

The above code generates the same data all the time, because the CPU runs the code much faster than the second level, and time.now ().unix () values are almost always the same, with only a very, very small chance of getting an exact second switch. Because a second is a billion nanoseconds.

Crypto/RAND uses real random numbers to generate different results each time they are run.

package main

import (
	"crypto/rand"
	"fmt"
	"math/big"
)

func main(a) {
	for i := 0; i < 5; i++ {
		result, _ := rand.Int(rand.Reader, big.NewInt(100))
		fmt.Println(result)
	}
}
Copy the code

First run result:

75, 52, 19, 73, 65Copy the code

Second running result:

82, 70, 58, 81, 7Copy the code

What Crypto does is take hardware information to generate highly secure random numbers.

But the price is performance, and here’s a set of performance tests:

package main

import (
	crand "crypto/rand"
	"math/big"
	"math/rand"
	"testing"
)

func BenchmarkRand1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		rand.Intn(1000)}}func BenchmarkRand2(b *testing.B) {
	for i := 0; i < b.N; i++ {
		crand.Int(crand.Reader, big.NewInt(1000))}}Copy the code

Here are the results:

Benchmarkrand1-4 55989594 28.3 NS /op 0 B/op 0 ALlocs /op benchmarkrand2-4 4134075 354 NS /op 56 B/op 4 Allocs /opCopy the code

As you can see, the performance of generating random numbers using crypto is about 100 times slower than pseudo-random.

In the process of software development, most business scenarios do not have high requirements for security. Even if there are security requirements, performance requirements are not high in most scenarios.

Of course, there are exceptions. In some special scenarios, which have high requirements on security and performance, the solution is usually to adopt a random number generation hardware, which has chips optimized for random number generation to give consideration to security and performance. Pseudo-random number generators are usually developed based on cellular automata and LFSR, and true random number generators are usually developed based on D-flip-flop.