Pages: 1 2 [3] 4 5 6   Go Down
Author Topic: Random Seeds and Random Numbers  (Read 9977 times)
0 Members and 1 Guest are viewing this topic.
nr Bundaberg, Australia
Offline Offline
Tesla Member
***
Karma: 129
Posts: 8530
Scattered showers my arse -- Noah, 2348BC.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Not particularly random in their own right, can you grab the LSBs and construct a few hundred bytes to see what that looks like.

______
Rob
« Last Edit: November 06, 2011, 09:23:09 pm by Graynomad » Logged

Rob Gray aka the GRAYnomad www.robgray.com

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

I changed the code:
Quote
void loop () {

  for (int i=0; i<200; i++) {
    val = lowByte(analogRead(0));
 
    Serial.println(val);
    delay (100);
  }
  Serial.println("Delaying ...");
  delay(10000);
}


Initially, this got me
Code:
035 226 204 207 235 240 215 202 218 240 236 208 203 229 241 226 204 208 236 241
215 203 220 241 235 208 204 230 242 225 204 210 237 241 214 204 222 241 235 207
205 232 242 224 204 211 238 241 214 204 223 242 234 208 205 232 242 223 204 212
239 241 214 204 224 242 234 208 206 233 242 223 204 213 239 241 213 203 224 242
233 207 206 233 242 222 204 213 239 240 213 204 224 242 233 207 206 233 242 222
204 214 239 240 213 204 225 243 232 207 206 234 242 221 204 214 240 240 212 204
226 242 231 206 207 235 242 220 204 216 241 240 212 205 228 243 232 207 208 236
243 221 205 217 242 241 213 206 229 244 232 208 209 238 244 221 206 219 243 241
213 207 230 246 233 209 210 238 245 222 207 220 244 242 213 207 231 246 233 209
211 239 246 222 208 221 245 243 214 208 232 247 234 210 212 240 247 223 208 222

But after waiting a couple minutes:
Code:
084 002 254 008 021 034 036 022 003 255 004 016 032 036 027 007 000 254 010 030
000 036 031 010 255 004 016 032 036 027 006 000 254 010 029 036 031 010 254 004
016 000 032 036 026 006 000 253 010 029 035 031 010 254 003 015 032 036 026 005
255 000 000 009 022 034 035 019 001 253 005 017 032 035 023 004 254 001 012 030
035 028 007 000 000 253 006 019 032 035 022 003 253 002 014 031 035 027 006 255
255 027 035 032 000 012 254 001 011 029 035 029 008 000 253 005 018 032 035 023
003 254 001 012 030 000 035 028 007 000 252 006 019 033 035 022 003 253 001 014
031 035 027 006 255 255 000 026 035 032 012 255 000 010 029 035 030 009 001 253
005 017 033 035 024 004 255 000 001 012 030 036 029 009 001 253 007 019 033 035
023 004 254 002 013 031 036 029 000 008 000 253 006 019 033 035 023 004 255 001
012 030 035 029 008 000 253 005 018 000

Then I noticed that jiggling wires had significant effects. Stray capacitance I guess. Makes me wonder about how well breadboarding works for things like this.

Anyhow, were you asking about just the low 4 bits? Easy enough to mask those off and bit-shift into an 8 or 12-bit integer.
Logged

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

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

While not super random, I have thought of a built in component of the ATMega328 that is "unpredictable" to a degree.  The 328 has a built in temperature sensor that is accurate to +-10 degrees C.  The inaccuracy actually works in your favor as a seed.

More information is in the datasheet.

http://code.google.com/p/tinkerit/wiki/SecretThermometer
Logged

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

Quote
The inaccuracy actually works in your favor as a seed.

Not in my testing.  Bear in mind there is a big difference between "inaccurate" and "unpredictable".
Logged

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

Well, hey, here's another tack:


Code:
// Checking out reading white noise

int  val, rval;

const int lmask = 0xF;

void setup()
{
  Serial.begin(9600);          //  setup serial
  analogReference(DEFAULT);
  delay (3000);  // give me time to turn on the power supply.
  Serial.println("Starting read loop...");
}

void loop () {

  for (int i=0; i<200; i++) {

    val = (analogRead(0)) & lmask;
    rval = 0 | (val << 4);
    rval = rval | (analogRead(0)) & lmask;
 
    Serial.println(rval);
    delay (100);
  }
  Serial.println("Delaying ...");
  delay(10000);
}

If I didn't get crosswise with edit windows, that's this block of numbers:
Code:
170 152 118 018 068 187 219 119 222 103 153 254 102 188 187 220 119 205 086 170
135 102 017 051 170 203 118 205 102 152 254 086 018 068 170 169 101 221 102 135
237 085 018 051 153 152 085 119 001 119 084 033 101 188 085 153 085 118 136 034
153 152 084 102 239 136 084 102 120 018 136 152 068 085 103 136 236 102 120 018
120 151 068 085 119 152 220 085 051 018 034 135 101 051 085 136 119 169 068 068
068 068 119 033 068 035 018 034 119 067 084 034 240 085 101 220 034 188 051 118
015 050 034 035 034 102 017 067 034 001 188 101 050 067 017 239 068 085 084 084
017 204 051 085 101 033 034 052 034 085 135 033 017 017 017 068 169 033 000 085
137 068 203 051 000 051 103 068 237 067 015 137 017 051 118 000 255 240 051 034
000 118 255 085 034 034 050 050 254 035 017 050 084 051 238 017 000 051 255 084

I also note that there appears to be a settling time involved -- results were better when I just left the circuit powered up when uploading a new sketch, and if I cycled power on the circuit while the sketch was running, I'd get significant clumping at first. Does that imply needing smaller caps -- at least on the input side? (Or a smaller load resistor, i.e. higher current through the zener?)

ETA: I'm using the TI NE3352P dual op-amp IC.
« Last Edit: November 06, 2011, 11:10:51 pm by justjed » Logged

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

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

There is some  very obvious clumping there. Rather than using nibbles can you accumulate just the lowest bit from each reading.

______
Rob
 
Logged

Rob Gray aka the GRAYnomad www.robgray.com

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

I might experiment with that. However, I recall reading some material, a while back, on the clumping phenomenon, and IIRC, it isn't necessarily an indictment of the randomness of a sequence. I will have to delve into that a bit. The classic example is the theoretically perfect coin toss. If the result of a sequence of tosses was always head - tail - head - tail - head - tail alternating, then that would not be considered random. I had hoped to find something informative at Wolfram, but no dice on my initial search. Fortunately, I know a few competent mathematicians.

I would, however, be much interested in suggestions for improving the circuit. If there's too much bit-banging needed to use it as a good RNG, then it won't be useful as a breakout board. I'm not striving for a DOD level cryptographic thing here (or whatever super certification you can think of), just something useful, and which doesn't require much processing oomph.

ETA: BTW, I was mostly curious about how well it might work to do what Tim7 suggested -- reading the output on an analog pin. As in the Intel dual-inverter method, the output should be "whitened", using something like von Neumann filtering, and in the case of this circuit, the signal would need to feed through a Schmitt trigger prior to that. Maximal success, it seems to me, would then require that the output voltage be swinging through a wider range. With output values hitting a max (so far) of 255, that's only 1.25 volts, and not adequate for producing a logical bitstream. Well, that's accepted practice, anyway, at least from what I've been reading.

p.s. And, since I'm thinking along other lines, of course, it took a moment to consider that one could use a Schmitt trigger with a threshold at the mean of whatever the output is -- I assume there are many varieties available.
« Last Edit: November 07, 2011, 08:24:04 pm by justjed » Logged

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

Connecticut
Offline Offline
Edison Member
*
Karma: 17
Posts: 1216
RTFD (Datasheet in our case)
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
Schmitt trigger with a threshold at the mean of whatever the output is -- I assume there are many varieties available.

Which threshold? The high one or the low one?

btw: would it be possible to feed a (regular) inverter a voltage inside "no-man's" zone? Would this produce a randomish bit stream? (i.e. for the 7404 the min. high voltage is 2V, yet the max. low voltage is .8V. So what would happen @, say, 1.3V (arbitrarily chosen)?)


baum
Logged

NYC
Offline Offline
Newbie
*
Karma: 0
Posts: 8
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
I've ran across tinkerit's TrueRandom library.  Maybe that will give you better results?

No.  It has at least two serious flaws.

What do you consider to be the flaws?  I think it's a flaw to throw away all the bits except the last one, since the others could have randomness, too.  And it's a flaw to sample a floating pin, since the signal on that pin varies wildly from one circuit and environment to the next.  It could be held to ground by parasitics and the ADC would output nothing but 0s.

I tried testing TrueRandom on my Duemilanove and it does not look "truly random".

Code:
~> ent TrueRandom.bin
Entropy = 7.544390 bits per byte.


Optimum compression would reduce the size
of this 92810048 byte file by 5 percent.

Chi square distribution for 92810048 samples is 131287892.21, and randomly

would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 93.7178 (127.5 = random).
Monte Carlo value for Pi is 3.682216212 (error 17.21 percent).
Serial correlation coefficient is -0.008583 (totally uncorrelated = 0.0).

which is "almost certainly not random".  The numbers it gives are clumped around 0 and powers of 2, which I think just means it spits out lots of 0s and few 1s.



https://gist.github.com/2472824
http://flic.kr/p/bB8bsu
« Last Edit: April 25, 2012, 10:43:52 pm by endolith » Logged

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

What do you consider to be the flaws?

It may take a few days to resurrect the memories.  I'll get back to you.

Quote
I think it's a flaw to throw away all the bits except the last one, since the others could have randomness, too.

I'm confused.  You state it's a flaw to throw away all but the last bit but then prove even the last bit is not random.
Logged

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

Using whitening improves this but it still clumps around powers of 2. Mega thread here

http://arduino.cc/forum/index.php/topic,66206.15.html

______
Rob
Logged

Rob Gray aka the GRAYnomad www.robgray.com

Pittsburgh, PA, USA
Offline Offline
Faraday Member
**
Karma: 98
Posts: 4808
I learn a bit every time I visit the forum.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I still think that a radio with wide reception is the best bet. Get a music station and talk station at the same time, the highs and lows should be unpredictable.

Besides... there's probably a serial interface board to build (and maybe sell) in there somewhere.

Other thing, how hard to detect ions released in a smoke detector?
Logged

I find it harder to express logic in English than in Code.
Sometimes an example says more than many times as many words.

NYC
Offline Offline
Newbie
*
Karma: 0
Posts: 8
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I'm confused.  You state it's a flaw to throw away all but the last bit but then prove even the last bit is not random.

Oh, well I was thinking of another micro I worked with, where it gives you 10 bits of valid signal and then 2 or 3 of noise.  Unlike the Arduino, where there are 10 bits of measurement and then the rest are all 0 and the value is exactly the same every time you read it, no matter what internal source and reference you use.  smiley-sad  Also, the example I was using for the other micro made an assumption that the LSB was random, when it actually wasn't; other bits were.

If at least one bit is truly random, but you're not sure which, and you XOR it with all the other bits, you should still have a truly random bit.  If two of the bits are somewhat random, and you XOR them together, you should have a somewhat more random bit.  But in general, it seems wasteful to throw away bits that are changing, even if they change rarely.

I still think that a radio with wide reception is the best bet. Get a music station and talk station at the same time, the highs and lows should be unpredictable.

Well, if there's nothing inside the micro that can be used as an entropy source, isn't the best bet to build a simple, cheap external thermal noise circuit?  It seems silly to go through the trouble of adding on expensive bulky hardware like a radio or geiger counter when all you need is a noise source (and every resistor is a noise source).

The jitter of the RC oscillator seems to be a better internal source of entropy than the ADC, though only generating 8 bits per second or 125 bits per second in example implementations.
Logged

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

Quote
The jitter of the RC oscillator seems to be a better internal source of entropy than the ADC, though only generating 8 bits per second or 125 bits per second in example implementations.

For a specific processor, maybe.  In the general sense, no.  The AVR internal oscillator (and watchdog oscillator) certainly has jitter but the entropy in the jitter appears to be considerably less on newer processors.  My suspicion is that the jitter for newer processors is primarily a function of the previous and current state of the processor (which is going to be rife with patterns) rather than thermal noise.
Logged

NYC
Offline Offline
Newbie
*
Karma: 0
Posts: 8
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

The AVR internal oscillator (and watchdog oscillator) certainly has jitter but the entropy in the jitter appears to be considerably less on newer processors.

Did you measure it?
Logged

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