-1
$\begingroup$

Not long ago I saw a discussion on the Bitcoin Talk forum:

https://bitcointalk.org/index.php?topic=5060735.msg50736695#msg50736695

Please give advice and working methods? Is it possible to find at least one private key from any public key from the list from the large list of compressed public keys secp256k1?

Public keys: https://drive.google.com/drive/folders/1HByDJR9Ck5CdIwTl-v_IzcaVhsG8aKaA

As I know, this list contains 15 million compressed public keys.

Is it possible to use any method for such a large list of compressed public keys in order to finally find at least one private key?

$\endgroup$
3
$\begingroup$

Is it possible to use any method for such a large list of compressed public keys in order to finally find at least one private key?

Actually, for ECC, it turns out that the problem 'given this long list of public keys, find any one private key' is no easier than 'given this public key, find the private key'

The proof is the converse; suppose we had a way, given a list if public keys $x_1G, x_2G, …, x_nG$, to recover $x_i$ (for any $i$). Then, given a single public key $xG$, we could pick $n$ random values $r_1, r_2, …, r_n$, and compute $r_1(xG), r_2(xG), … r_n(xG)$. Then, we hand this list off to our method, which gives a value $x_i$ with $x_i G = r_i(xG)$; we then can recover $x = r_i^{-1} x_i$, and that gives us the private key we're looking for.

Hence, a fast way to solve your problem would solve the general discrete log problem as well.

$\endgroup$
  • $\begingroup$ @poncho please advise me a tool for solving this problem? $\endgroup$ – BojarSONY Apr 24 at 12:31
  • 1
    $\begingroup$ @BojarSONY He has just explained that this is infeasible - so in that case there is no tool. In his answer it is even less possible than in my answer. We're just arguing on how infeasible it is (and I'm sure that poncho will win that argument, making it even less likely to do this). $\endgroup$ – Maarten Bodewes Apr 24 at 13:26
0
$\begingroup$

This is not possible, an EC private key for the secp256k1 curve is (almost) 256 bits of random data. Brute forcing such a large value is impossible even if you have oodles of public keys. The skeptics in that forum thread are correct, BitCoin would be broken if this was possible.

15 million is only $2^{23}$ while you have a key space near $2^{256}$; the birthday problem is not paradoxical enough to help you here. Note that there is a better way of finding keys called Pollard's Rho, which "only" takes $2^{128}$ tries. As poncho's answer shows, this faster-than-bruteforce approach cannot be accelerated by adding a table with public keys.

As $2^{128}$ tries is about as hard as finding a single AES-128 bit key you can probably guess that this is not a feasible option.

$\endgroup$
  • $\begingroup$ Actually, as I pointed out in my response, there isn't any speed up available at all with 15 million public keys... $\endgroup$ – poncho Apr 24 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.