Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it - page 326. (Read 239888 times)

It uses only cpu. If the search space is very limited, it is like you know already many bit of 256.
I'm saying:

for example, if you provide me:
1) a public key
2) the first 198 bit of the private key

then I can recover the last 58 bit of the key. Nothing more.

There is no magic, 58 bit is not so much. That is the meaning of the sentence: "the search space is very limited".
My code runs on a cpu. So I can use efficiently the Ram of my pc. Gpus are good for hashing computations, cpus are good for elliptic (multi integer precision, 256 bit in this case) computations.


I'll try a little explanation:

If I know already the first 255 bit, then the search space is 2 (the value for the right key ends with 0 or 1).
if I know already the first 254 bit, then the search space is 2^2 = 4
if I know already the first 246 bit, then the search space is 2^10 = 1024

With so small number, any cpu can in less than 1 sec retrieve the correct private key with brute force.

Now we talk about the key #57 of  the puzzle transaction. We all know that the first 200 bit are 000000.....00001
then I search only the last 56 bit (between 2^56 and 2^57 - 1). With brute force I would need to use 2^56  different private keys to generate 2^56 public keys. Too much time. But If I knew only the address and not the public key, that would be the only way.

But If I know the public key too, then I can exploit an algebraic property of the elliptic curve (of all elliptic curves, not only the secp256k1).  Then instead of doing 2^56 "computations", I need only to compute a list of 2^28 public keys, put it in Ram, then generate another list of 2^28 public keys and do a comparison between the 2 lists. In this way I get 2^58 combinations (that's the way the Baby Step Giant Step algorithm works). If you look at the links I provided in the previous post you can understand it better.


Input data:

private key #57 :

public key
(I got it from https://www.blockchain.com/btc/tx/95b77d69302fbc805f1a6e97a3f0d27159017341e5f2d40ec79785d830fe9d59 -->
PUSHDATA(33)[02a521a07e98f78b03fc1e039bc3a51408cd73119b5eb116e583fe57dc8db07aea], look at this answer to understand how to get the y coordinate too)

Output data:

last 56 bit of the private key#57:

Now, for the next private key #58:

Input data:

private key #58 :

public key

Output data:

last 57 bit of the private key#58:

This is a game for geniuses with great minds.

These addresses are not vanity addresses, they are made up ones.  it is just burning away some BTC... no one can claim them. 

Am I making sense?

Could you please show us how to change the code so it can search only range 2^56 to 2^57 - 1?

anyone notice the other transactions on #57? how on earth did they do that? Those are hellafied vanity addresses.
edit: Sorry pre coffee me.. someone just sent to those addresses .. had me freaking out for a sec.. like oh man if they
can generate vanity addresses that long that fast they pretty much own all the btc... *panic mode engaged*
Then *doh! eureka moment*  NOW it's funny.

@arulbero
I have an idea about #58. Can I message you the details?

Have you tried to search a key in space of 10 quadrillion? How many hours you think it can finish that large space?

That works only if you have enough RAM to store 2^28 keys. Otherwise that program cannot retrieve #57.

Besides if you want to retrieve only #57 and you don't modify the code, it starts always from 1 to 2^57 - 1 (instead from 2^56 to 2^57 - 1)

About 16.7 MKeys/s, 1 GKeys/min.
 
Let's say 2^24 Keys/s.
To compute 2 lists of 2^28 keys, it takes 2 * 2^4 seconds, about 30 seconds. That is the time it took to retrieve the key #57.

look this tx https://www.blockchain.com/btc/tx/c1c8a3c8c9dccc3dbbc470e294a0610a2bc2e22c41f9a0c2a06ef5dc1d6d4480
 and this address https://www.blockchain.com/btc/address/1LqJ9cHPKxPXDRia4tteTJdLXnisnfHsof ownd by https://github.com/brichard19/BitCrack/blob/master/README.md (scroll down you will find the address).  how fast BitCrack find the 57  
puzzle key?  "THIS MAN" is fast

If the public key is revealed it is still safe from bruteforce if the attacker don't know the range of bits to search for?

I you try this code (https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89) and want to get all puzzle private keys up to #57 , you need to change
 giant steps up to  2^28

#define GSTEP (1<<28)

otherwise it stops at #52

No, I can't.


Information:

https://sefiks.com/2018/02/28/attacking-elliptic-curve-discrete-logarithm-problem/
http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/


Code (not mine, slower than mine but good, with the first 51 public keys of the puzzle transaction) :

https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89