A Brief History of Random Numbers
- Transfer
“When I set out to get a really random number, I couldn’t find anything better for this than a regular dice,” Francis Galton wrote in 1890 in the journal Nature . "After the bones are shaken and thrown into the basket, they hit each other and against the walls of the basket in such an unpredictable way that even after a light throw it becomes completely impossible to determine its result."
(Dice from the time of the Roman Empire)
How can we generate a uniform sequence of random numbers? Randomness, so beautiful in its diversity, is often found in wildlife, but it was not always easy to extract artificially. The oldest of the dice were found in the Middle East, and they date back to about 24 century BC. Another example would be China, where back in the 11th century BC, smashing tortoise shell was used with a blow, with a further interpretation of the size of the random parts received. Centuries later, people chopped up plant stems several times and compared the sizes of the resulting parts.
But by the middle of the 40s of the XX century, humanity needed significantly more random numbers than could be obtained from throwing bones or cutting stems. American think tankRAND created a machine that was able to generate random numbers using a random pulse generator (something like electronic roulette). They started it and after some time received a sufficient number of random numbers, which they published in the form of the book “ One Million Random Numbers and One Hundred Thousand Normal Deviations ”.
You can read the book online or buy the 2001 paper reprint on Amazon . What today may seem like an absurd art project at that time was a major breakthrough. For the first time, a truly large sequence of truly random numbers has become available to scientists.
Another similar car, ERNIE, built in today's famous Bletchley Park in the 40s of the 20th century, was used to generate random numbers in the British Premium Bond lottery . In order to dispel fears about the randomness and honesty of the results, the documentary “The Importance of Being ERNIE” was even removed. Today you can watch it on Youtube:
In 1951, randomness was finally formalized and embodied in a real Ferranti Mark 1 computer , which came with a built-in random data generator based on shot noise and an instruction that allowed you to get 20 random bits. This functionality was developed by Alan Turing. His colleague Christopher Strachey used it to create a "love letter generator." Here is an example of the text that was generated by this program:
But the Turing random number generator did not make the programmers of those years happy because it introduced the factor of even greater instability into the already new and unstable computer systems. Wishing to achieve stable operation of a certain program - without debuggers and with random data - it was never possible to achieve repeatability of results. Then the following thought arose: “What if the random number generator can be represented as some deterministic function?” Then it would turn out that, on the one hand, the generated numbers would have signs of random, but on the other hand, with the same initialization of the generator, these sequences would be the same each time. This is how pseudorandom number generators (PRNGs) came about.
John von Neumann developed the PRNG in 1946. His idea was to start with a certain number, take his square, drop the numbers from the middle of the result, take the square again and drop the middle, etc. The resulting sequence, in his opinion, had the same properties as random numbers. Von Neumann's theory did not stand the test of time, because no matter what initial number you choose, the sequence generated in this way degenerates into a short cycle of repeating values, like 8100, 6100, 4100, 8100, 6100, 4100, ...
It is impossible to completely avoid cycles when we work with a determinate function whose subsequent values are based on previous ones. But what if the cycle period is so large that in practice it will no longer matter?
The mathematician Derrick Henry Lemer developed this idea in 1949 with the invention of the linear congruent method . Here is a pseudo random number generator based on the Lehmer approach and written in Javascript:
You may notice a number of “magic constants” in the code. These numbers (usually prime) were chosen in such a way as to maximize the cycle period before repeating the sequence of results. This generator uses the current time as an initial value and has a period of about 2 ^ 31. It became popular with the release of JavaScript 1.0, because at that time it did not yet have the built-in Math.random () function , and everyone wanted their banner ads to change randomly. “I would not use this algorithm for something related to security, but for many applications it is enough,” wrote Paul Houle, the author of the above code.
But the Internet just required something related to security. SSL appeared in 1995 and its implementation required a high-quality pseudo-random number generator. This led to a series of rather wild experiments in this field. If you look at patents related to the generation of random numbers issued in those days, you get the feeling that you are looking at modernized attempts to build the first aircraft.
Most popular processors in the 90s did not have special instructions for generating random numbers, so choosing a good starting value for a pseudo-random number generator was very important. This resulted in security issues when Phillip Hallam-Baker discovered that in the Netscape browser (dominant at the time), the SSL implementation used a combination of the current time and its process ID to initialize the PRNG. He showed how a hacker can easily pick up this value and decrypt SSL traffic. Guessing the initial value of the pseudo-random number generation algorithm is still a popular attack, although over the years it has become slightly more complicated. Here is an example of a successful attack published on Hacker News in 2009.
In 1997, programmers were limited in their ways of obtaining truly random numbers, so the SGI team created LavaRand, which consisted of a webcam aimed at a couple of lava lamps that were next to the table. The image from this camera was an excellent source of entropy - a Real Random Number Generator, the same as Turing's. But this time it turned out to generate 165 Kb of random numbers per second. The invention was immediately patented .
Most experiments in this area have not stood the test of time, but one PRNG, named the Mersenna Whirlwind and developed in 1997 by Makoto Matsumoto and Takuji Nishimura, was able to hold the palm. It combined performance and quality of results, which allowed it to quickly spread to many languages and frameworks. The Mersenne vortex is a round shift register with generalized returns and generates a deterministic sequence with a huge cycle period. In the current implementation, the period is 2¹⁹⁹³⁷− 1, and it is this implementation that is included in most programming languages today.
In 1999, Intel added a hardware random number generator to the i810 chipset. This was good, because this implementation gave really random numbers (based on temperature noise), but it didn’t work as fast as the software PRNGs, so most crypto applications still use the PRNPs, which now, at least, can be initialized with the initial value from the hardware random number generator.
This leads us to the concept of a cryptographically secure pseudo random number generator (KBGPSCH). (Oh, these abbreviations! It's not surprising that computer science seems boring to some people.) KBHPSCs became very popular in the SSL era. What are the requirements of the CBHRHF? Well, here's a 131-page documentwith these requirements, have fun. As you already understand, there are a lot of requirements. For example, the same Mersenne Whirlwind does not satisfy them, since having a sufficiently large sequence of numbers generated by it, you can guess the next number.
In 2012, INTEL added RDRAND and RDSEED instructions to its chips, allowing you to get real random numbers based on the same temperature fluctuations, but now at speeds up to 500 Mb / s, which should make the use of software PRNs unnecessary. But rumors and doubts about the honesty of these instructions roam in society. Do they have a specially made bookmark for the NSA? No one can say for sure. Rather, someone probably can, but he certainly will not post about it on Twitter.
(Random data received from a hardware random number generatorRedoubler )
In recent years, hardware random number generators from third-party manufacturers and even completely open (both in terms of software and hardware) have also begun to appear. The strength of these products is precisely in openness: you can study them yourself and even build houses yourself from among the generally available components. Examples are REDOUBLER and Infinite Noise TRNG .
Today, people are still discussing which particular random number generator should be used in a particular system, OS kernel, programming language, cryptographic library, etc. There are many options for algorithms, sharpened by speed, memory saving, security. And each of them is constantly attacked by hackers and security experts. But for everyday non-security tasks, you can very well rely on data from / dev / random or the rand () function , available on most platforms. This will give you a sufficiently large and random sequence of data that would make Alan Turing happy in due time.
(Dice from the time of the Roman Empire)
How can we generate a uniform sequence of random numbers? Randomness, so beautiful in its diversity, is often found in wildlife, but it was not always easy to extract artificially. The oldest of the dice were found in the Middle East, and they date back to about 24 century BC. Another example would be China, where back in the 11th century BC, smashing tortoise shell was used with a blow, with a further interpretation of the size of the random parts received. Centuries later, people chopped up plant stems several times and compared the sizes of the resulting parts.
But by the middle of the 40s of the XX century, humanity needed significantly more random numbers than could be obtained from throwing bones or cutting stems. American think tankRAND created a machine that was able to generate random numbers using a random pulse generator (something like electronic roulette). They started it and after some time received a sufficient number of random numbers, which they published in the form of the book “ One Million Random Numbers and One Hundred Thousand Normal Deviations ”.
You can read the book online or buy the 2001 paper reprint on Amazon . What today may seem like an absurd art project at that time was a major breakthrough. For the first time, a truly large sequence of truly random numbers has become available to scientists.Another similar car, ERNIE, built in today's famous Bletchley Park in the 40s of the 20th century, was used to generate random numbers in the British Premium Bond lottery . In order to dispel fears about the randomness and honesty of the results, the documentary “The Importance of Being ERNIE” was even removed. Today you can watch it on Youtube:
In 1951, randomness was finally formalized and embodied in a real Ferranti Mark 1 computer , which came with a built-in random data generator based on shot noise and an instruction that allowed you to get 20 random bits. This functionality was developed by Alan Turing. His colleague Christopher Strachey used it to create a "love letter generator." Here is an example of the text that was generated by this program:
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.But the Turing random number generator did not make the programmers of those years happy because it introduced the factor of even greater instability into the already new and unstable computer systems. Wishing to achieve stable operation of a certain program - without debuggers and with random data - it was never possible to achieve repeatability of results. Then the following thought arose: “What if the random number generator can be represented as some deterministic function?” Then it would turn out that, on the one hand, the generated numbers would have signs of random, but on the other hand, with the same initialization of the generator, these sequences would be the same each time. This is how pseudorandom number generators (PRNGs) came about.
John von Neumann developed the PRNG in 1946. His idea was to start with a certain number, take his square, drop the numbers from the middle of the result, take the square again and drop the middle, etc. The resulting sequence, in his opinion, had the same properties as random numbers. Von Neumann's theory did not stand the test of time, because no matter what initial number you choose, the sequence generated in this way degenerates into a short cycle of repeating values, like 8100, 6100, 4100, 8100, 6100, 4100, ...
It is impossible to completely avoid cycles when we work with a determinate function whose subsequent values are based on previous ones. But what if the cycle period is so large that in practice it will no longer matter?
The mathematician Derrick Henry Lemer developed this idea in 1949 with the invention of the linear congruent method . Here is a pseudo random number generator based on the Lehmer approach and written in Javascript:
// The Central Randomizer 1.3 (C) 1997 by Paul Houle (paul@honeylocust.com)
// See: http://www.honeylocust.com/javascript/randomizer.html
rnd.today=new Date();
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);
};You may notice a number of “magic constants” in the code. These numbers (usually prime) were chosen in such a way as to maximize the cycle period before repeating the sequence of results. This generator uses the current time as an initial value and has a period of about 2 ^ 31. It became popular with the release of JavaScript 1.0, because at that time it did not yet have the built-in Math.random () function , and everyone wanted their banner ads to change randomly. “I would not use this algorithm for something related to security, but for many applications it is enough,” wrote Paul Houle, the author of the above code.
But the Internet just required something related to security. SSL appeared in 1995 and its implementation required a high-quality pseudo-random number generator. This led to a series of rather wild experiments in this field. If you look at patents related to the generation of random numbers issued in those days, you get the feeling that you are looking at modernized attempts to build the first aircraft.
Most popular processors in the 90s did not have special instructions for generating random numbers, so choosing a good starting value for a pseudo-random number generator was very important. This resulted in security issues when Phillip Hallam-Baker discovered that in the Netscape browser (dominant at the time), the SSL implementation used a combination of the current time and its process ID to initialize the PRNG. He showed how a hacker can easily pick up this value and decrypt SSL traffic. Guessing the initial value of the pseudo-random number generation algorithm is still a popular attack, although over the years it has become slightly more complicated. Here is an example of a successful attack published on Hacker News in 2009.
In 1997, programmers were limited in their ways of obtaining truly random numbers, so the SGI team created LavaRand, which consisted of a webcam aimed at a couple of lava lamps that were next to the table. The image from this camera was an excellent source of entropy - a Real Random Number Generator, the same as Turing's. But this time it turned out to generate 165 Kb of random numbers per second. The invention was immediately patented .
Most experiments in this area have not stood the test of time, but one PRNG, named the Mersenna Whirlwind and developed in 1997 by Makoto Matsumoto and Takuji Nishimura, was able to hold the palm. It combined performance and quality of results, which allowed it to quickly spread to many languages and frameworks. The Mersenne vortex is a round shift register with generalized returns and generates a deterministic sequence with a huge cycle period. In the current implementation, the period is 2¹⁹⁹³⁷− 1, and it is this implementation that is included in most programming languages today.
In 1999, Intel added a hardware random number generator to the i810 chipset. This was good, because this implementation gave really random numbers (based on temperature noise), but it didn’t work as fast as the software PRNGs, so most crypto applications still use the PRNPs, which now, at least, can be initialized with the initial value from the hardware random number generator.
This leads us to the concept of a cryptographically secure pseudo random number generator (KBGPSCH). (Oh, these abbreviations! It's not surprising that computer science seems boring to some people.) KBHPSCs became very popular in the SSL era. What are the requirements of the CBHRHF? Well, here's a 131-page documentwith these requirements, have fun. As you already understand, there are a lot of requirements. For example, the same Mersenne Whirlwind does not satisfy them, since having a sufficiently large sequence of numbers generated by it, you can guess the next number.
In 2012, INTEL added RDRAND and RDSEED instructions to its chips, allowing you to get real random numbers based on the same temperature fluctuations, but now at speeds up to 500 Mb / s, which should make the use of software PRNs unnecessary. But rumors and doubts about the honesty of these instructions roam in society. Do they have a specially made bookmark for the NSA? No one can say for sure. Rather, someone probably can, but he certainly will not post about it on Twitter.
(Random data received from a hardware random number generatorRedoubler )
In recent years, hardware random number generators from third-party manufacturers and even completely open (both in terms of software and hardware) have also begun to appear. The strength of these products is precisely in openness: you can study them yourself and even build houses yourself from among the generally available components. Examples are REDOUBLER and Infinite Noise TRNG .
Today, people are still discussing which particular random number generator should be used in a particular system, OS kernel, programming language, cryptographic library, etc. There are many options for algorithms, sharpened by speed, memory saving, security. And each of them is constantly attacked by hackers and security experts. But for everyday non-security tasks, you can very well rely on data from / dev / random or the rand () function , available on most platforms. This will give you a sufficiently large and random sequence of data that would make Alan Turing happy in due time.