Some data on generating random numbers via ADC

Go To Last Post
9 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I've been playing around with this idea this morning, and have a bit of data. The idea is simply to regard the LSB of an ADC conversion as a random value (1 or 0) and generate a sequence of these values to create random numbers. I have no idea how valid such numbers would be, but I did do a number of measurements of two pieces of data related to the sequences:

1) How many 1s vs 0s are generated
2) How often a bit is the opposite of the previous bit

I did a number of tests of 1000 ADC readings, and found that both (1) and (2) were always about 50% +/- a couple of percent. Those seem to be encouraging findings. Now I'd like to generate large numbers of 8 and 16-bit values from these sequences and somehow test to see if they are good random numbers. Anybody know how to do that?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

https://www.avrfreaks.net/index.p...
https://www.avrfreaks.net/index.p... [leading to "diode"...]
https://www.avrfreaks.net/index.p... [with code]
https://www.avrfreaks.net/index.p...
...
That quick Forum search (random number adc) uncovered the above and enough links to get you going.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This is a popular method, and perfectly suitable for many non-security purposes ( such as collision back-off time on a CSMA net). However, for applications requiring 'real' randomness, its not that great. Have a read of this article...

http://arxiv.org/pdf/1212.3777.pdf

Another often attempted method of obtaining true random numbers is to sum up the contents of SRAM upon power up. While you might expect it to be completely random, it is not. I recently experimented with several atmega1284p chips. Despite there being 16K of SRAM on those delightful little chips, I could obtain, on average, only 6 bits of entropy. And that was under very controlled circumstances.

A promising method utilizing the 'jitter' between the 'calibrated' 8 Mhz RC oscillator and the 128 Khz Watchdog oscillator produces good results, but again only in very controlled circumstances. In non-trivial applications, the oscillators will usually phase-lock. At least, they did in every experiment I performed.

If true randomness is required, a diode noise generator, done correctly, is a cheap and effective method. But if the ultimate use is for encryption, why not go with an Xmega part which includes the random bit generator, along with AES and DES functionality?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

mikericetga wrote:
In non-trivial applications, the oscillators will usually phase-lock. At least, they did in every experiment I performed.
I'd be interested to see your experimental results, and how you drew that conclusion. It is one I had not considered. Typical watchdog oscillator frequency at 5V and 25C is about 111.8 kHz. That's 8MHz/71.556350626. It would seem unlikely that phase lock could occur naturally.

Have you done any test with an external crystal oscillator in place of the calibrated internal oscillator?

I've written an RNG library that makes use of the WDT to fill an entropy pool at a nominal rate of 62.5 bits per second. It passes most of the randomness tests I've subjected it to, but not all of them. I've only tested on an Arduino board with 16 MHz ceramic resonator.

JJ

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

Last Edited: Fri. Jun 21, 2013 - 05:04 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

mikericetga wrote:

If true randomness is required, a diode noise generator, done correctly, is a cheap and effective method. But if the ultimate use is for encryption, why not go with an Xmega part which includes the random bit generator, along with AES and DES functionality?

I don't actually have an application, I've just been curious about it for some time, and last night I actually dreamt about it, so this morning I thought i'd spend a little time playing with it. Thanks for the link to the article.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

kk6gm wrote:
The idea is simply to regard the LSB of an ADC conversion as a random value (1 or 0) and generate a sequence of these values to create random numbers.

The idea sounds easy, but it isn't.
You need a white noise source to get real random numbers.
In former days there are noise diode vacuum tubes used.
But they are big and expensive.

If you feed a constant voltage into the AVR-ADC, you get a constant reading of all 10 bits.
Only, if the AVR switch loads (e.g. LEDs) and lift the common GND with this current, then the readings are different.
But since switching loads was generated by the code, this differences are not random.
Also if you get different readings without it, it may be 50/60Hz influence, which was sinus, but no noise.

To check, if numbers are random, you may write them into a file as binary and try to zip it.
If the zipped file was larger, then they seems random.
But if the zipped file was smaller, then they are not random, since only repeated sequences can be compressed.
For this check you should use a large amount of numbers, e.g. 1MB.

Peter

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

mikericetga wrote:
But if the ultimate use is for encryption, why not go with an Xmega part which includes the random bit generator, along with AES and DES functionality?

I haven't found how to do this in the PDFs. I'm using (or planning to use) ATXMEGA192D3-AU because I have the silly notion that I'll be needing the RAM space.

The largest known prime number: 282589933-1

It's easy to stop breaking the 10th commandment! Break the 8th instead. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

danni wrote:
kk6gm wrote:
The idea is simply to regard the LSB of an ADC conversion as a random value (1 or 0) and generate a sequence of these values to create random numbers.

The idea sounds easy, but it isn't.


Yes, I can see that there's no guarantee of a random LSB. The setup I used had the ADC connected to a 10k pot so I could feed the ADC the full voltage range. The LSB seemed most random with the pot set at ~50%, as I would have expected. At 0% or 100% it was much less so, again as expected. I'm assuming the more resistance in the ADC input path, the more noise. I would expect that connecting the ADC to any active digital or analog signal would give good results in the LSB. I could also imagine that "abusing" the ADC during a conversion, such as changing the input channel immediately after starting a conversion, could be helpful.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

kk6gm wrote:
The LSB seemed most random with the pot set at ~50%, as I would have expected. At 0% or 100% it was much less so, again as expected. I'm assuming the more resistance in the ADC input path, the more noise.
Well, no. The 'noise' you are seeing is almost certainly generated internally by switching digital paths, normal to the operation of the device. As such, it isn't really random, as it is deterministically generated by the operation of the device.
Quote:
I would expect that connecting the ADC to any active digital or analog signal would give good results in the LSB.
Again, no. While an RNG based on this method possibly would be suitable for generating packet re-transmit intervals for a comms link, or perhaps for a 'Magic 8-ball' toy, I wouldn't trust it's 'randomness' to anything else.
Quote:
I could also imagine that "abusing" the ADC during a conversion, such as changing the input channel immediately after starting a conversion, could be helpful.
While that seems like a good approach, the ADC doesn't work that way. The MUX channel is latched before each conversion is started. Changing MUX at any time during a conversion will have no effect whatsoever on the conversion in progress. The best you can hope for is some entropy in the 1 or 2 LSB when switching between two MUX channels of different voltages, and even then only on the first conversion after a channel change. I still wouldn't expect much entropy, as the S/H cap will charge/discharge deterministically.

If you want to use the ADC as a source of noise for an RNG, the best and simplest approach is to use an avalanche diode or zener diode-based, or reverse-biased transistor-based noise generating circuit. Have a look at this Wikipedia article. It is a good place to start. Also check out:

If you're determined to have a decent (but not perfect) RNG with no external components, the WDT is a good choice (although possbily not while running on the calibrated internal oscillator as per @mikericetga, and certainly not while running on the 128 kHz oscillator!). I'll post code if you're interested.

JJ

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]