| Hi,
| Apologies if this has been asked before.
|
| The company I work for has been asked to prove the randomness of a random
| number generator. I assume they mean an PRNG, but knowing my employer it
| could be anything.. I've turned the work down on the basis of having
another
| gig that week. However, it raised the issue of just how this could be
| achieved. As far as I'm aware there are no strong mathematicians in the
| team, so it will get thrown out to the first available person (cool idea,
| eh?). There will most likely be very little time allocated to do it.
|
| So, the question is, how can the randomness of a PRNG be proved within
| reasonable limits of time, processing availability and skill?
It can't be *proved*, for any significant sense of that word, regardless of
the availability of resources. At best, you can - if you are lucky - prove
*non-randomness*. In practice, one makes attempts to prove non-randomness
and, if "enough" of those fail - "enough" being determined by available
resources - one just asserts randomness.
There are basically two kinds of tests one can do:
- Various kinds of statistical tests. These look at things like
average numbers of 0's and 1's (assume a series of random
bits), correlations between successive bits, and so on.
There are a number of test suites out there, the best known
of which is probably the Diehard suite. (I don't have a
link, but you should have no trouble finding it.)
Testing like this looks for "statistical randomness": That is,
the "random number generator" produces outputs that have the
same statistical properties as random numbers. They say
*nothing* about predictability by someone who knows how the
numbers have been generated. For example, any good PRNG
will pass most or all of these tests, but if you know the
starting key, you can predict the outputs exactly. So if
your interest is *cryptographic security*, statistical
randomness tells you little (though *lack* of it is
obviously
a red flag).
- Attack attempts. This is mainly relevant for cryptographic random
number generation, and is like cryptanalysis: Look at the
generator and try to "break" it, i.e., predict its output.
The techniques and expertise needed are as varied as the
techniques used to construct the generators. If the
generator uses measurements of system events, you need to
know, at a deep level, what causes those system events,
how an attacker might observe them, and how an attacker
might
influence them. If the generator is based on some
electronic
circuit, e.g., a noise diode, you need to understand the
physics and electronics. In almost all cases, you need to
understand how one attacks electronics, at various levels of
abstraction.
A thorough analysis like this is likely to be very expensive, and
is prone to miss things - it's just the nature of the beast.
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
