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.

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

"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....