Can anyone show me a skeleton code for *real* random numbers? Not just
using srand and rand that sometimes depends on the clock.
Asking people in comp.lang.c for "real random numbers" is like asking
a chiropractor for the recipe for coca cola. There simply is no
expertise whatsoever in the typical people in this news group on that
question.
Not surprisingly you get nonsense like: "No algorithm can produce a
truly random number sequence" which is tantamount to religious
evangelism.
Anyways, the problem of generating random numbers is just an exercise
in understanding.
So first you have to start with the definition of "random". It just
means the opposite of deterministic. What makes an algorithm
deterministic is that you can see it and all its inputs and
essentially pre-compute its results before you actually run it. So to
make something "random" on a computer, you have to feed it some input
that the observer (whether it be the user or the operator or
programmer or whatever) that cannot be predicted before the fact.
So the main problem with timer as a random seeder is usually that its
too low resolution, so you can guess or predict the time by other
external estimates. However, if you use a higher resolution timer,
you can do better. Unfortunately clock() is no good, because its
zeroed out at the start of program execution, which is when you want
to do PRNG initialization; so again in a typical OS with a
deterministic start-up mechanism, you can model its initial offsets,
and again reduce it to (statistical) determinism.
The best bet is to try to access your system's devices which operate
asynchronously to the CPU and then try to mix in high resolution time
offsets between accesses. But the C language does not define an
interface to any devices -- so you end up using some platform-specific
extensions. Some CPUs, like Intel's Pentium, or AMD's K6 have special
instructions for giving you extremely precise time counters -- you
should definitely use them if they are available (other CPUs may have
similar extensions). Precise time offsets and position of mouse
movements or keyboard input, for example, are extremely good sources
of "entropy" -- in most systems the device interrupts are event
driven, as opposed to time slice driven.
One pretty excellent source of entry can come from network based
systems -- if you are in a client-server or peer to peer arrangement
you can have each entity generate *part* of the entropy using some of
the techniques above in addition to any other instance-specific secret
information. You could mix the inputs with a reasonable hash function
to generate a seed or use that "Mersenne Twister" strategy of actually
storing the entropic inputs in an array and cycle through them for
your basic PRNGs. Certain online poker sites use this technique -- in
fact one posted the details of their algorithm publicly precisely for
the purpose of fostering confidence in the ultimate fairness and
resilience to rigging of their site (even to administrators of the
site) amongst its patrons.
This level of analysis is usually good enough, but some people like to
take things to the extremes. One might imagine that someone with a
debugger could access your program's PRNG state and reverse engineer
it to the point of making its stream predictable. If the person has
continuous access to your program, then there is nothing you can do
about that -- but what if they only have one time (or just a finite
number of times) access to your program in this manner? Then its
actually still possible to keep your random stream asymptotically
unpredictable, using the techniques described in the Fortuna random
number generator (go to the wikipedia article for details.)
If you actually go to the trouble of implementing Fortuna, or
something like it, then you can say you have "real random numbers"
with fairly good confidence. But its fairly rare that you cannot get
away with something a lot simpler in practice.
))))