[RC5] Birthday Paradox

Dimitris Tsapakidis dimitris at alien.bt.co.uk
Wed Mar 25 11:53:29 EST 1998

> In the ECCp-97 case, they just counted
> a DP as any point with an x coordinate in a particular range that was
> 2^30 wide (hence the 2^30 possible DPs).

The number of Points is really the modulus, between 96 and 97 bits long,
but for simplicity I take it to be 2^97.

x is 97 bits wide, and we defined a Distinguished Point whenever a
specific set of 30 bits is all zeros. This means two equivalent things:
1) One in every 2^30 Points, out of the total 2^97, is Distinguished.
2) We have 2^67 Distinguished Points.

> There's a shortcut to calculate the 50% mark.  When there are "n"
> possible values, then once k=sqrt(n*pi/2) points are encountered, the
> chances of a duplicate are 50%.  For n=2^97, this works out to
> 498901406404343.  Since only one in every 2^30 points are sent to the
> server, the server needs to find 498901406404343/2^30 =
> 464638 points to cross the 50% mark.   My earlier calculation used
> k=1.2*sqrt(n), which gives 444873 points required. 

That is right. You make the "birthday paradox" calculation over all
the 2^97 points and then divide by 2^30 (Points per Distinguished
Point). There is a massive confusion elsewhere on this thread, where
people attempt to make the "birthday paradox" calculation over the
number of DPs (and even this number is miscalculated). You shouldn't
do that because each DP represents on average 2^30 Points, where a
collision might happen.

> For the next ECC
> contest, ECCp-109, n=2^109, and the contest is about 64 times more
> difficult than ECCp-97.

We are happy to convert Robert Harley's code to ECCp-109 (or
whatever) for you and provide PowerPC & x86 assembly. Tim we can
discuss this over email.


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/19980325/eb4eec05/smime-0001.bin

More information about the rc5 mailing list