Re: [math-fun] How to generate an infinite number of true-random bits in hardware
The new Intel random number generator, code name "Bull Mountain", starts from thermal noise at 3 GHz, conditions the bits, and then uses these numbers as seeds to generate 511 pseusorandom numbers per true random number. It is this last step that I dislike and don't trust.
--Aha. However, this last step probably will be good enough to assure Intel bits pass all the usual test packages like TestU01 (unless they've been total idiots... which they might have been). It likely will destroy cryptographic security, but you could just only take 1 number per 512 to get that back. If Intel is doing this I don't see why they needed 3 GHz, why couldn't (3/512) GHz have sufficed?
Thermal noise has power 4kT per unit bandwidth. If you're building your own circuit, 10 MHz is a reasonable bandwidth, and at temperature 300 K, the noise is 1.6e-13 W. With a 1 Mohm input impedance, and using P = V*V/R, the RMS noise voltage is 400 microVolt.
--You already blew it because the input capacitance of typical op-amp pin is 4 pF, and R*C for R=1megaOhm and C=4pF is 4 microsec, so you just cut off your "10 MHz" bandwidth right there.
An amplifier gain of 2500 brings this up to a convenient 1 V, and this can be done in two or three stages using op-amps, with AC coupling between stages to avoid amplifying the op-amp bias voltages.
--Hi-gain amps are vulnerable to oscillation from tiny parasitic capacitances coupling output and input. You can try to avoid using fancy shielding, but, why even go there if you don't have to? This is especially worrying when your amp is high frequency (10 MHz is pretty high and with several cascaded amps you maybe need 3X more speed). Most commercial op-amps are designed for lower frequencies, or at least this used to be true. By the way, if you really want to take the "big amp" approach I disparage, a better source of noise is a neon light. Lots more than thermal noise in a resistor. --Intel and your schemes both seem vulnerable to crosstalk from nonrandom noise, i.e. from other signals within your computer (if phsyically located within your computer, e.g. on the processor chip) Your "random" bits would then be highly "predictable" to the right predictor. Again you can try to shield, but why go there if you do not have to?
HotBits uses a 5 microCurie Cs-137 source. This is 37,000 disintegrations per second. It takes 4 consecutive pulses, at times A, B, C, D, to generate 1 bit. The time differences T1 = B - A and T2 = D - C are compared. If T1 < T2 a zero is output, if T1 > T2 a one is output, and if T1 = T2 no bit is output. After the detection efficiency and timing processing, 100 bytes per second are provided to you, but maybe also to the CIA, KGB, and Mossad.
I actually sent the hotbots guy a note, below, but he responded in a very annoyed way, further below. WDS --> John Walker. About hotbits, you are not getting nearly as many bits per second as you could. Let C be the mean time between clicks on your rad detector, and assume that two clicks separated by less than B is bad news since the rad detector has trouble recovering that fast. Finally let A be the time-resolution of your time measuring device. I assume 0<A<<B<C. [C will change gradually as your rad source runs out of atoms, you need to keep its value updated.] Let a click occur that is time T after the preceding click. If T>B then compute Q = exp( (B-T)/C ) else wait for next click. Then Q will be (in principle) a uniformly distributed real number in (0,1) because T should be exponentially distributed.T Because A>0 we cannot get an infinite number of random bits out per click, but it ought to be safe to output the most significant log(C/A) bits of Q. I'm guesstimating that C=300 microsec, B=1 microsec, A=1 nanosec. If so, then each click ought to safely give you 11 more random bits. I gather this would be an improvement over your current bit rate by a factor of about 44. Walker --> WDS: This is complete nonsense. I have put my my own design of a random number generator by radioactive decay out for public scrutiny for more than a decade and every single quibble has been argued from every possible direction. I have a collection of letters from tenured professors in statistics which argue: A) I am crazy to measure two separate intervals delimited by four decay events, and B) I am crazy not not measure the intervals between the first and second and second and third of three decay events. To these, I say, thank you profs, but you can't claim A) has any correlation, and I'd rather not debate the partisans of B). Your suggestion makes vastly more assumptions than can be justified based upon the properties of the generator and the detector. Random event generation encourages radical conservatism in design as much as engineering of earth satellites where one "earns out" the engineering fee only if the bird functions in orbit more than 10 years. You can get a whole lot of bits per second by running an oscillator at, say, 50 MHz, and then latching it at each decay and passing that to the computer. Sounds great, until you think about whether the duty cycle of the oscillator was precisely 50/50 or worry about metastability in the latch. Try putting up a generator with your design and see what E-mail you get from people who critique your design. If I'd had it to do over, I'd never have done HotBits. I do not wish to discuss this further. --end.
Whoops, I made a mistake earlier. I gave the decay rate for a 1 μCi source. For 5 μCi, it's 185,000 per second. Warren, thanks for the reminder about input capacitance, it had completely slipped my mind. And thanks for the suggestion about neon tubes instead of resistors as the noise source. But this reminds me, there are noise diodes designed exactly for the purpose of generating noise. One supplier is noisecom.com (they were at the top of Google search). Their NC104 model provides 3 MHz bandwidth with noise output into a 2200 Ω load of 3 μV/Hz^1/2, i.e. 5 mV RMS if the full bandwidth is usable, or 1.6 mV if filtered down to 300 kHz. If the first amplifier has 7 pF input capacitance, then, together with the 2200 Ω load, the upper cutoff frequency is 10 MHz. But if you make your own circuit, there remains the problem of getting the random numbers into the computer. The Bull Mountain RNG is supposed to be available in the Intel Ivy Bridge processors that are expected out in early 2012. Since these CPUs, which will implement to RDRAND instruction, will be the main processor in PCs, it seems simplest to go this route, taking one out of 512 bytes if you distrust the AES. -- Gene
participants (2)
-
Eugene Salamin -
Warren Smith