Quote from: arulbero on November 16, 2018, 03:08:38 PM

Quote from: Elliptic23 on November 16, 2018, 01:15:41 AM

Quote from: noaj24 on November 14, 2018, 02:31:44 PM

@arulbero

If you have the public key and the search space is 2^160 how fast can you find the private key?

It would require 2^80 work. That is just beyond what is currently feasible today. But not impossible.

No, it would require much more than 2^80 work. Or you would require 2^80 work + a storage capable of containing a hash table of 2^80 * (256 bit + 80 bit) = 336 * 2^80 bit = 2^88.4 bit = more than 2^38 PB.

The current max size of my hash table is now 2^28 * (64 bit + 32 bit) = 96 * 2^28 bit = 2^34.58 bit = 24 GB (to store 2^28 keys in ram). It is only 1/2^54 of 2^88.4!

It is not possible to get such amount of ram in the next 40 years.

This is correct only for BSGS (Baby-Step-Giant-Step).

Using Pollard Rho method, the expected work is 3*2^80 group operations with almost zero memory requirements.

Note that unlike BSGS this method is probabilistic, and might fail with very low probability (on the order of 2^-160).

One can improve the algorithm using Distinguished Points, bringing the expected work down to 1.253*2^80 group operations, using both less memory and less group operations (on average) than BSGS.