After reading over the description of Pollard's kangaroo algorithm I think I understand it enough to be able to explain it to my 13 year old daughter so she can write the code as a fun educational exercise. She is always looking for a good subject for her next science fair project and I think this would make a good one. It's not so hard to write working Pollard's kangaroo, and there are some example implementation. Problem is writing CUDA implementation of it, as I understood CPU implementation can not compare by speed with CUDA one. Good point. For my real job I am writing all the TCG and secure boot ROM firmware for a next gen SSD controller ASIC. This SSD controller ASIC happens to have a built in hardware crypto engine for AES, SHA, HMAC, RSA, ECC, etc. I was thinking I could download a special test firmware into the SSD that would use the built in hardware crypto engine to do this calculation. It would be incredibly fast. I could justify downloading it to an entire rack of SSDs during manufacturing in order to do a "burn in test" of the crypto hardware on the drive. Should be fun. |
|
|
|
In that code the PRF is defined as: def f(Y):
(x, y) = Y.coords()
return pow(2, (y % k))
where k = 15 And the value of N is selected as: N = ( f(basePoint) + f(ecc.scale(basePoint, b))) / 2 * 2 Both interesting and unexpected choices. Where did you find this code? Is this from a supposedly working program? |
|
|
|
The x coordinate and y coordinate are both binary numbers in the range 2256.
the max is also a little bit less than 2 256 but unlike private keys the max is defined by P (the prime) not N (the curve order) After reading over the description of Pollard's kangaroo algorithm I think I understand it enough to be able to explain it to my 13 year old daughter so she can write the code as a fun educational exercise. She is always looking for a good subject for her next science fair project and I think this would make a good one. I have some questions about the PRF that someone might be able to answer. The only requirements listed in the article above are: 1) The PRF must map the finite cyclic group to "a set S of integers" 2) The PRF must be able to be changed in order to select a different S in order to create subsequent "kangaroos" Since the length of the pseudorandom sequence is not specified I assumed 256 bits, is that reasonable? So, it seems to me that f(X) = SHA256(X || nonce) where X is the binary representation of the the point X, || represents the concatenation operation, and the nonce is selected from a TRNG or is simply incremented would do the trick. However this seems to be overkill and we want to do this as fast as possible. Another option that comes to mind is to just define f(X) = (X + nonce) where X is the binary representation of the compressed form of X and the nonce is selected from a TRNG or is simply incremented. What PRF is generally used? Now that I think about this I think the science fair project could be something along the lines of measuring the conversion speed of various PRFs and PRF modification algorithms. The data set would be all the cracked addresses in this thread, the independent variable would be various PRFs and different ways of modifying them to produce the next "kangaroo", and the dependent variable would be the total time it takes to re-crack all the known cracked addresses listed in this thread. |
|
|
|
The x coordinate and y coordinate are both binary numbers in the range 2256.
the max is also a little bit less than 2 256 but unlike private keys the max is defined by P (the prime) not N (the curve order) For the curve used for Bitcoin public keys it turns out that for every x coordinate there are two possible y coordinates.
that doesn't depend on which curve is used, as long as it is an elliptic curve it will be symmetrical about the x-axis so for each x there are 2 y values. which is due to the formula being y 2=... A compressed public key give you the x coordinate and the sign of the y coordinate so in order to convert it to a full public key you have to calculate the correct y coordinate from the x coordinate.
that is not exactly the "sign", the first byte being 2 or 3 indicates if y is even or odd respectively. we don't actually use any signs in elliptic curve calculations since we are using modular arithmetic. for example if prime is 7 then we have 4 ≡ 11 ≡ 18 ≡ -3 ≡ -10 (mod 7) by a "contract" we only use the smallest positive number meaning "4" Thanks, I was trying to be a little less technical for zeilar since he is a total noob - I did not want to overwhelm him. You points are all well taken. Very good information for the more technical savvy in the audience. Thank you very much! I do not yet understand, however, where these values consisting of more than 150 SAME numbers come from. Converting hex to dec gives me a string of 77 characters. I could transform the logic to combine the DEC result from the first and the second and it will come out just right :-) but it probably does not work, because these strings usually also appear twice.
I have absolutely no idea how to decipher your post so I cannot help you. Good luck! |
|
|
|
After a night of searching the answer to the question bothering me (and not finding the answer), I can get the answer here ... The issue concerns the address 105 which has outgoing transactions and to which I know the pub (in HEX). How should I convert it to a string consisting ONLY OF NUMBERS .... From these patterns my head is already breaking and the level of knowledge in this direction has not changed. He understands that this is the index value 'x' or 'y', that for these addresses we have only 'y' because it's compressed, etc., but where do the DEC values come from in various Python scripts? Guest gives to try to find a value in the range of 2 ^ 20, giving me the index value 'y' consisting of 155 digits ...
I tried to transform it in a different way and I have no chance to approach this number ... it does not even occur to me what can be converted 33-character hex string being a compressed publickey to give it 155 digits being ... well, ... what other than the index? :-)
I apologize in advance for a vague description, but as I mentioned at the beginning ... the whole night does its job. Greetings!
There appears to be a few misunderstandings in your post. Specifically the part in bold is wrong. x and y are not "indexes" they are coordinates. A private key is a number between 1 and a little bit less than 2 256A public key is a point on a curve in two dimensional space. Therefore it has and x coordinate and a y coordinate. The x coordinate and y coordinate are both binary numbers in the range 2 256. For the curve used for Bitcoin public keys it turns out that for every x coordinate there are two possible y coordinates. A full public key give you both the x coordinate and y coordinate of the point that is the public key. A compressed public key give you the x coordinate and the sign of the y coordinate so in order to convert it to a full public key you have to calculate the correct y coordinate from the x coordinate. The script above does just that: calculates the correct y coordinate from the x coordinate and the sign of the y coordinate. |
|
|
|
what I did understand is that from the adress 1 to address 160 there is a difficulty of 1 bit added to the length of the private key.
A the new transaction is the difficulty 9 bit each time added to the private key, because what I see there is an incremantation of 9 at each balance
All he did was change the payout pattern. Originally for each bit of additional difficulty the payout went up by 0.001 BTC 62 bits of difficulty was = 0.062 BTC 64 bits of difficulty was = 0.064 BTC 101 bits of difficulty was = 0.101 BTC 105 bits of difficulty was = 0.105 BTC 120 bits of difficulty was = 0.120 BTC 150 bits of difficulty was = 0.150 BTC Etc... Now for each bit of difficult the payout goes up by 0.01 BTC 62 bits of difficulty total now = 0.62 BTC 64 bits of difficulty total now = 0.64 BTC 101 bits of difficulty total now = 1.01 BTC 105 bits of difficulty total now = 1.05 BTC (probably the next one to be cracked) 120 bits of difficulty total now = 1.20 BTC 150 bits of difficulty total now = 1.50 BTC Etc... You might be overthinking this. It is just that the total increased to 0.01 BTC per added bit of private key taking both funding transactions into account. |
|
|
|
sorry ,If it's restricted on this group for talking about out of topic,I will delete those posts my self,
and i know, where i am , and why this channel is made for, actually, it's just my curiosity ,sorry to ask here.
Your ability to learn from your mistakes, admit you were wrong, and delete your post is very rare on this forum and very refreshing! + merit |
|
|
|
Yes that transaction is one of the transactions listed in the OP. This thread covers the entire history of the challenge and the OP lists all cracked addresses including those from the first funding transaction and those included in the second funding transaction. So to answer your initial question, the private keys that have been cracked from the transaction you listed are all shown in the OP. thank you , I get it now , I'm confused because the adresses from 160 to 256 were swiped to the new transaction The creator/owner of the challenge moved those BTC due to a suggestion from a contributor to the original thread. |
|
|
|
Yes that transaction is one of the transactions listed in the OP. This thread covers the entire history of the challenge and the OP lists all cracked addresses including those from the first funding transaction and those included in the second funding transaction. So to answer your initial question, the private keys that have been cracked from the transaction you listed are all shown in the OP. |
|
|
|
All cracked private keys are listed in a maintained list in the the OP, see the section "EXISTING KEYS FOUND SO FAR:" https://bitcointalk.org/index.php?topic=5166284.msg51860206#msg51860206All of the transactions related to this challenge are also listed in the OP in the section "A BRIEF LIST OF IMPORTANT DATES IN THE HISTORY OF THE CHALLENGE:" Please read the first post in this thread and it will answer a lot of questions. |
|
|
|
Man, I really don't understand you. What is your goal in selling this script if it really works!?
WHY DONT YOU OPEN ALL KEYS from 61 -> whatever you can, if it takes you less time then others?
0.025 BTC price for script? Mate, if you open even #61 address you will cover ~24 buyers. ))
Why do you spend your time for prooving that your script does work? For the same time you could open #74 address and get the bounty!!!
Where is the logic???
If you sell your script to several people they will open all possible addresses (until the time required will be within an adequate range) in a days and then your scipt will just remain in a history of cracking.....
Because it only works on the addresses with spend transactions: 65, 70, 75, 80, 85, etc. and all of these have been opened up to #100. #105 will take a bit of effort to open so instead of running it all that time just sell it to others. Kind of makes sense at this point. What is your expected time for #105?
I was using 4x Tesla V100 for it. Here is a table with expected times: |------+-------------------+-------------------|
| bits | 4x V100 | 100x V100 |
|------+-------------------+-------------------|
| 100 | 2d 19:52:51 | 02:42:54 |
| 105 | 16 days | 15:21:34 |
| 110 | 90 days | 3d 14:53:14 |
| 115 | 1 year 147 days | 20 days |
| 120 | 7 years 341 days | 116 days |
| 125 | 44 years 323 days | 1 year 290 days |
| 130 | 253 years | 10 years 57 days |
| 135 | 1,436 years | 57 years 166 days |
| 140 | 8,125 years | 325 years |
| 145 | 45,964 years | 1,838 years |
| 150 | 260,011 years | 10,400 years |
| 155 | 1,470,848 years | 58,833 years |
| 160 | 8,320,376 years | 332,815 years |
|------+-------------------+-------------------|
Looks like a "world record" would be 120 bits. |
|
|
|
can anyone know, or explain to me please,
how it will be easy to find private keys which has spend transaction for the wallet in compare to wallet which hasn't spend transaction ?
please explain if anybody know , i am confused so, thanks.
When there is no spend transaction the search method is: Next Private Key -> Public Key -> Hash -> Bitcoin Address -> Compare Bitcoin Address, repeat until found Note that due to the hashing functions used the Bitcoin Address match is expected within a private key range of only 2 160A spend transaction exposes the public key so when there is a spend transaction the search method is: Next Private Key -> Public Key -> Compare Public Key, repeat until found Note that the private key range in this case is the full 2 256 but there are ways to speed up the process so the effective security is reduced to only 128 bits. See the following: So the two situations are: Full entropy 256 bit private keys with multiple spend transactions have 128 bits of security 160 bit Bitcoin address from a full entropy 256 bit private key with no spend transactions have 160 bits of securitySo Bitcoins kept on a Bitcoin address with no spend transactions are safer (160 bits of security) than Bitcoins kept on a Bitcoin address that has spend transactions (only 128 bits of security). thanks, let's say we got a spend transaction on bitcoin puzzle wallet #120, we got hash of it, so how do we calculate with bitcrack for 2^128 possibles? Please go back and read what I wrote way more carefully. A spend transaction exposes the public key so you no longer have to do any hashing. Bitcrack is for brute forcing when you do not have the public key. You would need/want to use one of the more advanced methods (see the links in my post) to calculate the private key directly from the public key because it will be so much faster than the primitive bitcrack program. There is no hashing involved any more since you no longer have to deal with the Bitcoin address - you have the public key. BTW there is a spend transaction on #120 so the public key for that address is in the block chain and is available. The person that solves #120 will not be using the primitive brute force bitcrack method. #120 will most certainly be solved using the Pollard Kangaros method. Depending on how much HW you can afford it will take between 116 days and about 8 years to find it. See: What is your expected time for #105?
I was using 4x Tesla V100 for it. Here is a table with expected times: |------+-------------------+-------------------|
| bits | 4x V100 | 100x V100 |
|------+-------------------+-------------------|
| 100 | 2d 19:52:51 | 02:42:54 |
| 105 | 16 days | 15:21:34 |
| 110 | 90 days | 3d 14:53:14 |
| 115 | 1 year 147 days | 20 days |
| 120 | 7 years 341 days | 116 days |
| 125 | 44 years 323 days | 1 year 290 days |
| 130 | 253 years | 10 years 57 days |
| 135 | 1,436 years | 57 years 166 days |
| 140 | 8,125 years | 325 years |
| 145 | 45,964 years | 1,838 years |
| 150 | 260,011 years | 10,400 years |
| 155 | 1,470,848 years | 58,833 years |
| 160 | 8,320,376 years | 332,815 years |
|------+-------------------+-------------------|
Looks like a "world record" would be 120 bits. |
|
|
|
Anyone solved this so far ?
RTFT |
|
|
|
can anyone know, or explain to me please,
how it will be easy to find private keys which has spend transaction for the wallet in compare to wallet which hasn't spend transaction ?
please explain if anybody know , i am confused so, thanks.
When there is no spend transaction the search method is: Next Private Key -> Public Key -> Hash -> Bitcoin Address -> Compare Bitcoin Address, repeat until found Note that due to the hashing functions used the Bitcoin Address match is expected within a private key range of only 2 160A spend transaction exposes the public key so when there is a spend transaction the search method is: Next Private Key -> Public Key -> Compare Public Key, repeat until found Note that the private key range in this case is the full 2 256 but there are ways to speed up the process so the effective security is reduced to only 128 bits. See the following: So the two situations are: Full entropy 256 bit private keys with multiple spend transactions have 128 bits of security 160 bit Bitcoin address from a full entropy 256 bit private key with no spend transactions have 160 bits of securitySo Bitcoins kept on a Bitcoin address with no spend transactions are safer (160 bits of security) than Bitcoins kept on a Bitcoin address that has spend transactions (only 128 bits of security). |
|
|
|
|
Hey, I got the math right this time! (pats self on back)
But, I did not go look up the original source for the world record and trusted someone else's post on the number. I have fixed my post above and taken back my pat on the back.
|
|
|
|
#100 - af55fc59c335c8ec67ed24826
Lucky with only 69% of the expected time - 1d 22:49:48 of the 2d 19:46:27 expected.
Great! zielar can fill in the #100 entry in the table in the OP. Congrats on your 1 BTC (approx $10,000) bounty! For private key 000000000000000000000000000000000000000af55fc59c335c8ec67ed24826 I get: Uncompressed Bitcoin Address: 1Bv8fD7w52gWTRpnAMTLPvMrsfpX6bySpe Compressed Bitcoin Address: 1KCgMv8fo2TPBpddVi9jqmMmcne9uSNJ5FWhat is your expected time for #105 (approx another $10,500)? My "back of the envelope" estimate for the estimated times, assuming you can afford or have access to the required hardware: #100 = 50.0 bits of security was estimated at about 3 days #105 = 52.5 bits of security will be about 3 x 2 2.5 = about 17 days #110 = 55.0 bits of security will be about 3 x 2 5.0 = about 96 days #115 = 57.5 bits of security will be about 3 x 2 7.5 = about 543 days = 1.49 years #120 = 60.0 bits of security will be about 3 x 2 10.0 = about 3,072 days = 8.41 years *** #125 = 62.5 bits of security will be about 3 x 2 12.5 = about 17,378 days = 47.56 years #130 = 65.0 bits of security will be about 3 x 2 15.0 = about 98,304 days = 269.14 years The last one would be: #160 = 80.0 bits of security will be about 3 x 2 30.0 = about 3,221,225,472 days = 8,819,234 years *** From what I understand 120 bits would be a new world record for "cracking" an EC key pair. On 2 December 2016, Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe, and Ralf Zimmermann announced the solution of a generic 117.35-bit elliptic curve discrete logarithm problem on a binary curve, using an optimized FPGA implementation of a parallel version of Pollard's rho algorithm. The attack ran for about six months on 64 to 576 FPGAs in parallel.[30] From https://en.wikipedia.org/wiki/Discrete_logarithm_records |
|
|
|
Now this will blow your mind:
For every Bitcoin Address there are about 296 = 79,228,162,514,264,337,593,543,950,336 valid possible Public/Private key pairs!
No it doesn't. It is well known, that many private keys map to the same address due to RIPEMD-160. But the converse is not well known: That one private key generates multiple addresses. In the current case exactly two addresses. So, for address generation, one uses only the x coordinate with the sign, but the algorithm for address generation stays the same? https://www.freecodecamp.org/news/how-to-create-a-bitcoin-wallet-address-from-a-private-key-eca3ddd9c05f/The algorithm for generating a Bitcoin address from a public key never changes. What changes is the value that is input into the Bitcoin address generation algorithm. In one case (uncompressed) the input value is both the X and Y coordinates, in the other case (compressed) it it just the X coordinate and the sign of the Y coordinate. Thanks for the explanation. Again I learned something.  Anyhow, why do you think, that the number sequence for the private keys can be generated by some rule? The canary bird hypothesis sounds convincing to me. There is a very good explanation, which I agree with, here: https://bitcointalk.org/index.php?topic=5166284.0 |
|
|
|
Now this will blow your mind:
For every Bitcoin Address there are about 296 = 79,228,162,514,264,337,593,543,950,336 valid possible Public/Private key pairs!
No it doesn't. It is well known, that many private keys map to the same address due to RIPEMD-160. But the converse is not well known: That one private key generates multiple addresses. In the current case exactly two addresses. So, for address generation, one uses only the x coordinate with the sign, but the algorithm for address generation stays the same? https://www.freecodecamp.org/news/how-to-create-a-bitcoin-wallet-address-from-a-private-key-eca3ddd9c05f/The algorithm for generating a Bitcoin address from a public key never changes. What changes is the value that is input into the Bitcoin address generation algorithm. In one case (uncompressed) the input value is both the X and Y coordinates, in the other case (compressed) it it just the X coordinate and the sign of the Y coordinate. |
|
|
|
Well, unfortunately - options to delete posts in their own topics are missing.
Yes, unfortunately you have to select "moderated topic" at the time you create the thread and you cannot change it after the tread is created. |
|
|
|
|
Show Posts
