Have any of the Propeller-based True Random Number generators been tested?
ElectricAye
Posts: 4,561
Have any of the Propeller-based True Random Number generators been tested and shown to be truly random? I've been googling for answers to that question, and though I've found lots of discussion about true random number generation using the Propeller with various objects, I haven't seen anyone mention that the outputs have been tested against any standards.
I've seen circuits on the internet that use transistors in avalanche mode, etc. and they seem fairly simple, and then their outputs are run through a PIC or Arduino to clean up any drifts, bias, etc., so it seems this would be easy for the Propeller, but I also read that the Propeller's internal circuits could provide randomness that could be filtered via software in a similar manner. I just haven't found any mention of these outputs actually passing any randomness tests.
Anyone know?
Thanks.
I've seen circuits on the internet that use transistors in avalanche mode, etc. and they seem fairly simple, and then their outputs are run through a PIC or Arduino to clean up any drifts, bias, etc., so it seems this would be easy for the Propeller, but I also read that the Propeller's internal circuits could provide randomness that could be filtered via software in a similar manner. I just haven't found any mention of these outputs actually passing any randomness tests.
Anyone know?
Thanks.
Comments
-Phil
Thanks, Phil.
Hey, that reminds me of another question. Is there any danger of a truly random seed inserted into a pseudo-random number generator resulting in a non-random output? Or are you somehow guaranteed that the pseudo-random number generator can't possibly add order to a completely disordered input?
-Phil
This is a fascinating subject, let's see what we can do... First of all it is impossible to prove conclusively that any set of numbers was produced randomly. That is to say, you can analyse the output of of a Propeller random number generator, or any other, until you are blue in the face and never be really sure it was randomly generated.
What you can do is apply a bunch of tests to your set of "random" numbers that show that they have a similar statistical distribution of various properties as you would expect from "real" randomness. For example: You might check that there is an equal number of zeros and ones in a binary output. You might check that the numer of consequtive ones (or zeros) follows the expected pattern. And many other things.
One such set of tests is quite famous and was developed by the mathematician George Marsaglia, the "Diehard" test suite. http://www.stat.fsu.edu/pub/diehard/ This has since been built upon to the "dieharder" tests by Robert Brown http://www.phy.duke.edu/~rgb/General/dieharder.php.
Now, if you search the Parallax forums back a few years ago you will find a discussion of the Prop's real random number generator where I subjected it's output to these tests. The tests declared that it may well be random!
Then there was forum member Cessnapilot who was also into testing this and came up with his "BUST" tests that could be run on the Propeller itself: http://forums.parallax.com/showthread.php/115936-How-to-check-the-TRUE-randomness-(of-Prop-for-example)-with-BUST-in-SPIN
My conclusion was that the Propeller real random number generator was as good as the transistors in avalanche circuits. According to the tests I mentioned above.
Note: The Spin random operator fails the above tests badly.
Never mind danger, it's certain, the pseudo-random number generator will always fail the above tests of randomness very badly. As I just mentioned above.
Pseudo random number generators are called "pseudo" for a reason. They are totally deterministic logic circuits or algorithms that produce a sequence of numbers with some statistical properties of randomness. With the same seed they always produce the same sequence. They are never in anyway random.
Heater,
that's great to hear. I was hoping one of them had been tested and passed. But do you recall exactly which object it was you tested?
Yes, I know that pseudo-random number generators by themselves can not produce true randomness. What I was wondering about in my side question was whether pseudo-random number generators could take a random input and somehow inflict non-randomness into it. For example, I know analog random number/event generators can suffer from the harmonics of their detector thresholds inserting a non-random component into otherwise random inputs, so I was wondering if a digitally-based pseudo-random number generator might do the same. I was merely curious about that case, since it makes no practical sense to take a signal you know is random and cram it through a pseudo-random number generator you're not quite sure about.
Thanks for your insights on this. I really know very little about RNGs, etc.
I think that Intel's RdRand runs the numbers through AES to "whiten" them. You might find a search for RdRand interesting given all of the recent news. Also NIST has some test suites and papers about them on their site.
KeithE,
Yes, Intel's RdRand is compromised by the NSA: http://blog.jim.com/crypto/rdrand.html
Actually that may or may not be true. It does not matter. When it comes down to cryptography you can trust no one. So why trust Intel?
-Phil
output N0 = Some really, really random number input.
output N1 = N0 + 1
output N2 = N1 + 1
output N3 = N2 + 1
and so on.
Like I said, "that's what pseudo random number generators do"
The concern about RdRand was the opposite - taking a non-random input, and making it look random ;-)
-Phil
Imagine:
You want to send a secret message to your friend that no one else can read. So you invent a scheme to scramble that message so that only your friend can unscramble it.
But, because you are lazy you ask me to help you scramble it.
Well, guess what? Even if I don't see your original message I might help you scramble it in such a way that I can also unscramble it.
You should not trust me!
Similarly, having someone like Intel as an input to your scrambling scheme is a bad idea.
Not being a crypto expert I have no idea.
Which of course bugs me like hell. Above I mentioned being lazy with respect to random number generation. Well, of course, the truth is if I want to use crypto I will be lazy and use whatever algorithm the "experts" tell me is good and strong. I am putting my trust in other people to scramble my messages, WTF?
And trust is what it all comes down to unless you have the savy to make the whole thing for yourself or at least fully understand what you are using.
Now as to pseudo random number algorithms, most are very crude, many are little more than a copy of the algorithm from The C Programming Language 2nd ED.
Also most Pseudo random number algorithms are either convergent or divergent, making for very poor distribution.
"...most are very crude...also most Pseudo random number algorithms are either convergent or divergent, making for very poor distribution."
Perhaps. But many people have been working on this. For example the late great George Marsaglia. See threads:
http://forums.parallax.com/showthread.php/136975-JKISS32-High-quality-PRNG-with-RealRandom-seed-save-a-COG.
and:
http://forums.parallax.com/showthread.php/137118-MWC256-Very-high-quality-PRNG-with-RealRandom-seed-save-a-COG.
That's even before we get onto cryptographically secure PRNGs.