"Random" Sequence
Brian A Crawford
or has a tendency to pattern?
To simplify: the numbers are 0 to 9 inclusive.
When you look at the frequency of each numbers occurences they all
appear over a large number of trials to occur equally and be random.
But in fact they could all be in the same order (0-9) 100's of times.
How do I try to find out these trends? Say for example the number
following the number 3 is a high proportion of 7's for example.
Can anyone help a newbie?
Thank
Brian
KBH
Guassian coordinate transformation.)
m...@my-deja.com
> Can anyone help a newbie?
I've heard search engines are helpful (google: "random number
testing", 104 hits). But apparently few people use them, so maybe my
information is incorrect.
Benjamin Goldberg
>
> How can I ascertain whether a sequence of numbers is actually random
> or has a tendency to pattern?
As has been said here many many times, you can't.
You can only test if a random number *generator* is random.
Consider the number "1", generated by flipping an unbiased coin, with
heads=1 and tails=0. It's random, right?
Now consider the number "1", generated by the formula sun rises in the
east=1, sun rises in the west=0. Nonrandom, right?
But there's no way, just by looking at the number (the "1", in this
case) whether it's random or not... only looking at the source can you
determine randomness.
--
There's a wild Fandango loose in the theater!
L. Kremkow
On Tue, 29 Jan 2002, Benjamin Goldberg wrote:
{snip}
>
> But there's no way, just by looking at the number (the "1", in this
> case) whether it's random or not... only looking at the source can you
> determine randomness.
If the source is the only means to judge by (as I've read a few times in
this NG now), could you outline what purpose things like DieHard and FIPS
serve? If I have determined the source to be True Random, then why would I
want to go off and test the sources output with Poker tests and what-not?
,,
LK
Mok-Kong Shen
"L. Kremkow" wrote:
>
> If the source is the only means to judge by (as I've read a few times in
> this NG now), could you outline what purpose things like DieHard and FIPS
> serve? If I have determined the source to be True Random, then why would I
> want to go off and test the sources output with Poker tests and what-not?
I think that one of the reasons is that, even if you
are quite sure that the source is truly random (and
very good), you don't have the guarantee that all the
equipments you use to tap that source never malfunction.
You need at least some controls.
M. K. Shen
Gregory G Rose
L. Kremkow <nob...@polytomy.org> wrote:
>If the source is the only means to judge by (as I've read a few times in
>this NG now), could you outline what purpose things like DieHard and FIPS
>serve? If I have determined the source to be True Random, then why would I
>want to go off and test the sources output with Poker tests and what-not?
Diehard exists because of the incredible amount of
supercomputer time that used to be wasted by
scientists doing monte-carlo simulations using bad
random number generators. It also provides a
useful service to stream cipher designers by
telling them if they've done something completely
stupid. This latter function is also done by other
packages like Crypt-X, the NIST statistical
tester, and the NESSIE project one.
FIPS 140 tests are for a different purpose.
Suppose you have a fielded military crypto device
that relies for security on its random number
generator. Suppose the resistor burns out, or
shorts to AC power, or something, and the
generator starts returning non-random values. With
high probability, the FIPS-140 tests will fail,
and the device will display "self-test error" and
refuse to work instead of leaking your invasion
plans to the enemy.
None of the above will actually prove that your
data is random.
Greg.
--
Greg Rose INTERNET: g...@qualcomm.com
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Benjamin Goldberg
If the source is true random, it will pass tests like Diehard etc.
If the source doesn't pass such tests, then it's nonrandom.
It takes a few minutes to run such tests.
It takes hours or days to analyse a source to see if it's True Random.
So, if you have a source, and want to know if it's true random, run the
tests, and if it fails, then it's not True Random. If it passes, now
it's time to do analysis. If you didn't have the tests, you would have
to go straight to analysis, which is alot of work.
Here's an analogy:
It's like asking why do trial division when doing a test to see if a
number is probably prime... you still have to do your miller-rabin tests
of whatever afterwards, and there'd be no harm in ommiting it... but
trial division is fast, and miller-rabin, etc is slow. If you skip
straight to miller-rabin, then it will take you much longer to find a
number which is prime.
L. Kremkow
I was under the impression tests like FIPS 140 were the acid tests for
true randomness. Thanks for the correction.
On Tue, 29 Jan 2002, Benjamin Goldberg wrote:
{snip}
> It takes a few minutes to run such tests.
> It takes hours or days to analyse a source to see if it's True Random.
{snip}
> tests, and if it fails, then it's not True Random. If it passes, now
> it's time to do analysis. If you didn't have the tests, you would have
> to go straight to analysis, which is alot of work.
{snip}
So where can I go find out what these analyses are? I'm intrigued. Is
there a formally acknowledged procedure or some such thing?
,,
LK
Benjamin Goldberg
No, there isn't. That's why it takes so much effort to do.
Douglas A. Gwyn
> If the source is the only means to judge by (as I've read a few times in
> this NG now), could you outline what purpose things like DieHard and FIPS
> serve? If I have determined the source to be True Random, then why would I
> want to go off and test the sources output with Poker tests and what-not?
The statistical tests indeed would be of no value if you know a priori
with certainty that the source is uniform random. However, in the real
world physical sources sometimes malfunction, e.g. a bus driver
transistor shorts out, in which case the stream can be far from random.
By monitoring the output, such a catastrophically bad stream can be
detected and steps taken to fix the problem.
The uses of these tests you usually read about in this newsgroup
are to check that some proposed randomizing scheme isn't hopelessly
bad. If it can't pass the standard tests then it can't be random.
corners
"Douglas A. Gwyn" <DAG...@null.net> wrote in message
news:3C57B3D5...@null.net...
> "L. Kremkow" wrote:
> > If the source is the only means to judge by (as I've read a few times in
> > this NG now), could you outline what purpose things like DieHard and
FIPS
> > serve? If I have determined the source to be True Random, then why would
I
> > want to go off and test the sources output with Poker tests and
what-not?
>
...
> The uses of these tests you usually read about in this newsgroup
> are to check that some proposed randomizing scheme isn't hopelessly
> bad. If it can't pass the standard tests then it can't be random.
Any output can come out of a true random number generator, including ones
that fail random number tests. If it doesn't pass the test, then it still
could be random. If your TRNG fails a test, you have to decide whether to
believe that it's a coincidence, or to believe that the test has discovered
a flaw in your TRNG.
***
corners
Imagine a day where no coincidences happen!
corners
"Benjamin Goldberg" <gol...@earthlink.net> wrote in message
news:3C576FA0...@earthlink.net...
> L. Kremkow wrote:
> >
> > On Tue, 29 Jan 2002, Benjamin Goldberg wrote:
> > {snip}
> > >
> > > But there's no way, just by looking at the number (the "1", in this
> > > case) whether it's random or not... only looking at the source can
> > > you determine randomness.
> >
> > If the source is the only means to judge by (as I've read a few times
> > in this NG now), could you outline what purpose things like DieHard
> > and FIPS serve? If I have determined the source to be True Random,
> > then why would I want to go off and test the sources output with Poker
> > tests and what-not?
>
> If the source is true random, it will pass tests like Diehard etc.
A true random generator will occasionally produce output that fails any
test.
On the other hand it is pretty easy to build generators that will pass these
tests, that are still easy to predict and are unsuitable for many security
uses.
> If the source doesn't pass such tests, then it's nonrandom.
Usually.
> It takes a few minutes to run such tests.
> It takes hours or days to analyse a source to see if it's True Random.
Imagine a one megabyte file that is generated from a geiger counter, tuned
to be perfectly unbiased and uncorrelated. Eight million bits of entropy.
Imagine a second file, also one megabyte, just a list of the first two
million integers, in order. Total Entropy is zero.
Now encrypt both files using AES in CBC mode, with a random key. Die Hard
will probably declare both encrypted files to be random, even though only
one of them is.
The other has a perfectly predictable pattern, with a rock solid disguise,
that no RNG tester can see through.
> So, if you have a source, and want to know if it's true random, run the
> tests, and if it fails, then it's not True Random.
Sometimes.
...
***
corners
Sometimes it's random, sometimes it isn't. You can never tell which it will
be.
Douglas A. Gwyn
> "Douglas A. Gwyn" <DAG...@null.net> wrote ...
> > The uses of these tests you usually read about in this newsgroup
> > are to check that some proposed randomizing scheme isn't hopelessly
> > bad. If it can't pass the standard tests then it can't be random.
> Any output can come out of a true random number generator, including
> ones that fail random number tests.
As I have pointed out before.
> If it doesn't pass the test, then it still could be random.
Read more carefully. I didn't say, "If it doesn't pass a standard
test ...". "Can't" denotes an *incapability*.