from Hacker News

How do computers generate random numbers?

by sunny--tech on 9/8/21, 3:16 PM with 78 comments

by betwixthewires on 9/8/21, 4:10 PM
It's a good introductory write up, but there are 3 things about it that frustrated me to no end.
> "As a human, I can do this very easily. 100101011010010110001101 There, I just did it.
No, you didn't. That number is most certainly not random, there are biases in it, you just don't know there are. Your mind is not random. This is why we use dice and not people to generate random bits.
> What do you mean by “kind of random number”? Aren’t all random numbers the same. Not really. There are two primary types of random number generators.
I growled audibly at this one. Random numbers should all be the same. In quality, not quantity, of course. There should be no discernible difference. There is one kind of random number, only different types of generators, with a PRNG if the seed is provably destroyed there should be absolutely no way to distinguish between a number generated by a PRNG and a TRNG.
> The computer hardware isn’t the only source of entropy. The user’s own mouse and keyboard movements can be used as well.
No. These movements are not random. Similar to my first gripe, your brain is not random. We used to use this approach to generate entropy and now we don't because this is understood, "random" user inputs should absolutely never be used to generate randomness in anything security related.
> Despite the benefits of CSPRNGs, as with everything else in the tech industry, security can never be guaranteed.
I'm glad you pointed this out. Everything in cryptography is based on unproven axioms, this is an important point that people should understand, it could be that P=NP, it could be that an algorithm exists to factor numbers to primes, we think not but really we don't know.
by xkeysc0re on 9/8/21, 3:31 PM
Writing your own random number generator can be a lot of fun. Lots of sources of entropy out there. Inspired by lavarand[0], I wrote an RNG in Python based on the output of the Global Conscousness Dot[1] (which is a ridiculous project in its own right). There's a lot of ways to visualize and ascertain how "random" your numbers are as well, whether plotting Pearson's with matplotlib or using a command line tool like ent[2] to calculate the degree of entropy.
[0] https://en.wikipedia.org/wiki/Lavarand
[1] https://gcpdot.com/
[2] https://manpages.ubuntu.com/manpages/bionic/man1/ent.1.html
by Someone on 9/9/21, 12:03 AM
“The most common algorithms used for PRNGs are linear congruential generators”
I doubt that is still true for ‘modern’ languages. Let’s google a few.
https://docs.microsoft.com/en-us/dotnet/api/system.random?vi... says “The current implementation of the Random class is based on a modified version of Donald E. Knuth's subtractive random number generator algorithm”. So, that’s a no.
https://rust-random.github.io/book/guide-rngs.html doesn’t appear to mention multiplicative algorithms, either.
https://developer.apple.com/documentation/swift/systemrandom... says “SystemRandomNumberGenerator is automatically seeded, is safe to use in multiple threads, and uses a cryptographically secure algorithm whenever possible.”
by SavantIdiot on 9/8/21, 3:50 PM
I've been working with the NIST 800-22 evaluation suite [1] and yes, it is very hard. There are an infinite number of tests to determine if a number is random. Ultimately it comes down to probability that it is a good RNG/PRNG and the application. Ironically, if a PRNG is good enough, it can often be BETTER than a random source (which is why RNGs have a conditioning phase).
[1] https://csrc.nist.gov/Projects/Random-Bit-Generation/Documen...
by lscharen on 9/8/21, 9:56 PM
I'll take this opportunity to link to Luc Devroye's freely available book "Non-Uniform Random Variate Generation".
http://www.nrbook.com/devroye/
An undergraduate algorithms + statistics class is sufficient to get a lot out of this book, even if it's just exposure to the wide variety of techniques for generating random numbers on a computer.
by Borrible on 9/8/21, 3:35 PM
Use leftovers. They're all over the Universe.
https://www.researchgate.net/publication/283762433_The_Cosmi...
by simonblack on 9/8/21, 10:58 PM
Two basic ways:
Computed:
NOT truly random. Way back in the late 70s, I had a BASIC program that used to output the very same set of 8-digit 'random' numbers every time the program was used.
(Unless you did a special thing the first time, to obtain a random seed to generate a different sequence of pseudo-random numbers. IIRC, it was the number of machine cycles since the last time the floppy disk was accessed.)
Hardware:
Truly random: The machine counts machine cycles with a small maximum number before it overflows and restarts at zero. The machine looks at the time difference between things like key presses, or disk-spins, or something else that varies in time.
No matter how good you are the variation in time between your key-presses is never the same at the very small time-flow level. That number is used as a seed to a pseudo-random generator.
by dragontamer on 9/8/21, 3:33 PM
A modern "pseudo random number" is simply a sequence of numbers that visits the state-space in an order that's difficult to detect with modern statistical tests. (Chi-squared, among others). See PractRand or TestU01 as two packages for testing these sequences. That is to say: instead of the sequence "0, 1, 2, 3, 4, 5... 4294967296... 0", your RNG will do some other sequence.
Yes, "0, 3, 6, 9... 4294967295, 2, 5, 8... 4294967294, 1, 4, 7... 4294967293, 0, 3..." is a RNG of sorts, but an example of a really, really bad one that would instantly fail most statistical tests. :-) But conceptually, the Mersenne Twister, LCGRNG, and LSFR all accomplish this. Its a "reordering" of the sequence. That's it.
A "cryptographic random number" just adds a few additional tests to the pool of statistical tests. In particular: differential cryptography gets into the nitty gritty about which bits can predict the results of other bits. You have to assume that the "opponent" is willing to use extraordinary amounts of computing power to detect patterns.
If bit#25 has a 51% correlation with bit#30, you fail cryptographic random numbers. You need to be within 2^128 (at least) worth of security or more. That means a near 50% correlation (maybe 50.00000000001% is fine) between bits and future bits.
For example: the sequence: {AES(0, key), AES(1, key), AES(2, key)... AES(2^128, key), AES(0, key)...} is a cryptographically secure random number generator. The sequence will loop after its 128 bits of state are exhausted. If the "opponent" doesn't know the key, the bitwise correlations are cryptographically sound (thanks to the hard work of the engineers behind AES).
A true random number generator is just a cryptographic number generator applied to a truly random seed. White noise generators are a well known electronic-engineer trick: resistor noise is everywhere but is rather small (but you can build a white-noise generator from Johnson Nyquist noise if you really wanted). More likely, you use shot-noise from a transistor junction, at least at the hobbyist level.
Intel / AMD have true random number generators from some kind of electrical noise generator on every CPU, which feeds into cryptographic random number generators.
There are other sources of noise: radiation is a well known one but I'm not sure if they're practical.
There's a "speed limit" to white noise generators. You only can extract so much entropy from them in a given time (ex: Remember: CPUs operate at 4GHz, or 0.25 nanoseconds per clock tick). Cryptographic random number generators "stretch" the true seed of randomness, while the white-noise generator continues to grab more entropy.
by rrauenza on 9/8/21, 4:58 PM
I'm trying to remember a technique based on listening to static or whitenoise and taking the least significant bit. You then take that stream of bits and postprocess it by looking for bit changes and don't use them directly.
That's a vague and I'm sure inaccurate description, but it isn't enough for me to google it ... anyone know what I'm referring to?
by mjreacher on 9/8/21, 6:47 PM
"Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin."
- John von Neumann
by hdivider on 9/8/21, 3:40 PM
PCIe and USB cards like this are available, generating TRNs using quantum optics:
https://www.idquantique.com/random-number-generation/product...
by anotherevan on 9/8/21, 9:32 PM
“The generation of random numbers is too important to be left to chance.” — Robert R. Coveyou
by qq4 on 9/8/21, 5:17 PM
I always wanted a Geiger counter for experiments like this.
by kerblang on 9/8/21, 5:07 PM
Did we ever resolve the flame war over /dev/random vs /dev/urandom? I recall puzzling over endless threads of no-you're-wrong
by comeonseriously on 9/8/21, 4:46 PM
Back in the day, IIRC, you could set a sound blaster to generate white noise, then use that as either random number or input to your RNG algo.
by dunefox on 9/9/21, 4:50 AM
I was asked to implement a random number generator in an interview not too long ago. This article should help...
by jason_s on 9/9/21, 5:29 AM
I lost interest at "The most common algorithms used for PRNGs are linear congruential generators."
by fnord77 on 9/8/21, 3:39 PM
I thought this was a solved problem for at least a decade with CPU instructions like `RDRAND`
by sunny--tech on 9/8/21, 3:51 PM
Link to bypass paywall: https://betterprogramming.pub/generating-random-numbers-is-a...
by abnry on 9/8/21, 4:00 PM
Obligatory XKCD: https://xkcd.com/221/
And also Dilbert: https://dilbert.com/search_results?terms=Random+Number+Gener...
by dekken_ on 9/8/21, 3:46 PM
some might say, it's impossible.
by chipuni on 9/8/21, 5:19 PM
I just use the XKCD random number generator:
https://xkcd.com/221/