# [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

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.

```