Pages: 1 2 3 [4] 5   Go Down
Author Topic: The reliable but not very sexy way to seed random  (Read 8596 times)
0 Members and 1 Guest are viewing this topic.
Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 200
Posts: 12782
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset


Thanks.  That was an interesting read.
Logged

nr Bundaberg, Australia
Offline Offline
Tesla Member
***
Karma: 126
Posts: 8475
Scattered showers my arse -- Noah, 2348BC.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Interesting technique, I wonder if they'll spin it off to a 3-pin chip anyone can use?

_____
Rob
Logged

Rob Gray aka the GRAYnomad www.robgray.com

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 200
Posts: 12782
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset


The big difference that Intel brings to the table is generation rate.  In the article, the author claims a raw bit rate of 3 gigabits per second.  That just cries out "simulation".  I suspect that is the market they are targeting.  Which means the generator, at least initially, will always be coupled with a processor capable of doing useful things with all that random data.

In other words, until they develop a 3-pin i7, I think we're out of luck.
Logged

CO, USA
Offline Offline
God Member
*****
Karma: 5
Posts: 711
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


Well, that's interesting. I hadn't known that Intel was including a hardware RNG.  In Linux, the kernel still gathers entropy:
Quote
The random number generator gathers environmental noise from device drivers and other sources into an entropy pool. The  generator  also  keeps  an estimate of the number of bits of noise in the entropy pool. From this entropy pool random numbers are created. (from man random)

Probably some reason for doing it. Maybe, for some purposes, only a few hundred kilobits of random numbers a second isn't enough? I have no idea.

Looking at the simplified drawing (without knowing it was that) I thought, hey, I have inverter ICs, I could try that. But then comes the rub:
Quote
To keep the inverters in balance, we built a feedback loop into the new hardware. The circuitry in that loop performs some targeted fiddling until the two possible output values, 0 and 1, each occur roughly half the time.
And they're using IGFETS -- maybe I could subsitute MOSFETs, or something else, as long as I don't care about how fast the switching is. I don't have the knowledge to know whether there's some reason an insulated gate FET is needed here. And, even without the feedback loop, there's more to it than drawn -- VCC and ground, e.g.
Logged

... it is poor civic hygiene to install technologies that could someday
facilitate a police state. -- Bruce Schneier

Guildford, UK
Offline Offline
Full Member
***
Karma: 0
Posts: 218
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
Very interesting article.

Quote
The big difference that Intel brings to the table is generation rate.  In the article, the author claims a raw bit rate of 3 gigabits per second.  That just cries out "simulation".  I suspect that is the market they are targeting.  Which means the generator, at least initially, will always be coupled with a processor capable of doing useful things with all that random data.

In other words, until they develop a 3-pin i7, I think we're out of luck.
I wonder if anyone has made a chip of their initial analogue approach http://www.cryptography.com/public/pdf/IntelRNG.pdf (Block diagram is on Page 3 of the link). This still has a digital corrector and I'm guessing they're not interesting in making one themselves.

Iain
Logged

CO, USA
Offline Offline
God Member
*****
Karma: 5
Posts: 711
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I wonder if anyone has made a chip of their initial analogue approach http://www.cryptography.com/public/pdf/IntelRNG.pdf (Block diagram is on Page 3 of the link). This still has a digital corrector and I'm guessing they're not interesting in making one themselves.

Well, my first question would be what the signal level is from an undriven resistor.
Logged

... it is poor civic hygiene to install technologies that could someday
facilitate a police state. -- Bruce Schneier

Grand Blanc, MI, USA
Offline Offline
Faraday Member
**
Karma: 93
Posts: 3973
CODE is a mass noun and should not be used in the plural or with an indefinite article.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset


I happened across that the other day as well, the September issue of IEEE Spectrum just arrived, it's the cover story!
Logged

MCP79411/12 RTC ... "One Million Ohms" ATtiny kit ... available at http://www.tindie.com/stores/JChristensen/

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 200
Posts: 12782
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

The latest version...

Code:
#include <avr/eeprom.h>

/*==============================================================================
  Call reseedRandom once in setup to start random on a new sequence.  Uses
  four bytes of EEPROM.
==============================================================================*/

void reseedRandom( uint32_t* address )
{
  static const uint32_t HappyPrime = 937;
  uint32_t raw;
  unsigned long seed;

  // Read the previous raw value from EEPROM
  raw = eeprom_read_dword( address );

  // Loop until a seed within the valid range is found
  do
  {
    // Incrementing by a prime (except 2) every possible raw value is visited
    raw += HappyPrime;

    // Park-Miller is only 31 bits so ignore the most significant bit
    seed = raw & 0x7FFFFFFF;
  }
  while ( (seed < 1) || (seed > 2147483646) );

  // Seed the random number generator with the next value in the sequence
  srandom( seed );  

  // Save the new raw value for next time
  eeprom_write_dword( address, raw );
}

inline void reseedRandom( unsigned short address )
{
  reseedRandom( (uint32_t*)(address) );
}


/*==============================================================================
  So the reseedRandom raw value can be initialized allowing different
  applications or instances to have different random sequences.

  Generate initial raw values...

  https://www.random.org/cgi-bin/randbyte?nbytes=4&format=h
  https://www.fourmilab.ch/cgi-bin/Hotbits?nbytes=4&fmt=c&npass=1&lpass=8&pwtype=3

==============================================================================*/

void reseedRandomInit( uint32_t* address, uint32_t value )
{
  eeprom_write_dword( address, value );
}

inline void reseedRandomInit( unsigned short address, uint32_t value )
{
  reseedRandomInit( (uint32_t*)(address), value );
}


uint32_t reseedRandomSeed EEMEM = 0xFFFFFFFF;

void setup( void )
{
  reseedRandomInit( &reseedRandomSeed, 42 );
  reseedRandom( &reseedRandomSeed );

  reseedRandomInit( (unsigned short) 0, 42 );
  reseedRandom( (unsigned short) 0 );
}


void loop( void )
{
}
« Last Edit: May 24, 2014, 11:46:08 pm by Coding Badly » Logged

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 212
Posts: 13531
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


Thanks,

If I see correctly the code is essentially the same, mostly the reseeding improved
Do you have performance numbers / footprint numbers ?

Time to make a class of it ? => multiple (pseudo)random sequences side by side smiley

Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 200
Posts: 12782
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

If I see correctly the code is essentially the same, mostly the reseeding improved

I simplified it a bit and added some comments.  The code is basically the same as the first version.

Quote
Do you have performance numbers / footprint numbers ?

At the very most, the do-while executes twice so it should be faster than generating a random number.

I'll check the size tomorrow.

Quote
Time to make a class of it ? => multiple (pseudo)random sequences side by side smiley

 smiley-grin  I think I've spent enough time on it.  I have an ATtiny84 that has been begging to play with my three new thermistors.
Logged

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 200
Posts: 12782
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset


Regarding analogRead on a floating pin...

http://reykjavik.academia.edu/BenediktKristinsson/Papers/1225216/Ardrand_The_Arduino_as_a_Hardware_Random-Number_Generator

See Section 5.1 if you don't want to wade through the details.
Logged

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


Regarding analogRead on a floating pin...

http://reykjavik.academia.edu/BenediktKristinsson/Papers/1225216/Ardrand_The_Arduino_as_a_Hardware_Random-Number_Generator

See Section 5.1 if you don't want to wade through the details.


 As I recall this doesn't disagree with the general conclusions of our rather long posted threads on the same subject. As I recall we were still in search of a more 'perfect' initialization of the seed function?

Lefty
Logged

CO, USA
Offline Offline
God Member
*****
Karma: 5
Posts: 711
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset


Bletcherous Scribd. Anyone have a direct link to a PDF? I'd like to read that.

As I recall this doesn't disagree with the general conclusions of our rather long posted threads on the same subject. As I recall we were still in search of a more 'perfect' initialization of the seed function?

Well, I was not really getting anywhere with that. But I'd like to. However, I'm at a point where I think I really need an o-scope. If not for my decrepit Volvo finally reaching the point where I decided to replace it, I might have picked one up this month. And I probably need some other dual op-amp ICs to try out. I was sorta eyeballing a Tektronix 2336 YA -- portable, 100mhz, dual trace. Appeal for me is the ability to close the case, thus protecting the front panel. With all the junk I have around, that's a big plus.
Logged

... it is poor civic hygiene to install technologies that could someday
facilitate a police state. -- Bruce Schneier

Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Bletcherous Scribd. Anyone have a direct link to a PDF? I'd like to read that.

Yes, Blecherous Scribd indeed (I'm the author of this paper). You can find a normal PDF on http://benedikt.sudo.is/ardrand.pdf.
Logged

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 200
Posts: 12782
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

As I recall this doesn't disagree with the general conclusions of our rather long posted threads on the same subject.

That's my recollection as well.

Quote
As I recall we were still in search of a more 'perfect' initialization of the seed function?

Yup.

Well, reseedRandom may not be perfect but it is a reasonable choice.   smiley-grin


@benediktkr: Thank for the research and the paper.
Logged

Pages: 1 2 3 [4] 5   Go Up
Jump to: