Random Number Generation -----> Hardware or Software?

"Guy Macon" <http://www.guymacon.com/> wrote in message 
news:112j9n6eo4jhq29@corp.supernews.com...
>
>
>
> Peter wrote:
>
>>However if you do need random numbers without the pseudo bit then
>>an Intel Motherboard does the job.
>
> Only certain no-longer produced Intel Motherboards. (Only those based
> on the Pentium III or Pentium III Xeon processor with the 810/815/
> 820/845/850 Chipset AND the optional Intel 82802 Firmware Hub.)
>
> See [ ftp://download.intel.com/design/chipsets/datashts/29065804.pdf ].
> (See section 4.10 on page 28)

If you need only a modest number of truely random bits and don't want to buy 
any hardware, but have network access, there is always John Walker's hotbits 
for a free and readily available source.

http://www.fourmilab.ch/hotbits/

-- 
 - Stephen Fuld
   e-mail address disguised to prevent spam 

Nicholas O. Lindan wrote:

>A prng is just one more code.  It is crackable just
>like any other.

Of course it is.  However, the claim I responded to was *not*
a claim that all PRNGs are crackable, but rather a claim that
there exists a method, taught in statistics classes, that can 
distinguish the output of a PRNG from a true random output.
*That* claim is false.  They can all be cracked, but there 
does not at this time exist a method that can crack them all.

>Funny.  None of them say prngs are really-truly random.

Nor do I say such a silly thing.  I only say that you can't tell
whether the output is from a PRNG or is really-truly random.
See proof below.

>They say you can get 'good enough.

That's what I say as well.  In particular, you can get good enough that
the output cannot be distinguished from a true random output using any
known method running on any known hardware.

The proof is as follows:


[1]
A true random source can have any output pattern.  If any patterns are
impossible, it isn't a true random generator.  

[2]
"Any output pattern" includes the *exact same* patterns as are produced 
by any and all PRNGs.

[3]
Therefore, one cannot look at an output pattern and tell for sure
whether it came from PRNG X or a true random number generator that
just happened to have that exact same output by random chance.

In addition to the absolute proof above, there are the following
difficulties for any realizable system:

[A]
All known methods running on all known hardware are limited to 
examining only a finite amount of the output.  If the universe 
is finite, all possible methods running on all possible hardware
will have the same limitation.    

[B]
A PRNG produces a deterministic pattern.  If it has a finite internal 
state it must repeat, but even seeing it repeat a billion times does 
not tell the person examining the output that it will repeat the
billion and first time.  You need to look at an infinite amount of 
output to know for sure that it doesn't stop repeating at some point
above the highest number you looked at.

-- 
Guy Macon <http://www.guymacon.com/>

Nicholas O. Lindan wrote:

>That is not the point.  The pattern is not random.  It is deterministic.
>If the generating method is known then each number coming out is known
>with 100% certainty.  The only thing random about such a generator is
>the algorithm.  The seed at which it starts is irrelevant to the
>discussion: the sequence is circular - any starting point on the
>circle is equivalent to any other.
>
>It is like reading a book (it is exactly like reading a book), though
>one may not know the next word, there is only _one_ possibility.
>There is _no_ uncertainty.  That the observer is ignorant does not
>make the sequence random.

Exactly so.

I am guessing from some of your comments that you may be under the
false impression that I have claimed some sort of uncertainty or 
some departure from determinism in a PRNG, but if you examine my 
posts you will fail to find any example of me making such a claim.

I *do* claim that there exist PRNGs where the observer is ignorant 
and cannot become non-ignorant by looking at the output. For example:

01234567890123456789012345678901234567890123456789... 
(Take it out as far as you wish, including to infinity).

Is it the output of a PRNG?  You don't know for sure.  
Maybe it is a random pattern that just happens by chance 
to be exactly the same pattern as the output of a simple 
repeating 0-9 counter.  Unlikely, but possible.  If that 
pattern wasn't possible, it wouldn't be a random pattern.
All you can do is look at the statistics and assign a 
probability (in this case very high, in the case of a good 
PRNG very close to 50/50) that it is the output of a PRNG.

-- 
Guy Macon <http://www.guymacon.com/>


  
  

  

Bernd Paysan wrote:

>Or the thermal noise of a resistor. If you use an auto-zero amplifier, the
>bias goes away, but the noise level depends on temperature. Add an
>automatic gain control (which takes the noise amplitude only), and you get
>rid of that influence, too.

There is a far better method, one that I used when I designed a 
hardware RNG.

Take any repeating but random event.  Thermal noise crossing zero,
radioactive decay events, key-presses, cosmic rays - any event that
repeats at somewhat random intervals.

Make a high resolution timer with a very stable high frequency 
clock.  Use it to measure the time of each event.

Measure time between two consecutive events.  If the time is longer
than the last time between the last two consecutive events, output a
one.  If it is shorter, output a zero.  Don't output anything if it
is a tie.

-- 
Guy Macon <http://www.guymacon.com/>
    

In article <38v7sbF5pklorU1@individual.net>,
del cecchi <dcecchi.nojunk@att.net> wrote:
>"Nicholas O. Lindan" <see@sig.com> wrote in message
>news:efqWd.2538$CW2.455@newsread3.news.atl.earthlink.net...
>>
>> > But your answer is not the answer to your question.
>>
>> To me it is.  If you don't like it, well what do I care ...
>>
>> > You claim to be an engineer.
>>
>> Implying what?  Is this sort of remark relevant?
>>
>> This is the end of this conversation.
>>
>Fine.  Don't let the virtual door hit you in the virtual behind on the
>way out.
>
>The comment was reflecting on your .sig where you claim to be an
>engineer.  Then you ignore one of the attributes of engineering, where
>the requirements of the problem are considered when formulating the
>solution and proceed to dis prn in favor of true random when there are
>many applications in which the difference makes no difference.
>
>Are you sure you are not a Mathematician traveling incognito?

I can assure you that he isn't!


Regards,
Nick Maclaren.

In article <112lgs7f1891u02@corp.supernews.com>,
Guy Macon  <http://www.guymacon.com/> wrote:
>Bernd Paysan wrote:
>
>>Or the thermal noise of a resistor. If you use an auto-zero amplifier, the
>>bias goes away, but the noise level depends on temperature. Add an
>>automatic gain control (which takes the noise amplitude only), and you get
>>rid of that influence, too.
>
>There is a far better method, one that I used when I designed a 
>hardware RNG.
>
>Take any repeating but random event.  Thermal noise crossing zero,
>radioactive decay events, key-presses, cosmic rays - any event that
>repeats at somewhat random intervals.
>
>Make a high resolution timer with a very stable high frequency 
>clock.  Use it to measure the time of each event.
>
>Measure time between two consecutive events.  If the time is longer
>than the last time between the last two consecutive events, output a
>one.  If it is shorter, output a zero.  Don't output anything if it
>is a tie.

Yes, that would work, but is very complex.  There are easier approaches
to removing bias.

A) Generate bits in pairs, ignore ones that are the same, and convert
(0,1) to 0 and (1,0) to 1.

B) Generate bits, in parallel generate alternating 0 and 1, and return
the exclusive or of the two.

I should require notice of the question of whether your method is
likely to be better at removing flaws other than bias - it may well
be - the ones that I describe remove only bias.  The second can be
extended to any fixed size group of bits, of course, in the obvious
way :-)


Regards,
Nick Maclaren.

Nick Maclaren wrote:

> You claim to be an engineer.

>>...a Mathematician traveling incognito?

>I can assure you that he isn't!


 "When anyone resorts to personal attacks, it is almost always 
  because they are losing an argument."    -The Happy Heretic 

In comp.arch Nicholas O. Lindan <see@sig.com> wrote:
> 
> I should amend the above to: "Prng's pass randomness checks with
> 100% flying colors and that's why they fail.  They cheat on the test."
> 
> Yes, it is theoretically possible to create a prng with some arbitrarily
> long repeat cycle.  And one can postulate that in some arbitrarily long
> lived universe the pattern will repeat.
> 
> That is not the point.  The pattern is not random.  It is deterministic.
> If the generating method is known then each number coming out is known
> with 100% certainty.  The only thing random about such a generator is
> the algorithm.  The seed at which it starts is irrelevant to the
> discussion: the sequence is circular - any starting point on the
> circle is equivalent to any other.

This has nothing to do with randomness and everything to do with
security. Whetever some generator is random vs secure is entirely 
different mater to it being secure.

-- 
	Sander

+++ Out of cheese error +++

Vadim Borshchev <vadim.borshchev@127.0.0.1> writes:


> Note also that these (software) library functions generate
> *pseudo-random* sequences.  True random sequences are impossible to be
> achieved by solely software means.
>
>    Vadim


"Anyone who considers arithmetical methods of producing random digits is, of
course, in a state of sin."
 John Von Neumann

 > humans are very good in seeing patterns in cases where
> there isn't one.

As the film "A Beautiful Mind" so convincingly illustrates.

	Jan