Alon Zakai: Big Beard

Translation: the original huziketang.com/blog/posts/… A Brief History of Random Numbers

Please indicate the source, keep the original link and author information

(Roman 12mm dice, British Museum Portable Conservation Scheme -CC BY-SA 2.0)

“Of all the things that generate random numbers, I do not think there is anything better than dice,” wrote statistician Francis Galton in Nature in 1890. Their positions and shapes in the container are so unpredictable to the outside world that it is impossible for the outside world to know what shape is inside even if the container is shaken only once.

Ancient random number

So how do you generate a uniform random sequence? Randomness is abundant and almost perfect in nature, and humans cannot accurately predict or quantify it. The earliest dice ever found (with four faces) came from a tomb in the Middle East in the 24th century BC. More recently, in China in 1100 BC, some “prophets” used the random cracking of a turtle’s shell caused by fire to make judgments about the future. A few centuries later, the I Ching divination method was developed in China, using the 49 yarrow method, which operates in a split process much like flipping a coin.

The machine generates a random number for the first touch

(From: “A Million Random Digits with 100,000 Normal Deviates”)

By the mid-1940s, the modern world needed more random numbers than dice or yarrow could handle. The RAND Corporation invented a machine that could generate large numbers of random numbers through a random pulse generator. They aggregate the numbers generated by the machine and publish them in the book “A Million Random Digits with 100,000 Normal Deviates.” It seems absurd now, but it was a breakthrough at the time. This is the first time that such a large number of high-quality random numbers have been generated and are available to the public. The book was printed by the RAND Corporation until 2001 and is now available on Amazon.

A similar machine: The Raffle machine was invented by the famous Bletchley Park WWII team in the 1940s and was used to generate the random numbers used in the UK insurance bond lottery. To quell public concerns about The fairness and accuracy of lottery machines, officials financed The production of “The Importance of Being E.R.N.I.E.”, a huge documentary film of The time. The video below is worth checking out.

(The Importance of Being E.R.N.I.E.)

Randomness was finally formalized and integrated into the Ferranti Mark 1 computer in 1951. Ferranti Mark 1 has built-in random number generation instructions, which can generate 20 random bits at a time using electrical noise. This feature was designed by Alan Turing. Christopher Strachey took advantage of this feature to write a random love letter generator. Here is an example of a love letter, using the program to generate David Link’s 2009 composite plan:

JEWEL LOVE

MY LIKING HUNGERS FOR YOUR ADORABLE INFATUATION.

YOU ARE MY EROTIC ARDOUR.: MY FOND RAPTURE. MY THIRST

SIGHS FOR YOUR INFATUATION. MY HEART SEDUCTIVELY WISHES YOUR

BREATHLESS LONGING.

YOURS CURIOUSLY

M. U. C.

(Because the above text is too leaky, the translator tries to paraphrase the following)

I have a crush on your cuteness.

You bring up all my fantasies about love.

I’m crazy about you.

Your charm fills me with longing.

My heart is with you and I can’t breathe.

Your suitor

M.U.C

But Turing’s random number instructions almost broke the heart of the developers of the day, because this randomness introduced uncertainty into an already unstable development environment. People expect consistent results in software, but software with such instructions can never get repeatable consistent results, which makes software testing almost impossible.

So what if the random number generator could be replaced by a deterministic function? What if, given certain initial conditions, the same random sequence could be generated every time? This is the pseudorandom number generator (PRNG).

Pseudo random number Generator (PRNG)

The pseudorandom number generator was created by Von Neumann in 1946. His basic idea was to start with a random number seed, square it, and take the median. Then repeat the process of squaring the resulting number and taking the median, and you get a random sequence of numbers with statistically significant attributes. This is also known as the middle square method.

Von neumann’s method did not stand the test of time, however, because no matter what random seed you started with, the sequence would eventually fall into a short loop, such as: 8100,6100,4100,8100,6100,4100… .

The number in the sequence is such a generating function that depends on the previous number, and the problem of repeating the loop above is unavoidable. But what if the loop interval is so large that it doesn’t matter in practice?

In 1949, mathematician D.H.Lehmer implemented this idea using the linear congruence generator (LCG). The following is a naive PRNG implemented by lehmer-based methods, called the Central Random Number Generator, written in JavaScript in 1995.

    // The Central Randomizer 1.3 (C) 1997 by Paul Houle ([email protected])
    // See: http://www.honeylocust.com/javascript/randomizer.html
    rnd.today=new Date(a); rnd.seed=rnd.today.getTime();function rnd() {
      rnd.seed = (rnd.seed*9301+49297) % 233280;
      return rnd.seed/(233280.0);
    };

    function rand(number) {
      return Math.ceil(rnd()*number);
    };Copy the code

Note the magic numbers in your code (9301, etc.) that are used (usually prime numbers) to maximize the repetition interval — the self-repeating loop interval mentioned above. This PRNG uses the current time as the seed value, and the repetition interval can be 2 ^ 31.

This central random generator was very popular when it was invented because JavaScript 1.0 didn’t have math.random () built into it, and Web 1.0 was a time when everyone wanted their banner ads to rotate randomly. “It works well in many cases, but you can’t use it for secret use,” says Paul Houle, a developer.

Higher requirements for PRNG

The Internet does need secrecy. SSL was born in 1995, and its encryption scheme required high quality PRNG. Its development also led directly to a period of savage innovation in PRNG. If you look back at all the random number generator patents, you might feel something like a modern version of the wave that first made airplanes.

Cpus in the mid-1990s did not have built-in instructions for generating random numbers, making good random seeds especially hard to come by at the time. This wasn’t a big problem until Philips’ Hallam-Baker discovered that Netscape, then the market leader, was seeding its SSL Web server with a “current time + a special set of ids” combination. Hallam-baker shows how an attacker can easily guess the seed value and decrypt the server traffic they receive. Seed guessing is a fairly routine attack, although it’s becoming more difficult. Here’s a very classic hack drill from Hacker News in 2009.

By 1997, computer scientists had grown tired of the limitations of generating random numbers, and a team from SGI created LavaRand, which used a webcam to take pictures of lava lamps. The image data from the camera is a real source of entropy — a Turing like real Random number generator (TRNG) — that generates random numbers at a rate of 165 kilobytes per second. True to Silicon Valley style at the time, the lava lamp platform was quickly patented.

John Walker, the founder of AutoDesk, has been pushing HotBits around the world, a “random-number as a service” application that relies on geiger counters to guarantee its quantum randomness. Random.org, founded in 1998, provides the Internet with truly random numbers. The services they offer include real coin toss randomness, dice randomness and card shuffling randomness.

Most of these algorithms have since fallen by The wayside, but a piece of software called PRNG, The Mersenne Twister, It was invented by Makoto Matsumoto and Takuji Nishimura in 1997. It strikes a perfect balance between performance and the quality of random numbers, and it has stood the test of time. The basic idea is based on a linear feedback shift register (LFSR), which produces a deterministic sequence with a very long cycle cycle, giving a cycle cycle of 2¹⁹⁹³⁷− 1. In current programming languages, this algorithm is still the default PRNG.

In 1999, a big change took place in the random number market when Intel incorporated a chip-level random number generator into its i810 chipset. As a result, the new servers are equipped with thermal noise native source random number generation capability – true random number generator (TRNG). This is great, but it’s never as fast as software PRNG, so encryption software still has to rely on pseudo-random number generators (PRNG).

Which brings us to “Password Security PRNG” (CSPRNG) (those pesky acronyms! No wonder many people think computer science is annoying). CSPRNG is particularly important for SSL. So how does CSPRNG work? Here is a 131-page paper introducing CSPRNG. Have fun reading it.

It goes without saying that CSPRNG is a strong requirement. The Mersenne rotation random number generator is not a CSPRNG because the following numbers can be predicted if a large number of previous sequences can be given.

Moving closer, in 2012, Intel added RDRAND and RDSEED instructions to TRNG with a productivity of 500MB/s. But the integrity of RDRAND has been questioned, is there some flaw in it? Or something built in for the NSA? No one knows for sure, and I’m guessing someone, somewhere, does, but they’re not going public.

Open source hardware random number generator



PEDOUBLER

In recent years, open source hardware TRNG has also gradually emerged. Their popularity is due to the transparency of their design: you can build your own wiring, or you can build it from existing components. Complete transparency makes hardware random number generation without any worries and doubts. REDOUBLER and Infinite Noise TRNG are two open source hardware random number generators. Their Github source addresses are given in the link.

At the end

Today, there is still debate over the choice of random number generation methods, in terms of operating system kernels, programming languages, and security packages such as OpenSSL or OpenSSH. There are many different algorithms that focus on different characteristics, such as speed, footprint, and security, and some security experts are still looking for ways to hack existing algorithms. But for everyday use, on most operating systems you can safely use /dev/random, or in programming languages you can use the rand() function as you please, and Alan Turing would be happy if you did.

Welcome to pay attention to my front end daha – Zhihu column, regularly release high-quality front end articles.

I’m currently working on a little book called React.js.