[RC5] Birthday Paradox

Dimitris Tsapakidis dimitris at alien.bt.co.uk
Mon Mar 23 17:42:34 EST 1998


> For the ECCp-97 challenge, the number of DPs is 1073741824. My calculations
> give n=38582 when the 50% mark is crossed. TimC recently said their 50%
> mark was around 450000. Did I screw up somewhere? Here's the perl program I
> used to calculate my results:
> Can anybody tell me where I've gone wrong?

Greg, I haven't received the rest of the discussion, but here it
goes anyway:

The number of DPs is as large as you want. There is a tradeoff
between the number of iterations required to reach a DP and
the number of DPs. We chose to have 2^30 iterations per DP,
which (ignoring a couple of constant factors) gives us 2^(97-30)
DPs. The theoretic 50% mark was calculated at 393K, but by taking
into account the non-randomness of the iteration function and
depending on how much pessimistic you want to be, this can be
as high as 450K.

In your calculation you have taken the number of DPs to be 2^30,
instead of roughly 2^67.

  Dimitris

-- 
Dimitris Tsapakidis        http://www.rabbit.co.uk/dimitris/
dimitris at alien.bt.co.uk    Security Research, BT Labs, Ipswich, UK
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 2746 bytes
Desc: S/MIME Cryptographic Signature
Url : http://lists.distributed.net/pipermail/rc5/attachments/19980323/6cd0b864/smime-0001.bin


More information about the rc5 mailing list