[RC5] Statistics of Key Distribution
gindrup at okway.okstate.edu
gindrup at okway.okstate.edu
Tue Apr 7 12:07:40 EDT 1998
Well... Actually... The Normal Distribution is what you get in the
limit of infinite numbers of dice. It's convenient however that the
sequence of distributions converges somewhat rapidly to its limit.
This result is called the "Central Limit Theorem".
Thm. Let a_i be a set of independent identically distributed random
variables where each has finite variance, 0<=i<n for some n a
positive integer. Then in the limit as n goes to infinity, their
sum (or equivelantly, their arithmetic mean) approaches a normally
distributed random variable.
The strength of this theorem is that it does not place strong
requirements on the a_i. They could all come from any (excluding
pathological cases without positive measurable support)
distribution. Thus, from any population from which independent
samples can be taken, any randomly distributed variable can be
summed over subsequences of samples to produce a normal distribution
(in the limit of infinite sampling and unboundedly finite
subsequences).
What this has to do with Distributed Computing, Cracking, RC5, DES,
programming, UI issues, or DCTI is entirely beyond me.
-- Eric Gindrup ! gindrup at Okway.okstate.edu
______________________________ Reply Separator _________________________________
Subject: Re: [RC5] Statistics of Key Distribution
Author: <rc5 at llamas.net> at SMTP
Date: 4/4/98 9:56 PM
Skip Huffman wrote:
> Dead wrong. The curve will be flat if we measure where in the
> keyspace the key was. If I take a die and roll it 1000 times, I am
> going to get just about as many ones and sixes as I am threes and
> fours.
That's true...
> Now if you generate two random numbers and add them, the sum will
> tend towards a bell curve. Look at two dice. There are six
..but that's not. Two dice don't form a bell curve - it's not really a
curve at all, just a triangle.
> *
> * * *
> * * * * *
> * * * * * * *
> * * * * * * * * *
> * * * * * * * * * * *
> 02 03 04 05 06 07 08 09 10 11 12
It doesn't even look curvy :-)
Like Zoe, I wrote a (somewhat shorter) program to convince myself, but in
BASIC :-)
DEFLNG A-Z
max = 640
DIM r(0 TO max) AS INTEGER
c = 4
FOR z = 1 TO 125000 * c
res = RND * (max / 2) + RND * (max / 2)
r(res) = r(res) + 1
NEXT
SCREEN 12
FOR i = 1 TO 640
LINE (i * 640 / max, 480)-(i * 640 / max + 640 / max, 480 - r(i) / c), 8,
BF
NEXT
Not highly portable, I imagine. Anyway, the plot has very straight sides.
Now don't ask me why, but I slightly modified the program to use *3* dice,
and suddenly I get a normal distribution (bell curve). Go figure.
So, 1 die (like in key situation) = flat, 2 dice = triangle, 3 dice+ = normal
dist.
As for the time-to-find-the-key, while it won't be a normal dist, it will
have a mean in the middle, and you can calculate a standard distribution.
They just don't do anything useful for you.
--
Steve Bennett, stevage at earthling.net
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
More information about the rc5
mailing list