aboulang@bbn.com (Albert Boulanger) (01/07/90)
I noticed the spec sheet for this little guy in the Sams book "Video Scrambling & Descrambling" Rudolf Graf, & William Sheets. The specs for this chip say that it produces TRULY random bits based on the phase jitter of a free-running oscillator. It is a companion chip to AT&T's T7000A DES chip. Is there any analysis of the quality of the random numbers based on the technology used in this chip? I have been thinking of a similar idea but based on XORING a bank of free running oscillators (which is in turn based on a simple asynchronous random sequence algorithm I have been playing with for MIMD machines). Is there some general analysis and description of this generic class of methods for producing random sequences? Inquiringly yours, Albert Boulanger BBN Systems & Technologies Corp. aboulanger@bbn.com
mmm@cup.portal.com (Mark Robert Thorson) (01/08/90)
One pitfall to consider is the possibility that the free-running oscillators might get coupled to each other by the noise they inject into the power supply rails. Obviously, this would prevent them from being truly free-running, hence you might end up with less randomness than you would otherwise expect.
tomb@hplsla.HP.COM (Tom Bruhns) (01/09/90)
aboulang@bbn.com (Albert Boulanger) writes: >I noticed the spec sheet for this little guy in the Sams book "Video >Scrambling & Descrambling" Rudolf Graf, & William Sheets. The specs >for this chip say that it produces TRULY random bits based on the >phase jitter of a free-running oscillator. It is a companion chip to >AT&T's T7000A DES chip. > >Is there any analysis of the quality of the random numbers based on >the technology used in this chip? I have been thinking of a similar >idea but based on XORING a bank of free running oscillators (which is >in turn based on a simple asynchronous random sequence algorithm I >have been playing with for MIMD machines). Is there some general >analysis and description of this generic class of methods for >producing random sequences? A slightly tangential comment: usually "true random" generators have one or more statistical characteristics that are significantly less than ideal, and may drift with time. PRN generators, on the other hand, are quite predictable in many of their lower-order statistics (which is usually where the "true random" fail...from my meager understanding) but not so good in some of the higher-order things. Thus one good ploy is to mix (e.g., XOR) a PRN and a "true random" bit stream. I think there are indeed well-known analysis techniques; when you discover them, you might want to apply them to the suggested implementation. -- As a simple example, however, consider a "true random" generator with a bias: although higher-order statistics are good, its probability of generating a "1" is, say, 0.4. If you mix this with a PRN stream with probability of "1" equal to (2^(n-1)/(2^n-1)) (which is really close to 0.5 for a moderate n), the probability of generating a "1" is now even closer to 0.5 than for the PRN stream. And similarly, the "true random" helps out the higher-order stuff of the PRN: there is no longer a zero probability of observing streams of 1's or of 0's longer than n, and the combination also "never" repeats, even though the PRN sequence, in theory, does.
jgk@osc.COM (Joe Keane) (01/10/90)
In article <25718@cup.portal.com> mmm@cup.portal.com (Mark Robert Thorson) writes: >One pitfall to consider is the possibility that the free-running >oscillators might get coupled to each other by the noise they inject >into the power supply rails. Obviously, this would prevent them from >being truly free-running, hence you might end up with less randomness >than you would otherwise expect. Not just the power supply rails, either. They need some big capacitors in a bunch of places, and better not use any inductors. It's not clear to me why you'd want to use free-running oscillators. How do you model the phase jitter? You can't possibly get more than about a bit per oscillator cycle. It seems to me that you could get a lot more bandwidth out of amplified Johnson noise or shot noise. If you know the spectrum of the source, you can filter it to get flat energy per frequency (white noise) across a known frequency band, and do the appropriate sampling to get independent bits. It's a bit more complicated to do it right, but then you have some assurance about the correlations, since you know the frequency spectrum and how it may vary. Of course, no matter how good you think your source is, at least some post-processing is a good idea. With a good enough hashing function, you can probably keep most of the bits, but if you're cheap about it some patterns are going to come through. Remember, you should assume the spooks have built a circuit just like yours and have figured out what radio stations it picks up.
ISW@cup.portal.com (Isaac S Wingfield) (01/13/90)
...(lots of stuff about random number generators)... Wasn't it John von Neumann who said "anyone who thinks they know how to build a random number generator doesn't understand the problem"? Isaac isw@cup.portal.com
Nagle@cup.portal.com (John - Nagle) (01/14/90)
No, what Von Neumann said was:
"Anyone who considers arithmetical methods of producing random digits
is, of course, in a state of sin."
John Nagle