[rc5] key block
Eric Gindrup
gindrup at okway.okstate.edu
Wed Aug 27 19:52:10 EDT 1997
Let q(x) be the largest integer smaller than x. This allows us to
round up to the nearest whole block.
Let p(n) be the number of blocks left after n iterations, so p(1) =
q(.99 * 2^28) and p(2) = q(.99 * p(1)). Therefore,
p(n+1) = q(.99 * p(n))
Writing a quick basic program that effectively calculates p(100k) for
increasing integer values of k until the amount calculated is less
than 1 and then rolling forward by 1s from the previous value, we get
the following table of values:
n p(n)
0 268435456
100 98256023
200 35964850
300 13164267
400 4818519
500 1763704
600 645543
700 236259
800 86447
900 31612
1000 11540
1100 4191
1200 1502
1300 520
1400 162
1500 31
1530 1
1531 0
So after completing the smallest number of blocks to complete 1% of
the remaining keyspace 1531 times, the entire keyspace is exhausted.
If partial blocks and even partial keys (the continuous limit) were
permitted (until exactly 1 or fewer keys remained), then we need to
solve .99^n < 2^-56, or n = 3862.18 rounds to 3863 iterations.
The requirement that whole blocks be done helps exhaust the
keyspace significantly.
-- Eric Gindrup ! gindrup at Okway.okstate.edu
______________________________ Reply Separator _________________________________
Subject: Re: [rc5] key block
Author: <rc5 at llamas.net> at SMTP
Date: 8/27/97 4:01 PM
Brian Murphy (brianm at earthlink.net), on 8/27/1997 7:46 AM, wrote the
following:
>> Well, actually there is a 50% change that we will find the key when
>> 86% is complete. Either we find it there or we don't.
>
>I have a 50% chance of winning the lottery. Either I win, or I
>don't.
>
>(hrm..wait a sec..that doesn't sound right!)
The mathematician in me is having conniptions! Seriously, this
conversation is almost bad enough to cause physical pain in a few people
I know (myself included).
:)
When we were working on the first 1% of the keyspace, we didn't find the
key, so that 1% was removed. Then we worked on 1% of the remaining space,
and still didn't find it, so that 1% was removed. And so on, and so on...
until this happened sixty four times and we ran out of keys!
Therefore, we're guranteed to find the key within the first 64%!
Anybody care to check my math? ;)
Seth
As I said, the mathematician in me is having conniptions.
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the
body.
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5
mailing list