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

41–50 of 52 posts

Re: How Do Computers Generate Random Numbers?

#41

Post by dfox »

shadowprofile77 wrote: post #16
mceachen wrote: post #9

Earlier quoted context omitted.

Any stochastic data source may not (and almost certainly isn't) evenly distributed--it'll probably follow some normal distribution. Your PRNG that reads from your telescope would need to compensate for this. As far as using radiation to generate random numbers, check out https://www.fourmilab.ch/hotbits/

Your claim makes me a bit skeptical unless im misunderstanding something here... I'd assume that a data source of pure natural radiation would be genuinely random even if its distribution isn't even, and that using anything in your computer to compensate for it would actually do the opposite: reduce randomness with damaging bias. It reminds me of a story from Cryptonomicon in which a character mentions a secretary gr…

The signal coming from typical radiation detector is analog pulse train which you have to somehow convert into useful binary data. Simply sampling this analog value at some regular interval will create samples that are hugely biased to small number of values (and distribution between these values has more to do with measurement uncertainty than with the supposedly random phenomena you are trying to measure) so you need some kind of processing step to get useful random numbers. Typical radiation based TRNG works by comparing the analog value from the sensor against some kind of threshold (usually in analog hardware) and producing stream of digital samples from that which is then either directly passed through von Neumann whitening algorithm or converted into stream of pulse times from which only few low-order bits are taken and whitened (in fact, the end result is mostly same as whitening the bit stream directly, but timing the pulse lengths is slightly more efficient). One can argue that "quantum TRNG" based on semi-transparent mirror produces unbiased output, but that is not true in practice because of manufacturing (the mirror will not be perfectly semi-transaparent) and implementation (producing and measuring single photons is hard) constraints.

The point is that you are going to do some kind of whitening anyway and you then have essentially three choices:

1) design something which requires only von Neuman-style whitening where there still are arbitrary parameter choices hidden in the hardware

2) Design some non-trivial, but still simple entropy-extraction/whitening algorithm (ie. take 16b sample and discard top 10 and bottom one bit).

3) just take the measurement results and pass it through some kind of CSPRNG or sponge function.

Third variant is what makes most sense for most applications because mostly you either don't care about the randomness that much or you want to use it for cryptographic purposes. And if you want to do cryptography then philosophical arguments about the cryptography-based whitening not being "truly random" do not make sense, because your application itself is based on belief that the crypto primitives used are "random enough".

Re: How Do Computers Generate Random Numbers?

#42

Post by dfox »

rini17 wrote: post #17
mceachen wrote: post #9

Earlier quoted context omitted.

Any stochastic data source may not (and almost certainly isn't) evenly distributed--it'll probably follow some normal distribution. Your PRNG that reads from your telescope would need to compensate for this. As far as using radiation to generate random numbers, check out https://www.fourmilab.ch/hotbits/

If the distribution non-evenness result is, say, 1000 bits of entropy in every 1024 bits of RNG output, but we save circuitry and have simple auditable RNG then it's worth it. I'm not going to lose sleep over my RSA key having effectively 4000 bits instead of 4096 when it was generated by maximally simple and transparent process. As compared to complicated crypto whitening that everyone thinks "must have".

The bias of unwhitened output of almost any TRNG is hugely biased. For almost anything based on detecting some kind of radiation (which at the same time are exactly the kinds of TRNGs that are truly random according to current understanding of physics, not only practically impossible to predict) you are on the order of one bit of entropy per 1024bits of output, not 1000.

Re: How Do Computers Generate Random Numbers?

#44

Post by mschuetz »

My favourite is this one: https://preshing.com/20121224/how-to-generate-a-sequence-of-...

* Creates a sequence of unique integers

* Uses prime numbers that are congruent to P = 3 (mod 4).

* A single iteration has noticable patterns but applying it twice already results in randomness that is sufficiently good for many use cases.

* It is "embarrassingly parallel", a simple mapping of randomValue = randomize(i). You can calculate unique and deterministic random numbers from input i in parallel threads with no sync between threads.

* Since it is a unique mapping of i to r, you can use it to shuffle data sets virtually instantly. Take the index of a value in the original array, and use it to compute the target index in the shuffled array.

* I've used it to shuffle up to 800 million items per second on a GPU, including the time it took to transfer the data from RAM to GPU. So without the IO, you could probably shuffle billions of values per second, probably mostly bound by GPU bandwidth. E.g., 700GB/s and each item is 70 bytes -> could perhabs shuffle 10 billion items per second.

Re: How Do Computers Generate Random Numbers?

#45

Post by jfindley »

UncleMeat wrote: post #37
jfindley wrote: post #32

Earlier quoted context omitted.

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).

Thanks for the comment, yes I should have phrased that very differently.

What I was trying to say is that the kernel CSPRNG (exact mechanism depends on version) mixes together a bunch of things that aren't truly random from an information-theoretical perspective in order to produce uniform random output from the CSPRNG function - and that it doesn't actually matter that those sources aren't information-theoretically random. That'll teach me to comment in haste!

Re: How Do Computers Generate Random Numbers?

#46

Post by rini17 »

dfox wrote: post #42
rini17 wrote: post #17

Earlier quoted context omitted.

If the distribution non-evenness result is, say, 1000 bits of entropy in every 1024 bits of RNG output, but we save circuitry and have simple auditable RNG then it's worth it. I'm not going to lose sleep over my RSA key having effectively 4000 bits instead of 4096 when it was generated by maximally simple and transparent process. As compared to complicated crypto whitening that everyone thinks "must have".

The bias of unwhitened output of almost any TRNG is hugely biased. For almost anything based on detecting some kind of radiation (which at the same time are exactly the kinds of TRNGs that are truly random according to current understanding of physics, not only practically impossible to predict) you are on the order of one bit of entropy per 1024bits of output, not 1000.

That is an overkill. Measuring time between geiger detector events with 555-like counter is okay with me, it's still simple enough to be fully auditable and the bias is not so tragic.

Re: How Do Computers Generate Random Numbers?

#47

Post by chriselles »

ficklepickle wrote: post #20
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…

#2 reminds me of Benford's Law, which I recently learned about and find truly fascinating. https://en.wikipedia.org/wiki/Benford%27s_law

Interesting.

On first pass, Benford’s Law looks a lot like Zipf’s Law.

What differentiates Benford’s Law from Zipf’s Law?

Re: How Do Computers Generate Random Numbers?

#48

Post by rmrfstar »

dfox wrote: post #41
shadowprofile77 wrote: post #16

Earlier quoted context omitted.

Your claim makes me a bit skeptical unless im misunderstanding something here... I'd assume that a data source of pure natural radiation would be genuinely random even if its distribution isn't even, and that using anything in your computer to compensate for it would actually do the opposite: reduce randomness with damaging bias. It reminds me of a story from Cryptonomicon in which a character mentions a secretary gr…

The signal coming from typical radiation detector is analog pulse train which you have to somehow convert into useful binary data. Simply sampling this analog value at some regular interval will create samples that are hugely biased to small number of values (and distribution between these values has more to do with measurement uncertainty than with the supposedly random phenomena you are trying to measure) so you ne…

Facts I looked up to understand this comment:

* Bias in a bit-stream means any deviation from IID Bernoulli trials with p=0.5

* Von Neumann whitening addresses the IID Bernoulli case for p!=0.5 by looking at bit pairs. It takes the first bit when they differ, and no bits when they match. This works because (1,0) and (0,1) both occur with equal probability p(1-p).

* NIST wrote a remarkably accessible document [1]

[1] https://csrc.nist.gov/csrc/media/publications/sp/800-90b/dra...

Re: How Do Computers Generate Random Numbers?

#49

Post by IIAOPSW »

bregma wrote: post #30
IIAOPSW wrote: post #4

My personal favorite RNG is the logistical map. x_{n+1} = 4x_n(1-x_n). There is no hidden seed beyond the current output. Thus if you have a scientific calculator that lets you refer to the value on screen then you can rig it into an RNG. Seeing a simple, non-programmable machine "misbehave" and act random melts my mind a little.

That's still just a linear congruential PRNG with state sizeof(unsigned int). LCG is simple and has well-known flaws.

No it is not an LCG. When you distribute the terms there is a -4x_n^2. Therefore it is non-linear.

Re: How Do Computers Generate Random Numbers?

#50

Post by pmiller2 »

chriselles wrote: post #47
ficklepickle wrote: post #20

Earlier quoted context omitted.

#2 reminds me of Benford's Law, which I recently learned about and find truly fascinating. https://en.wikipedia.org/wiki/Benford%27s_law

Interesting. On first pass, Benford’s Law looks a lot like Zipf’s Law. What differentiates Benford’s Law from Zipf’s Law?

From https://en.wikipedia.org/wiki/Zipf%27s_law :

> It has been argued that Benford's law is a special bounded case of Zipf's law,[22] with the connection between these two laws being explained by their both originating from scale invariant functional relations from statistical physics and critical phenomena.[24] The ratios of probabilities in Benford's law are not constant. The leading digits of data satisfying Zipf's law with s = 1 satisfy Benford's law.

Post reply on HN