Pages: [1]   Go Down
Author Topic: hardware random numbers  (Read 1534 times)
0 Members and 1 Guest are viewing this topic.
Ontario
Offline Offline
God Member
*****
Karma: 20
Posts: 835
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I have been doing some design and testing of a super-simple hardware RNG solution for Arduino projects.  There's a lot of these out there, but I find most of them either too complicated, lacking in any sound theory or analysis, or both.  Here's mine:
http://1474orchard.ca/projects/?x=entry:entry120926-185104

Some of my objectives are:
  • a hardware solution with some basis in believable, verifiable theory of operation
  • minimal interfacing requirements -- just one pin, no interrupts or timers, no strange register configs
  • very simple and foolproof so that even a beginner can bodge it together -- no exotic chips, just normal parts-bin items, and something you can test without a 'scope
  • does not depend on environmental factors or user input or sensors
  • can work with any old Arduino, not depending on internal features or implementation details of a specific AVR chip
  • very low memory requirements -- no eeprom
  • able to generate 64 bits of random goodness in less than the blink of an eye
  • able to run in a setup() and give good results right at power-on
  • software is able to validate that the hardware is working right, if the calling sketch cares

The writeup I've done so far really just covers the hardware.  I will follow up with some more analysis of a simple whitening algorithm and, if I have the patience to wait long enough, I will generate enough data for a Diehard analysis.  The requirement to be able to generate good data right after power on limits the rate that I can generate test data, and Diehard need a fair slog of test data.
Logged

Left Coast, CA (USA)
Offline Offline
Brattain Member
*****
Karma: 331
Posts: 16548
Measurement changes behavior
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Nice project, thanks for posting it. I've always been interested in hardware noise generators and their applications in 'true' random number generators. There is tons of stuff on the web but many are either too complex or expensive to experiment with or if simple don't do a good job of 'quantifying' their ability to generate 'good' random number distribution. I will attempt to keep up with your progress if you post an update here once in a while.

Lefty
Logged

Ontario
Offline Offline
God Member
*****
Karma: 20
Posts: 835
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Here is part two, now with some actual measurements to substantiate that there is randomness in the machine:
http://1474orchard.ca/projects/?x=entry:entry120927-232456

I have my mega generating a batch of data that would be large enough to feed into diehard.  This will take about 40 hours.  I had meant to wait until that was done before posting again, but as I appear to have made hackaday, I thought I should get a move on.  When I have enough data I will have a run at diehard and see what it thinks.  I have been using a decent quality PRNG to simulate analogRead() data with the right distribution and using that to tune my whitening function so that it can pass diehard.  I am interested to see how it works with real data.

Assuming all is well, or can be made well with a little tuning, I will neaten up my sketches and hand them over.  What I have in mind is a sketch with a set of statistical tests that a newbie could use to test out the circuit and make sure it's working right.  Then a short set of functions that could be used to incorporate the RNG into a project.
Logged

Dubuque, Iowa, USA
Offline Offline
Edison Member
*
Karma: 33
Posts: 2277
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

wanderson's random number generator project.
Logged

Ontario
Offline Offline
God Member
*****
Karma: 20
Posts: 835
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


Yes, seen that.  Though not before I got 60% through my own.
Logged

Ontario
Offline Offline
God Member
*****
Karma: 20
Posts: 835
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I have updated my project writeup.  I have gotten enough data to run a pass of diehard, which mostly looked okay, except for utter failures on some specific tests.  I am assuming my whitening algorithm is at fault -- it never pays to invent your own crypto type algorithms -- and I am switching to xorshift64 for another go.  Meanwhile I did generate a bit over 1.3 million 64-bit seeds with no duplicates, so it's not a total failure.
Logged

Ontario
Offline Offline
God Member
*****
Karma: 20
Posts: 835
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Another update.

Changing the whitening algorithm to use xorshift64 yields results that look okay in diehard.  Here's the details:
http://1474orchard.ca/projects/?x=entry:entry121002-012642

The xorshift I'm using is left 13, right 7, left 17.  This is also a good PRNG, so it likely makes sense to have the code around anyway.

If anyone's interested in implementing this or studying it further, just follow up here or by PM or what-have-you.
Logged

Pages: [1]   Go Up
Jump to: