[RC5] Statistics of Key Distribution

Steve Bennett bennetts at alphalink.com.au
Sat Apr 4 21:56:41 EST 1998


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



More information about the rc5 mailing list