Real Random Number Generator Object
cgracey
Posts: 14,250
THIS OBJECT HAS BEEN UPGRADED (AGAIN)·- NEW VERSION ATTACHED (V1.2)
Here's an object that is of value when you need TRULY RANDOM numbers -- not just pseudo-random sequences.
This came from the desire to have the Propeller be able to generate real random numbers internally for the purpose of data encryption. It can be used for lots of applications, though. It achieves randomness by jittering·a·CTR PLL and recycling the jitter into a pseudo-random excitation sequence. A few days ago, I was resigned to the notion that there was no way, shy of external hardware, that the Propeller would be able to generate random numbers. This opens up a lot of doors now.
I tried lots of variations on the theory until I distilled down the essentials. The main loop is only six instructions:
······················· org
entry·················· movi··· ctra,#%00001_111······· 'set ctra to internal pll mode, select x16 tap
······················· movi··· frqa,#$020············· 'set frqa to system clock frequency / 16
······················· movi··· vcfg,#$040············· 'set vcfg to discrete output, but with no pins
······················· mov···· vscl,#70··············· 'set vscl to 70 pixel clocks per waitvid
:loop·················· waitvid 0,0···················· 'do a waitvid -- waits a randomly-varying time
······················· add···· phsa,cnt··············· 'incorporate time into pseudo-random sequence
······················· test··· phsa,#%10111··· wc····· 'step pseudo-random sequence while affecting...
······················· rcr···· phsa,#1················ '...pll target phase -- generates random jitter
······················· wrlong· phsa,par··············· 'write random value back to spin variable
······················· jmp···· #:loop················· 'loop·····························
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
Post Edited (Chip Gracey (Parallax)) : 3/23/2007 7:01:27 PM GMT
Here's an object that is of value when you need TRULY RANDOM numbers -- not just pseudo-random sequences.
This came from the desire to have the Propeller be able to generate real random numbers internally for the purpose of data encryption. It can be used for lots of applications, though. It achieves randomness by jittering·a·CTR PLL and recycling the jitter into a pseudo-random excitation sequence. A few days ago, I was resigned to the notion that there was no way, shy of external hardware, that the Propeller would be able to generate random numbers. This opens up a lot of doors now.
I tried lots of variations on the theory until I distilled down the essentials. The main loop is only six instructions:
······················· org
entry·················· movi··· ctra,#%00001_111······· 'set ctra to internal pll mode, select x16 tap
······················· movi··· frqa,#$020············· 'set frqa to system clock frequency / 16
······················· movi··· vcfg,#$040············· 'set vcfg to discrete output, but with no pins
······················· mov···· vscl,#70··············· 'set vscl to 70 pixel clocks per waitvid
:loop·················· waitvid 0,0···················· 'do a waitvid -- waits a randomly-varying time
······················· add···· phsa,cnt··············· 'incorporate time into pseudo-random sequence
······················· test··· phsa,#%10111··· wc····· 'step pseudo-random sequence while affecting...
······················· rcr···· phsa,#1················ '...pll target phase -- generates random jitter
······················· wrlong· phsa,par··············· 'write random value back to spin variable
······················· jmp···· #:loop················· 'loop·····························
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
Post Edited (Chip Gracey (Parallax)) : 3/23/2007 7:01:27 PM GMT
Comments
Did you do any checking of the results, to see if the results comply with real randomness?
(Thinking something is random, or proving it, is quite a different story [noparse];)[/noparse] )
Post Edited (IWriteCode) : 3/22/2007 9:44:00 AM GMT
The Mima started to develop its own conscience and provided new insights that no man had had before. "The inventor was beaten by the things he saw - half the Mima had been invented by the Mima itself!" (sorry, not an authorised translation).
I have a feeling that the Propeller is going that way, too.
Graham
http://www.randomnumbers.info/content/Generating.htm
I hope it holds the key to getting this straightened out.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
1) Gather·your 'random' bits in sets of two.
2) If they are the same, throw them away.
3) If they are different,·output the first one.
4) Repeat.
So, you throw away quite a few bits, but wind up with an unbiased stream, which does indeed check out fine.
I updated the new version of RealRandom·into the first post of this thread.
This subject of randomness is quite fascinating and has a lot of very practical application, even for simple projects. Here is some explanation text I wrote for the object which I·hope conveys the significance of the matter:
Background and Detail:
····································································································
A real random number is impossible to generate within a closed digital system. This is because·there are no reliably-random states within such a system at power-up, and after power-up, it·behaves deterministically. Random values can only be 'earned' by measuring something outside of the·digital system.················································
In your programming, you might have used 'var?' to generate a pseudo-random sequence, but found the same pattern playing every time you ran your program. You might have then used 'cnt' to 'randomly' seed the 'var'. As long as you kept downloading to RAM, you saw consistently 'random' results. At some point, you probably downloaded to EEPROM to set your project free. But what happened nearly every time you powered it up? You were dismayed to discover the same sequence playing each time! The problem was that 'cnt' was always powering-up with the same initial value and you were then sampling it at a constant offset. This can make you wonder, "Where's the end to this madness? And will I ever find true randomness?".
In order to have real random numbers, either some external random signal must be input, or some·analog system must be used to generate random noise which can be measured. We're in luck here, because it turns out that the Propeller does have sufficiently-analog subsystems which can be·exploited for this purpose -- each cog's CTR PLLs. These can be exercised internally to good effect, without any I/O activity.
This object sets up a cog's CTRA PLL to run at the main clock's frequency. It then uses a pseudo-random sequencer to modulate the target phase of the PLL. The PLL responds by speeding up and slowing down in a an endless effort to lock. This results in very unpredictable frequency jitter which is fed back into the sequencer to keep the bit salad tossing. The final output is a truly-random 32-bit unbiased value that is updated every few microseconds. This value can be sampled by your application whenever a random number is needed.···············································
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
Post Edited (Chip Gracey (Parallax)) : 3/22/2007 11:55:20 PM GMT
Finding this amazing Propeller has some capabilities
unplanned really surprises me. Nicely.
A very satisfied Prop-head.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Harley Shanko
h.a.s. designn
I am curious how many hours you have invested in getting the random number. It looks like some interesting side benefits have come out of the dongle pursuit.
It's pretty amazing, all right.
However, I think in some ways the first one might be better than the replacement. The second one is a random source of bits, granted, which are generated by the jittery phase accumulator. In the second version the random bits are shifted into a long from the left, and the pattern propagates to the right (the variable "_random_value"). If you look at the variable as it comes out, you can see the patterns propagating to the right like a wave. This is why LFSRs are considered potent as a source of random bits (especially after the bias is removed), but they are not good for random bytes, or longs, unless there is some other serious mixing. But again, if an application only needs a series of one bit coin tosses from bit 0, it should be fine.
I'm still puzzling over the first routine. It uses the value of phsa directly as the output, and between adding the value of the systems counter and the LFSR and the jitter, there is quite going on and lots of bits are going to change at once. That largely because of adding in the system counter. But the system counter itself is going to have that long 2*32 period. Somehow that is going to be reflected in the output, huh? For some purposes it would probably be fine. But there are so many kinds of statistical tests it might have to pass. Maybe it did not pass the test for unbiased coin tossing, but maybe that could be corrected in a way such that all of the bits qualify as unbiased, and all uncorrelated with one another under time shifts.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
I looked at what Knuth (Seminumerical Algorithms) has to say about it. He claims that LFSR psuedo-random bits shiifted to make a word do not pass the "serial test" for correlations between pairs of numbers (successive longs or words or bytes in this case).
However, in the present case it is not by a long shot a simple deterministic LFSR. There is that extra randomnes introduced by the WAITVID, jitter in the PLL, and adding in the system counter. That would make a big difference, I wonder. Still, random words would have to be drawn at intervals longer than the time it takes the algorithm to shift in n bits needed.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
Post Edited (Tracy Allen) : 3/23/2007 4:54:35 PM GMT
I took a cryptography course at McGill University. LFSR is very easy to break with a very short known plaintext ciphertext pair. LFSRs are still good for making white noise.
This PRBG should be very easy to do with the propeller: It's the Blum Blub Shub generator. S=S^2 mod N. where N is the product of two large primes.
http://en.wikipedia.org/wiki/Blum_Blum_Shub
EDIT: I would have to add that it is in reality not straightfoward. The integers should be larger than 32 bits and require special algorithms. For small values, a code breaker can figure out the two primes in the product, while for larger values, the computational time is quite impractical.
Post Edited (TransistorToaster) : 3/25/2007 1:52:08 AM GMT
I've kind of lost track of how Chip is going to use these (truely) random numbers to protect IP in the Prop+eeprom+dongle, which I think was the original motivation for this.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
He needs random values to feed to the dongle input.
>The key in that case would be the secret knowledge of the two large primes, wouldn't it?
You can use a PRBG for encryption only once for a given seed. The encryption would be the xor of the plaintext with the PRBG output. The concept of Chip's dongle is for the Propeller to compute the output for a given input and check if it matches the same input output pair of the dongle.
It's true that it's now effectively generating one bit at a time (with the biasing algorthm in place), but if that bit is really random, I don't see how it changes anything in the aggregate (i.e. larger numbers made of multiple random bits). I just ran a bunch of tests and determined that, on average, it's updating the entire long every 100us. Worst case was measured at 170us, so I think 200us would be a conservative sample interval. I've added a waitcnt into the Spin routine·which returns·the random long, so that all-new bits are·guaranteed. I'm posting·the new version at the top of this thread. I made the assembly code a little more efficient and improved the docs.
Like you said, the LFSR is only serving as an excitation impetus. Most of the wackiness comes straight from the PLL, itself, in the form of CNT deviations which dramatically re-steer the LFSR every cycle.
One funny thing that seems apparent to me is that·high-integrity random generators·all seem to be rather event-driven, and never completely deterministic in their timing. After all, a basic task of theirs is to observe, not dictate. This means that samples don't lend themselves to exact timing, but percolate out when they are ready. I guess that's just part of randomness.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
At first, I bothered to get the actual CNT delta over the WAITVID period, both·direct and zero-biased. I quickly found, though,·that it didn't matter what the bias was -- the raw CNT was quite satisfactory by itself, which is the simplest, anyways. All that mattered was that some of the bits (jittering lsb's in this case) were random. Just inject a little randomness and the thing burns great.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
in Qbas Rnd generates the # by the decoded output of the available bits ....
still a 'pattern' but a much longer one ....
I was reading some papers on the efficient generation of gaussian pseudorandom noise, and ran across the following survey. It has a section on tests for randomness that you might find relevent. I didn't realize that so much work including custom hardware design was being put into the generation of pseudorandom noise with a gaussian distribution. I started just thinking that a quick hack would be to sum multiple numbers, but people are more sophisticated than that.
http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/grng_acmcs07.pdf
This is really unrelated to the "true" random generator, but you may run across some aspect of testing that's interesting.
http://www.cse.cuhk.edu.hk/~phwl/publications.html
He talks about generating and analyzing true random numbers in an FPGA in this paper:
http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm03.pdf
But, I saw it is discussed that the main problem with a very simple quasi-random number generator is that it would start with the same seed after every power-on cycle.
However, it seems to me that one could use save to EEPROM functions in the:
Fempto Basic and PE Kit Lab Applications – EEPROM Datalogging and I2C
to save the seed. I vaguely recall making simple quasi-random number generator with a 32-bit register and XOR. Probably just a few lines of code and wouldn't use an extra cog...
"Wow, the "Search" functioned worked!"
Sometimes it does... and sometimes it doesn't. I get what seem to be perfectly random results... no matter what search engine I use or what terms I enter... maybe it is my seed.
"... the main problem..."
all random number generator are quisi-random... something always determines the numbers we get out of a generator. Most of the time we don't actually need random numbers... we just need numbers that have no discoverable relationship to each other... they "look" random.
The ? operator is really nice... except that it produces the same result every time... if you use the same seed. So, honestly the only thing you need is some way to gurantee that you aren't using the same seed very often. Measureing some "real world" ..."analog" type function... or a controller function with a time varying value... ... which value you don't know until you look is more than good enough for generating the kind of randomness that we need for game playing.
Pure noise doesn't exist either... so let's say that you base your seed on some measurement of noise in the room... and then you look at your game very carefully... you will find that there is a pattern related to patterns in the noise that you didn't notice until you started playing your game.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Harley Shanko
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Stan Dobrowski
0,0,0,0,0,0,0,0 can perfectly be issued by a random generator, as such sequences of "rouge" or "noir" happen daily in casinos all over the world.
The question is how difficult it will be to guess the NEXT digit from this generator.
To check this, you can try a number of proven "guessers" (e.g. hard boiled roulette addicts); if ALL of them fail, you can be quite confident that your source is in fact "ergodic".
As it is terribly easy to guess the next number of a pseudo-random generator, either knowing its mechanism or having a long enough sequence (say 4 billion bits), those sequences are out of competition already from the beginning.
However this strict verdict might soften, when your "opponent" is not an intelligent being, but some dumb mechanism- Then you can ask the following questions to any part of a sequence:
- is the difference between the number of ones and zeros within a given limit?
- is the difference between the number of the two bit combinations 00, 01, 10, 11 within a given limit?
- and so on
You will immediately recognize that a sequence fulfilling just those first two rule can be generated by a simple two bit counter 0, 1, 2, 3 - no randomness at all! However ANY pseudorandom sequence will look as 0,1,2,3 to a sufficiently intelligent being!
But look at the binary pattern:
0 - 0 - 0 - 1 - 0 - 1 - 1
Doesn't that LOOK terribly random to US??? So may be it will fool your "opponent" as well and thus will be just fine for your use!
Post Edited (deSilva) : 10/9/2007 6:29:40 PM GMT
- Assume the probability for a 0 is z and for a 1 is o = (1-z)
- Now generate pairs of bits:
So the pattern 01 and 10 both have the same probability and you can encode whatever value you want to them, e.g. 0 or 1 again.
Note that this works even for a fast changing "bias"!
Everything I learned about computers and random number generators just took a big flip-flop. I just assumed that we would be stuck with 'pseudo random number generators' forever. I never would have considered using jitter to exploit the physical natue of chips.
I see we are getting into a large memory model gratis Bill Henning. Is there anything the Propeller cannot do? Boundaries are falling. More shall be revealed.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"Everything in the world is purchased by labour; and our passions are the only causes of labor." -- David·Hume (1711-76)········