Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 52. (Read 58537 times)

full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 20, 2021, 10:35:41 PM
How then were the ranges calculated in https://privatekeys.pw/puzzles/bitcoin-puzzle-tx
?

The private keys were deliberately generated within those ranges by the author. The ranges themselves weren't calculated.

So it's like the author made #64's private key between ranges 2^64 and 2^65-1, #65 between 2^65 and 2^66-1, and so on.

why at certain times the kangaroo program start to accumulate dead kangaroos? does this give any indication as to solving the the puzzle
Not really.  I don't know what range you are running but normally they start accumulating when running through a small range.  There is limited space in smaller range so the kangaroos in the same herd start to trip over each other.  But if you do get dead kangaroos in a larger range, no worries, the program automatically resets them to different random points.
jr. member
Activity: 76
Merit: 4
June 20, 2021, 10:13:28 PM
How then were the ranges calculated in https://privatekeys.pw/puzzles/bitcoin-puzzle-tx
?

The private keys were deliberately generated within those ranges by the author. The ranges themselves weren't calculated.

So it's like the author made #64's private key between ranges 2^64 and 2^65-1, #65 between 2^65 and 2^66-1, and so on.

why at certain times the kangaroo program start to accumulate dead kangaroos? does this give any indication as to solving the the puzzle
jr. member
Activity: 38
Merit: 1
June 20, 2021, 01:26:20 PM
I am very grateful to you for your answer.
GoldTiger69
NotATether

P.S.
It is a pity that this puzzle has already exhausted itself, there are literally 1-3 addresses left that can be obtained, the rest will remain unattainable.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
June 20, 2021, 01:21:58 PM
How then were the ranges calculated in https://privatekeys.pw/puzzles/bitcoin-puzzle-tx
?

The private keys were deliberately generated within those ranges by the author. The ranges themselves weren't calculated.

So it's like the author made #64's private key between ranges 2^64 and 2^65-1, #65 between 2^65 and 2^66-1, and so on.
jr. member
Activity: 38
Merit: 1
June 20, 2021, 01:09:31 PM
How then were the ranges calculated in https://privatekeys.pw/puzzles/bitcoin-puzzle-tx
?
hero member
Activity: 583
Merit: 502
June 20, 2021, 12:53:43 PM
Hi everybody.
I read a very interesting topic.
I have a question.
How do you know in which exact range is this or that address?


For example, take any address

1AnQDYo81Ta4VcSbeQNWp9CwPcsZqRvPGD
How to find out in what range its private key?

I apologize if the question is stupid.

You can't, that's why Bitcoin is secure (by now).
jr. member
Activity: 38
Merit: 1
June 20, 2021, 12:22:22 PM
Hi everybody.
I read a very interesting topic.
I have a question.
How do you know in which exact range is this or that address?


For example, take any address

1AnQDYo81Ta4VcSbeQNWp9CwPcsZqRvPGD
How to find out in what range its private key?

I apologize if the question is stupid.
jr. member
Activity: 76
Merit: 4
June 18, 2021, 06:51:13 PM
I am new to this and I appreciate the help. i tested this one on 63 and 65, starting at 0 straight not random in the keyspace and it took 0 seconds to find 63 and about 1 minute on 65 with just the 1 public key so i know it works. I just wasted the last month on 120 because i divided the keyspace up in 8 parts (lack of understanding) with none of the parts able to merge with the other. I should have asked people with knowledge first LOL. If i do find 120 or 125 I will definitely take care of you. Thanks
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 18, 2021, 06:21:04 PM
Ok with 200 keys loaded I get
 Thread ac696c49b9408a82028a45ab2a0629ds: 2754540302104 keys/s
  • Thread fbba3026c71c044279bbfa174174d5ds: 2750714982463 keys/s
  • Thread 9468dafbf9970e2876c5cc4199a3edds: 2752389277771 keys/s
  • Thread cfe35ea9483be51a01a063acbcbf3eds: 2748653881650 keys/s
  • Thread eefb0efefad83846f455cf5b9bd98eds: 2750316472506 keys/s
  • Thread db0b986adc150b65b3624c4c3351bads: 2751949106769 keys/s
  • Thread 996ef3f4b518d1e2842ba5f0cf0551^C: 2753552586849 keys/s

Normally this computer gets 600 trillion per second

my other computer usually does with 1 key loaded 2.7 quadrillion per second but with 1000 keys loaded it is doing 76 billion / second.
I really can't speak to a different BSGS program.  Jean Lucs loads all pubkeys, performs the baby steps one time, and then runs each pubkey through the giant steps, sequentially.

If it takes 10 seconds to perform/store the baby steps and then 1 second to run and check one public key in a 2^48 range, then if you were to run 1,000 pubkeys in the same  range, it would take about 1 minute to search all 1,000 pubkeys loaded.

I wouldn't use another BSGS because I haven't found one faster than Jean Luc's.
jr. member
Activity: 76
Merit: 4
June 18, 2021, 05:42:34 PM
Ok with 200 keys loaded I get
 Thread ac696c49b9408a82028a45ab2a0629ds: 2754540302104 keys/s
  • Thread fbba3026c71c044279bbfa174174d5ds: 2750714982463 keys/s
  • Thread 9468dafbf9970e2876c5cc4199a3edds: 2752389277771 keys/s
  • Thread cfe35ea9483be51a01a063acbcbf3eds: 2748653881650 keys/s
  • Thread eefb0efefad83846f455cf5b9bd98eds: 2750316472506 keys/s
  • Thread db0b986adc150b65b3624c4c3351bads: 2751949106769 keys/s
  • Thread 996ef3f4b518d1e2842ba5f0cf0551^C: 2753552586849 keys/s

Normally this computer gets 600 trillion per second

my other computer usually does with 1 key loaded 2.7 quadrillion per second but with 1000 keys loaded it is doing 76 billion / second.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 18, 2021, 05:29:55 PM
For example If I am running with 1 loaded public key BSGS and for argument sake with 1 key loaded I am operating at 100 million keys per second but if I substract and load  1000 of the same key just offset by a different distance from the target key my keys per second drops 100 million/1000 (more actually) but now I have 1000 more possible chances of a collision because i have added 1000 targets.

Example
03b6c66d90910721ac8e6f8ef0ebb222fff638227122b21c5853e787ca3d119f08 # - 651321717934608777722865459537368854
030e7b9ccf0feabe79d8745a89b575b52ff21333368b4a9c95c72dbef88a6105e2 # + 651321717934608777722865459537368854
029a564b60e6bed3449052228a609334b43d59bc5f79ca5c622334658ce89b6026 # - 657967857913533357087384494838770577
03a127833050783f814ee013e796fbc937067a86741564bdb9086a6e6e6398e11d # + 657967857913533357087384494838770577
03d0203676b61edda6208b2f9b204de5e8ee2849723458dc7531b1eaba503de390 # - 664613997892457936451903530140172300
0247dd5a10ae3aab4187c7af2a5babcc8ee401ed09e67fbc6ea75e35cc8471d8c9 # + 664613997892457936451903530140172300
02ceb6cbbcdbdf5ef7150682150f4ce2c6f4807b349827dcdbdd1f2efa885a2630 # target


If one of these keys hits then i just add or subtract the decimal value on the right from the hex private key found  convert to decimal add or subtract than convert back to hex  and now I have the  key for 120 02ceb6cbbcdbdf5ef7150682150f4ce2c6f4807b349827dcdbdd1f2efa885a2630
I don't think keys per second drops using BSGS, not the one I put out that Jean Luc built.
It's actually faster because with multiple pubkeys you do not have to rewalk the baby steps every time.  If you are using another version of BSGS, then I'm not sure about it. But the one I use, it's the same speed, but overall faster because it doesn't have to perform and store the baby walks every time.

With Kangaroo, it probably is faster searching 1 pubkey.  Let's say you shifted down 2^10; now you'd have to search 1024 pubkeys in the 2^110 range.
Avg operations of 1 pubkey at 2^120 = 2^60 (roughly) but 1024 at 2^110 = 1024 * 2^55 = 2^65 operations
jr. member
Activity: 76
Merit: 4
June 18, 2021, 04:59:49 PM
For example If I am running with 1 loaded public key BSGS and for argument sake with 1 key loaded I am operating at 100 million keys per second but if I substract and load  1000 of the same key just offset by a different distance from the target key my keys per second drops 100 million/1000 (more actually) but now I have 1000 more possible chances of a collision because i have added 1000 targets.

Example
03b6c66d90910721ac8e6f8ef0ebb222fff638227122b21c5853e787ca3d119f08 # - 651321717934608777722865459537368854
030e7b9ccf0feabe79d8745a89b575b52ff21333368b4a9c95c72dbef88a6105e2 # + 651321717934608777722865459537368854
029a564b60e6bed3449052228a609334b43d59bc5f79ca5c622334658ce89b6026 # - 657967857913533357087384494838770577
03a127833050783f814ee013e796fbc937067a86741564bdb9086a6e6e6398e11d # + 657967857913533357087384494838770577
03d0203676b61edda6208b2f9b204de5e8ee2849723458dc7531b1eaba503de390 # - 664613997892457936451903530140172300
0247dd5a10ae3aab4187c7af2a5babcc8ee401ed09e67fbc6ea75e35cc8471d8c9 # + 664613997892457936451903530140172300
02ceb6cbbcdbdf5ef7150682150f4ce2c6f4807b349827dcdbdd1f2efa885a2630 # target


If one of these keys hits then i just add or subtract the decimal value on the right from the hex private key found  convert to decimal add or subtract than convert back to hex  and now I have the  key for 120 02ceb6cbbcdbdf5ef7150682150f4ce2c6f4807b349827dcdbdd1f2efa885a2630
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 18, 2021, 04:26:44 PM
Is it better to go with the 1 public key and get the higher keys per second or go with keysubtracter of 100 or 1000 public keys and get proportionally lower keys per second?
Please explain...
full member
Activity: 706
Merit: 111
June 18, 2021, 04:07:54 PM
Thanks for the answer. i always wondered because if there was just one point then  why could I merge two files and solve the key with kangaroo unless there were at least two points to merge to give the answer. That would be the wild and tame?
Each wild point found has a tame match, somewhere in the range.
Example, let's say private key is (keep it integer for ease of illustration) 1060

You could solve the key in many different ways, just depends on which tame and wild match first,

Tame 2000 and wild 940 would solve the key.

Tame 1100 and wild 40 would solve the key.

To solve when you merge files, one of the Tame points must match one of the Wild points.  Then (for this program) T-W + beginning range = private key.

Quote
last night I test run kangaroo python script version all night with puzzle #120 it is not work good
Did you really think you would solve it overnight running a slower python script??

For each tame, there is a wild to solve the key. If you would stop mixing hex with decimal I would try to explain it better but I'm not going to convert them back and forth. I'm still not 100% sure what you do not understand or what you are trying to figure out. But I will tell you, you may get lucky and solve the key using python script only using a CPU but the odds are low; on average it would take thousands of years to solve.

Do you know how many pairs of tames + wilds can solve a key in a given range or is it just 1 pair that can solve a key?
I'm not 100% sure but if you use DP = 0 (meaning every point would be saved) then I would say every tame has a wild that would solve the key.  If one used a different DP, then it would depend on how many of those DPs exist in the range. Example, if one used DP 32, in a 2^64 range, for every tame DP of 32, then there would probably be a wild DP of 32 to solve the key.

That's what I was trying to ask a while ago about how many ways to solve a key.
jr. member
Activity: 76
Merit: 4
June 18, 2021, 03:34:45 PM
Is it better to go with the 1 public key and get the higher keys per second or go with keysubtracter of 100 or 1000 public keys and get proportionally lower keys per second?
jr. member
Activity: 76
Merit: 4
June 18, 2021, 03:19:01 PM
Understood, I know that Kangaroo has a merge function and that is what made me wonder if there were more than 1 point to put together to get the answer. the problem is that 120 has such a large range using a GPU for it is like finding a specific speck of sand in the Sahara. Even with 100 GPU's it will all come down to really good luck.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
June 18, 2021, 02:59:10 PM
Thanks for the answer. i always wondered because if there was just one point then  why could I merge two files and solve the key with kangaroo unless there were at least two points to merge to give the answer. That would be the wild and tame?
Each wild point found has a tame match, somewhere in the range.
Example, let's say private key is (keep it integer for ease of illustration) 1060

You could solve the key in many different ways, just depends on which tame and wild match first,

Tame 2000 and wild 940 would solve the key.

Tame 1100 and wild 40 would solve the key.

To solve when you merge files, one of the Tame points must match one of the Wild points.  Then (for this program) T-W + beginning range = private key.
member
Activity: 110
Merit: 61
June 18, 2021, 11:42:58 AM
Thanks for the answer. i always wondered because if there was just one point then  why could I merge two files and solve the key with kangaroo unless there were at least two points to merge to give the answer. That would be the wild and tame?

If K is unknown private key, W - known wild distance, T - known tame distance, then in case of collision (when wild and tame kangaroos meets in same distinguished point), you have the following equation: K+W = T whose solution is trivial.
jr. member
Activity: 76
Merit: 4
June 18, 2021, 11:25:46 AM
Thanks for the answer. i always wondered because if there was just one point then  why could I merge two files and solve the key with kangaroo unless there were at least two points to merge to give the answer. That would be the wild and tame?
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
June 18, 2021, 11:12:36 AM
So is the hex private key located at one specific point in the range which equals the hex private key address or is the key spread out and is the addition of different points in the range. If the latter it would not make sense to search in portions of the entire range like dividing the search into 0 through F individually

It's located at one specific point.

Kangaroo does not split up the search range - that would be a waste of time as you said - instead the algorithm bounces between different points in the range, using a random walk, at each iteration, until two points collide.

Kangaroo bounces two sets of about a thousand points each (this kind of cluster of points is called a herd - and 1000 is a hard-coded constant) at a time per iteration, for CPU and also GPU, to make the search parallel, and a match happens when two points from different sets collide.
Pages:
Jump to: