Quote from: pawel7777 on January 08, 2017, 01:48:58 PM

Quote from: shorena on January 08, 2017, 12:22:05 PM

...
Your source is ~~wrong~~ slightly off as it ignores the birthday paradox. Due to it, on average you have found a collision after checking half of the keyspace with almost certainty. Thus you only need 2^159 key generations. Not that it changes the numbers in any significant way.

Why half? According to the birthday paradox, you'd have near certainty (99.9%) of finding 2 people with matching birthday with as little as 70 people. So wouldn't you need roughly one fifth (366/70) of the key space?

It just goes for a higher probability (I dont remember how many decimal 9 digits, but its essentially 100%) and a factor two is easier to handle since almost all of these calculations are done for binary numbers.

Quote from: pawel7777 on January 08, 2017, 01:48:58 PM

Also, doesn't the "2^160 generations" relate to finding any collision (defined as randomly generating 2 identical priv keys), so including zero-balance ones (also those previously generated by attacker)? If so, finding collision with specific (non-zero) addresses would be a lot harder.

There are 2^256 different private keys, but because of the use of RIPEMD-160 it is assumed that 2^96 private keys result in the same address. Compressed und uncompressed pubkey are usually ignored. IIRC You try to find a collision with one specific address, thus finding one with a balance would be easier as your chance increases from 1 in 2^160 to ~8*10^7 in 2^160.

Finding a collision with any hash you create yourself is even easier as it would only take 2^80 operations. -> https://en.wikipedia.org/wiki/Collision_attack#Classical_collision_attack

Quote from: pawel7777 on January 08, 2017, 01:48:58 PM

And is the birthday paradox even applicable for targeting specific addresses? I thought it's only about finding any matching pair.

Yes, its just an example for a more general problem -> https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem