[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