Shop OBEX P1 Docs P2 Docs Learn Events
Real Random Number Generator Object — Parallax Forums

Real Random Number Generator Object

cgraceycgracey Posts: 14,131
edited 2008-12-15 13:51 in Propeller 1
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
«1

Comments

  • IWriteCodeIWriteCode Posts: 16
    edited 2007-03-22 09:34
    Nice... [noparse]:)[/noparse]

    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
  • SkogsgurraSkogsgurra Posts: 231
    edited 2007-03-22 14:04
    There is a poet named Harry Martinsson. Back in the fifties, he wrote a rhymed tale of a space-ship where the inhabitants of Earth set out to find a new world where they could continue their existence - the Earth had been destroyed by pollution and radiation. On-board this ship, there was a thing callled "the Mima". It was the earthlings link to the Earth and to the future.

    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. smile.gif
  • Graham StablerGraham Stabler Posts: 2,507
    edited 2007-03-22 14:21
    Lol, at least the counters [noparse]:)[/noparse]

    Graham
  • cgraceycgracey Posts: 14,131
    edited 2007-03-22 18:16
    IWriteCode said...

    Nice... [noparse]:)[/noparse]

    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] )
    After reading your post, I thought I'd better investigate this issue. Sure enough, there IS a bias, slightly towards 0's. Apparently, this is a common problem with random generators based on physics, as no system is perfectly balanced. This interesting page here talks about bias cancellation:

    http://www.randomnumbers.info/content/Generating.htm

    I hope it holds the key to getting this straightened out.


    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


    Chip Gracey
    Parallax, Inc.
  • BergamotBergamot Posts: 185
    edited 2007-03-22 18:43
    Chip Gracey (Parallax) said...
    IWriteCode said...


    Nice... [noparse]:)[/noparse]

    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] )
    After reading your post, I thought I'd better investigate this issue. Sure enough, there IS a bias, slightly towards 0's. Apparently, this is a common problem with random generators based on physics, as no system is perfectly balanced. This interesting page here talks about bias cancellation:

    http://www.randomnumbers.info/content/Generating.htm

    I hope it holds the key to getting this straightened out.
    Why not just use the physically-generated value as a seed for a more robust random number algorithm?
  • SkogsgurraSkogsgurra Posts: 231
    edited 2007-03-22 21:47
    Does "a slight bias towards zero" really bother us in the cypher application? I think not.
  • cgraceycgracey Posts: 14,131
    edited 2007-03-22 23:24
    Bothersome bias or not, it's now fixed! Von Neumann had come up with a simple means to remove bias:

    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
  • HarleyHarley Posts: 997
    edited 2007-03-22 23:40
    Really COOL! yeah.gifhop.gifturn.gifroll.gifcool.gif

    Finding this amazing Propeller has some capabilities
    unplanned really surprises me. Nicely.

    A very satisfied Prop-head.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Harley Shanko
    h.a.s. designn
  • T ChapT Chap Posts: 4,198
    edited 2007-03-23 01:34
    Chip

    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.
  • Tracy AllenTracy Allen Posts: 6,656
    edited 2007-03-23 05:29
    Chip,

    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
  • IWriteCodeIWriteCode Posts: 16
    edited 2007-03-23 09:51
    Chip, would it be possible to submit a (long) list of generated numbers as attachment to this thread? That list could be used for testing purposes. [noparse]:)[/noparse] Preferable both list, one biased and one non-biased...
  • Tracy AllenTracy Allen Posts: 6,656
    edited 2007-03-23 15:59
    The _random_value is is generated by shifting in random bits one at a time and that is output on every time around the loop, so it takes 32 iterations to fill up a Long. Then it would take 32 more iterations to completely clear that out and form the next ostensibly uncorrelated next random long so on.

    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
  • TransistorToasterTransistorToaster Posts: 149
    edited 2007-03-23 16:39
    >LFSRs are considered potent as a source of random bits

    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
  • Tracy AllenTracy Allen Posts: 6,656
    edited 2007-03-23 17:06
    That Blum Blum Shub generator does seem to have a strong theoritical background for cryptography. The key in that case would be the secret knowledge of the two large primes, wouldn't it?

    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
  • TransistorToasterTransistorToaster Posts: 149
    edited 2007-03-23 18:03
    >I've kind of lost track of how Chip is going to use these (truely) random numbers t
    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.
  • cgraceycgracey Posts: 14,131
    edited 2007-03-23 18:58
    Tracy,

    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.
    Tracy Allen said...
    The _random_value is is generated by shifting in random bits one at a time and that is output on every time around the loop, so it takes 32 iterations to fill up a Long. Then it would take 32 more iterations to completely clear that out and form the next ostensibly uncorrelated next random long so on. I looked at what Knuth (Seminumerical Algorithms) has to say about it. He claims that LFSR numbers generated in that way do not easily pass the "serial test" for correlations between pairs of numbers (successive longs or words or bytes in this case). However, in the present case there is that extra randomnes that is introduced in the low bit. 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.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


    Chip Gracey
    Parallax, Inc.
  • cgraceycgracey Posts: 14,131
    edited 2007-03-23 20:00
    Tracy Allen said...

    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.

    It's true that the CNT has a very long period, but those upper bits cancel themselves out with the repetitive adding and shifting. Plus, the LFSR acts like a garbage disposal, pulverizing everything.·And,·I·figured that·adding·CNT to·the LFSR is as disruptive to its state as adding a pseudo-random number to·CNT would be. They are very different function domains and interaction results in needed chaos.

    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.
  • hitswarehitsware Posts: 156
    edited 2007-04-04 03:33
    the BasicStamp seems to do Rnd with the number of bits available as the number of possible numbers .....
    in Qbas Rnd generates the # by the decoded output of the available bits ....
    still a 'pattern' but a much longer one ....
  • KeithEKeithE Posts: 957
    edited 2007-04-04 22:39
    Does anyone know what the distribution looks like? Uniform or Gaussian or ?

    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.
  • KeithEKeithE Posts: 957
    edited 2007-04-04 22:44
    I should add that this publications page has some interesting reading:

    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
  • RaymanRayman Posts: 13,767
    edited 2007-10-09 15:34
    Wow, the "Search" function worked!

    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...
  • rjo_rjo_ Posts: 1,825
    edited 2007-10-09 17:12
    Rayman,

    "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.
  • HarleyHarley Posts: 997
    edited 2007-10-09 17:31
    Wouldn't using the System Counter cnt be a variable seed?

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Harley Shanko
  • RaymanRayman Posts: 13,767
    edited 2007-10-09 17:41
    I think it could be if you waited for some user input, e.g., mouse click on a button, before sampling it. Otherwise, it's deterministic and you get the same answer every time...
  • Stan671Stan671 Posts: 103
    edited 2007-10-09 18:01
    I thought that cnt does not start at zero after a power-up. That is contines where it was when the power went off.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Stan Dobrowski
  • deSilvadeSilva Posts: 2,967
    edited 2007-10-09 18:23
    "Randomness" is not a feature of a given sequence but of the process which has generated it.
    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
  • RaymanRayman Posts: 13,767
    edited 2007-10-09 18:41
    I wonder if using the 2-pin sigma-delta ADC (like that of the Microphone2VGA object) with no input would also make a pretty good random-number generator... This is basically built-in to the demo board. (Maybe even the ambient audio would help the randomness...) It could be biased, but then Chip said earlier how to get around this...
  • deSilvadeSilva Posts: 2,967
    edited 2007-10-09 18:54
    Do you understand how von Neumann's idea works:
    - Assume the probability for a 0 is z and for a 1 is o = (1-z)
    - Now generate pairs of bits:
    00 - p= z*z
    01 - p = o*z
    10 - p = z*o
    11 - p = o*o
    



    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"!
  • RaymanRayman Posts: 13,767
    edited 2007-10-09 20:14
    Nice explaination. Thanks!
  • LoopyBytelooseLoopyByteloose Posts: 12,537
    edited 2007-10-10 08:38
    Awesome,
    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)········
    ···················· Tropically,····· G. Herzog [noparse][[/noparse]·黃鶴 ]·in Taiwan
Sign In or Register to comment.