Pollard's kangaroo ECDLP solver - page 75.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: crytolog on February 11, 2021, 12:35:30 PM

Quote from: WanderingPhilospher on February 11, 2021, 12:24:56 PM

Quote from: crytolog on February 11, 2021, 12:01:54 PM

i am using gtx 970 gpu and win 10. how can i use kangaroo? can anybody instruct me? i downloded kangaroo.exe but i dont know how to use it. thank you in advance

Simplest way:

Setup your input file; line 1 is start range, line 2 is end range, line 3 is public key you are searching for:
Example input file (we will call it input.txt):

Code:

1
FFFFFFFFFFFFFFFFFF
038DB9A3FC1A4A4721A8F79F5A38DA2379D352CA0666554B0E401C33BD4A3DB123

Now, set up batch file (we will call it KangarooStart.bat):

Code:

Kangaroo -t 3 -d 12 -gpu -gpuId 0 -o results.txt input.txt

This is where you tell the program what you want. Kangaroo is the name of the program (.exe file) -t how many cpu threads you want to use -d the number of distinguished points (in bits) you want to search for - gpu lets it know you want to use a gpu, -gpuId is the device number of the gpu you want to use (if you only have one gpu, you can leave out this option) -o is where you want the results to be stored once program finds the key, and the last entry in batch file is the input file we created above (start and end range and public key).

thank you very much for the information. i have one more question, i want to use it in puzzle 64 how can i find publickey?

You cannot find the public key for #64, it has not been exposed in a transaction therefore the Kangaroo program will not help you find #64. You have to look at the ones with known public keys, #120, #125....(incremented by 5) through #160

crytolog

jr. member

Activity: 102

Merit: 6

Quote from: WanderingPhilospher on February 11, 2021, 12:24:56 PM

Quote from: crytolog on February 11, 2021, 12:01:54 PM

i am using gtx 970 gpu and win 10. how can i use kangaroo? can anybody instruct me? i downloded kangaroo.exe but i dont know how to use it. thank you in advance

Simplest way:

Setup your input file; line 1 is start range, line 2 is end range, line 3 is public key you are searching for:
Example input file (we will call it input.txt):

Code:

1
FFFFFFFFFFFFFFFFFF
038DB9A3FC1A4A4721A8F79F5A38DA2379D352CA0666554B0E401C33BD4A3DB123

Now, set up batch file (we will call it KangarooStart.bat):

Code:

Kangaroo -t 3 -d 12 -gpu -gpuId 0 -o results.txt input.txt

This is where you tell the program what you want. Kangaroo is the name of the program (.exe file) -t how many cpu threads you want to use -d the number of distinguished points (in bits) you want to search for - gpu lets it know you want to use a gpu, -gpuId is the device number of the gpu you want to use (if you only have one gpu, you can leave out this option) -o is where you want the results to be stored once program finds the key, and the last entry in batch file is the input file we created above (start and end range and public key).

thank you very much for the information. i have one more question, i want to use it in puzzle 64 how can i find publickey?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: crytolog on February 11, 2021, 12:01:54 PM

i am using gtx 970 gpu and win 10. how can i use kangaroo? can anybody instruct me? i downloded kangaroo.exe but i dont know how to use it. thank you in advance

Simplest way:

Setup your input file; line 1 is start range, line 2 is end range, line 3 is public key you are searching for:
Example input file (we will call it input.txt):

Code:

1
FFFFFFFFFFFFFFFFFF
038DB9A3FC1A4A4721A8F79F5A38DA2379D352CA0666554B0E401C33BD4A3DB123

Now, set up batch file (we will call it KangarooStart.bat):

Code:

Kangaroo -t 3 -d 12 -gpu -gpuId 0 -o results.txt input.txt

This is where you tell the program what you want. Kangaroo is the name of the program (.exe file) -t how many cpu threads you want to use -d the number of distinguished points (in bits) you want to search for - gpu lets it know you want to use a gpu, -gpuId is the device number of the gpu you want to use (if you only have one gpu, you can leave out this option) -o is where you want the results to be stored once program finds the key, and the last entry in batch file is the input file we created above (start and end range and public key).

crytolog

jr. member

Activity: 102

Merit: 6

i am using gtx 970 gpu and win 10. how can i use kangaroo? can anybody instruct me? i downloded kangaroo.exe but i dont know how to use it. thank you in advance

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: bigvito19 on January 31, 2021, 10:37:21 AM

..

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.

Ah ok, so this is measuring just the number of DPs Kangaroo needs for a 50% collision, not all the possible DPs in a range.

Quote from: bigvito19 on January 31, 2021, 10:53:25 AM

Oh well that depends on what size of the DP you're using then. So does it looks for x and y bit DPs or just x bit DPs?

The algorithm for deriving the y point from the x point uses two modular exponentations so chances are it's probably not going to have the same leading zeros for x if at all, i.e only x DPs are considered.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: WanderingPhilospher on January 31, 2021, 10:41:02 AM

Quote

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.

Oh well that depends on what size of the DP you're using then. So does it looks for x and y bit DPs or just x bit DPs?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote

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.

The program doesn't add or just make DPs or just add zeros, those are actual DPs within the actual pubkey.

If you take this private key:
43de528a515bcced5665c496838b

The actual public key is:
0200000000b1dc84f28a1d971aec280000104f08c1ff34fa980ffe0ab97846c7d4

So as you can see, it has (take away the leading 02) 00000000 leading DPs which equals a 32 bit DP, 8 zeros times 4.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote

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.

bigvito19

full member

Activity: 706

Merit: 111

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

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: bigvito19 on January 31, 2021, 06:50:15 AM

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

full member

Activity: 706

Merit: 111

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

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: WanderingPhilospher on January 31, 2021, 12:30:28 AM

Quote from: NotATether on January 30, 2021, 08:38:47 AM

Quote from: WanderingPhilospher on January 29, 2021, 02:16:16 PM

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.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: NotATether on January 30, 2021, 08:38:47 AM

Quote from: WanderingPhilospher on January 29, 2021, 02:16:16 PM

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?

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: [email protected] on January 29, 2021, 02:07:30 PM

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

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: NotATether on January 30, 2021, 08:38:47 AM

Quote from: WanderingPhilospher on January 29, 2021, 02:16:16 PM

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.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: WanderingPhilospher on January 29, 2021, 02:16:16 PM

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

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: [email protected] on January 29, 2021, 02:07:30 PM

is there any kangaroo version for ethereum?

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

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: NotATether on January 29, 2021, 03:13:35 AM

Quote from: WanderingPhilospher on January 28, 2021, 07:05:33 PM

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.

[email protected]

newbie

Activity: 2

Merit: 0

is there any kangaroo version for ethereum?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: WanderingPhilospher on January 28, 2021, 07:05:33 PM

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.

Topic: Pollard's kangaroo ECDLP solver - page 75. (Read 59389 times)