[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