Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How Do Computers Generate Random Numbers?

digitalbunker.dev

Post reply on HN
Print view View original

31–40 of 52 posts

Re: How Do Computers Generate Random Numbers?

#31

Post by blauditore »

lsc36 wrote: post #13

1. You don't turn PRNG into "true" RNGs simply by picking seeds from environmental randomness. The seed is just the initial state, as long as the output is generated by a deterministic algorithm, by definition it's a PRNG. At the very best you can make a CSPRNG, but not a "true" RNG. 2. The dice roll example is not uniform distribution, I think this is a common pitfall when generating random integers of a range. `ran…

Re 2.: OTOH, the bias is extremely tiny, there's only 2 out of 2^31 cases which are problematic, or one in a billion. A generic RNG obviously shouldn't do it this way, but for most applications it would be good-enough really.

Re: How Do Computers Generate Random Numbers?

#32

Post by jfindley »

cm2187 wrote: post #23

Is a hardware random number generator that would use environment or electrical sensors to generate noise expensive or hard to manufacture? I would assume this should be part of any standard motherboard given the importance of cryptography. Or does it create an attack vector?

Cryptography doesn't depend on random numbers for its random seed. It depends on unpredictable numbers. These are not the same thing. As long as no-one can predict what the next number will be it doesn't matter how "random" they are. TFA is sufficiently vague it's unclear if the author understands this.

The more I read it, the more confused the article appears to be (e.g. mersenne twister is NOT a good example of a modern or high quality PRNG). For more about secure random numbers in Linux, I'd suggest reading [0].

0: https://buttondown.email/cryptography-dispatches/archive/cry...

Re: How Do Computers Generate Random Numbers?

#33

Post by teddyh »

lsc36 wrote: post #13

1. You don't turn PRNG into "true" RNGs simply by picking seeds from environmental randomness. The seed is just the initial state, as long as the output is generated by a deterministic algorithm, by definition it's a PRNG. At the very best you can make a CSPRNG, but not a "true" RNG. 2. The dice roll example is not uniform distribution, I think this is a common pitfall when generating random integers of a range. `ran…

To make a dice roll uniform, wouldn’t it be easier to do randomNumber % 8 and only use it if it is from 0 to 5, and discard and re-roll otherwise?

(Since we can reasonably assume that randomNumber is a binary number, and thus would be balanced over 8 values instead of 6.)

Re: How Do Computers Generate Random Numbers?

#34

Post by lsc36 »

blauditore wrote: post #31
lsc36 wrote: post #13

1. You don't turn PRNG into "true" RNGs simply by picking seeds from environmental randomness. The seed is just the initial state, as long as the output is generated by a deterministic algorithm, by definition it's a PRNG. At the very best you can make a CSPRNG, but not a "true" RNG. 2. The dice roll example is not uniform distribution, I think this is a common pitfall when generating random integers of a range. `ran…

Re 2.: OTOH, the bias is extremely tiny, there's only 2 out of 2^31 cases which are problematic, or one in a billion. A generic RNG obviously shouldn't do it this way, but for most applications it would be good-enough really.

The article claims that "it is indeed a uniform distribution" so I wanted to point it out.

Re: How Do Computers Generate Random Numbers?

#35

Post by lsc36 »

teddyh wrote: post #33
lsc36 wrote: post #13

1. You don't turn PRNG into "true" RNGs simply by picking seeds from environmental randomness. The seed is just the initial state, as long as the output is generated by a deterministic algorithm, by definition it's a PRNG. At the very best you can make a CSPRNG, but not a "true" RNG. 2. The dice roll example is not uniform distribution, I think this is a common pitfall when generating random integers of a range. `ran…

To make a dice roll uniform, wouldn’t it be easier to do randomNumber % 8 and only use it if it is from 0 to 5, and discard and re-roll otherwise? (Since we can reasonably assume that randomNumber is a binary number, and thus would be balanced over 8 values instead of 6.)

That depends on the modulus being divisible by 8, which is not always the case. A common example is modulus = 2^31 - 1 [0] which is prime.

[0] https://en.wikipedia.org/wiki/Linear_congruential_generator#...

Re: How Do Computers Generate Random Numbers?

#36

Post by rurban »

benibela wrote: post #28
Straw wrote: post #18

Earlier quoted context omitted.

Its slow, large, and statistically worse than modern PRNGs- and jumping ahead takes longer and a more complicated algorithm. Even a truncated 128-bit LCG has far better properties. See https://www.pcg-random.org/index.html The homepage might come across as a a little overzealous (for example ChaCha quality listed as good rather than excellent), but generally has good points.

However, this page claims PCG is rather bad: http://pcg.di.unimi.it/pcg.php They recommend to use their xoshiro PRNG.

Xoshiro ist only fast, nothing else. PCG has much better properties. Fast is not everything.

But there exist some new and very fast PRNG's which are fast and extremely good. Almost TRNG, wyrand eg.

Re: How Do Computers Generate Random Numbers?

#37

Post by UncleMeat »

jfindley wrote: post #32
cm2187 wrote: post #23

Is a hardware random number generator that would use environment or electrical sensors to generate noise expensive or hard to manufacture? I would assume this should be part of any standard motherboard given the importance of cryptography. Or does it create an attack vector?

Cryptography doesn't depend on random numbers for its random seed. It depends on unpredictable numbers. These are not the same thing. As long as no-one can predict what the next number will be it doesn't matter how "random" they are. TFA is sufficiently vague it's unclear if the author understands this. The more I read it, the more confused the article appears to be (e.g. mersenne twister is NOT a good example of a m…

I wouldn't be so universal with this statement.

Some cryptosystems really do need uniform randomness (ECDSA) rather than just negligible probability of choosing values. Other cryptosystems depend on not reusing values, though the values could be predictable. Sometimes there are subtle shifts in these needs based on modes (AES/CBC vs AES/GCM is a good example).

Re: How Do Computers Generate Random Numbers?

#38

Post by ImaCake »

Animats wrote: post #10
shadowprofile77 wrote: post #5

Just out of layman's curiosity, what would be the problem or difficulty of somehow connecting a more compact type of radio telescope that detects some level of cosmic background radiation and hooking that up to a computer. Would this not be a guaranteed way of generating truly random numbers for any need flawlessly? I know that serious radio telescopes cost way more than any random person could afford to pay but I've…

A small radiation source works well, although the data rate is low.[1] The idea is to count the number of events (beta particles here) per time interval. Do this twice. If count A > count B, output a 1. If count A Don't use the low-order bit of the count. That has a bias. [1] https://www.fourmilab.ch/hotbits/

That is a fantastic resource. It never occured to me that such a thing would exist, but now that I know it does, I find it hard to think of how it wouldn't - since so much of the internet would rely on these kind of tricks to keep working.

Only practical use for me would be to confound markers trying to reproduce my RNG's in statistics assignments.

Re: How Do Computers Generate Random Numbers?

#39

Post by ImaCake »

For those interested, one can get from a uniform distribution to pretty much any defined statistical distribution using just the uniform random number generator and the inverse cumulative distribution function of the desired random distribution. A useful trick for non-standard distributions with no function available in your prefered language.

Example from matlab: https://www.mathworks.com/help/stats/generate-random-numbers...

Re: How Do Computers Generate Random Numbers?

#40

Post by benibela »

Straw wrote: post #29
benibela wrote: post #28

Earlier quoted context omitted.

However, this page claims PCG is rather bad: http://pcg.di.unimi.it/pcg.php They recommend to use their xoshiro PRNG.

That author has a history of extreme bias and almost-vindictive personal attacks on the author of PCG. See the reddit comments: https://www.reddit.com/r/programming/comments/8jbkgy/the_wra... And the PCG author's response: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html For example, for one of his arguments, he specifically chose a generator called pcg32_once_insecure, which the PCG author does not recom…

Well, I had only skimmed the page

But I am using xoshiro in my projects, because I thought xor was simpler than multiplication.

Post reply on HN