Random Number Generation -----> Hardware or Software?

"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." John Von Neumann

As the film "A Beautiful Mind" so convincingly illustrates.

Jan

A person who states that philosophy has merely embraced a particularly simplistic one.

No. Since a small and deterministic algorithm can calculate the n-th number of the sequence.

I have always wanted to read a version in which the prince was named Omelette.

Diehard Battery of Tests of Randomness

stat.fsu.edu/pub/diehard/

And for a distillation of the Diehard Battery into 3 tests, see:

Good movie!

Last night here in Norway, the Bruce Willis' film "Mercury Rising" was shown on NRK. The really funny premise of the movie was that a 9-year old autistic boy could directly decode NSA's most secure code, simply by looking at a page of encrypted data. :-)

Terje

And you are positive that the the noise is only coming from the quantum fluctuations and not from coupled electrical noise, local radio stations, or power supply ripple? :-)

Or is there some process for removing those sorts of things?

del

Or he who fears he is losing an argument publicly killfiles his antagonist.

Alas, I re-installed my OS and changed my news reader recently, and lost much of my killfile. It won't take long to identify the tossers and re-plonk them, though - flamers can't stop from being flamers.

Your accusation is false. You can examine my posting record and see that I don't killfile when I am losing an argument, but rather when someone stops having a reasoned discourse and engages in personal attacks. Perhaps you believe that flaming someone rather than sticking to facts and logic is "winning the argument", but most people believe that the first person to engage in personal attacks has *lost* the argument.

If you believe that the above is incorrect, I invite you to attempt to win an argument without resorting to personal attacks. You will find that this will *not* result is a public killfiling. Then try a personal attack with no argumnts of any kind attached, and watch as I plonk you.

Don't forget the Polonium rinse.

No. It won't.

One on the characteristics of a true random number generator is that any output stream is possible; if some output streams are not possible then the generator is not a true random generator.

Among these possible output streams are output streams that are identical to the output stream of any pseudo-random number generator. So if your test says "It's a PRNG" it really means "It's either a PRNG or a True RNG that, by chance, just happened to output the exact same stream that a PRNG would have generated."

Therefore, your "right with probability one" distinguisher cannot exist. The best you can do is a probability that approaches one.

I am well aware of Kolmogorov-Smirnov test and the Kolmogorov- Chaiten definition. One doesn't design hardware RNGs without learning the basics.

The Kolmogorov-Chaiten definition of a random sequence is a sequence that has the characteristic that the shortest computer program which can generate it is as long as the sequence itself. This is also known as the compressability test. This is easily disproven by counterexample; take N bits the output of a hardware-based RNG and try to compress them with PKZIP in self-extracting .exe mode. In most cases the resulting file will be larger - discard that result and try again. Eventually, by pure chance, the hardware-based RNG will output a sequence of N bits that *can* be compressed into a smaller self-extracting .exe file. That file is a computer program which generates the random sequence and is shorter than the sequence itself. If you have a very, very long time to search and a very, very fast computer, eventually, by pure chance, the hardware-based RNG will output a sequence of N bits that are all zeros and which can be generated by a very simple computer program.

The Kolmogorov-Smirnov test is a statistical test that approaches "right with probability one" as the output streams it tests approach infinity. You can never reach "right with probability one." An additional difficulty is that The Kolmogorov complexity of sequence is not computable, even with infinite resources.

He probably read the solution in the movie manuscript before. It is easy to break codes when you have the access to the key.

"Nicholas O. L> Yes, and they fail them. Have to. They _do_ repeat, so there

"Eric Smith" wrote

"Nicholas O. L> I should amend the above to: "Prng's pass randomness checks with

Having a long period is "cheating"? I'd think it would be a desirable characteristic of a PRNG.

Where did I say it was? I only contradicted the idea that in practice, all PRNGs "have to" fail multi-dimensional frequency checks. If you want to postulate running a test for an arbitrarily long time (perhaps billions of years), I don't think that can be considered useful in terms of proving or disproving the randomness of a generator. I'm rather more interested in tests that can be completed within a reasonably small fraction of my own lifetime, even if they must in some cases produce incorrect results.

Eric

No, in fact I'm positive that much of the noise is in that form, certainly that's what the spectral analysis shows. But there's still a couple of bits (per 16-bit sample) of genuine wide-band noise, and we're very conservative about the entropy counts. The predictable content of the noise is irrelevant to the end result.

As well, the more (theoretically) deterministic noise sources still form a fairly unpredictable stream... As I said in another message, randomness isn't the issue, it's unpredictability. Which is why all the posturing about the theory of non-determinism is irrelevant nonsense.

It's not like we needed Gb/s of random data - plus, with a 32768 bit entropy pool, the PRNG has a *very* long sequence length :-). New entropy is mixed in by MD5'ing it into a cyclic 16-byte segment of the pool, and delivered random bits are extracted similarly, so you can't discover what's in the pool even though you can see the delivered bits. And yes, I know MD5 isn't perfect :-). Neither apparently is SHA-1 any more...

Clifford

Exactly so. Alas, all True RNGs "have to" fail multi-dimensional frequency checks; you just have to keep testing them over and over until you get an output that fails the test. It may take a really huge number of tries but it will happen if you try often enough.

In addition, even if you *do* have those billions of years, a rather modest increase in the number of bits in the internal PRNG state will make it so that you need quintillions of years to prove that an output is from a PRNG, which means that you need quintillions of years to try the same test and fail when testing the output from a true RNG.

The idea of a known method that can differentiate between True RNGs and PRNGs with absolute certainty is a fantasy of the type often cooked up by those who have had some exposure to theory but have never created any actual systems. If one is willing to be satisfied with answers such as "this output has a 99.999999% chance of being the output of a such-and-such PRNG", then the job can be done. Alas, identifying something as being from a particular PRNG is a lot easier than identifying something as being from any PRNG, including ones not yet invented. Identifying something as being from a true RNG is even harder - so hard that many educated people doubt whether a true RNG with 100% entropy exists.

And unfortunately almost all programming language runtime systems have historically used generators with at best 32-bit math (some are even limited to 16 bits!) resulting in *terrible* "random" number output, certainly not anything useful for security or any statistical process. In fact the inappropriate use of such built-in "randomness" sources has frequently been used to defeat real-world security systems based on them.

One of the best places to learn about the use of serious PRNGs these days is from (of all places) online casino companies. Most have pages dedicated to explaing why their systems are fair/secure and some of these go into a surprising amount of detail about PRNGs. The Mersenne Twister seems to be a favorite there as well.

A similar application is in massively multi-player online games, where PRNGs are used to determine issues such as which player gets a treasure item, etc. One of these is World of Warcraft by Blizzard Entertainment, who recently addressed questions about whether players were cheating at aspects of the random processes:

G.

What accusation? I made a neutral statement, not referring to anyone specific. The source of the noise appears to be in the receiver, not the transmitter.

Are you attempting to flame me by unwarrantedly accusing me of personal attacks?

Nick Maclaren wrote: (snip)

There is a story about the German cypher machines used in WW2 that would never encypher a letter to itself, a non-randomness that was exploited in breaking it.

The problems of making hardware random number generators are even more interesting.

-- glen