Bitcoin puzzle transaction ~32 BTC prize to who solves it - page 324.

Andzhig

jr. member

Activity: 184

Merit: 3

Quote

Do you have a formula or anything close?

There is no formula, there is a random and our collective unconscious. Therefore, someone will write something, someone will think of something. Grin

You never know, I will write now and you will light up (light bulb lights up).

Take the last number found. 1011000110011101011011100001010010000110001001101000100001 take the first 3 bytes from it 10110001 10011101 01101110 here we have 10 zeros. Check how many combinations will be from the first byte 10110001, 8008 combinations which we need in place 583 (depending on the given data of course, table for counting in python, I'll leave it down) bin 101100011001110101101110 dec 11640174 multiply this number 34 times by 2 will get ~199976666598998016 practically what you need 199976667976342049. 199976667976342049-199976666598998016=1377344033 error on 1377344033 using a scanner "bitcrack" it's practically nothing. You need to guess just 3 bytes then "bitcrack" will do everything himself.

The most important question is how to guess these 3 bytes (and multiply by 2 35 times for 59 puzzle).

Now back to my writing.

Quote

174176B015F4D
22BD43C2E9354
75070A1A009D4
EFAE164CB9E3C
180788E47E326C
236FB6D5AD1F44
6ABE1F9B67E114
9D18B63AC4FFDF
1EB25C90795D61C
2C675B852189A21
5 or 6 or 7 ...

Well, what's next, 288230376151711744-576460752303423488 ,if 6 it's 430000000000000000-500000000000000000 if 7 500000000000000000-570000000000000000

Depending on the initial number in hex, we get our initial bytes in bit.

hex ~610000000000000-6F0000000000000 ~436849163854938112-499899558638125056, 710000000000000-7F0000000000000 ~508906757892866048-571957152676052992.

6 or 7 implies 110 or 111

Quote

("11000000"),("11000001"),("11000010"),("11000011"),("11000100"),("11000101"),("11000110"),("11000111"),
("11001000"),("11001001"),("11001010"),("11001011"),("11001100"),("11001101"),("11001110"),("11001111"),

("11010000"),("11010001"),("11010010"),("11010011"),("11010100"),("11010101"),("11010110"),("11010111"),
("11011000"),("11011001"),("11011010"),("11011011"),("11011100"),("11011101"),("11011110"),("11011111"),

("11100000"),("11100001"),("11100010"),("11100011"),("11100100"),("11100101"),("11100110"),("11100111"),
("11101000"),("11101001"),("11101010"),("11101011"),("11101100"),("11101101"),("11101110"),("11101111"),

("11110000"),("11110001"),("11110010"),("11110011"),("11110100"),("11110101"),("11110110"),("11110111"),
("11111000"),("11111001"),("11111010"),("11111011"),("11111100"),("11111101"),("11111110"),("11111111"),

As we judging by the previous numbers 6 we have mostly hex letters 6ABCDEF and seven with hex numbers 7123456789.

We narrow our space 6A0000000000000-6F0000000000000 477381560501272576-499899558638125056.

And we get 16 bytes.

Quote

("11010000"),("11010001"),("11010010"),("11010011"),("11010100"),("11010101"),("11010110"),("11010111"),
("11011000"),("11011001"),("11011010"),("11011011"),("11011100"),("11011101"),("11011110"),("11011111"),

For each of which options are possible with 8-15 zeros.

But then you have to think further, or launch a "bitcrack" for everyone 16. It can run multiple copies at the same time. Or try to further filter for example in three bytes "111". On the example of our previous number 10110001 10011101 01101110 here are 2 of them "111" the number of options reduced from 8008 to 4802.

python script

Quote

l1= [("10110001")]

#l1= [("11010000"),("11010001"),("11010010"),("11010011"),("11010100"),("11010101"),("11010110"),("11010111"),
# ("11011000"),("11011001"),("11011010"),("11011011"),("11011100"),("11011101"),("11011110"),("11011111")]

l2= [("10000000"),("10000001"),("10000010"),("10000011"),("10000100"),("10000101"),("10000110"),("10000111"),
   ("10001000"),("10001001"),("10001010"),("10001011"),("10001100"),("10001101"),("10001110"),("10001111"),
   ("10010000"),("10010001"),("10010010"),("10010011"),("10010100"),("10010101"),("10010110"),("10010111"),
   ("10011000"),("10011001"),("10011010"),("10011011"),("10011100"),("10011101"),("10011110"),("10011111"),
   ("10100000"),("10100001"),("10100010"),("10100011"),("10100100"),("10100101"),("10100110"),("10100111"),
   ("10101000"),("10101001"),("10101010"),("10101011"),("10101100"),("10101101"),("10101110"),("10101111"),
   ("10110000"),("10110001"),("10110010"),("10110011"),("10110100"),("10110101"),("10110110"),("10110111"),
   ("10111000"),("10111001"),("10111010"),("10111011"),("10111100"),("10111101"),("10111110"),("10111111"),
   ("11000000"),("11000001"),("11000010"),("11000011"),("11000100"),("11000101"),("11000110"),("11000111"),
   ("11001000"),("11001001"),("11001010"),("11001011"),("11001100"),("11001101"),("11001110"),("11001111"),
   ("11010000"),("11010001"),("11010010"),("11010011"),("11010100"),("11010101"),("11010110"),("11010111"),
   ("11011000"),("11011001"),("11011010"),("11011011"),("11011100"),("11011101"),("11011110"),("11011111"),
   ("11100000"),("11100001"),("11100010"),("11100011"),("11100100"),("11100101"),("11100110"),("11100111"),
   ("11101000"),("11101001"),("11101010"),("11101011"),("11101100"),("11101101"),("11101110"),("11101111"),
   ("11110000"),("11110001"),("11110010"),("11110011"),("11110100"),("11110101"),("11110110"),("11110111"),
   ("11111000"),("11111001"),("11111010"),("11111011"),("11111100"),("11111101"),("11111110"),("11111111"),
   ("00000000"),("00000001"),("00000010"),("00000011"),("00000100"),("00000101"),("00000110"),("00000111"),
   ("00001000"),("00001001"),("00001010"),("00001011"),("00001100"),("00001101"),("00001110"),("00001111"),
   ("00010000"),("00010001"),("00010010"),("00010011"),("00010100"),("00010101"),("00010110"),("00010111"),
   ("00011000"),("00011001"),("00011010"),("00011011"),("00011100"),("00011101"),("00011110"),("00011111"),
   ("00100000"),("00100001"),("00100010"),("00100011"),("00100100"),("00100101"),("00100110"),("00100111"),
   ("00101000"),("00101001"),("00101010"),("00101011"),("00101100"),("00101101"),("00101110"),("00101111"),
   ("00110000"),("00110001"),("00110010"),("00110011"),("00110100"),("00110101"),("00110110"),("00110111"),
   ("00111000"),("00111001"),("00111010"),("00111011"),("00111100"),("00111101"),("00111110"),("00111111"),
   ("01000000"),("01000001"),("01000010"),("01000011"),("01000100"),("01000101"),("01000110"),("01000111"),
   ("01001000"),("01001001"),("01001010"),("01001011"),("01001100"),("01001101"),("01001110"),("01001111"),
   ("01010000"),("01010001"),("01010010"),("01010011"),("01010100"),("01010101"),("01010110"),("01010111"),
   ("01011000"),("01011001"),("01011010"),("01011011"),("01011100"),("01011101"),("01011110"),("01011111"),
   ("01100000"),("01100001"),("01100010"),("01100011"),("01100100"),("01100101"),("01100110"),("01100111"),
   ("01101000"),("01101001"),("01101010"),("01101011"),("01101100"),("01101101"),("01101110"),("01101111"),
   ("01110000"),("01110001"),("01110010"),("01110011"),("01110100"),("01110101"),("01110110"),("01110111"),
   ("01111000"),("01111001"),("01111010"),("01111011"),("01111100"),("01111101"),("01111110"),("01111111")]

def funk():
   for element1 in (l1):
   for element2 in (l2):
   for element3 in (l2):
   bina = element1+element2+element3
   nuli = bina.count("0")
   if nuli == 10: #zeros count

   print(bina)
   pass
   else:
   pass
   return None

funk()

[/size]

Bajula

member

Activity: 166

Merit: 16

Quote from: PietCoin97 on December 05, 2018, 04:30:39 PM

Quote from: arulbero on December 05, 2018, 04:08:45 PM

Quote from: PietCoin97 on December 05, 2018, 02:41:51 PM

you say we could calculate a specific search space when we know the pub key from these addresses.

but why are the BTC still there ?

is it also impossible with the specific search space ?

We can't "calculate" a specific search space, we need to know the specific search space before starting the computation. That's the reason why those btc are still there, because nobody (except the btc owner) knows the specific search space for those private keys.

OK so the possibility that the addresses are in the 250 - 256 space is high.

When we take one of these space and make this with the baby step giant step?

Or do I understand something really wrong?

Each is double what is was before.. so imagine the memory needed for such a thing. Let's say (arbitrary example- not real) it takes 8 gb ram to do giant step 1 >>> 28 then 29 would be 16 gb ram 30 would be 32 .. --> 40 would be 32 terrabytes ram ---> 50 would be 32 PETAbytes of on board ram... etc.... so you can see where the issue lies.

PietCoin97

jr. member

Activity: 91

Merit: 3

Quote from: arulbero on December 05, 2018, 04:08:45 PM

Quote from: PietCoin97 on December 05, 2018, 02:41:51 PM

you say we could calculate a specific search space when we know the pub key from these addresses.

but why are the BTC still there ?

is it also impossible with the specific search space ?

We can't "calculate" a specific search space, we need to know the specific search space before starting the computation. That's the reason why those btc are still there, because nobody (except the btc owner) knows the specific search space for those private keys.

OK so the possibility that the addresses are in the 250 - 256 space is high.

When we take one of these space and make this with the baby step giant step?

Or do I understand something really wrong?

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: PietCoin97 on December 05, 2018, 02:41:51 PM

you say we could calculate a specific search space when we know the pub key from these addresses.

but why are the BTC still there ?

is it also impossible with the specific search space ?

We can't "calculate" a specific search space, we need to know the specific search space before starting the computation. That's the reason why those btc are still there, because nobody (except the btc owner) knows the specific search space for those private keys.

bill32767

newbie

Activity: 26

Merit: 1

Quote from: Andzhig on December 03, 2018, 03:00:04 PM

arulbero,thx.

(for reference)
1Dn8NF8qDyyfHMktmuoQLGyjWmZXgvosXf
bin 1011000110011101011011100001010010000110001001101000100001
hex 2C675B852189A21
dec 199976667976342049

1011000110011101011011100001010010000110001001101000100001 33 zeros,25 ones.

10110001 10011101 01101110 00010100 10000110 00100110 10001000 01 33-25
11110101 10010010 11100100 10000011 11001010 11101011 00001110 0 28-29
10011101 00011000 10110110 00111010 11000100 11111111 11011111 22-34
11010101 01111100 00111111 00110110 11001111 11000010 0010100 24-31
10001101 10111110 11011011 01010110 10110100 01111101 000100 23-31

1111111111111111111111111000000000000000000000000000000000
111111111111111111111111111110000000000000000000000000000
11111111111111111111111111111111110000000000000000000000
1111111111111111111111111111111000000000000000000000000
111111111111111111111111111111100000000000000000000000

79 1001111
86 1010110
71 1000111
81 1010001
86 1010110
104 1101000 (1+9+9+9+7+6+6+6+7+9+7+6+3+4+2+0+4+9)

7D4FE747
B862A62E
1A96CA8D8
34A65911D
4AED21170
9DE820A7C
1757756A93
22382FACD0
4B5F8303E9
E9AE4933D6
153869ACC5B
2A221C58D8F
6BD3B27C591
E02B35A358F
122FCA143C05
2EC18388D544
6CD610B53CBA
ADE6D7CE3B9B
174176B015F4D
22BD43C2E9354
75070A1A009D4
EFAE164CB9E3C
180788E47E326C
236FB6D5AD1F44
6ABE1F9B67E114
9D18B63AC4FFDF
1EB25C90795D61C
2C675B852189A21
5 or 6 or 7 ...

Well, what's next, 288230376151711744-576460752303423488 ,if 6 it's 430000000000000000-500000000000000000 if 7 500000000000000000-570000000000000000

You always gat some SH*T to post anytime an address is being swept. Are you the one sweeping them? Do you have a formula or anything close? What exactly do your calculations mean? I'll appreciate some explanations!

bill32767

newbie

Activity: 26

Merit: 1

Quote from: PietCoin97 on December 05, 2018, 02:41:51 PM

Quote from: arulbero on November 11, 2018, 03:38:51 PM

Quote from: noaj24 on November 11, 2018, 03:29:24 PM

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?

Of course.
Many blocks mined by Satoshi have txs with "pay to public key" script (P2PK) instead of "pay to public key hash" script (P2PKH, pay to address).

The public keys are known, but the btc are still there:

block #100

https://www.blockchain.com/it/btc/tx/2d05f0c9c3e1c226e63b5fac240137687544cf631cd616fd34fd188fc9020866

PUSHDATA(65)[04e70a02f5af48a1989bf630d92523c9d14c45c75f7d1b998e962bff6ff9995fc5bdb44f1793b3749 5d80324acba7c8f537caaf8432b8d47987313060cc82d8a93] CHECKSIG

Code:

x = e70a02f5af48a1989bf630d92523c9d14c45c75f7d1b998e962bff6ff9995fc5

y = bdb44f1793b37495d80324acba7c8f537caaf8432b8d47987313060cc82d8a93

you say we could calculate a specific search space when we know the pub key from these addresses.

but why are the BTC still there ?

is it also impossible with the specific search space ?

i have a list with 42k of this addresses

I believe his explanations were clear. He could calculate the private key from a minimal range e.g 2^80 but cannot calculate if its above that using Baby Step Giant Step as he explained previously. The puzzle keys are within a known range making it easy to get the private key after the funds has been spent. Your 42k address is IMPOSSIBLE to crack (at least not in this generation or next) even if you got all their public keys because their range are scary and larger than you can imagine.

PietCoin97

jr. member

Activity: 91

Merit: 3

Quote from: arulbero on November 11, 2018, 03:38:51 PM

Quote from: noaj24 on November 11, 2018, 03:29:24 PM

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?

Of course.
Many blocks mined by Satoshi have txs with "pay to public key" script (P2PK) instead of "pay to public key hash" script (P2PKH, pay to address).

The public keys are known, but the btc are still there:

block #100

https://www.blockchain.com/it/btc/tx/2d05f0c9c3e1c226e63b5fac240137687544cf631cd616fd34fd188fc9020866

PUSHDATA(65)[04e70a02f5af48a1989bf630d92523c9d14c45c75f7d1b998e962bff6ff9995fc5bdb44f1793b3749 5d80324acba7c8f537caaf8432b8d47987313060cc82d8a93] CHECKSIG

Code:

x = e70a02f5af48a1989bf630d92523c9d14c45c75f7d1b998e962bff6ff9995fc5

y = bdb44f1793b37495d80324acba7c8f537caaf8432b8d47987313060cc82d8a93

you say we could calculate a specific search space when we know the pub key from these addresses.

but why are the BTC still there ?

is it also impossible with the specific search space ?

i have a list with 42k of this addresses

holy_ship

jr. member

Activity: 115

Merit: 1

haha! puzzle 58 is cracked. some guys with superclusters got involved? Grin

Andzhig

jr. member

Activity: 184

Merit: 3

arulbero,thx.

(for reference)
1Dn8NF8qDyyfHMktmuoQLGyjWmZXgvosXf
bin 1011000110011101011011100001010010000110001001101000100001
hex 2C675B852189A21
dec 199976667976342049

1011000110011101011011100001010010000110001001101000100001 33 zeros,25 ones.

10110001 10011101 01101110 00010100 10000110 00100110 10001000 01 33-25
11110101 10010010 11100100 10000011 11001010 11101011 00001110 0 28-29
10011101 00011000 10110110 00111010 11000100 11111111 11011111 22-34
11010101 01111100 00111111 00110110 11001111 11000010 0010100 24-31
10001101 10111110 11011011 01010110 10110100 01111101 000100 23-31

1111111111111111111111111000000000000000000000000000000000
111111111111111111111111111110000000000000000000000000000
11111111111111111111111111111111110000000000000000000000
1111111111111111111111111111111000000000000000000000000
111111111111111111111111111111100000000000000000000000

79 1001111
86 1010110
71 1000111
81 1010001
86 1010110
104 1101000 (1+9+9+9+7+6+6+6+7+9+7+6+3+4+2+0+4+9)

7D4FE747
B862A62E
1A96CA8D8
34A65911D
4AED21170
9DE820A7C
1757756A93
22382FACD0
4B5F8303E9
E9AE4933D6
153869ACC5B
2A221C58D8F
6BD3B27C591
E02B35A358F
122FCA143C05
2EC18388D544
6CD610B53CBA
ADE6D7CE3B9B
174176B015F4D
22BD43C2E9354
75070A1A009D4
EFAE164CB9E3C
180788E47E326C
236FB6D5AD1F44
6ABE1F9B67E114
9D18B63AC4FFDF
1EB25C90795D61C
2C675B852189A21
5 or 6 or 7 ...

Well, what's next, 288230376151711744-576460752303423488 ,if 6 it's 430000000000000000-500000000000000000 if 7 500000000000000000-570000000000000000

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: j2002ba2 on November 25, 2018, 02:24:32 PM

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 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.

Thanks for the information, I will take a look at these algorithms.

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: stalker00075 on December 03, 2018, 04:14:52 AM

arulbero Help!
what key can there be 1Dn8NF8qDyyfHMktmuoQLGyjWmZXgvosXf
2..............
3..............

Code:

Private key : 00000000000000000000000000000000000000000000000002c675b852189a21
Public key : 11569442e870326ceec0de24eb5478c19e146ecd9d15e4666440f2f638875f42 524c08d882f868347f8b69d3330dc1913a159d8fb2b27864f197693a0eb39a23

PrKey WIF c.: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjv2kTamEYQT9BNC7o1
Address c. : 8c2a6071f89c90c4dab5ab295d7729d1b54ea60f
Address c. : 1Dn8NF8qDyyfHMktmuoQLGyjWmZXgvosXf

stalker00075

newbie

Activity: 54

Merit: 0

arulbero Help!
what key can there be 1Dn8NF8qDyyfHMktmuoQLGyjWmZXgvosXf
2..............
3..............

racminer

member

Activity: 245

Merit: 17

#58 1Dn8NF8qDyyfHMktmuoQLGyjWmZXgvosXf has been spent an hour ago

tx: 17d31de2bd300bc1bad430ec0db77ca27466bbb97bf03df6a3ff386d60e58996

jason589

newbie

Activity: 1

Merit: 0

Quote from: zielar on November 25, 2018, 06:35:40 AM

Bearing in mind the above scheme and the fact that yesterday a new version of BitCrack released allowing to set the initial value and the final part of the selected key part - what is the correct setting in order to find the next private key? Possibly someone has a schematic how will the command syntax look to find more keys? I have 5x GTX 1080ti so I would like to try it because I was interested in this topic

^

j2002ba2

full member

Activity: 206

Merit: 450

Quote from: arulbero on November 18, 2018, 05:49:13 AM

Quote from: j2002ba2 on November 18, 2018, 05:24:15 AM

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.

zielar

full member

Activity: 282

Merit: 114

Quote from: digitalcitizen on November 19, 2018, 11:50:30 PM

Wow.

Code:

james@research:~$ time ./baby-step-giant-step.exe
Build Hash
Search Keys
Found private key 1: ffffffffffffffff or 1
Found private key 2: fffffffffffffffd or 3
Found private key 3: fffffffffffffff9 or 7
Found private key 4: fffffffffffffff8 or 8
Found private key 5: ffffffffffffffeb or 15
Found private key 6: ffffffffffffffcf or 31
Found private key 7: ffffffffffffffb4 or 4c
Found private key 8: ffffffffffffff20 or e0
Found private key 9: fffffffffffffe2d or 1d3
Found private key 10: fffffffffffffdfe or 202
Found private key 11: fffffffffffffb7d or 483
Found private key 12: fffffffffffff585 or a7b
Found private key 13: ffffffffffffeba0 or 1460
Found private key 14: ffffffffffffd6d0 or 2930
Found private key 15: ffffffffffff970d or 68f3
Found private key 16: ffffffffffff36ca or c936
Found private key 17: fffffffffffe89b1 or 1764f
Found private key 18: fffffffffffcf7f3 or 3080d
Found private key 19: fffffffffffa8b61 or 5749f
Found private key 20: fffffffffff2d3ab or d2c55
Found private key 21: ffffffffffe45acc or 1ba534
Found private key 22: ffffffffffd21bf1 or 2de40f
Found private key 23: ffffffffffaa91ae or 556e52
Found private key 24: ffffffffff23d5fc or dc2a04
Found private key 25: fffffffffe05a11b or 1fa5ee5
Found private key 26: 340326e or 4bfcd92
Found private key 27: 6ac3875 or 953c78b
Found private key 28: a6e9318 or d916ce8
Found private key 29: 17e2551e or 181daae2
Found private key 30: 3a6b329c or 3d94cd64
Found private key 31: 7ab018b9 or 7d4fe747
Found private key 32: b79d59d2 or b862a62e
Found private key 33: 1a6935728 or 1a96ca8d8
Found private key 34: 34a65911d or 34d9a6ee3
Found private key 35: 4aed21170 or 4b12dee90
Found private key 36: 9de820a7c or 9e17df584
Found private key 37: 1757756a93 or 17588a956d
Found private key 38: 2237d05330 or 22382facd0
Found private key 39: 4b5f8303e9 or 4b607cfc17
Found private key 40: e9ae4933d6 or e9b1b6cc2a
Found private key 41: 153869acc5b or 153896533a5
Found private key 42: 2a21e3a7271 or 2a221c58d8f
Found private key 43: 6bd3b27c591 or 6bd3cd83a6f
Found private key 44: e02b35a358f or e02b4a5ca71
Found private key 45: 122fca143c05 or 122fcdebc3fb
Found private key 46: 2ec18388d544 or 2ec184772abc
Found private key 47: 6cd60f4ac346 or 6cd610b53cba
Found private key 48: ade6d7ce3b9b or ade6d831c465
Found private key 49: 174176b015f4d or 174176cfea0b3
Found private key 50: 22bd43bd16cac or 22bd43c2e9354
Found private key 51: 750709e5ff62c or 75070a1a009d4

real 4m8.237s
user 4m7.784s
sys 0m0.432s
james@research:~$

Bearing in mind the above scheme and the fact that yesterday a new version of BitCrack released allowing to set the initial value and the final part of the selected key part - what is the correct setting in order to find the next private key? Possibly someone has a schematic how will the command syntax look to find more keys? I have 5x GTX 1080ti so I would like to try it because I was interested in this topic

Amnuazka

newbie

Activity: 15

Merit: 0

Quote from: saatoshi_rising on April 27, 2017, 01:41:08 AM

Quote from: sabbybibi on March 13, 2017, 11:17:30 AM

This puzzle is very strange. If it's for measuring the world's brute forcing capacity, 161-256 are just a waste (RIPEMD160 entropy is filled by 160, and by all of P2PKH Bitcoin). The puzzle creator could improve the puzzle's utility without bringing in any extra funds from outside - just spend 161-256 across to the unsolved portion 51-160, and roughly treble the puzzle's content density.

If on the other hand there's a pattern to find... well... that's awfully open-ended... can we have a hint or two? Cheesy

I am the creator.

You are quite right, 161-256 are silly. I honestly just did not think of this. What is especially embarrassing, is this did not occur to me once, in two years. By way of excuse, I was not really thinking much about the puzzle at all.

I will make up for two years of stupidity. I will spend from 161-256 to the unsolved parts, as you suggest. In addition, I intend to add further funds. My aim is to boost the density by a factor of 10, from 0.001*length(key) to 0.01*length(key). Probably in the next few weeks. At any rate, when I next have an extended period of quiet and calm, to construct the new transaction carefully.

A few words about the puzzle. There is no pattern. It is just consecutive keys from a deterministic wallet (masked with leading 000...0001 to set difficulty). It is simply a crude measuring instrument, of the cracking strength of the community.

Finally, I wish to express appreciation of the efforts of all developers of new cracking tools and technology. The "large bitcoin collider" is especially innovative and interesting!

The pattern is 12 or 24 mnemonic ?

Bajula

member

Activity: 166

Merit: 16

Quote from: arulbero on November 21, 2018, 06:57:20 PM

Quote from: Bajula on November 21, 2018, 04:46:31 PM

Quote from: arulbero on November 16, 2018, 10:08:38 AM

For the #57 key instead:

Code:

#define GSTEP (1<<28)

typedef struct hashtable_entry {

uint64_t x;

uint32_t exponent;

} hashtable_entry;

#define HASH_SIZE (2*GSTEP)

hashtable_entry table[HASH_SIZE];

I use 32 bit for the exponent (32 > 28) and I store only the first 64 bit of the x coordinate (there is a low chance to have a partial collision in a list of 2^28 element, i.e. two different x with the same first 64 bit) --> (64 + 32 bit)

To avoid any collisions you should use always 256 bit for the x coordinate. And the size of the hash table should be at least two times the size of the list you want to store.

With the above in mind how does the other guy's program work for the first 51 with only uint32_t x; instead of 64?? Mostly curious.

Because I oversimplified my explanation to avoid technical details.

GSTEP 2^25
HASHSIZE 2^26

hash table is for one list of 2^25 public keys (baby steps)
the second list of 2^25 public keys (giant steps) is computed and compaired with the first one "on fly" (no memory)

Take the x coordinate of a public key: xst (256 bit)
and split it:

xst.n[0] 64 bit
xst.n[1] 64 bit
xst.n[2] 64 bit
xst.n[3] 64 bit

the index of the table (entry) is 26 bit of xst.n[0]
if that entry is already occupied, use xst.n[1] to modify the index (this way you avoid collisions between elements in the hash table)
instead of the entire x, x = 32 bit of xst.n[2]
exponent = i (which step it is, to retrieve the private key to that public key)

Code:

for (size_t i = 1; i < GSTEP; i++) {
   secp256k1_fe x,zinv;
   secp256k1_fe_storage xst;
   secp256k1_fe_inv_var(&zinv, &pt.z);
   secp256k1_fe_sqr(&zinv, &zinv);
   secp256k1_fe_mul(&x, &pt.x, &zinv);
   secp256k1_fe_to_storage(&xst, &x);
   uint32_t entry = xst.n[0] & (HASH_SIZE-1);
   while (table[entry].exponent != 0) {
   entry = (entry + (xst.n[1] | 1)) & (HASH_SIZE - 1);
   }
   table[entry].exponent = i;
   table[entry].x = xst.n[2];
   secp256k1_gej_add_ge_var(&pt, &pt, &secp256k1_ge_const_g, NULL);
   }

This program uses at least 26 + 32 bit = 58 bit of each public key that is in the hash table (but 26 bit are the position in the memory, so it stores effectively only 32 bit of the key in the table + 32 bit for the exponent, the private key) .

Then it generates the second list (giant steps). A wrong collision between an element of this list and a element in the table can occur only if 2 public keys share exactly 58 bit (let's say for semplicity the first 58 bit, but they are not adjacent). To find a 51 bit key then 32 bit for the x coordinate is enough.

If you need to retrieve a 60 bit private key or more, you should use more space.

Thank you! Honestly when I first looked at this thread it was because "whaaaat puzzle? free bitcoin?" *robble robble* but it has prompted me to learn, and re-invigorated this old fellas mind.

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Bajula on November 21, 2018, 04:46:31 PM

Quote from: arulbero on November 16, 2018, 10:08:38 AM

For the #57 key instead:

Code:

#define GSTEP (1<<28)

typedef struct hashtable_entry {

uint64_t x;

uint32_t exponent;

} hashtable_entry;

#define HASH_SIZE (2*GSTEP)

hashtable_entry table[HASH_SIZE];

I use 32 bit for the exponent (32 > 28) and I store only the first 64 bit of the x coordinate (there is a low chance to have a partial collision in a list of 2^28 element, i.e. two different x with the same first 64 bit) --> (64 + 32 bit)

To avoid any collisions you should use always 256 bit for the x coordinate. And the size of the hash table should be at least two times the size of the list you want to store.

With the above in mind how does the other guy's program work for the first 51 with only uint32_t x; instead of 64?? Mostly curious.

Because I oversimplified my explanation to avoid technical details.

GSTEP 2^25
HASHSIZE 2^26

hash table is for one list of 2^25 public keys (baby steps)
the second list of 2^25 public keys (giant steps) is computed and compaired with the first one "on fly" (no memory)

Take the x coordinate of a public key: xst (256 bit)
and split it:

xst.n[0] 64 bit
xst.n[1] 64 bit
xst.n[2] 64 bit
xst.n[3] 64 bit

the index of the table (entry) is 26 bit of xst.n[0]
if that entry is already occupied, use xst.n[1] to modify the index (this way you avoid collisions between elements in the hash table)
instead of the entire x, x = 32 bit of xst.n[2]
exponent = i (which step it is, to retrieve the private key to that public key)

Code:

for (size_t i = 1; i < GSTEP; i++) {
   secp256k1_fe x,zinv;
   secp256k1_fe_storage xst;
   secp256k1_fe_inv_var(&zinv, &pt.z);
   secp256k1_fe_sqr(&zinv, &zinv);
   secp256k1_fe_mul(&x, &pt.x, &zinv);
   secp256k1_fe_to_storage(&xst, &x);
   uint32_t entry = xst.n[0] & (HASH_SIZE-1);
   while (table[entry].exponent != 0) {
   entry = (entry + (xst.n[1] | 1)) & (HASH_SIZE - 1);
   }
   table[entry].exponent = i;
   table[entry].x = xst.n[2];
   secp256k1_gej_add_ge_var(&pt, &pt, &secp256k1_ge_const_g, NULL);
   }

This program uses at least 26 + 32 bit = 58 bit of each public key that is in the hash table (but 26 bit are the position in the memory, so it stores effectively only 32 bit of the key in the table + 32 bit for the exponent, the private key) .

Then it generates the second list (giant steps). A wrong collision between an element of this list and a element in the table can occur only if 2 public keys share exactly 58 bit (let's say for semplicity the first 58 bit, but they are not adjacent). To find a 51 bit key then 32 bit for the x coordinate is enough.

If you need to retrieve a 60 bit private key or more, you should use more space.

Bajula

member

Activity: 166

Merit: 16

Quote from: arulbero on November 18, 2018, 04:37:22 PM

Quote from: ZafotheNinja on November 18, 2018, 04:00:26 PM

Quote from: arulbero on November 16, 2018, 10:08:38 AM

For the #57 key instead:

Code:

#define GSTEP (1<<28)

typedef struct hashtable_entry {

uint64_t x;

uint32_t exponent;

} hashtable_entry;

#define HASH_SIZE (2*GSTEP)

hashtable_entry table[HASH_SIZE];

I use 32 bit for the exponent (32 > 28) and I store only the first 64 bit of the x coordinate (there is a low chance to have a partial collision in a list of 2^28 element, i.e. two different x with the same first 64 bit) --> (64 + 32 bit)

To avoid any collisions you should use always 256 bit for the x coordinate. And the size of the hash table should be at least two times the size of the list you want to store.

With the above in mind how does the other guy's program work for the first 51 with only uint32_t x; instead of 64?? Mostly curious.

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