Pollard's kangaroo ECDLP solver

[Mangal99]

Is it possible to add the "--stride" parameter to the program like in bitcrack?
This is needed to calculate the private key if public key and part of the private key is known, for example:  5JgvpXDfzXbqqtFmLJy???7aR9n6WoTWvPSb1oUEm4
When can we calculate the start point, end point and step.

[PawGo]

Is it possible to add the "--stride" parameter to the program like in bitcrack?
This is needed to calculate the private key if public key and part of the private key is known, for example:  5JgvpXDfzXbqqtFmLJy???7aR9n6WoTWvPSb1oUEm4
When can we calculate the start point, end point and step.

I worked on that.
https://github.com/PawelGorny/Kangaroo
The solution is not perfect, but for me it was enough.
As a entry parameters it expects to have:
- the real beginning of the range
- the fake end of the range. If you know the real end and stride, divide the difference by stride and result add to the real beginning.
- the real public key

and then launching program use parameter -stride to specify the stride.
In the sources there is an example with the configuration file test_240921C8BE82FD68A2A77FBA0089F71029354609C9.txt

Code:

ef235aacf9050dd4d345af03378ba06d2108b927f084b2ab133c9b7d1187e6be
ef235aacf9050dd4d345af03378ba06d2108b927f084b2ab133d050abbcaa8a6
02b4632d08485ff1df2db55b9dafd23347d1c47a457072a1e87be26896549a8737

If you launch program using:

Code:

./kangaroo -stride 240921C8BE82FD68A2A77FBA0089F71029354609C9 test_240921C8BE82FD68A2A77FBA0089F71029354609C9.txt

you will receive result:

Code:

Key# 0 [2N]Pub:  0x02B4632D08485FF1DF2DB55B9DAFD23347D1C47A457072A1E87BE26896549A8737
       Priv: 0xEF235AACF9050DD4D345AF03378BA06D2108B927F084B2AB133CD85B91858012
   RealPriv: 0xEF235AACF90D9F4AADD8C92E4B2562E1D9EB97F0DF9BA3B508258739CB013DB2

Where Priv is a fake priv from the fake range, and EF235AACF90D9F4AADD8C92E4B2562E1D9EB97F0DF9BA3B508258739CB013DB2 is the real result.

I used that modified version of Kangaroo as a one more implementation of the method I described here: https://bitcointalk.org/index.php?topic=5265788

[WanderingPhilospher]

Question to the smart people:

If one is using the kangaroo method, searching for 32 bit distinguished points, and searching in the 120 bit range, how many x coordinates (x coordinate is what the program finds of a given public key, which in kangaroo terminology means "distance traveled") would have a 32 bit distinguished point?

There are 2^120 possibilities, but we know not every private key in the 120 bit range has a public key x coordinate that has a DP of 32. Is there a good guesstimate or is it just anyone's guess?

I should clarify, how many tame points in a 120 bit range would/could have distinguished points of 32 bits?

[bigvito19]

Question to the smart people:

If one is using the kangaroo method, searching for 32 bit distinguished points, and searching in the 120 bit range, how many x coordinates (x coordinate is what the program finds of a given public key, which in kangaroo terminology means "distance traveled") would have a 32 bit distinguished point?

There are 2^120 possibilities, but we know not every private key in the 120 bit range has a public key x coordinate that has a DP of 32. Is there a good guesstimate or is it just anyone's guess?

I should clarify, how many tame points in a 120 bit range would/could have distinguished points of 32 bits?

If you're in the 120 bit range it should be 120/2 = 60 - 32 = 28. Finally answer is 2^28 = 268,435,456 tame distinguished points of 32 bits, that's my guess.

[WanderingPhilospher]

Question to the smart people:

If one is using the kangaroo method, searching for 32 bit distinguished points, and searching in the 120 bit range, how many x coordinates (x coordinate is what the program finds of a given public key, which in kangaroo terminology means "distance traveled") would have a 32 bit distinguished point?

There are 2^120 possibilities, but we know not every private key in the 120 bit range has a public key x coordinate that has a DP of 32. Is there a good guesstimate or is it just anyone's guess?

I should clarify, how many tame points in a 120 bit range would/could have distinguished points of 32 bits?

If you're in the 120 bit range it should be 120/2 = 60 - 32 = 28. Finally answer is 2^28 = 268,435,456 tame distinguished points of 32 bits, that's my guess.

Probably a good as a guess as any. One also has to remember there are leading DPs example: 00001234 and trailing DPs, example: 12340000. There are also in between DPs, example: 12000034. I've seen all three used in different Kangaroo programs. Not sure which is best/faster to search for. If they are of the in between type, they have to line up. Example, 12000034 won't work with 10000234. All interesting.
I went through a small range 1-300FFF and didn't find any 32 DPs. I was closely looking at trailing, but I don't think there were any leading or in between either.

Anywho, if we use your 2^28, that would mean 2^28 for each type of DP, leading, trailing, and in between. So that would mean 2^29.5 (minimum, because the in between ones can be in between anywhere.)

[bigvito19]

Question to the smart people:

If one is using the kangaroo method, searching for 32 bit distinguished points, and searching in the 120 bit range, how many x coordinates (x coordinate is what the program finds of a given public key, which in kangaroo terminology means "distance traveled") would have a 32 bit distinguished point?

There are 2^120 possibilities, but we know not every private key in the 120 bit range has a public key x coordinate that has a DP of 32. Is there a good guesstimate or is it just anyone's guess?

I should clarify, how many tame points in a 120 bit range would/could have distinguished points of 32 bits?

If you're in the 120 bit range it should be 120/2 = 60 - 32 = 28. Finally answer is 2^28 = 268,435,456 tame distinguished points of 32 bits, that's my guess.

Probably a good as a guess as any. One also has to remember there are leading DPs example: 00001234 and trailing DPs, example: 12340000. There are also in between DPs, example: 12000034. I've seen all three used in different Kangaroo programs. Not sure which is best/faster to search for. If they are of the in between type, they have to line up. Example, 12000034 won't work with 10000234. All interesting.
I went through a small range 1-300FFF and didn't find any 32 DPs. I was closely looking at trailing, but I don't think there were any leading or in between either.

Anywho, if we use your 2^28, that would mean 2^28 for each type of DP, leading, trailing, and in between. So that would mean 2^29.5 (minimum, because the in between ones can be in between anywhere.)

You said you went through a small range 1-300FFF, that's 2^24 range with distinguished points of 32 bits. 32 bits is to big for that small space. That space 2^24 would require distinguished points of 6 bits.

[WanderingPhilospher]

Question to the smart people:

If one is using the kangaroo method, searching for 32 bit distinguished points, and searching in the 120 bit range, how many x coordinates (x coordinate is what the program finds of a given public key, which in kangaroo terminology means "distance traveled") would have a 32 bit distinguished point?

There are 2^120 possibilities, but we know not every private key in the 120 bit range has a public key x coordinate that has a DP of 32. Is there a good guesstimate or is it just anyone's guess?

I should clarify, how many tame points in a 120 bit range would/could have distinguished points of 32 bits?

If you're in the 120 bit range it should be 120/2 = 60 - 32 = 28. Finally answer is 2^28 = 268,435,456 tame distinguished points of 32 bits, that's my guess.

Probably a good as a guess as any. One also has to remember there are leading DPs example: 00001234 and trailing DPs, example: 12340000. There are also in between DPs, example: 12000034. I've seen all three used in different Kangaroo programs. Not sure which is best/faster to search for. If they are of the in between type, they have to line up. Example, 12000034 won't work with 10000234. All interesting.
I went through a small range 1-300FFF and didn't find any 32 DPs. I was closely looking at trailing, but I don't think there were any leading or in between either.

Anywho, if we use your 2^28, that would mean 2^28 for each type of DP, leading, trailing, and in between. So that would mean 2^29.5 (minimum, because the in between ones can be in between anywhere.)

You said you went through a small range 1-300FFF, that's 2^24 range with distinguished points of 32 bits. 32 bits is to big for that small space. That space 2^24 would require distinguished points of 6 bits.

No, that is not accurate. A distinguished point could be anywhere. It's merely how many "zeros" are in a row (consecutive) in a given public key x coord.  It shouldn't matter how large the range or private key is. It will just take a lot longer to find a 32 bit DP, in any range. I found several 24 bit DP in that 2^24 range, just no 32 bit DPs.  I'm not looking at this to find a key, I am just curious how many trailing or leading 32 bit DPs could be in a range, in particular, the 2^120 range. I thought there might have been a good calculator for it but maybe it is all just mathematical luck, where DPs fall.

[NotATether]

No, that is not accurate. A distinguished point could be anywhere. It's merely how many "zeros" are in a row (consecutive) in a given public key x coord.  It shouldn't matter how large the range or private key is. It will just take a lot longer to find a 32 bit DP, in any range. I found several 24 bit DP in that 2^24 range, just no 32 bit DPs.  I'm not looking at this to find a key, I am just curious how many trailing or leading 32 bit DPs could be in a range, in particular, the 2^120 range. I thought there might have been a good calculator for it but maybe it is all just mathematical luck, where DPs fall.

"Computing discrete logarithms with the parallelized kangaroo method" by Teske (page 7, link) states that you can find the number of DPs in a range can be calculated with (2**C)/sqrt[b-a]. C is the number of bits you are using for your DP, and for your problem you can use the full 120-bit range for a and b. So this means 2**32 / 2**(120-1=119) = 2**(32-119) = 2**-87 th of the space are DPs.

To put this in perspective, there are about 27 zeros after the decimal point before the first significant figure.

[alipostaci2002@gmail.com]

 is there any kangaroo version for ethereum?

[WanderingPhilospher]

No, that is not accurate. A distinguished point could be anywhere. It's merely how many "zeros" are in a row (consecutive) in a given public key x coord.  It shouldn't matter how large the range or private key is. It will just take a lot longer to find a 32 bit DP, in any range. I found several 24 bit DP in that 2^24 range, just no 32 bit DPs.  I'm not looking at this to find a key, I am just curious how many trailing or leading 32 bit DPs could be in a range, in particular, the 2^120 range. I thought there might have been a good calculator for it but maybe it is all just mathematical luck, where DPs fall.

"Computing discrete logarithms with the parallelized kangaroo method" by Teske (page 7, link) states that you can find the number of DPs in a range can be calculated with (2**C)/sqrt[b-a]. C is the number of bits you are using for your DP, and for your problem you can use the full 120-bit range for a and b. So this means 2**32 / 2**(120-1=119) = 2**(32-119) = 2**-87 th of the space are DPs.

To put this in perspective, there are about 27 zeros after the decimal point before the first significant figure.

2^-87? negative 87? Well that's definitely not right. Maybe you meant 2^32 / 2^119 ? Even 2^32 / sqrt(2^119) wouldn't be right. But maybe if you take (2^32 / sqrt(2^119)) and multiply that back by the range = 350,142,318,592,413,374,492,074,613. That would come out to be about .0000054 percent of the 2^119 range.

[WanderingPhilospher]

is there any kangaroo version for ethereum?

Not to my knowledge...But there is a Bitcrack version for ethereum. Developer was selling it though.

[NotATether]

2^-87? negative 87? Well that's definitely not right. Maybe you meant 2^32 / 2^119 ? Even 2^32 / sqrt(2^119) wouldn't be right. But maybe if you take (2^32 / sqrt(2^119)) and multiply that back by the range = 350,142,318,592,413,374,492,074,613. That would come out to be about .0000054 percent of the 2^119 range.

It's a ratio of 2^-87 to 1. Where the 1 is proportional to the range 2^120 and the 2^-87 is proportional to the number of DPs in that range. That means there are 2^120-87=33 or 8,589,934,592 DPs in the 120-bit range.

[WanderingPhilospher]

2^-87? negative 87? Well that's definitely not right. Maybe you meant 2^32 / 2^119 ? Even 2^32 / sqrt(2^119) wouldn't be right. But maybe if you take (2^32 / sqrt(2^119)) and multiply that back by the range = 350,142,318,592,413,374,492,074,613. That would come out to be about .0000054 percent of the 2^119 range.

It's a ratio of 2^-87 to 1. Where the 1 is proportional to the range 2^120 and the 2^-87 is proportional to the number of DPs in that range. That means there are 2^120-87=33 or 8,589,934,592 DPs in the 120-bit range.

Ok, I misread your first post.

Now, from the 8,589,934,592 32 bit DPs, I wonder how many are trailing, leading, and in between? If it's an equal spread or one occurs more than the other.

[MrFreeDragon]

is there any kangaroo version for ethereum?

This tool finds the private key for the know public key. ETH uses the same elliptic curve, so this tool will work for ETH as well.

[WanderingPhilospher]

2^-87? negative 87? Well that's definitely not right. Maybe you meant 2^32 / 2^119 ? Even 2^32 / sqrt(2^119) wouldn't be right. But maybe if you take (2^32 / sqrt(2^119)) and multiply that back by the range = 350,142,318,592,413,374,492,074,613. That would come out to be about .0000054 percent of the 2^119 range.

It's a ratio of 2^-87 to 1. Where the 1 is proportional to the range 2^120 and the 2^-87 is proportional to the number of DPs in that range. That means there are 2^120-87=33 or 8,589,934,592 DPs in the 120-bit range.

Been looking at different numbers; so how many 36bit Distinguished Points in a 72 bit range?

Applying what you said earlier, (2^36-72) = 2^-36. Then use 2^72-36 = 36 or 68,719,476,736 36bit DPs in a 72 bit range?

[NotATether]

2^-87? negative 87? Well that's definitely not right. Maybe you meant 2^32 / 2^119 ? Even 2^32 / sqrt(2^119) wouldn't be right. But maybe if you take (2^32 / sqrt(2^119)) and multiply that back by the range = 350,142,318,592,413,374,492,074,613. That would come out to be about .0000054 percent of the 2^119 range.

It's a ratio of 2^-87 to 1. Where the 1 is proportional to the range 2^120 and the 2^-87 is proportional to the number of DPs in that range. That means there are 2^120-87=33 or 8,589,934,592 DPs in the 120-bit range.

Been looking at different numbers; so how many 36bit Distinguished Points in a 72 bit range?

Applying what you said earlier, (2^36-72) = 2^-36. Then use 2^72-36 = 36 or 68,719,476,736 36bit DPs in a 72 bit range?

That sounds about right according to the paper's formula. Except you forgot to subtract 1 from 72 so it would actually be 2^(36-71) or 2^-35 of the space being DPs, or equivalently 137,438,953,472 DPs.

It's getting interesting how as the search space is getting smaller, this is still returning a fairly large number of DPs for large bit counts (relative to the search space). I wonder if this is how it's supposed to work? 137 billion DPs sounds like a lot for a 72-bit search space.

[bigvito19]

So you don't half the search space first then subtract the DP?

[NotATether]

So you don't half the search space first then subtract the DP?

To be honest I don't understand why the search space would have to be halved in the first place. Can you enlighten me how you reached that conclusion?

I'm also having trouble comprehending why the DP size should be subtracted from the power of two, because you can't possibly have more than 2^(DP size) DPs and have them all fit in the DP's bit length. For example for the 32-bit DPs in the 120-bit range example your calculation lead to 2^28 32-bit DPs. This doesn't really make sense to me because Jean_Luc's Kangaroo just makes DPs by putting zeros at the left of the number until there are 32, or whatever the size of the DP, bits left.

[bigvito19]

As you see in the images above the person that solved #110 and #115.

Example with #120 using 32 bit Dp: Operations = 2^(120/2+1) = 2^61.

61 - 32 = 29

32 + 29 = 61 When you merged both work files they both should be 2^29 each, then they should equal to 61 or close to it.

So 32 bit Dps for #120 is 536,870,912

[WanderingPhilospher]

As you see in the images above the person that solved #110 and #115.

Example with #120 using 32 bit Dp: Operations = 2^(120/2+1) = 2^61.

61 - 32 = 29

32 + 29 = 61 When you merged both work files they both should be 2^29 each, then they should equal to 61 or close to it.

So 32 bit Dps for #120 is 536,870,912

That is the expected # you have to find before finding the solution, not how many x bit DPs exist in the range.