Random Number Generators
Hi all For a class project, I will be designing a VLSI cmos chip to generate truly random numbers (The chip will be fabricated). I'm limited to a 2-micron standard cmos technology (no fancy BiCMOS, MISC, or anthing else). The most promising design I've seen so far (that I can actually do) is based on clocking a D flip-flop in the following way: ----- 8Khz clock ------ | |----- Random output | | | | (sloppy) slow clock ---- |> | | | ----- The slow clock has enough random variation in it's period for the Dff to generate random numbers. The random bits will , of course, have biases that will need to be corrected with things like Xor gates. Can anyone give me pointers or references to other types of true random number generators and to ways of correcting the biases and other problems in the resulting random bitstream? I'd also appreciate a pointer to an intro text (if such a thing exists) on what makes random numbers good random numbers. (and before you say it, yes I have Applied Cyptography. It's a great book.) One thing I'm concerned about is making sure the random bitstream is uniformly random. What effects, if any, will things like thermal noise, power comsumption (what if there is a sudden rise in power comsumption in another part of the circuit), etc. have on the randomness of the bitstream? I'd also appreciate any other suggestions or advice you have on RNGs. Thanks in advance.
"Timothy L. Nali" writes:
For a class project, I will be designing a VLSI cmos chip to generate truly random numbers (The chip will be fabricated). I'm limited to a 2-micron standard cmos technology
The most promising design I've seen so far (that I can actually do) is based on clocking a D flip-flop in the following way:
I'd say that the design you have picked has a couple of problems with it. The first is that you are, from what I can tell, building a synchronizer, which means that you may have metastability problems. (Your diagram wasn't completely clear so I can't tell). Also, you are depending on a sloppy clock and a not sloppy clock actually having the stated properties, which means you aren't really generating randomness so much as hoping you can detect and exploit it. As it is very hard to determine if a stream is really random, this makes your life difficult. Far better to try to use some analog tricks in the circuit itself to generate the random numbers for you. Of course, some of these end up producing metastability problems of their own... Can anyone point this guy at good texts on all of this? I've never found one... Perry
Timothy Nali writes:
[ CMOS RNG chip ] ... The most promising design I've seen so far (that I can actually do) is based on clocking a D flip-flop in the following way: ... The slow clock has enough random variation in it's period for the Dff to generate random numbers.
While a scheme like this will work, one of the needs in a design like this is convincing yourself of how much entropy is available from the noisy clock and where it comes from. It's nontrivial to evaluate the phase noise of a CMOS relaxation oscillator, for example. Also, at what rate do you want random bits?
Can anyone give me pointers or references to other types of true random number generators and to ways of correcting the biases and other problems in the resulting random bitstream?
The references in Applied Cryptography are pretty useful; the only other ones I know of are a tech report by Gifford at MIT/LCS and a thesis by Sridhar Vembu (who also works here at Qualcomm) on optimal extraction of entropy from biased sources.
One thing I'm concerned about is making sure the random bitstream is uniformly random. What effects, if any, will things like thermal noise, power comsumption (what if there is a sudden rise in power comsumption in another part of the circuit), etc. have on the randomness of the bitstream?
I'd say thermal noise is your friend; the other systematics, as you say, are a slight issue, but their effect on the entropy is very small and they'll be taken out by the postprocessing (hash function, etc.).
I'd also appreciate any other suggestions or advice you have on RNGs.
I plan to make a simple board-level RNG design available to the net Real Soon Now. I'd be interested to see your CMOS design when it's finished. (By the way, try searching the cypherpunks and sci.crypt archives on the subject. There's lots of good discussion.) Cheers, Peter Monta pmonta@qualcomm.com Qualcomm, Inc./Globalstar
On Wed, 17 Jan 1996, Timothy L. Nali wrote:
Hi all
For a class project, I will be designing a VLSI cmos chip to generate truly random numbers (The chip will be fabricated). I'm limited to a 2-micron standard cmos technology (no fancy BiCMOS, MISC, or anthing else). The most promising design I've seen so far (that I can actually do) is based on clocking a D flip-flop in the following way:
----- 8Khz clock ------ | |----- Random output | | | | (sloppy) slow clock ---- |> | | | -----
you can enhance the thermal stability with a temperature control scheme. and you can virtually eliminate voltage problems with separate regulation. use a digital oscillator and clean up the edges. would you not be better off for true randomness to use a) a > 8Mz clock, and b) to chain the output of one into the control gate of a second? I think that gives you better spectral distribution presuming you use a second clock frequency. unlike most, I am still of the opinion that digital means of generating this should be more uniform. otherwise, use a high-frequency diode, analog weight the curve, analog high-pass it, sample it, and go for it. or take several TV stations, phase and mix the horizontal scans, etc. --but I thought this was a digital project for CMOS --actually CMOS can generate white noise, but you probably will end up with a DSP on your chip! biasing should be controllable with edge control. However, all of above needs to be bench tested for the practical results --keeping in mind measuring randomness of segments of a bit stream are "impossible" --thoroughly frustating. another schema is to play the old enigma game of lining up the spinning wheels -that works digitally, the gates on CMOS are not too hairy -the question is how many wheels and their relative rotation (including direction)? and, how many levels? how much real estate do you have at 2u? I ask because the use of the rotating wheels has been an old project I dumped since fab was far to expensive in the 70s --but it has held my interest. there has also been a thorough trashing or thrashing of RNG recently which should be in the archives.
I'd also appreciate any other suggestions or advice you have on RNGs.
Thanks in advance.
__________________________________________________________________________ go not unto usenet for advice, for the inhabitants thereof will say: yes, and no, and maybe, and I don't know, and fuck-off. _________________________________________________________________ attila__ To be a ruler of men, you need at least 12 inches....
You might find this article instructive: Herschell F. Murry, "A General Approach for Generating Natural Random Numbers," IEEE Transactions on Computers, December 1970, p. 1210. A fairly recent patent uses your approach of two oscillators: No. 4,855,690 by Dias, assigned to Dallas Semiconductor Corp., "Integrated Circuit Random Number Generator using sampled output of variable frequency oscillator." I'd suggest using Johnson noise; reverse-biased diodes generate noise which is pink. Ive built devices using amplified Johnson noise, squared up with a comparator, then averaged by a D flip-flop. The preliminary results look pretty good. Please post your results here -- and good luck. John A. Thomas jathomas@netcom.com
participants (5)
-
attila -
John A. Thomas -
Perry E. Metzger -
Peter Monta -
Timothy L. Nali