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

Right!


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.

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

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?

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:

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?

Code is only for cpu. Why GPU?

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

Can you share the code?

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.

Ok, that's fine, becouse  I began to get nervous yesterday about  my own wallet security.

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)

You mean that everybody can calculate the private key of wallets or what?

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

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

Ok, I understand

Knowing that the private key has a limited width, so maybe you do your search so to  match the transaction script ?

So this person is still unknown ?

Just to be clear, I didn't find the key. I got the key only after the address was swept by somebody else.

He is finding keys using some sort of smart way but still random. He probably figured out a nice way to narrow the search.
It took 60 days to find  15c9mPGLku1HuW9LRtBf4jcHVpBUt8txKz after 17aPYR1m6pVAacXg1PTDDU7XafvK1dxvhi
I am not sure if he is the one who got 1LzhS3k3e9Ub8i2W1V8xQFdB8n2MYCHPCa.
If his algorithm is linear, we will see the next one in 60 days or so.
I thing we should show a lot of respect to this MAN 
bravo !!!

You are kinda pissing me off man! You keep finding the keys and making it worth no ones time to make use of their GPU miners with the Bitcrack program.

0000000000000000000000000000000000000000000000000000000000000001 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH
0000000000000000000000000000000000000000000000000000000000000003 1CUNEBjYrCn2y1SdiUMohaKUi4wpP326Lb
0000000000000000000000000000000000000000000000000000000000000007 19ZewH8Kk1PDbSNdJ97FP4EiCjTRaZMZQA
0000000000000000000000000000000000000000000000000000000000000008 1EhqbyUMvvs7BfL8goY6qcPbD6YKfPqb7e
0000000000000000000000000000000000000000000000000000000000000015 1E6NuFjCi27W5zoXg8TRdcSRq84zJeBW3k
0000000000000000000000000000000000000000000000000000000000000031 1PitScNLyp2HCygzadCh7FveTnfmpPbfp8
000000000000000000000000000000000000000000000000000000000000004c 1McVt1vMtCC7yn5b9wgX1833yCcLXzueeC
00000000000000000000000000000000000000000000000000000000000000e0 1M92tSqNmQLYw33fuBvjmeadirh1ysMBxK
00000000000000000000000000000000000000000000000000000000000001d3 1CQFwcjw1dwhtkVWBttNLDtqL7ivBonGPV
0000000000000000000000000000000000000000000000000000000000000202 1LeBZP5QCwwgXRtmVUvTVrraqPUokyLHqe
0000000000000000000000000000000000000000000000000000000000000483 1PgQVLmst3Z314JrQn5TNiys8Hc38TcXJu
0000000000000000000000000000000000000000000000000000000000000a7b 1DBaumZxUkM4qMQRt2LVWyFJq5kDtSZQot
0000000000000000000000000000000000000000000000000000000000001460 1Pie8JkxBT6MGPz9Nvi3fsPkr2D8q3GBc1
0000000000000000000000000000000000000000000000000000000000002930 1ErZWg5cFCe4Vw5BzgfzB74VNLaXEiEkhk
00000000000000000000000000000000000000000000000000000000000068f3 1QCbW9HWnwQWiQqVo5exhAnmfqKRrCRsvW
000000000000000000000000000000000000000000000000000000000000c936 1BDyrQ6WoF8VN3g9SAS1iKZcPzFfnDVieY
000000000000000000000000000000000000000000000000000000000001764f 1HduPEXZRdG26SUT5Yk83mLkPyjnZuJ7Bm
000000000000000000000000000000000000000000000000000000000003080d 1GnNTmTVLZiqQfLbAdp9DVdicEnB5GoERE
000000000000000000000000000000000000000000000000000000000005749f 1NWmZRpHH4XSPwsW6dsS3nrNWfL1yrJj4w
00000000000000000000000000000000000000000000000000000000000d2c55 1HsMJxNiV7TLxmoF6uJNkydxPFDog4NQum
00000000000000000000000000000000000000000000000000000000001ba534 14oFNXucftsHiUMY8uctg6N487riuyXs4h
00000000000000000000000000000000000000000000000000000000002de40f 1CfZWK1QTQE3eS9qn61dQjV89KDjZzfNcv
0000000000000000000000000000000000000000000000000000000000556e52 1L2GM8eE7mJWLdo3HZS6su1832NX2txaac
0000000000000000000000000000000000000000000000000000000000dc2a04 1rSnXMr63jdCuegJFuidJqWxUPV7AtUf7
0000000000000000000000000000000000000000000000000000000001fa5ee5 15JhYXn6Mx3oF4Y7PcTAv2wVVAuCFFQNiP
000000000000000000000000000000000000000000000000000000000340326e 1JVnST957hGztonaWK6FougdtjxzHzRMMg
0000000000000000000000000000000000000000000000000000000006ac3875 128z5d7nN7PkCuX5qoA4Ys6pmxUYnEy86k
000000000000000000000000000000000000000000000000000000000d916ce8 12jbtzBb54r97TCwW3G1gCFoumpckRAPdY
0000000000000000000000000000000000000000000000000000000017e2551e 19EEC52krRUK1RkUAEZmQdjTyHT7Gp1TYT
000000000000000000000000000000000000000000000000000000003d94cd64 1LHtnpd8nU5VHEMkG2TMYYNUjjLc992bps
000000000000000000000000000000000000000000000000000000007d4fe747 1LhE6sCTuGae42Axu1L1ZB7L96yi9irEBE
00000000000000000000000000000000000000000000000000000000b862a62e 1FRoHA9xewq7DjrZ1psWJVeTer8gHRqEvR
00000000000000000000000000000000000000000000000000000001a96ca8d8 187swFMjz1G54ycVU56B7jZFHFTNVQFDiu
000000000000000000000000000000000000000000000000000000034a65911d 1PWABE7oUahG2AFFQhhvViQovnCr4rEv7Q
00000000000000000000000000000000000000000000000000000004aed21170 1PWCx5fovoEaoBowAvF5k91m2Xat9bMgwb
00000000000000000000000000000000000000000000000000000009de820a7c 1Be2UF9NLfyLFbtm3TCbmuocc9N1Kduci1
0000000000000000000000000000000000000000000000000000001757756a93 14iXhn8bGajVWegZHJ18vJLHhntcpL4dex
00000000000000000000000000000000000000000000000000000022382facd0 1HBtApAFA9B2YZw3G2YKSMCtb3dVnjuNe2
0000000000000000000000000000000000000000000000000000004b5f8303e9 122AJhKLEfkFBaGAd84pLp1kfE7xK3GdT8
000000000000000000000000000000000000000000000000000000e9ae4933d6 1EeAxcprB2PpCnr34VfZdFrkUWuxyiNEFv
00000000000000000000000000000000000000000000000000000153869acc5b 1L5sU9qvJeuwQUdt4y1eiLmquFxKjtHr3E
000000000000000000000000000000000000000000000000000002a221c58d8f 1E32GPWgDyeyQac4aJxm9HVoLrrEYPnM4N
000000000000000000000000000000000000000000000000000006bd3b27c591 1PiFuqGpG8yGM5v6rNHWS3TjsG6awgEGA1
00000000000000000000000000000000000000000000000000000e02b35a358f 1CkR2uS7LmFwc3T2jV8C1BhWb5mQaoxedF
0000000000000000000000000000000000000000000000000000122fca143c05 1NtiLNGegHWE3Mp9g2JPkgx6wUg4TW7bbk
00000000000000000000000000000000000000000000000000002ec18388d544 1F3JRMWudBaj48EhwcHDdpeuy2jwACNxjP
00000000000000000000000000000000000000000000000000006cd610b53cba 1Pd8VvT49sHKsmqrQiP61RsVwmXCZ6ay7Z
0000000000000000000000000000000000000000000000000000ade6d7ce3b9b 1DFYhaB2J9q1LLZJWKTnscPWos9VBqDHzv
000000000000000000000000000000000000000000000000000174176b015f4d 12CiUhYVTTH33w3SPUBqcpMoqnApAV4WCF
00000000000000000000000000000000000000000000000000022bd43c2e9354 1MEzite4ReNuWaL5Ds17ePKt2dCxWEofwk
00000000000000000000000000000000000000000000000000075070a1a009d4 1NpnQyZ7x24ud82b7WiRNvPm6N8bqGQnaS
000000000000000000000000000000000000000000000000000efae164cb9e3c 15z9c9sVpu6fwNiK7dMAFgMYSK4GqsGZim
00000000000000000000000000000000000000000000000000180788e47e326c 15K1YKJMiJ4fpesTVUcByoz334rHmknxmT
00000000000000000000000000000000000000000000000000236fb6d5ad1f46 19LeLQDmSR8nxFa4v7UdX9SC41mdxP6Rx9
000000000000000000000000000000000000000000000000006abe1f9b67e114 1LzhS3k3e9Ub8i2W1V8xQFdB8n2MYCHPCa
000000000000000000000000000000000000000000000000009d18b63ac4ffdf 17aPYR1m6pVAacXg1PTDDU7XafvK1dxvhi
00000000000000000000000000000000000000000000000001eb25c90795d61c 15c9mPGLku1HuW9LRtBf4jcHVpBUt8txKz

or in binary

0000000000000000000000000000000000000000000000000000000000000001 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH
0000000000000000000000000000000000000000000000000000000000000011 1CUNEBjYrCn2y1SdiUMohaKUi4wpP326Lb
0000000000000000000000000000000000000000000000000000000000000111 19ZewH8Kk1PDbSNdJ97FP4EiCjTRaZMZQA
0000000000000000000000000000000000000000000000000000000000001000 1EhqbyUMvvs7BfL8goY6qcPbD6YKfPqb7e
0000000000000000000000000000000000000000000000000000000000010101 1E6NuFjCi27W5zoXg8TRdcSRq84zJeBW3k
0000000000000000000000000000000000000000000000000000000000110001 1PitScNLyp2HCygzadCh7FveTnfmpPbfp8
0000000000000000000000000000000000000000000000000000000001001100 1McVt1vMtCC7yn5b9wgX1833yCcLXzueeC
0000000000000000000000000000000000000000000000000000000011100000 1M92tSqNmQLYw33fuBvjmeadirh1ysMBxK
0000000000000000000000000000000000000000000000000000000111010011 1CQFwcjw1dwhtkVWBttNLDtqL7ivBonGPV
0000000000000000000000000000000000000000000000000000001000000010 1LeBZP5QCwwgXRtmVUvTVrraqPUokyLHqe
0000000000000000000000000000000000000000000000000000010010000011 1PgQVLmst3Z314JrQn5TNiys8Hc38TcXJu
0000000000000000000000000000000000000000000000000000101001111011 1DBaumZxUkM4qMQRt2LVWyFJq5kDtSZQot
0000000000000000000000000000000000000000000000000001010001100000 1Pie8JkxBT6MGPz9Nvi3fsPkr2D8q3GBc1
0000000000000000000000000000000000000000000000000010100100110000 1ErZWg5cFCe4Vw5BzgfzB74VNLaXEiEkhk
0000000000000000000000000000000000000000000000000110100011110011 1QCbW9HWnwQWiQqVo5exhAnmfqKRrCRsvW
0000000000000000000000000000000000000000000000001100100100110110 1BDyrQ6WoF8VN3g9SAS1iKZcPzFfnDVieY
0000000000000000000000000000000000000000000000010111011001001111 1HduPEXZRdG26SUT5Yk83mLkPyjnZuJ7Bm
0000000000000000000000000000000000000000000000110000100000001101 1GnNTmTVLZiqQfLbAdp9DVdicEnB5GoERE
0000000000000000000000000000000000000000000001010111010010011111 1NWmZRpHH4XSPwsW6dsS3nrNWfL1yrJj4w
0000000000000000000000000000000000000000000011010010110001010101 1HsMJxNiV7TLxmoF6uJNkydxPFDog4NQum
0000000000000000000000000000000000000000000110111010010100110100 14oFNXucftsHiUMY8uctg6N487riuyXs4h
0000000000000000000000000000000000000000001011011110010000001111 1CfZWK1QTQE3eS9qn61dQjV89KDjZzfNcv
0000000000000000000000000000000000000000010101010110111001010010 1L2GM8eE7mJWLdo3HZS6su1832NX2txaac
0000000000000000000000000000000000000000110111000010101000000100 1rSnXMr63jdCuegJFuidJqWxUPV7AtUf7
0000000000000000000000000000000000000001111110100101111011100101 15JhYXn6Mx3oF4Y7PcTAv2wVVAuCFFQNiP
0000000000000000000000000000000000000011010000000011001001101110 1JVnST957hGztonaWK6FougdtjxzHzRMMg
0000000000000000000000000000000000000110101011000011100001110101 128z5d7nN7PkCuX5qoA4Ys6pmxUYnEy86k
0000000000000000000000000000000000001101100100010110110011101000 12jbtzBb54r97TCwW3G1gCFoumpckRAPdY
0000000000000000000000000000000000010111111000100101010100011110 19EEC52krRUK1RkUAEZmQdjTyHT7Gp1TYT
0000000000000000000000000000000000111101100101001100110101100100 1LHtnpd8nU5VHEMkG2TMYYNUjjLc992bps
0000000000000000000000000000000001111101010011111110011101000111 1LhE6sCTuGae42Axu1L1ZB7L96yi9irEBE
0000000000000000000000000000000010111000011000101010011000101110 1FRoHA9xewq7DjrZ1psWJVeTer8gHRqEvR
0000000000000000000000000000000110101001011011001010100011011000 187swFMjz1G54ycVU56B7jZFHFTNVQFDiu
0000000000000000000000000000001101001010011001011001000100011101 1PWABE7oUahG2AFFQhhvViQovnCr4rEv7Q
0000000000000000000000000000010010101110110100100001000101110000 1PWCx5fovoEaoBowAvF5k91m2Xat9bMgwb
0000000000000000000000000000100111011110100000100000101001111100 1Be2UF9NLfyLFbtm3TCbmuocc9N1Kduci1
0000000000000000000000000001011101010111011101010110101010010011 14iXhn8bGajVWegZHJ18vJLHhntcpL4dex
0000000000000000000000000010001000111000001011111010110011010000 1HBtApAFA9B2YZw3G2YKSMCtb3dVnjuNe2
0000000000000000000000000100101101011111100000110000001111101001 122AJhKLEfkFBaGAd84pLp1kfE7xK3GdT8
0000000000000000000000001110100110101110010010010011001111010110 1EeAxcprB2PpCnr34VfZdFrkUWuxyiNEFv
0000000000000000000000010101001110000110100110101100110001011011 1L5sU9qvJeuwQUdt4y1eiLmquFxKjtHr3E
0000000000000000000000101010001000100001110001011000110110001111 1E32GPWgDyeyQac4aJxm9HVoLrrEYPnM4N
0000000000000000000001101011110100111011001001111100010110010001 1PiFuqGpG8yGM5v6rNHWS3TjsG6awgEGA1
0000000000000000000011100000001010110011010110100011010110001111 1CkR2uS7LmFwc3T2jV8C1BhWb5mQaoxedF
0000000000000000000100100010111111001010000101000011110000000101 1NtiLNGegHWE3Mp9g2JPkgx6wUg4TW7bbk
0000000000000000001011101100000110000011100010001101010101000100 1F3JRMWudBaj48EhwcHDdpeuy2jwACNxjP
0000000000000000011011001101011000010000101101010011110010111010 1Pd8VvT49sHKsmqrQiP61RsVwmXCZ6ay7Z
0000000000000000101011011110011011010111110011100011101110011011 1DFYhaB2J9q1LLZJWKTnscPWos9VBqDHzv
0000000000000001011101000001011101101011000000010101111101001101 12CiUhYVTTH33w3SPUBqcpMoqnApAV4WCF
0000000000000010001010111101010000111100001011101001001101010100 1MEzite4ReNuWaL5Ds17ePKt2dCxWEofwk
0000000000000111010100000111000010100001101000000000100111010100 1NpnQyZ7x24ud82b7WiRNvPm6N8bqGQnaS
0000000000001110111110101110000101100100110010111001111000111100 15z9c9sVpu6fwNiK7dMAFgMYSK4GqsGZim
0000000000011000000001111000100011100100011111100011001001101100 15K1YKJMiJ4fpesTVUcByoz334rHmknxmT
0000000000100011011011111011011011010101101011010001111101000110 19LeLQDmSR8nxFa4v7UdX9SC41mdxP6Rx9
0000000001101010101111100001111110011011011001111110000100010100 1LzhS3k3e9Ub8i2W1V8xQFdB8n2MYCHPCa
0000000010011101000110001011011000111010110001001111111111011111 17aPYR1m6pVAacXg1PTDDU7XafvK1dxvhi
0000000111101011001001011100100100000111100101011101011000011100 15c9mPGLku1HuW9LRtBf4jcHVpBUt8txKz


(to be checked )

Ok thanks a lot