Many electronics hobbyists can whip up a circuit which generates noise and amplifies it to digital levels. Then, presumably, all we need do is sample the noise generator occasionally with a computer, to pick up a random bit. Case closed.
Actually, this technique may not be too bad, provided that the samplings are well-spaced and irregular, and providing also that we accept that the 1's and 0's we get may not have the same probability. Substantial post-processing would be reasonable, and not particularly expensive, but all too often the resulting bits are simply used "as is."
Perhaps the best worked-out random number machine is described in Vincent. Shot noise from a reverse-biased junction is amplified -- perhaps a factor of 10,000 -- in a wideband linear amplifier. The amplified noise is then compared to a relatively high level control voltage. Pulses which exceed that level in a given time are counted, and output generated based on whether the count was even or odd.
Another form of random number machine samples a high-frequency wave with an unstable low-frequency clock. Unfortunately, it is difficult to build a clock which is sufficiently unstable to generally have a different period between each sample. In the example here, Fairfield, Mortenson and Coulthart introduce an on-chip shift-register "scrambler" to avoid the very substantial bit-to-bit correlations they found in the raw sampled bits. [One opportunity here might be to use a chaotic circuit as the sampling clock, especially if some noise were added to the chaotic feedback.]
Yet another form of random number machine is simply a sampled hardware chaotic circuit. Usually, this has various problems of balance and correlation, but in addition these circuits generally are not closely associated to true physically-random sources as one might like. While even the best design must contribute some noise to the mix, the whole point here should be to use noise to cause unusual variations in the chaos, instead of trying to achieve results similar to some ideal simulation.
There are probably various randomness opportunities at the chip level, simply because noise may be easier to connect to down there.
Some other proposals are subsets or combinations of the above, or use somewhat questionable techniques. At this point, there still is no simple, universally-accepted way to tap into physical randomness.
Rand Corporation. 1955. A Million Random Digits with 100,000 Normal Deviates. The Free Press. Glencoe, Illinois.
"The random digits in this book were produced by the randomization of a basic table generated by an electronic roulette wheel. Briefly, a random frequency pulse source, providing on the average about 100,000 pulses per second, was gated about once per second by a constant frequency pulse. Pulse standardization circuits passed the pulses through a 5-place binary counter. In principle the machine was a 32-place roulette wheel which made, on the average, about 3000 revolutions per trial and produced one number per second. A binary-to-decimal converter was used which converted 20 of the 32 numbers (the other twelve were discarded) and retained only the final digit of two-digit numbers; this final digit was fed into an IBM punch to produce finally a punched card table of random digits."
"Production from the original machine showed statistically significant biases, and the engineers had to make several modifications and refinements of the circuits before production of apparently satisfactory numbers was achieved. The basic table of a million digits was then produced during May and June of 1947. This table was subjected to fairly extensive tests and it was found that it still contained small but statistically significant biases." "Block 1 was produced immediately after a careful tune-up of the machine; Block 2 was produced after one month of continuous operation without adjustment. Apparently the machine had been running down despite the fact that periodic electronic checks indicated it had remained in good order."
"The table was regarded as reasonably satisfactory because the deviations from expectation in the various tests were all very small -- the largest being less than 2 per cent -- and no further effort was made to generate better numbers with the machine. However, the table was transformed by adding pairs of digits modulo 10 in order to improve the distribution of the digits. There were 20,000 punched cards with 50 digits per card; each digit on a given card was added modulo 10 to the corresponding digit of the preceding card to yield a randomized digit. It is this transformed table which is published here . . . ."
"The transformation was expected to, and did, improve the distribution . . . ."
Murry, H. 1970. A General Approach for Generating Natural Random Variables. IEEE Transactions on Computers. C-19: 1210-1213.
"Random numbers generated from natural fluctuation phenomena promise to rectify [the main disadvantages of pseudorandom numbers] but their statistics must be monitored . . . ."
"Although it might be one's first thought, straightforward analog-to-digital conversion of noise signals is doomed to failure for two reasons: 1) the random number generator would be constrained to producing only the random number distribution corresponding to the amplitude distribution of the particular noise source used and 2) it would be dependent on the long-term stability of the noise source."
"Since our concern is about the numbers produced and not about the source producing them, we would do well to concentrate our attention on them and be as unconcerned as possible about the source producing them. This can be done if we have high-speed statistical tests adequate for the numbers [6] and extract only a single feature -- such as zero crossings -- from the basic noise source."
[ Note: apparently the author published his "high speed statistical tests" in a hard-to-get reference. If anybody can get this, I'd like to have a copy: ]
Murry, H. 1968. High speed probability tests on random number sequences. Proceedings of the Region III IEEE Convention. New Orleans, La, April 1968.
"Even if the statistical tests are not satisfied, they can provide valuable information for correcting difficulties in the noise source / quantizer circuits [6], [7]. The only restriction is that the noise be at least stationary in the mean and in autocorrelation, for otherwise, continuous circuit adjustment would be necessary."
Vincent, C. 1970. The generation of truly random binary numbers. Journal of Physics E. 3(8): 594-598.
". . . the generation of truly random numbers must have a physical basis, and some care is needed to ensure accuracy. For example, a circuit giving an output digit dependent on whether a random noise voltage was above or below a specified level could give a probability that changed with drift. A feedback circuit to measure and correct the drift could introduce some degree of correlation between digits."
"The method proposed for obtaining the binary digits is to count randomly generated voltage pulses over a measured time interval and to select a 0 or 1 according as the result is an even or odd number."
"Suitable pulses can be derived from a radioactive source and detector (figure 1) or, more conveniently perhaps, from a discriminator set to trigger of exceptionally high peaks (at a multiple of the standard deviation sigma) in a random noise voltage (figure 2). Obviously, a counter of only one binary stage would suffice to determine oddness or evenness, but a full counter may be provided to permit monitoring the numbers to be used. The probability that the number r will occur in a Poisson distribution with mean A is given by"
P(r)=(Ar/r!)e-A.
"The difference between the sum of the even terms and the sum of the odd terms is"
d=SUM[r=0..inf](-1)rP(r)
d=e-2A.
"Since e-2A is about 10-13 for a value of A as low as 15, this principle offers a means of obtaining very high accuracy quite easily. Any drift that occurred in the discriminator or noise level would only affect the value of A and would have an extremely small effect on the probabilities of the 0's and 1's."
"The required Poisson distribution will be obtained if the
pulses counted have a constant probability per unit time."
"The occurrences of high peaks in a true random noise voltage
(such as amplified thermal or shot noise) can also be made
effectively quite independent of each other by using a sufficiently
wide-band noise and a correspondingly high discriminator level.
The time range over which there is any appreciable correlation
between the voltages at different times must vary inversely as
bandwidth
Vincent, C. 1971. Precautions for accuracy in the generation of truly random binary numbers. Journal of Physics E. 4(11): 825-828.
". . . dead time is not in itself a necessary source of inaccuracy in the generation of random binary digits. However, any difference in the dead time between the odd and even states of the counter, due to residual asymmetry in the latter, could be a source of error by affecting the equality of the average times spent in the two states. "
"Another possible source of error due to residual asymmetry would be a difference in the trigger sensitivity between the two states. This would cause an error if there was any possibility that some pulses might reach the counter in the marginal range of amplitude that would cause it to trigger in one state but not in the other."
"Another possible cause of trigger sensitivity error in the counter would be the failure of the type of discriminator used to give a perfect all-or-none action in all circumstances, that is, to emit always either a full-size, normal pulse or none at all. Such a failure is liable to occur, for example, when the discriminator itself is triggered by a pulse that is barely sufficient in amplitude."
"With correctly functioning equipment incorporating the precautions given above, it seems likely that the error in the probabilities in the generation of random binary digits can be made too small to be measured by any practical method or to be of any practical significance."
Maddocks, R., S. Matthews, E. Walker and C. Vincent. 1972. A compact and accurate generator for truly random binary numbers. Journal of Physics E. 5: 542-544.
"The accurate generation of truly random numbers is a long outstanding problem. In a surprising early application of what are now known as Monte Carlo techniques, Lord Kelvin (1901) encountered difficulties in taking numbered pieces of paper at random from a jar."
"The difficulties of producing accurately random digits and of
producing them at a suitable rate were such that the Rand
Corporation (1955) published their well-known book of one million
random decimal digits
Noise source Discriminator Monostable
and --> uA 710 --> 74121 --+
amplifier (w/ ref. pot) |
|
+--------------------------------------------+
|
| Input Gate Monostable Scale-of-2 Output gate
+---> 7400 --> 74121 --> 7474 --> 7400
| |
+-------<------- timing control ------>------+
Figure 1
Figure 1 shows first a block representing a commercial noise source and amplifier "of 500 kHz bandwidth." The amplified noise is conducted into a discriminator block which uses a 710 comparator, and also has an adjustable reference voltage input. The discriminator output triggers a monostable (74121). The output of the monostable is gated by an AND gate (7400) for "Timing control." The timing gate triggers yet another monostable (74121), which clocks a single-bit counter (7474). The counter output is also gated by timing via an AND gate to the output. Presumably, the purpose of the timing is to prevent the counter from changing state as its contents are being read.
"A typical set of results is shown in table 1. In this set,
no runs of more than 20 bits occurred. The expected value of the
run counts were calculated as np and their standard
deviations as {np(1 - p)}1/2, where
n is the total number of runs counted, and p is
1/2 for a run of one, 1/4 for a run of two, and so on. The mean
and variance of the run length distribution provide a good test
of the randomness of the digits and are 2.0023 and 2.0144,
respectively, in these results, being very close to the
theoretical value of 2 in each case. The mean pulse rate from
the discriminator was 50 kHz and the random bit production rate
was 2.5 kHz, giving a mean count of 20." "A noise amplifier
bandwidth of 200 MHz and a monostable dead time of 12 ns would
seem to be reasonably feasible, and would permit a mean pulse
rate of, say, 20 MHz. This would give a random bit in 1 us
or less
Vincent, C. 1973. Random Pulse Trains, their Measurement and Statistical Properties. Institution of Electrical Engineers (I.E.E.) monograph series.
". . . although the compact generator operated entirely satisfactorily, under normal laboratory conditions, without any feedback control of the random pulse rate, such control would be desirable in a more variable environment and can be achieved quite adequately by means of a simple diode-pump ratemeter feedback circuit (Fig. 7.5b), controlling the reference voltage from the pulse train into the input gate. Such a circuit has, in fact, been added, since the publication of the paper."
Figure 7.5 b
+- Ratemeter <--+
| |
v |
White noise source --> Amplifier --> Discriminator --+-----+
|
+-------------------------------------------------+
|
+-> Input Gate --> Discriminator --> Binary Ctr --> Output gate ->
| |
+--------<-------- timing control ------->-------+
Figure 7.5b shows one new block, a "ratemeter," which takes input from the first discriminator and outputs into the discriminator. Presumably, this might be as simple as an R-C from the discriminator pulse train, delivering some proportional level as the control input to the discriminator, but no details are given.
[Tag-line to Fig. 7.8] "The timing is controlled so that the input gate is always open, except for a short interval during which the reading of the scale-of-2 circuit is taken, via the output gate."
Yarza, A. and P. Martinez. 1978. A true random pulse train generator. Electronic Engineering. 50(614): 21-23. (Mid. Oct.)
"A circuit which gives true randomly spaced output pulses is described." "A Zener diode biased in the knee of its characteristic curve is the primary noise source. The noise signal is amplified and compared with a threshold level which acts as a control signal. Lastly, the binary random signal of the comparator output is sampled by the clock train giving the true random pulse train."
"[Zener] noise peak-to-peak amplitude typically ranges between 50 and 100 millivolts in the units we have sampled."
+12 Fig. 4
|
--- +12
/ \ ZD1 |
--- LM-371 |
| 3.3k
*--3.9k--10uF--*--|\ | 710 7474 7400
| | | \ | ___
39k 1k | /--*--10uF--*-----|\ | |
| | | / | | /----|D Q|----|\
| *--|/| 1.5k +-|/ | | | )o-- X
20K pot | | | | +->|C | +-|/
| *----- v 1.5k | |___| |
v 10uf | | |
| v *---------+
v | clock
Fig. 4 shows a Zener capacitively coupled to one input of an LM-371 "wide-band amplifier." An R-C integrated version of the same noise signal is collected on the other input, thus producing a level-tracking differentiator. The amplified noise is capacitively coupled to one input of a high-speed comparator. The output from the comparator feeds the D-input for a "D" flip-flop. The "Q" output from the flip-flop along with clock feeds an NAND gate thus producing either clock-width pulses, or no pulse at all.
By varying the external control signal, one can move the comparator level up the supposedly Gaussian noise amplitude distribution and select an average pulse rate.
Bungay, H. and R. Martin. 1979. Truly Random Numbers. Kilobaud. 3(4): 46-47. (#28)
+12 +12
| |
| 10k 74L00
6.8k |
| *-------|\
| |/ | )o--> to
+---*---68k---*--0.068uF--1k--*---| +--|/ ctr
| | | | |> |
| <| |/ | | |
10uF |-----| --- |
| /| |> Ge /_\ v /RD
| | | |
| (nc) | |
-5 -5 v
The circuit diagram shows a reverse-biased base-emitter junction feeding the base of another transistor. That output is capacitively coupled into the base of a third transistor, to square up the signal. The output of the third transistor drives a TTL AND gate input, along with address select (to stop the count so the value can be read). The output of the gate drives an 8-bit counter which is the random value output. The counter thus counts noise pulses.
"Imagine a roulette wheel spinning at a fast and variable rate.
If the wheel can complete thousands of revolutions before it is
suddenly stopped, the number lining up with a pointer beside the
wheel will be random. Perhaps the intervals between sampling the
wheel are exactly the same every time. This is where the erratic,
variable spinning rate is important
Mayhugh, T. 1981. Build a Noise-Based Random Number Generator. Byte. May. 452-456.
"Figure 1 is a block diagram of a simple generator capable of producing truly random sequences of any length."
Figure 1: A noise source and adjustable level feed a comparator; the comparator output gates an oscillator into an 8-bit counter.
Figure 2: A Zener is amplified through two successive wideband op-amps, each with a gain of about 150. The amplified noise is capacitively coupled into a comparator along with a control level; the comparator has some positive feedback for Schmitt operation. The comparator output gates an R-C oscillator running at about 3 MHz. The oscillator output clocks a 8-bit binary counter, which is the digital output. The control level is adjusted until the comparator output is high (and low) about half the time.
"A great deal of power-supply decoupling and isolation is used in the analog section of the generator. This is necessary to avoid picking up the 60 Hz power signal or any other periodic power-supply noise that could destroy the randomness of this circuit."
"The circuit should be constructed within a shielded enclosure
to avoid RF (radio frequency) or other interference that could
cause a periodic output
Tang, Y., A. Mees and L. Chua. 1983. Synchronization and Chaos. IEEE Transactions on Circuits and Systems. CAS-30(9): 620-626.
"Abstract -- We believe that synchronization and chaos are closely related." "This paper studies a simple but realistic model for a large class of triggered oscillators. Theory and experiments both confirm that the output shows the properties of sensitivity to initial conditions, nonperiodicity, broad spectrum, and complicated recurrence, that characterize chaotic motion."
". . . successful synchronization depends on appropriate relationships between the signal levels and other parameters, and in a system designed to synchronize, some means is always provided to adjust the parameters to make it work correctly. When the parameters are outside some range, the system is not synchronized and the output is not periodic."
"We want to emphasize that we have chosen a class of systems that are easy to understand mathematically and for which the circuit elements are all behaving the way they were designed to behave."
+15
|
100k
pot +15 4558 +15
| | 555 | 555
4.7k __|__ +-120k-*--27k--+ __|__ +--2.2k--+
| | 1 | | | | | 1 | | |
+---|2 3|--pot--+ | |\ | | 3|---* Q1 |
+---|6 | | +--|-\ *-----|6 | | |<
| | | v | \-+ | | 10k-----|
+---|7 5|--+ | / +--|2 | pot |\
| |__8__| | +--|+/ | |__8__| | _|_
| | | | |/ | | 27k \ /
0.1uF v 0.01uF | | v | ---
| | | | v |
v v +----------*---------------------*
| |
C0 | +15---27k---+ Q2 |
0.1uF | |/
| 10k-----|
| pot |>
v | |
| |
*--4.7k--+
|
v
"A standard integrated circuit module NE555 performs the switching between charging and discharging. The output [ pin 3 ] of the NE555 jumps from 15 V down to 0 whenever the threshold input [ pin 6 ] reaches 10 V and jumps from 0 to 15 V whenever the trigger input [ pin 2 ] falls below 5 V. Two transistors act as current sources. When the output of the NE555 is high, Q1 overcomes Q2 and charges C0. Otherwise Q1 is off and C0 is discharged by Q2. The other NE555 generates the triggering signal which is added to the oscillator via an operational amplifier."
". . . the discontinuities in our system remove all stable periodic solutions, whereas the usual one-hump functions tend to have stable periodic solutions even in their chaotic regions [8]-[10]."
Fairfield, R., R. Mortenson and K. Coulthart. 1984. An LSI Random Number Generator (RNG). Advances in Cryptology -- CRYPTO '84. 203-230. Springer-Verlag.
"This paper describes a CMOS digital LSI device which generates a random bit stream based on the frequency instability of a free running oscillator." "The use of this phenomena to generate truly random numbers is not new. The RAND Corporation used this phenomena to generate a table of a million random digits which it published in 1955 [1]."
"In the device under discussion here, a random bit stream is generated by digitally mixing two independent square waves in a positive-edge-triggered D-type flip-flop. In the implementation, a low frequency wave is used to clock the flip-flop and in so doing sample a high frequency wave which is applied to the flip-flop input data lead."
"If the high frequency signal has a 50% duty cycle and the low frequency clock has significant cycle to cycle period variation, each successively generated bit is independent and has equal probability of being a 'one' or 'zero.' What is meant by significant is defined below."
"If the high frequency sampled square wave has something other than a 50% duty cycle there will be a bias toward either 'one' or 'zero' bits at the sampling D-type flip-flop output. This bias can be effectively removed if groups of samples are passed through an exclusive-OR chain."
"The second bias or difficulty which arises stems from insufficient phase jitter or frequency fluctuations on the clock input [the low frequency oscillator]." ". . . if twice the standard deviation of the low frequency period variation is but a fraction of the high frequency oscillator period there is significant bit to bit correlation and individual bits can be guessed from the state of preceding bits. On the other hand, if the ratio of twice the standard deviation of the low frequency period variation to the high frequency oscillator period is greater than 1.5 there is little bit to bit correlation."
"In general one does not get cycle to cycle period variations from the D-type flip-flop clock such that variations span 1.5 or more cycles of the data input signal. Thus, there will be sample to sample correlation between bits out of the flip-flop and knowing one sample and the mean frequencies of the input signals one can predict the state of the next sample with some degree of accuracy." "The correlation correction is achieved as samples generated many clock cycles apart are exclusive-ored together."
"The magnitude of the correlation correction stems from the Gaussian distribution model which can be used for the low frequency oscillator period variations. The Gaussian distribution has the property that a change in the random variable (the period) yields a like change in the standard deviation. This linear property has been experimentally verified in the case of the on-chip oscillator. If we consider samples taken ten cycles apart, as opposed to successive samples, the standard deviation of the tenth clock edge with respect to the first clock edge is tenfold the standard deviation between successive edges. Thus, samples taken many cycles apart have low correlation and the lower the correlation of the samples passing through the exclusive-or network, the lower the probability of predicting the state of the exclusive-or output with any degree of certainty."
Random bits apparently enter a 536-bit shift register or "scrambler" through one of five sequentially selected mixing taps. The shift register accumulates new random bits, and helps with correlation and balance.
Vazirani, U. 1985. Towards a Strong Communication Complexity theory, or Generating Quasi-random Sequences from Two Communicating Slightly-random Sources. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing. 366-378.
"Santha & Vazirani [SV] showed how to use [on the order of] (log n log * n) [ that's what it looks like on the paper ] slightly-random sources working in parallel to produce n-bit quasi-random sequences. Such sequences have the property that they cannot be distinguished from the flips of a fair coin in a very strong sense."
"In this paper we show how to generate quasi-random sequences using only two slightly-random sources."
"The algorithm for generating n-bit quasi-random sequences
from 2 slightly-random sequences is very simple: let x
and y denote [on the order of]
(log n log * n) [ again! ]
bit outputs of the two sources. Then one bit of the output is
simply
[ This appears to say that we get m bits from each of two sources, then AND these bit-sequences and take the parity of the result. But I note that if both sources are heavily biased toward 0's, then we may have no 1's, thus carrying input bias through to the output. The number of sources should at least depend on the bias d in some way. ]
Santha, M. and U. Vazirani. 1986. Generating Quasi-random Sequences from Semi-random Sources. Journal of Computer and System Sciences. 33: 75-87.
"Several computational applications require a source of 'random bit-sequences.'" "Unfortunately, the available physical sources of randomness (including zener diodes and geiger counters) are imperfect [9]. Their output bits are not only biased but also correlated."
"We introduce a very general mathematical model for the physical source and an algorithm to convert the output of such sources into bit-sequences that are provably good for computational applications."
"Shannon's coding theorem says roughly that from any source one may extract as many independent unbiased bits as the entropy of the source . . . ." "By contrast, we prove that there is no algorithm that can extract even a single unbiased bit from a semi-random source . . . ." "This difference stems from the following distinction: the slightly random source with parameter d specifies a certain large class of distributions . . . ." ". . . we show that no bit extracting algorithm is uniformly good for every semi-random distribution with parameter d."
". . . the problem of designing a noise diode with small correlation in its output bits is hard, and the most effective method is to sample the output of the diode at a slow rate. The results of this paper indicate that a radically different approach is viable: sample the output of the diode frequently, thereby getting correlated but semi-random bits. Then extract quasi-random sequences from the outputs of several independent noise diodes." ". . . to generate an n-bit quasi-random sequence, [on the order of] ((1/d)[log?] n) semi-random bits are required. The engineering design effort must now focus upon ensuring independence of the [on the order of] ((1/d)log n) noise diodes."
[ There appears to be some confusion in the use of n and k here. ]
"An easy implementation of a high quality source is the following: On input n, let x11x12 ... x1n ; x21x22 ... x2n ; ... ; xk1xk2 ... xkn be the n bit outputs from k = [on the order of]((1/d)log n) independent semi-random sources. The output is y1y2 ... yn where y = parity(x1ix2i...xki)."
". . . the parity function achieves optimum unbiasing on m semi-random bits."
Agnew, G. 1986. Random Sources for Cryptographic Systems. Advances in Cryptology -- CRYPTO '85. 77-81. Springer-Verlag.
"A common structure in semiconductor systems is a metal
insulator semiconductor capacitor (MISC)." "It consists of a
p-type semiconducting substrate material covered by insulating
silicon oxide (SiO2) with a
metalized pad placed over the insulation
"Electrons will eventually migrate into the potential well and fill it up (see Fig. 2b). The period over which electrons are collected is referred to as the integration period. If we now remove the voltage Vg from the metalization, a net surplus of electrons will be present and this "charge" can be measured."
"There are two major mechanisms by which free electrons can be
generated to fill the potential well
"The implementation consists of two identical structures, cells X and Y, in close physical proximity. We allow them to "charge" over the same integration period, then measure the difference in charge between them and assign either a 1 or 0 to the outcome. This amounts to the construction of a device with high common-mode rejection since any attempt at influence will be common to both devices and removed in the comparison. In addition, the close physical proximity of the devices will result in consistent temperature effects in both cells."
[ A background to chaos may seem a little off-topic, but several proposals for randomness machines use chaotic circuits. Alas, chaos is not a magic way to produce a guaranteed unpredictable sequence. Indeed, it was the ability to analyze chaos that created the field of study. ]
Bak, P. 1986. The Devil's Staircase. Physics Today. December. 38-45.
"In the 17th century the Dutch physicist Christian Huygens observed that two clocks hanging back to back on the wall tend to synchronize their motion. This phenomenon is known as phase locking."
"If some parameter is varied -- the length of a pendulum or the frequency of the force that drives it, for instance -- the system will pass through regimes that are phase locked and regimes that are not." "For weak coupling the phase-locked intervals are narrow, so that even if these is an infinity of intervals, the motion is quasiperiodic for most driving frequencies; that is the ration between the two frequencies is more likely to be irrational."
"We shall see that if one plots the frequency of the oscillator against the frequency of the applied force the resulting curve may consist of an infinity of steps -- the Devil's staircase."
"As the interaction between two competing frequencies increases, the oscillations eventually begin to interfere with each other, and there is a transition to a state that features chaotic motion in addition to the periodic and quasiperiodic motion."
"The transition to chaos is basically caused by the overlap of resonances, and one can visualize the chaotic motion as an erratic jumping between resonances."
McKean, K. 1987. The Orderly Pursuit of Pure Disorder. Discover. January. 72-81.
"In a world as crazy as this one, it ought to be easy to find something that happens solely by chance. It isn't. Take the case of the experimental random number generator that computer scientist David Gifford built when he worked for Xerox a few years ago."
"Gifford's plan was to pluck his numbers from the randomness inherent in white noise -- sound composed of a broad jumble of frequencies, like that of a TV set tuned to an unused channel. The white noise in his machine wasn't sound, but only a randomly fluctuating voltage. The machine would sample this voltage as often as ten million times a second, registering a zero if it was negative, a one if it was positive."
"As Gifford had expected, the machine's output at top speed was hardly random. The voltage didn't oscillate fast enough to move from positive to negative, or vice versa, during the 100 nanoseconds between samples. The result was a correlation between digits: that is, ones were more likely to be followed by ones, and zeros by zeros, than would be expected by chance. To reduce the correlation, Gifford slowed the sampling speed, giving the voltage time to wiggle around before the next sample. 'I began to get acceptably random numbers at something like a few thousand bits per second.' he says.
"But the correlation never disappeared completely. Even at the glacial pace of only a digit or two per second, Gifford calculated, a faint ghost of correlation would still haunt the data. Says Gifford, who's now at MIT, 'My conclusion was that it would be difficult, if not impossible, to create true randomness with that machine."
[ . . . ]
"In theory, devices like the reverse-biased diode should be capable of perfect randomness, because they rely on events at the atomic level that quantum mechanics holds to be completely random."
"Yet attempts to mine this randomness run afoul of problems of scale. Wolfram offers an example: a randomizer that works by counting the decay of individual cobalt-60 atoms. Gama rays from a disintegrating atom trigger a flash of light in a phosphor; the light sets off a cascade of electrons in a photomultiplier tube; the cascade is detected as a faint pulse of current. While the gamma rays may be random enough, the photomultiplier's output won't be. Why? 'Because if the next gamma ray arrives too soon after the last one,' Wolfram says, 'the previous cascade won't be cleared out, and the detector won't fire.' The result: correlations between succeeding bits of data, induced by the measuring device itself."
[ . . . ]
"The fundamental difficulty faced by Blum and others who seek true randomness is that while there are many ways to prove that a isn't random, there is no way to prove that it is. The statistical tests used to evaluate randomness all have an ad hoc quality to them."
Espejo-Meana, S., A. Rodriquez-Vazquez, J. Huertas and J. Quintana. 1989. Application of Chaotic Switched-Capacitor Circuits for Random Number Generation. European Conference on Circuit Theory and Design. 440-444.
"Resorting to switched-capacitor (SC) is a well established
technique in the field of analog VLSI
"Recently, it has been demonstrated that very simple SC circuits can generate chaotic behaviors . . . . Although these circuits are interesting from a circuit-theoretic point of view, their actual practical applications have not been clearly identified. It has been suggested to use them as practical noise generators (6). However, a clear demonstration of this application is lacking."
"The proposed random number generator is based on a one-hump piecewise linear discrete map"
x(n+1)=A-B|x(n)|
"Analysis shows that the parameter A in eq.(2) does not influence the qualitative behavior of the map, but acts just as a scale factor. Different qualitative behaviors can be however observed depending on the value of parameter B."
"Fig. 2 has been breadboarded using off-the-shelf components. The measured results are in accordance to the numerical ones."
"Although directly generated sequences appear to have a nonideal autocorrelation function, this can be improved by periodic sampling."
Nisley, E. 1990. BASIC Radioactive Randoms. Circuit Cellar Ink. April/May. 58-68.
"While pseudo-random (pronounced "fake random") numbers may be OK for computer science types, Real Engineers get Real Random Numbers by timing nuclear disintegrations with a Geiger-Muller detector." "A few months ago I saw the RM-60 Micro Roentgen Radiation Monitor from Aware Electronics. It is a Geiger-Muller tube that connects to a PC's parallel or serial port, with the circuitry drawing power from a single interface pin."
"The RM-60 produces a down-going 75-90us pulse each time it detects a radioactive decay particle. It is sensitive to alpha, beta, and gamma particles, but the output pulse is identical for all three because the detector tube operates in Geiger mode. The maximum count rate is thus over 10,000 counts per second . . . at which point you have more than just a radon problem in your basement."
"The background radiation in my office provides about 10-15
counts per minute, with the time between counts ranging from
100us to over 45 seconds
Most of the article concerns details of programming a "RTC52 Single Board Microcontroller" in BASIC and then assembly language for better performance. The program measures the time between Geiger pulses.
"A histogram shows that the random intervals are not uniformly distributed; there is a definite peak around an 'average' value, but you'll find all values between zero and huge." "From what little I remember from my courses in probability theory, the curve resembles a Poisson distribution."
[ Actually, the intervals between random events are not expected to be Poisson, but instead should be a simple negative exponential:
-rt
I1(t) dt = re dt
where I is the interval,
r the average event rate,
dt the differential time increment,
rt the average number of events over t,
and e the base of natural logs Bernstein, G. and M. Lieberman. 1990. Secure Random Number Generation Using Chaotic Circuits. IEEE Transactions on Circuits and Systems. 37(9): 1157-1164.
"In this paper we show how to use a chaotic circuit as a secure random number generator and give an example using a first-order nonuniformly sampling digital phase-locked loop operating in a chaotic regime." "By the security of a pseudorandom or random number generator we mean, roughly, how difficult it is, based on past values of the sequence, to predict future values of the sequence."
"The first order DPLL [digital phase-locked loop] is the simplest synchronization system [11] that exhibits chaos."
". . . to use this circuit as a secure random number generator
it is best to wait 4-8 iterations before taking another
bit
"One aspect of chaotic circuits not mentioned so far is the sensitive dependence of the Lyapunov exponent on the value of the system parameters." "For out application, we must operate in a region having relatively large Lyapunov exponents, far from significant stable orbits."
[ There is no attempt to provide a statistical analysis of the resulting random sequences. ]
Wallace, C. 1990. Physically random generator. Computer Systems Science and Engineering. 5(2): 82-88.
"There are (at least) three ways of making an unpredictable generator: first, one can use a pseudorandom generator in which the functions f( ) and g( ) are such that the discovery of the state S is a difficult cryptographic problem; second, one can amplify and digitize a fundamentally random physical signal such as thermal noise; and third, one can construct a device which, even when physical noise is ignored and the device is regarded as fully deterministic, has a provably unpredictable output. Here a generator which combines these approaches is designed."
Figure 1
+-----+ 12-bit Ctr +-----+
| | | | |
| v | v |
| X RAM <----------*----------> Y RAM |
| | | |
| v | |
| Times 8 +-----------*-----(------*
| | | | | |
*----(-------*--(--------+ | | |
| | | | | | | |
| | v v v v | |
| | F G | |
| +----+ | | +----+ |
| v v v v |
| Add Add |
| | | |
| v v |
| Xreg Yreg |
| | | |
+------------*-----+ +-----*------------*
v v
Add
|
v
Figure 1 shows two 4k-element tables which are scanned by a 12-bit counter. At each step, a value is taken from each table, combined with the other table in various ways, and new values placed in each table. Apparently the data paths are 16-bits wide. Functions F and G select 14 bits from the 32 inputs, and also compute some AND-OR-NOT result for the last two bits.
"The sequential algorithm of this section is not intended as a secure encryption scheme, but does lead to a sequence of values which is hard to predict."
+5 MC10125
Figure 2 |
220 +---------*---|\
| | | |+\
+----* | 1.5nF | /--+
74F74 T1 | | | | |-/ |
___ |< 220 | VB---*---|/ |
1--|D Q|----*---| | | | |
clk--|C | | |\ -5 | 0.1uF |
| | | | | | |
|_/R| | *---------+ v |
FFA o | | |
| | | |
+-----(-----(------------------------------+
| | +---------+
| | | ___ |
| | +-|D Q|--(-----> output
+5 +----(-----------|C | |
| | | /Q|---+
1.8k *----+ |___|
| | | FFB
*-----+ | C
| T3 | T2 | |
\| | |/ -5
|---*-------|
<| | |> +---220---*---> VB
| 0.1uF | | |
390 | 390 v 330
| -5 | |
-5 -5 -5
"Flipflop A is turned on by every rising clock edge [ unless held off by the 10125, which only occurs transiently ]. While it is on, condenser C is discharged by a constant current from transistor T2, the current being determined by the common bias voltage source T3. When, after a time which may exceed a clock period, the voltage on C falls below the switching threshold of the ECL-to-TTL converter MC10125, A is asynchronously turned off. Switched current source T1 then charges up C until the next clock edge turns A on again. Flipflop B, which gives the output, is inverted whenever A turns on.
"Choose units such that the clock period is 1, the voltage z on condenser C rises at rate 1 when A is off and falls at rate 1/h when A is on, and the switching threshold is zero. Assume h is an integer greater than 1. Voltage z cannot fall below zero (neglecting circuit delays). Since A cannot remain off for more than one clock period, z cannot rise above 1."
". . . the operation of the current sources and threshold detector are affected by noise processes, primarily in the transistors, which generate electrical noise equivalent to errors of the order of a microvolt at the input of the threshold detector." ". . . an initial noise error of a microvolt is amplified to about a volt in 25 cycles."
Hsueh, K. and R. Hamernick. 1990. A generalized approach to random noise synthesis: Theory and computer simulation. Journal of the Acoustical Society of America. 87(3): 1207-1217.
"A generalized approach to the synthesis of Gaussian and non-Gaussian random noises as well as purely impulsive waveforms has been developed. The basic idea behind the synthesis is to construct the amplitude-time waveform from the frequency domain, i.e., from the amplitude and phase spectra. By maintaining a predetermined (reference) amplitude spectrum and performing certain specific manipulations of the phase spectrum within any selected band of frequencies and then applying the inverse discrete Fourier transform (IDFT), peaks in the non-Gaussian random waveform from the selected band of frequencies that have been phase manipulated. Entire families of signals can thus be produced having the same energy spectrum, but statistical characteristics that vary along the continuum from Gaussian (skewness = 0 and kurtosis = 3) through non-Gaussian (variable skewness, kurtosis, and crest factor) to purely impulsive (shock/transient) signals."
[ Let me say from the outset that I am dubious. ]
Davis, D., R. Ihaka and P. Fenstermacher. 1994. Cryptographic Randomness from Air Turbulence in Disk Drives. Advances in Cryptology -- CRYPTO '94. 114-120. Springer-Verlag.
"Abstract. A computer disk drive's motor speed varies slightly but irregularly, principally because of air turbulence inside the disk's enclosure. The unpredictability of turbulence is well-understood mathematically; it reduces not to computational complexity, but to information losses. By timing disk accesses, a program can efficiently extract at least 100 independent, unbiased bits per minute, at no hardware cost."
"We call these measurements sanity checks, because our argument for the disk's value as a noise-source actually rests on the mathematical properties of the disks air turbulence, and not on our observations."
"For our measurements, we used an IBM RT/PC desktop workstation and a Micropolis 1320 series 40 MB hard disk with nonremovable 5.25 inch media. A permanent-magnet brushless DC motor turns the disk spindle at a nominal rate of 3600 r.p.m. The motor's phase-locked loop stabilizes the rate to +/- 0.03%, which amounts to a positional accuracy of 5 usec." "To measure disk-speed fluctuations, we repeatedly read a chosen disk block, and recorded each access-completion time." "The RT's 1024 Hz hardware clock limited our measurement precision to about 1 msec."
"Our measurements were consistent with the 5 usec variation."
"Our analysis of 1.7 million disk-periods showed that some noise was present in the variation, its auto-correlation fell off within 5 seconds, and its entropy amounted to 100 bits/minute [12], enough for 2,600 highly random DES keys/day."
[ Alas, your editor (Ritter) thinks this analysis has not been nearly skeptical enough:
I'd have to see a great deal more skeptical analysis before I would believe that any so-called random values result from air turbulence inside a hard drive. ]
Last updated: 2002-12-04