Author

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

legendary
Activity: 1948
Merit: 2097
Quote
I search only the last 56 bit (between 2^56 and 2^57 - 1)

Btw why -1?

Because 2^57 has 58 digits (in binary form '1' + 57 '0'). Then 2^57 could be the key #58, not #57

key 1 -> 1 bit :  1  ( from 2^0 to 2^1 - 1)

key 2 -> 2 bit :  from 2 to 3 (from 2^1 to 2^2 - 1) : 10 or 11

key 3 -> 3 bit : from 4 to 7 (from 2^2 to 2^3 - 1) : 100 or 101 or 110 or 111

key 57 -> 57 bit : from 2^56 to 2^57 - 1

key 58 -> 58 bit : from 2^57 to 2^58 - 1

If you look at

key #3
.....0000000000000000000000000000000000000000000000000000000000000111 (to address 19ZewH8Kk1PDbSNdJ97FP4EiCjTRaZMZQA)

and at the #4
.....0000000000000000000000000000000000000000000000000000000000001000 (to address 1EhqbyUMvvs7BfL8goY6qcPbD6YKfPqb7e)

key #3 = 2^3 - 1 = 7
key #4 = 2^3      = 8
newbie
Activity: 14
Merit: 0
Quote
I search only the last 56 bit (between 2^56 and 2^57 - 1)

Btw why -1?
legendary
Activity: 1948
Merit: 2097
Quote

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.

Wow faster than libsecp256k1

I don't know, did you test it?

Look at this thread:
https://bitcointalksearch.org/topic/m.47210876
https://bitcointalksearch.org/topic/m.47263144
newbie
Activity: 14
Merit: 0
Quote

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.

Wow faster than libsecp256k1
member
Activity: 462
Merit: 14
I don't know why but I'm smelling a big scam. Because a newbie that offer more than 12 000€ to solve a following of numbers this is strange...
Well it ain't newbie in fact he ranked up to member. Anyway, I do not see something relevant with the data presented. It maybe some sort of coincidence. Even if so BTC won't be decrypted that easily and for that the reward is nothing. I bet no one could manage to predict on or cracked the things with BTC.
legendary
Activity: 1948
Merit: 2097
Quote

My code instead uses a different library written by myself for the LBC project.

In your code how many keys can you generate per minute?

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.
newbie
Activity: 14
Merit: 0
Quote

My code instead uses a different library written by myself for the LBC project.

In your code how many keys can you generate per minute?
legendary
Activity: 1948
Merit: 2097
If I get this correctly, you need the Raw Public Key to recover the private key.

But it is not possible to get the Raw Public Key  from a Bitcoin Address unless some transaction is done by whoever cracked the private key first, right?

Right!

which program you use to generate a large number of address and keys?

You have to use a library tailored to elliptic computations.

The most famous is the libsecp256k1 written by Pieter Wuille (it is in Bitcoin Core).

These programs https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89 and https://github.com/klynastor/supervanitygen use this library.

My code instead uses a different library written by myself for the LBC project.
newbie
Activity: 2
Merit: 0
@arulbero

which program you use to generate a large number of address and keys?

I'm currently using electrum however it's not reliable for this puzzle. and bitaddress.org bulk wallet not fast enough to generate large number of addresses.
member
Activity: 245
Merit: 17
Hi

If I get this correctly, you need the Raw Public Key to recover the private key.

But it is not possible to get the Raw Public Key  from a Bitcoin Address unless some transaction is done by whoever cracked the private key first, right?
legendary
Activity: 1948
Merit: 2097
Im a bit lost, you mean you create a code that can be run on mobile fast enough to search for the private key of a known public key within a limited search space?

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 :
Code:
first 200 bit:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

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)
Code:
x = a521a07e98f78b03fc1e039bc3a51408cd73119b5eb116e583fe57dc8db07aea
y = 6fb15c871dd7cf7d287390acd4e09d41f705081a98d5fe3a930ca032525dbcdc

Output data:

last 56 bit of the private key#57:
Code:
11101011001001011100100100000111100101011101011000011100

Now, for the next private key #58:

Input data:

private key #58 :
Code:
first 199 bit:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

public key
Code:
x = ?
y = ?

Output data:

last 57 bit of the private key#58:
Code:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

newbie
Activity: 14
Merit: 0
Quote

Im a bit lost, you mean you create a code that can be run on mobile fast enough to search for the private key of a known public key within a limited search space?
legendary
Activity: 1948
Merit: 2097
I will look into it but last I looked it wasn't available for any GPUs.

Code is only for cpu. Why GPU?
legendary
Activity: 1948
Merit: 2097
I used the Baby Step - Giant Step applied to a search space of 2^54 points --> 2^27 steps (more or less). It took about 18 seconds to retrieve the private key. Obviously if I had to search the private key in the entire search space of 2^256 points, I couldn't perform the 2^128 required steps (this is computationally infeasible).

Can you share the code?

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
newbie
Activity: 11
Merit: 0
I used the Baby Step - Giant Step applied to a search space of 2^54 points --> 2^27 steps (more or less). It took about 18 seconds to retrieve the private key. Obviously if I had to search the private key in the entire search space of 2^256 points, I couldn't perform the 2^128 required steps (this is computationally infeasible).

Can you share the code?
newbie
Activity: 14
Merit: 0

16.8 seconds :

what do you use to calculate cpu gpu ? what's the wattage?


I used a mobile cpu (only 1 core): Intel Xeon E3-1505M v6

If you use just only a mobile cpu, what repository you use (searching the space) that also work in mobile?

I'm currently using one in github but only works in pc.
member
Activity: 616
Merit: 10
You mean that everybody can calculate the private key of wallets or what?

i think that this sentence is pretty clear:

You can get the private key from a public key only if you know already that the private key lies in a very limited range (in this case from 2^56 to 2^57).

That means: only in the puzzle transaction case (for the keys number 1, 2,  3, ...., 80 more or less, more than 80 bit is not a very limited range)

Ok, that's fine, becouse  I began to get nervous yesterday about  my own wallet security.
legendary
Activity: 1948
Merit: 2097
You mean that everybody can calculate the private key of wallets or what?

i think that this sentence is pretty clear:

You can get the private key from a public key only if you know already that the private key lies in a very limited range (in this case from 2^56 to 2^57).

That means: only in the puzzle transaction case (for the keys number 1, 2,  3, ...., 80 more or less, more than 80 bit is not a very limited range)
member
Activity: 616
Merit: 10
You mean that everybody can calculate the private key of wallets or what?
legendary
Activity: 1948
Merit: 2097
Just to be clear, I didn't find the key. I got the key only after the address was swept by somebody else.

How did you get private key then If you don't know the person?

Read 5/6 posts from here: https://bitcointalksearch.org/topic/m.40086839
Jump to: