Bitcoin Forum
May 30, 2024, 02:07:22 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: « 1 2 3 4 5 6 7 8 9 10 [11]
201  Bitcoin / Bitcoin Discussion / Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it on: June 13, 2019, 11:26:09 AM
112 bit is the current record for the ECDLP (Elliptic Curve Discrete Logarithm Problem = retrieve the private key from the public key)

I understood correctly: if you have 200 playstation3 and 6 months, then you can find a private key to any Bitcoin address that had outgoing transactions?


If you have 2^143 * 200 = 2230074519853062314153571827264836150598041600 PS3 and 6 months. And the electricity to power them, let's say about 100W per PS3.
202  Bitcoin / Bitcoin Discussion / Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it on: June 12, 2019, 09:08:17 AM
I don't understand thoroughly the algorithm Embarrassed
can you explain in short why the size of RAM matters in this algorithm?
I thought it just generates privkey hex sequentially, finds corresponding pubkey and compares it to target pubkey

You could look up the algorithms here: https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html
BSGS is in chapter 13.3
When memory is limited - Distributed Kangaroo in chapter 14.6
203  Bitcoin / Bitcoin Discussion / Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it on: November 25, 2018, 07:24:32 PM
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.


Pollard Rho can't exploit the fact that the private key is in the range from 1 to 2^160 for example, because it is probabilistic. It would need always 2^128 steps. Only BSGS is suitable for this task.

If you try to retrieve #57 with Pollard Rho, you won't retrieve the private key in a few seconds or in a few years.

With "space search is 2^160" in this context we mean a 2^160 points subset in the space of the 2^256 points of the secp256k1 curve.

Pollard Rho can be modified for an interval shorter than the whole group, at the cost of more group operations, i.e. for range 1 to 2^160 a possible solution would take 10*3*2^80 group ops plus 10*2^16 group points additional memory.

There are other probabilistic algorithms when private key is in a range significantly smaller than the size of the whole group - Pollard Kangaroo, and Gaudry-Schost algorithms.

Pollard Kangaroo with four kangaroos (the optimal) and distinguished points (DP) has expected work 1.715*2^80.

Four set Gaudry-Schost algorithm with DP gives 1.661*2^80 group operations, and is easy to parallelise.

There might be additional memory requirements for both methods, negligible compared to the enormous cost of BSGS.
204  Bitcoin / Bitcoin Discussion / Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it on: November 18, 2018, 10:24:15 AM
@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.
Pages: « 1 2 3 4 5 6 7 8 9 10 [11]
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!