Pollard's kangaroo ECDLP solver

[WanderingPhilospher]

So I still believe it could solve 130 and then you would have to do some manual math (nothing hard) to get the actual private key. If the key starts with a 2, I think it would not require the manual math, but if it starts with a 3, then it will.

You can't because GPU uses only 128 bit variable to store distance on each kernel call, it means that when kangaroo jumps out of 128 bit space, all subsequent jumps are calculated incorrectly.

130 puzzle still can be solved with unmodified JLP's kangaroo if you divide 129 bit space into two 128 bits parts, but kangaroos still can jumps out, so you have to control the wrong DPs.

Are you sure? When I tested many moons ago, if I ran a higher range than 128 (b/c hash table only stores 32 hex characters for point and distance (32x4 = 128)), the distances and points were correct, but obviously the leading characters were left out/off because of the 128 bit max storage.

I may have to run again and retest, and extract the hash table....I will check it now.

Update:

It is as how I remembered it. I just ran a super quick test for the 130 bit range. As you know, the program subtracts starting range so we are working with 0 thru 1ffffff.....(129 bit range)
Here is extracted DP, DP of 20:

178559a1004e94449e90d76ca10b3600 26311140a6e43a1530526461aed458e4

On the surface, if you just plugged in 26311140a6e43a1530526461aed458e4, it seems false, but we know that the only other possible number that could be added in front is a 1, so add a 1 to 26311140a6e43a1530526461aed458e4 and you get 126311140a6e43a1530526461aed458e4, now cross reference that distance and you get this point:
0300000B71D19F5FCD4AC6184EDE7C000C178559A1004E94449E90D76CA10B3600
which matches up to:
178559a1004e94449e90d76ca10b3600
178559A1004E94449E90D76CA10B3600

So that is what I mean by doing some manual work if you use JLPs unmodded version and find a collision in the 130 bit range. But if you go up to 135, it gets a little more tricky/complicated.

But you could be correct! Maybe I didn't let the program run long enough to see how any subsequent keys would be handled.

Honestly, I wouldn't use the unmodded version, nor the 256 bit one on github (doesn't work).

To be safe, use Etayson's Kangaroo on github or mod your own version. That's the safer bet.

[1714485910]

1714485910

[1714485910]

1714485910

[1714485910]

1714485910

[Woz2000]

Can you make public your modded version of JLP's kangaroo?

So I still believe it could solve 130 and then you would have to do some manual math (nothing hard) to get the actual private key. If the key starts with a 2, I think it would not require the manual math, but if it starts with a 3, then it will.

You can't because GPU uses only 128 bit variable to store distance on each kernel call, it means that when kangaroo jumps out of 128 bit space, all subsequent jumps are calculated incorrectly.

130 puzzle still can be solved with unmodified JLP's kangaroo if you divide 129 bit space into two 128 bits parts, but kangaroos still can jumps out, so you have to control the wrong DPs.

Are you sure? When I tested many moons ago, if I ran a higher range than 128 (b/c hash table only stores 32 hex characters for point and distance (32x4 = 128)), the distances and points were correct, but obviously the leading characters were left out/off because of the 128 bit max storage.

I may have to run again and retest, and extract the hash table....I will check it now.

Update:

It is as how I remembered it. I just ran a super quick test for the 130 bit range. As you know, the program subtracts starting range so we are working with 0 thru 1ffffff.....(129 bit range)
Here is extracted DP, DP of 20:

178559a1004e94449e90d76ca10b3600 26311140a6e43a1530526461aed458e4

On the surface, if you just plugged in 26311140a6e43a1530526461aed458e4, it seems false, but we know that the only other possible number that could be added in front is a 1, so add a 1 to 26311140a6e43a1530526461aed458e4 and you get 126311140a6e43a1530526461aed458e4, now cross reference that distance and you get this point:
0300000B71D19F5FCD4AC6184EDE7C000C178559A1004E94449E90D76CA10B3600
which matches up to:
178559a1004e94449e90d76ca10b3600
178559A1004E94449E90D76CA10B3600

So that is what I mean by doing some manual work if you use JLPs unmodded version and find a collision in the 130 bit range. But if you go up to 135, it gets a little more tricky/complicated.

But you could be correct! Maybe I didn't let the program run long enough to see how any subsequent keys would be handled.

Honestly, I wouldn't use the unmodded version, nor the 256 bit one on github (doesn't work).

To be safe, use Etayson's Kangaroo on github or mod your own version. That's the safer bet.

i don't know how to mod so this is not option for me

i can break into 2 parts and run on different rigs - thats what i thought at beginning, but how do i control the wrong DPs?

So I still believe it could solve 130 and then you would have to do some manual math (nothing hard) to get the actual private key. If the key starts with a 2, I think it would not require the manual math, but if it starts with a 3, then it will.

You can't because GPU uses only 128 bit variable to store distance on each kernel call, it means that when kangaroo jumps out of 128 bit space, all subsequent jumps are calculated incorrectly.

130 puzzle still can be solved with unmodified JLP's kangaroo if you divide 129 bit space into two 128 bits parts, but kangaroos still can jumps out, so you have to control the wrong DPs.

yes please make open source, just like original was open source to benefit you, please help us

Can you make public your modded version of JLP's kangaroo?

So I still believe it could solve 130 and then you would have to do some manual math (nothing hard) to get the actual private key. If the key starts with a 2, I think it would not require the manual math, but if it starts with a 3, then it will.

You can't because GPU uses only 128 bit variable to store distance on each kernel call, it means that when kangaroo jumps out of 128 bit space, all subsequent jumps are calculated incorrectly.

130 puzzle still can be solved with unmodified JLP's kangaroo if you divide 129 bit space into two 128 bits parts, but kangaroos still can jumps out, so you have to control the wrong DPs.

Are you sure? When I tested many moons ago, if I ran a higher range than 128 (b/c hash table only stores 32 hex characters for point and distance (32x4 = 128)), the distances and points were correct, but obviously the leading characters were left out/off because of the 128 bit max storage.

I may have to run again and retest, and extract the hash table....I will check it now.

Update:

It is as how I remembered it. I just ran a super quick test for the 130 bit range. As you know, the program subtracts starting range so we are working with 0 thru 1ffffff.....(129 bit range)
Here is extracted DP, DP of 20:

178559a1004e94449e90d76ca10b3600 26311140a6e43a1530526461aed458e4

On the surface, if you just plugged in 26311140a6e43a1530526461aed458e4, it seems false, but we know that the only other possible number that could be added in front is a 1, so add a 1 to 26311140a6e43a1530526461aed458e4 and you get 126311140a6e43a1530526461aed458e4, now cross reference that distance and you get this point:
0300000B71D19F5FCD4AC6184EDE7C000C178559A1004E94449E90D76CA10B3600
which matches up to:
178559a1004e94449e90d76ca10b3600
178559A1004E94449E90D76CA10B3600

So that is what I mean by doing some manual work if you use JLPs unmodded version and find a collision in the 130 bit range. But if you go up to 135, it gets a little more tricky/complicated.

But you could be correct! Maybe I didn't let the program run long enough to see how any subsequent keys would be handled.

Honestly, I wouldn't use the unmodded version, nor the 256 bit one on github (doesn't work).

To be safe, use Etayson's Kangaroo on github or mod your own version. That's the safer bet.

[WanderingPhilospher]

yes please make open source, just like original was open source to benefit you, please help us

Can you make public your modded version of JLP's kangaroo?

So I still believe it could solve 130 and then you would have to do some manual math (nothing hard) to get the actual private key. If the key starts with a 2, I think it would not require the manual math, but if it starts with a 3, then it will.

You can't because GPU uses only 128 bit variable to store distance on each kernel call, it means that when kangaroo jumps out of 128 bit space, all subsequent jumps are calculated incorrectly.

130 puzzle still can be solved with unmodified JLP's kangaroo if you divide 129 bit space into two 128 bits parts, but kangaroos still can jumps out, so you have to control the wrong DPs.

Are you sure? When I tested many moons ago, if I ran a higher range than 128 (b/c hash table only stores 32 hex characters for point and distance (32x4 = 128)), the distances and points were correct, but obviously the leading characters were left out/off because of the 128 bit max storage.

I may have to run again and retest, and extract the hash table....I will check it now.

Update:

It is as how I remembered it. I just ran a super quick test for the 130 bit range. As you know, the program subtracts starting range so we are working with 0 thru 1ffffff.....(129 bit range)
Here is extracted DP, DP of 20:

178559a1004e94449e90d76ca10b3600 26311140a6e43a1530526461aed458e4

On the surface, if you just plugged in 26311140a6e43a1530526461aed458e4, it seems false, but we know that the only other possible number that could be added in front is a 1, so add a 1 to 26311140a6e43a1530526461aed458e4 and you get 126311140a6e43a1530526461aed458e4, now cross reference that distance and you get this point:
0300000B71D19F5FCD4AC6184EDE7C000C178559A1004E94449E90D76CA10B3600
which matches up to:
178559a1004e94449e90d76ca10b3600
178559A1004E94449E90D76CA10B3600

So that is what I mean by doing some manual work if you use JLPs unmodded version and find a collision in the 130 bit range. But if you go up to 135, it gets a little more tricky/complicated.

But you could be correct! Maybe I didn't let the program run long enough to see how any subsequent keys would be handled.

Honestly, I wouldn't use the unmodded version, nor the 256 bit one on github (doesn't work).

To be safe, use Etayson's Kangaroo on github or mod your own version. That's the safer bet.

I do not have a modded version of JLPs.

Peeps, listen up lol, use Etayson EtarKangaroo on github. Then you don't have to worry about all the tomfoolery.

[citb0in]

i've been reading this thread since last week till now and I don't find the answer

so if the program is limited to 125bit interval, ...

This is a false statement which is not true. Kangaroo is not limited to 125bit ranges. It works fine with all ranges intended for this little game-

[WanderingPhilospher]

i've been reading this thread since last week till now and I don't find the answer

so if the program is limited to 125bit interval, ...

This is a false statement which is not true. Kangaroo is not limited to 125bit ranges. It works fine with all ranges intended for this little game-

What say you now?

The JLP, unmodded, kangaroo program, will not work for all the remaining ranges.

Now you’ll have everyone using it and wind up disappointed 😔

[citb0in]

What say you now?

The JLP, unmodded, kangaroo program, will not work for all the remaining ranges.

Now you’ll have everyone using it and wind up disappointed 😔

Code:

#ifdef USE_SYMMETRY
  int jumpBit = rangePower / 2;
#else
  int jumpBit = rangePower / 2 + 1;
#endif

  if(jumpBit > 128) jumpBit = 128;
  int maxRetry = 100;
  bool ok = false;
  double distAvg;
  double maxAvg = pow(2.0,(double)jumpBit - 0.95);
  double minAvg = pow(2.0,(double)jumpBit - 1.05);
  //::printf("Jump Avg distance min: 2^%.2f\n",log2(minAvg));
  //::printf("Jump Avg distance max: 2^%.2f\n",log2(maxAvg));
 
  // Kangaroo jumps
  // Constant seed for compatibilty of workfiles
  rseed(0x600DCAFE);

you have max setup : 128 bit as jumpBit if more  if(jumpBit > 128) jumpBit = 128;

As JLP says:

This program is limited to a 125bit interval search.

interval search not means the range of privatekey but diff beetween start and end of privatekey.


Start range
End range
Key #1
Key #2

max different end_range-start_range < 2**128

have fun!

[WanderingPhilospher]

What say you now?

The JLP, unmodded, kangaroo program, will not work for all the remaining ranges.

Now you’ll have everyone using it and wind up disappointed 😔

Code:

#ifdef USE_SYMMETRY
  int jumpBit = rangePower / 2;
#else
  int jumpBit = rangePower / 2 + 1;
#endif

  if(jumpBit > 128) jumpBit = 128;
  int maxRetry = 100;
  bool ok = false;
  double distAvg;
  double maxAvg = pow(2.0,(double)jumpBit - 0.95);
  double minAvg = pow(2.0,(double)jumpBit - 1.05);
  //::printf("Jump Avg distance min: 2^%.2f\n",log2(minAvg));
  //::printf("Jump Avg distance max: 2^%.2f\n",log2(maxAvg));
 
  // Kangaroo jumps
  // Constant seed for compatibilty of workfiles
  rseed(0x600DCAFE);

you have max setup : 128 bit as jumpBit if more  if(jumpBit > 128) jumpBit = 128;

As JLP says:

This program is limited to a 125bit interval search.

interval search not means the range of privatekey but diff beetween start and end of privatekey.


Start range
End range
Key #1
Key #2

max different end_range-start_range < 2**128

have fun!

Ahhhh, now go and look at how the hash table is built/what goes into it. I’ll give you a hint, as I’ve said all along, 128 bits max, for points and distances.

So no people, don’t use it unless you want headaches and possible heartbreaks 😁

Code:

ENTRY *HashTable::CreateEntry(int128_t *x,int128_t *d) {

Now on JLPs Kangaroo GitHub repository:

Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

[qq569160818]

I probably miss something here, but please explain why do you guys use Kangaroo while there is another tool Keyhunt, which BSGS option is very very fast. With above average hardware, you can get around 10 exa keys per second. That is 10,000,000,000,000,000,000 keys per second.  I have never seen such numbers with Kangaroo.

I have been testing keyhunt and the conclusion is that its speed is very fast within a small range. For example, with a 45 bit interval, 8GB of memory is much faster than 1060 speed. However, once it reaches a high level, the efficiency of keyhunt is relatively low. Currently, I am testing with 128GB of memory, and the speed has reached 2Ekey/s. However, it is obvious that these speeds are negligible in such a huge space, so I prefer kangaroo high search. I am still testing more kangaroo conclusions. Thank you and greetings

[Baskentliia]

I probably miss something here, but please explain why do you guys use Kangaroo while there is another tool Keyhunt, which BSGS option is very very fast. With above average hardware, you can get around 10 exa keys per second. That is 10,000,000,000,000,000,000 keys per second.  I have never seen such numbers with Kangaroo.

I have been testing keyhunt and the conclusion is that its speed is very fast within a small range. For example, with a 45 bit interval, 8GB of memory is much faster than 1060 speed. However, once it reaches a high level, the efficiency of keyhunt is relatively low. Currently, I am testing with 128GB of memory, and the speed has reached 2Ekey/s. However, it is obvious that these speeds are negligible in such a huge space, so I prefer kangaroo high search. I am still testing more kangaroo conclusions. Thank you and greetings

Well, sir, if our luck is high, is there a possibility that we can find it with a bad graphics card by using the Kangaroo program?


Is JLP's Kangaroo program used for puzzle 130, which is original and published on github? Yes or no ?

Some said you can use it because the range width is 125 bits. Some have said that the original version of JLP has 130 puzzles and you cannot use it for more comprehensive puzzles.

Which one is right ?


What I'm talking about is the 130 bit range width, that is, if there is more than a 125 bit gap between the start and end, does the program work?

Mod note: consecutive posts merged

[3dmlib]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

[Baskentliia]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

[WanderingPhilospher]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

It has been answered multiple times, please read.

Again, on JLPs github (the person who built this program)

#130
Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

[qq569160818]

I probably miss something here, but please explain why do you guys use Kangaroo while there is another tool Keyhunt, which BSGS option is very very fast. With above average hardware, you can get around 10 exa keys per second. That is 10,000,000,000,000,000,000 keys per second.  I have never seen such numbers with Kangaroo.

I have been testing keyhunt and the conclusion is that its speed is very fast within a small range. For example, with a 45 bit interval, 8GB of memory is much faster than 1060 speed. However, once it reaches a high level, the efficiency of keyhunt is relatively low. Currently, I am testing with 128GB of memory, and the speed has reached 2Ekey/s. However, it is obvious that these speeds are negligible in such a huge space, so I prefer kangaroo high search. I am still testing more kangaroo conclusions. Thank you and greetings

Well, sir, if our luck is high, is there a possibility that we can find it with a bad graphics card by using the Kangaroo program?

It is obvious that Kangaroo and Keyhunt each have their own strengths. As far as I know, the Kangaroo program GPU cannot be used for multiple public keys and has a limit of 125 bit intervals. Therefore, Kangaroo is currently only used as a puzzle solver. Keyhunt does not use GPU, but it can be tested in the full range space and under multiple public keys simultaneously, although its efficiency is not high when running at high bits. If kangaroos can support full range and multiple public keys, then undoubtedly it will be the most suitable. Also, I come from China and the translator may not be accurate. I apologize!

[3dmlib]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

It has been answered multiple times, please read.

Again, on JLPs github (the person who built this program)

#130
Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

Sorry, but I can't find 100% official answer that it will work on 128-bit range.
125-bit will work, 129-bit (#130 puzzle) no, as stated in readme.
Some speculation that it can work with 126, 127 and 128-bit ranges.
But I need 100% to know so. I think developer of this program should know this 100%.
Thanks.

[WanderingPhilospher]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

It has been answered multiple times, please read.

Again, on JLPs github (the person who built this program)

#130
Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

Sorry, but I can't find 100% official answer that it will work on 128-bit range.
125-bit will work, 129-bit (#130 puzzle) no, as stated in readme.
Some speculation that it can work with 126, 127 and 128-bit ranges.
But I need 100% to know so. I think developer of this program should know this 100%.
Thanks.

It will work with 128 and below, 100%

[Baskentliia]

It will be nice to know from this program developer if kangaroo can work with 128-bit range?
Or it absolute maximum 125-bit as stated in the readme?
So, splitting in half #130 puzzle will help? It will be exactly two 128-bit ranges then.
Thanks.

I'm waiting for the answer to this question, but no one can say anything definitive. It is necessary to find the person who made this program.
Does this program work with more than 125 BIT RANGE?

It has been answered multiple times, please read.

Again, on JLPs github (the person who built this program)

#130
Expected time: several years on 256 Tesla V100 (Not possible with this program without modification)

Sorry, but I can't find 100% official answer that it will work on 128-bit range.
125-bit will work, 129-bit (#130 puzzle) no, as stated in readme.
Some speculation that it can work with 126, 127 and 128-bit ranges.
But I need 100% to know so. I think developer of this program should know this 100%.
Thanks.

It will work with 128 and below, 100%

Can it work with 128 bit? Then can we divide the puzzle into 2 and run it?
Can we divide it into two parts as 20-2F and 30-3F and run it?
The owner of the program says that it can work with a range width of 125 bits.
You say that it will work at 128 bits and below. Do you have any proof of what?

[3dmlib]

Can it work with 128 bit? Then can we divide the puzzle into 2 and run it?
Can we divide it into two parts as 20-2F and 30-3F and run it?
The owner of the program says that it can work with a range width of 125 bits.
You say that it will work at 128 bits and below. Do you have any proof of what?

After quick look at kangaroo code, looks like there is 3-bits of 128-bit value used for something. So, it actually really 125-bit max. I can be wrong and I think only JLP can answer 100%.

[WanderingPhilospher]

lol…yall are killing me.

Stop asking for proof and/or videos.

Run some tests, extract the stored points and distances, and see for yourself.

If you do not want to do that, then use the version of Kangaroo that I have mentioned several times.

If you don’t want to do that; then mod the original or pay someone to mod the original.

[Jean_Luc]

After quick look at kangaroo code, looks like there is 3-bits of 128-bit value used for something. So, it actually really 125-bit max. I can be wrong and I think only JLP can answer 100%.
[/quote]

Hello,
Yes you are right. The GPU code should also be modified to return good distances.
Do not try to solve this puzzle, it will take years using a rendering farm !

[kTimesG]

Hello,
Yes you are right. The GPU code should also be modified to return good distances.
Do not try to solve this puzzle, it will take years using a rendering farm !

Hello OP,
I'm expressing my gratitude for stepping in to clear out this matter. Obviously, it should be a good lesson for absolutely anyone to always take with a big grain of salt what some users are trying to convince people of their "guaranteed" truth.

For everybody else - make your own judgments always in everything. Most of the claims done in these forums are complete bogus, with no actual underlying rationale to cover it up. Start by grabbing a statistics fast course, don't expect to miraculously reduce space-time algorithmic complexities, unless you change the fundamental hypothesis some way. Otherwise the Universe will just slap you in the face, since it's rules don't work according to our (very bad) intuition and perception.