Hardware RNG (measures AC mains chaos to make random numbers)

[Mr RB]

Hi, I mentioned this project in another thread. Here is a hardware based random number generator that outputs the random numbers as serial bytes at 9600 baud. The random numbers can be used for encryption seeds or statistic tests or any other use you might have for natural entropy.

**broken link removed**

The AC mains waveform (at 12v, from a small plug-pack transformer) is measured against the PICs xtal based 5MHz counter, and the least significant bit is used to build the random number.

It uses a cheap PIC 16F628A and produces a very nice quality output;

**broken link removed**

I have provided the schematic, C source code and PIC HEX files etc, everything you need to build one or play with this concept, the project is here;
https://www.romanblack.com/HardRNG/HardRNG1.htm

 

[4pyros]

Neat idea! Reminds me of the pig pen RNG in mind craft.

 

[alec_t]

Nice work, RB. If and when I need one of those I know where to look.

 

[jpanhalt]

Can any two oscillators be used in this manner, or is there something special about using the mains?

John

 

[throbscottle]

Can any two oscillators be used in this manner, or is there something special about using the mains?

John

Mains is a very 'dirty' signal - constantly there are lots of things connected to and disconnected from it which affect phase, frequency, and add noise, and the frequency is only kept within about ±2Hz or so of your country's nominal value anyway - hence it's a good source of random numbers. Mr RB explains this extremely well if only you'd look at the web page...

 

[jpanhalt]

@throbscottle:

1) I most certainly did look at and read the link provided by Roman Black.
2) Is a "dirty" signal always random? Are connections and disconnections of loads to the mains random, or is there a predictable periodicity? If it is random, then why not measure it directly, rather than rely on a second crystal oscillator?

In other words, what I am trying to get at, perhaps in too round about a way, is why you need a second accurate oscillator if the variations in the main voltage are random.

John

 

[throbscottle]

It's a good point, and I'm not qualified to answer about the quality of the randomness of connections to and from the mains. I expect there is a very mathematical solution which is way, way beyond me. However, I think it's what you would call a safe assumption.

I think you need a precise second oscillator to be able to sample the source of random events at regular intervals - this way you convert the variations between each sample into actual useful numbers.

 

[jpanhalt]

I think you need a precise second oscillator to be able to sample the source of random events at regular intervals - this way you convert the variations between each sample into actual useful numbers.

That gets at the essence of my question. Assuming the number of cycles counted is large enough for the three LSB to show errors in the cycle time, results from irregular or regular samplings cannot be distinguished. The results are both random. (I am not sure what the minimum number of counts must be. Obviously, since you are looking at the 3 LSB, you would not want the sample to be so small that statistically, one would only expect the 2 LSB's to be affected. Going larger should not make any difference.) Since 50,000 counts is about 17 minutes at 50 Hz, one could use his wrist watch to start and stop the counting interval.

Now, why can't any old oscillator that has short-term stability than 0.2% (100 parts/50,000) be used?*

John

*Edit: Actually, a worse oscillator than that might work better, so long as you measured enough of a period so the 3LSB's were not affected by known variables such as temperature and appeared to be random.

 

[edeca]

Have you tried running the output through the http://en.wikipedia.org/wiki/Diehard_tests ?

There is http://www.phy.duke.edu/~rgb/General/dieharder.php which looks promising.

 

[cachehiker]

I can't help but be reminded of the novel "His Master's Voice", by Stanislaw Lem.

You've found a repeating cycle indicating a signal. Is it a sign of intelligent life? Is it just random? Or just yet to be explained and/or debunked?

 

[alec_t]

Just wondering; can the switching characteristics (e.g. dv/dt sensitivity, threshold shift) of the comparator in the PIC introduce bias in the randomness? Or does it all cancel out in the wash?

 

[jpanhalt]

I can't help but be reminded of the novel "His Master's Voice", by Stanislaw Lem.

You've found a repeating cycle indicating a signal. Is it a sign of intelligent life? Is it just random? Or just yet to be explained and/or debunked?

Good point. Maybe that is how "They" communicate? "Contact" is a movie along similar lines that I enjoyed. RIP Carl Sagan. https://en.wikipedia.org/wiki/Contact_(film)

John

 

[Mr RB]

Wow lots of questions!

To Jpanhalt; You are correct that the accuracy of the second oscillator is not that critical. The chaos component exists in the shape of each mains cycle, and the chaos will not be removed by any small additional chaos in the timing of the measuring. Basically entropy + pattern = entropy, entropy + slight entropy = entropy etc.

The reason I originally specced a 20MHz xtal was to run the cheap PIC at its max speed so it gave a 5MHz counter. In the hardware unit I used a 20MHz ceramic resonator which is still accurate 20MHz enough for good serial comms but is less accurate than a proper XTAL. Now if you used a better PIC that had internal OSC with PLL that could still give you a 5MHz timer that would be ok too, but I wanted to stick with the cheap and very popular 16F628A that most people have and that I have used in other projects on my web page.

To Edeca; I'm familiar with diehard and dieharder suite of tests, but they are tailored for very large sample sizes. I used ENT.EXE which is good enough for smallish data sizes. The results are well within what you would expect for true random data, in fact the 3 samples that I made roughly 100kb each all measured good and all were significantly different to each other, which are all things to be expected from real world entropy. Below shows one of the tests;

**broken link removed**

To Cachehiker; Actually I didn't find any repeating data although that is in the mains chaos if you look for the components (other frequencies etc). By using the data from the least significant bits this eliminates the larger patterns, in the same way you could measure the spacing of bricks in a brick wall down to the millionth of an inch, then just keep the last digit.

To Alec_t; That's a great question! On my first test I almost canned the project. I was using a gentle RC filter of about 47k to 0.1uF (I think) on the PIC capture input pin, and was seeing significant biasing where the capture module was firing on odd capture counts most of ther time, with count 1 (out of 256) having a rather high bias. It took me half an hour to realise that the timer1 CCP1 counter was drawing a Vdd current spike on clocking from 255 to 0, and this was dragging down Vdd by some microvolts and this was pushing the PIC CCP1 schmidt trigger pin to clock that instant in time.

To fix it I used the PIC comparator to detect the input voltage, and dropped the mains source impedance to a few hundred ohms and removed the input cap. Then added a larger tantalum cap to Vdd, and another on the comparator Vref. The result was an honest triggering of the exact voltage of the mains input regardless of tiny Vdd changes. The comparator output is a very fast digital output that now clocks the CCP1 capture pin instantly, not depending on any factors of the capture module. I then run about 100kb of data and recorded the 3 LSB bits and there was no significant bias I could detect.

Ideally all other factors will "average out in the wash", especially since the design now XORs three different and independent bits from different points in time. Ultimately this RNG data would be used by seeding it into a software psuedo RNG anyway if you want the very best data, as real RNG data can trend (for instance it could make the same byte 10 times in a row, which happens in nature, but could never happen in most psuedo RNGs).

 

[jpanhalt]

1) Would it make any difference if the line frequency were stable and your local oscillator was the source of chaos? How can you tell the difference?

2) Let me suggest that we call this the Black Noise Theorem: The 3LSB of the count of any recurring event will appear to be random when measured for a sufficiently long time.

John

 

[alec_t]

Ultimately this RNG data would be used by seeding it into a software psuedo RNG anyway if you want the very best data, as real RNG data can trend (for instance it could make the same byte 10 times in a row, which happens in nature, but could never happen in most psuedo RNGs).

I guess it depends how you define 'best'. If real random data can trend then shouldn't you let your RNG output trend? Pseudo-random, by definition, isn't truly random.

 

[ericgibbs]

A truly [real] random 'sequence' would be infinite in size, all the known random sequences we generate must by definition be pseudo random values of a finite sequence size.

 

[cachehiker]

Actually I didn't find any repeating data although that is in the mains chaos if you look for the components (other frequencies etc). By using the data from the least significant bits this eliminates the larger patterns, in the same way you could measure the spacing of bricks in a brick wall down to the millionth of an inch, then just keep the last digit.

I'm aware of the technique. I've also used it, just not as part of such a rigorous implementation.

The novel I couldn't help but be reminded off opens with the author of a book of truly random digits generated from cosmic background noise being persecuted by statisticians complaining that a pattern had been found. This of course sets all the scientists, politicians, evangelics, military contractors, etc. off on their own investigations intent on furthering their own agendas.

 

[Mr RB]

1) Would it make any difference if the line frequency were stable and your local oscillator was the source of chaos? How can you tell the difference?

Well if you could invent an oscillator that had a GOOD chaos component, then you could just sample that at periodic intervals and produce good RNG data. I've tried a couple of designs for a "Chaoscillator" and have some ideas that might work, although a lot of testing needs to be done to see whether they are actually chaotic or just a very complex blend of beat frequencies.

I'll probably post a "Chaoscillator" thread when I've done some more testing as it is an area i want to explore.

The big benefit of useing the mains waveform shape is that it is affected by thousands or millions of things that exist in the real world and are all unknown to us (like appliances being switched on), and those things are not related to the 5MHz counter frequency. I guess an analogy might be a weather system, you have a day and night temperature waveform (like the mains waveform) but at any sampled instant there are millions of tiny factors affecting the local temperature so you have a large chaos system where big trends are known but on a microscopic level it is beyond prediction. The extracted data is far inside the "noise floor".

2) Let me suggest that we call this the Black Noise Theorem: The 3LSB of the count of any recurring event will appear to be random when measured for a sufficiently long time.
...

Hmm, that's not really what I am saying. If the thing being measured has a noise component that is significantly larger than the LSB measurement, then the LSB measurement is unpredictable as it can only clock part of the noise and none of the large trends. For instance in the mains waveform timing each cycle is 50000 counts but there are always +/- 50 to 100 counts of noise included in each cycle, so measuring to 3 LSB keeps only 8 counts of those 100 or so noise counts.

I can't claim any great originality as this is just a standard way of measuring the period (time) noise, which is done in some other RNG systems. Maybe I am the first to use the convenient AC mains waveform as a noise source for a small hardware RNG, or that XORing different bits from different points in time might be original but both are "obvious" and have likely been done before.

I guess it depends how you define 'best'. If real random data can trend then shouldn't you let your RNG output trend? Pseudo-random, by definition, isn't truly random.

Yeah the both have their uses, but for smaller to medium sample sizes a good PRNG is better, like for a keyword or for a statistical process like gambling software. If that small chunk of data you are using has a bad trend it's worse for those cases. From what I've read in many cases it's better to use real RNG data to seed or hash with PRNG data so it gives the best of both worlds.

Maybe MisterT will speak up, if I remember right he had some college time with RNGs, or at least with some statistical stuff needing RNGs.

 

[jpanhalt]

Thank you for the very thoughtful responses. This Winter, when I will have more time for my hobbies, I will play with your circuit.

John

 

[Mr RB]

You're welcome. I look forward to seeing anything you come up with!