Pollard's kangaroo ECDLP solver

[COBRAS]

I really like this race
HardwareCollector or Zielar ?

Ford VS Ferrari 

[WanderingPhilospher]

Published a new release with a faster merger.
Thanks to test it

tested with several files over 1GB; works well!

[Etar]

@JeanLuc and other folks who has knowledge in this area..
From what I realized that DP is just the x coordinate with a certain number of leading zeros .. like a brilliant among stones.
Kangaroo algorithm, creates a tribe of tame and a tribe of wild kangaroos.
Tame kangaroos are tied to a range, and wild to the desired public key.
Now the idea itself .. Why can not we use the experience of previous work?
What I mean. For example, we’ll start accumulating experience with a 54-bit key
The range where this private key located is
40000000000000
7fffffffffffff
and seek public key 0385a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963
we can shift the range to 0
and subtract the beginning of the range from the public key
(0x85a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963,0x0eb400323654cec63999b56f4ba44e8b21ab92d9d697fabe4666df3678585669)
-
(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)
=
(b1f8ba606a61026d1ecaa93d9e9ceb12260c33e92809ed1ecb0850a2856accc1,ac46d892583d7fdd24a25a229b6ea8d17add77b1f410a9d30441e0acbec19c74)
and range
0
3fffffffffffff
as result we will have key 0x2ABE1F9B67E114
if we add range we can regenerate real key
0x2ABE1F9B67E114+0x40000000000000=0x6ABE1F9B67E114
So we have a saved working file, where there are DP both tame and wild kangaroos in range 0-3fffffffffffff
DP of wild kangaroos we do not need more  so they are tied to the public key.
We can cut only tame kangaroos points from the work file and save to a new file.
And this tame will be correct for next puzzle because they are in the same range as next pazzle(after shifting ofcourse)
So we can use this file like initial to next pazzle
Next 59bit Puzzle..
range
800000000000000
fffffffffffffff
and seek public key 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
do the same thing, shift the range to 0 and subtract the beginning of the range from the public key
(0x48e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d,0xd094fcabf8995e2a25c73298a9f7419720db622daff89c67fd5535f6ac29720f)
-
(8991225911b9132d28f5c6bc763ceab7d18c37060e8bd1d7ed44db7560788c1e,da8b4d987cc9ac9b27b8763559b136fa36969c84fdef9e11635c42228e8f0ef1)
=
(2b90a8680d08cf81e15e209acadbb16b7bdff19787d6d13ca6a7852fee8d1013,447a29425ea9773471ad9810d21a976cf5bd4bdb46d0c8ae537591dce43252f2)
and range
0
7ffffffffffffff
Don`t forget that we already have some tame DPs on this range(0-3fffffffffffff), so we should find collision faster!
result key is 0x7C07A1825367BBE
add range and real key
0x7C07A1825367BBE+0x800000000000000=0xFC07A1825367BBE
than do the same, cut from work file only tame kangaroos, save and solve next pazzle...
In this case, after each puzzle, we will already have more and more DP points from tame kangaroos.
What you think?

[MrFreeDragon]

-snip-
we can shift the range to 0
and subtract the beginning of the range from the public key
-snip-

This "shift" was already discussed here. And moreover, Jean_Luc made the shift in his program.
So if we input the range [a..b], the program actually shifts it to 0 and making the search within the range [0... (a-b)]
I also read all read all the DPs from binary file and can confirm this: all the tames distances are within the range [0...(a-b)] and all the wilds are within the range [0...(a-b)/2] - for wilds also the sign is used.

But you are right, Etar, that the "tame" DPs from previous keys could be used for subsequent, however their concentration will be very high on the left side of the range. Tames are distributed within the whole range, however if you use these tames for 1bit more key, they are all be only within the first half of the range, if for 2bit more key, all the tames will be on the first 25% of the range, etc...

But yes, the working files could be used for higher bits keys. However you should use the same DP size.

[MrFreeDragon]

I really like this race
HardwareCollector or Zielar ?

There is a high probability that if we combine HardwareCollector's and Zielar's working files there will be the required collision.

There is also a way to check it right now without sharing the whole files - only the information with X-coordinates and kangaroo type should be shared (excluding distances), and if we have the same X-coordinate with different types (wild and tame) so we can confirm that the key is found.

HWCollector and Zielar, do you want me to perform such check for you? 

[WanderingPhilospher]

-snip-
we can shift the range to 0
and subtract the beginning of the range from the public key
-snip-

This "shift" was already discussed here. And moreover, Jean_Luc made the shift in his program.
So if we input the range [a..b], the program actually shifts it to 0 and making the search within the range [0... (a-b)]
I also read all read all the DPs from binary file and can confirm this: all the tames distances are within the range [0...(a-b)] and all the wilds are within the range [0...(a-b)/2] - for wilds also the sign is used.

But you are right, Etar, that the "tame" DPs from previous keys could be used for subsequent, however their concentration will be very high on the left side of the range. Tames are distributed within the whole range, however if you use these tames for 1bit more key, they are all be only within the first half of the range, if for 2bit more key, all the tames will be on the first 25% of the range, etc...

But yes, the working files could be used for higher bits keys. However you should use the same DP size.

So if this is possible, then is it also possible to:

Start out with range: 100000:FFFFFF and run a round of kangaroos through it
and then run kangaroos at different ranges within that range, example : 111111:FFFFFF OR 203AB9:FFFFFF, etc. etc.

[HardwareCollector]

I really like this race
HardwareCollector or Zielar ?

There is a high probability that if we combine HardwareCollector's and Zielar's working files there will be the required collision.

There is also a way to check it right now without sharing the whole files - only the information with X-coordinates and kangaroo type should be shared (excluding distances), and if we have the same X-coordinate with different types (wild and tame) so we can confirm that the key is found.

HWCollector and Zielar, do you want me to perform such check for you? 

Thanks for the offer, but I’ve not started yet as I am giving time for Zielar to solve the challenge first. He has poured a lot of resources to it already, and out of common courtesy, I will begin late Sunday night assuming that he’s hasn’t solved it yet. But I am working on precomputation for the 115-bit private key challenge. 

[WanderingPhilospher]

I really like this race
HardwareCollector or Zielar ?

There is a high probability that if we combine HardwareCollector's and Zielar's working files there will be the required collision.

There is also a way to check it right now without sharing the whole files - only the information with X-coordinates and kangaroo type should be shared (excluding distances), and if we have the same X-coordinate with different types (wild and tame) so we can confirm that the key is found.

HWCollector and Zielar, do you want me to perform such check for you? 

Thanks for the offer, but I’ve not started yet as I am giving time for Zielar to solve the challenge first. He has poured a lot of resources to it already, and out of common courtesy, I will begin late Sunday night assuming that he’s hasn’t solved it yet. But I am working on precomputation for the 115-bit private key challenge. 

Are you worried his boss/owners of the company will be mad at him?

[Etar]

-snip-
But you are right, Etar, that the "tame" DPs from previous keys could be used for subsequent, however their concentration will be very high on the left side of the range. Tames are distributed within the whole range, however if you use these tames for 1bit more key, they are all be only within the first half of the range, if for 2bit more key, all the tames will be on the first 25% of the range, etc...

But yes, the working files could be used for higher bits keys. However you should use the same DP size.

I agree that their concentration will be very high on the left side of the range, ofcourse.
About the same DP size, you are absolutly right, this size should be selected to 24bit or so, i think.
But it is much better than start from scratch.
if using every 5 tx, we will have 10% initial points. (20% with wild, but they are useless)

[MrFreeDragon]

if using every 5 tx, we will have 10% initial points. (20% with wild, but they are useless)

Why are wilds useless? If you find the key for some lower range, all the wilds are actually become tames also! Because you have the key to all that wilds  

EDIT: for wilds we have their x-coordinates and distance Wd. If we found the key k, the exact distance to every wild x-coordinate will be k + Wd, where Wd stored in hashtable together with the sign (positive or negative distance)

[Etar]

-snip-

Why are wilds useless? If you find the key for some lower range, all the wilds are actually become tames also! Because you have the key to all that wilds  

EDIT: for wilds we have their x-coordinates and distance Wd. If we found the key k, the exact distance to every wild x-coordinate will be k + Wd, where Wd stored in hashtable together with the sign (positive or negative distance)

Because wild produced from public key, we not need in next puzzle wild from previous work because you will get incorrect collission.
Wd + new pubkey give you incorrect collision!

[MrFreeDragon]

-snip-

Why are wilds useless? If you find the key for some lower range, all the wilds are actually become tames also! Because you have the key to all that wilds  

EDIT: for wilds we have their x-coordinates and distance Wd. If we found the key k, the exact distance to every wild x-coordinate will be k + Wd, where Wd stored in hashtable together with the sign (positive or negative distance)

Because wild produced from public key, we not need in next puzzle wild from previous work because you will get incorrect collission.
Wd + new pubkey give you incorrect collision!

All wilds became tames if you found the private key. I wrote you above how to retrieve the distance to all wilds, it is just one more group operation.

[MrFreeDragon]

All small pk110 solvers, I have just uploaded some calculated distinguished points DP=28 for pk #110. There are 1.4million DPs (2^20.42).
The table includes x-coordinate (DP 28) together with the kangaroo type (0 for tame, 1 for wild).

Here is zipped txt file: https://gofile.io/d/zD2RHe

Have a look at your tables, an if you have the same x-coordinate but with the different type (i.e im my table wild, but in yours tame) - so we immediately could retrieve the private key for #110

PS. The table includes only x-coordinates. Without distance it is useless, but helpful to find cross-collision with others.

[patatasfritas]

All wilds became tames if you found the private key. I wrote you above how to retrieve the distance to all wilds, it is just one more group operation.

Good point. I will try to code a merger.

All small pk110 solvers, I have just uploaded some calculated distinguished points DP=28 for pk #110. There are 1.4million DPs (2^20.42).
The table includes x-coordinate (DP 28) together with the kangaroo type (0 for tame, 1 for wild).

Here is zipped txt file: https://gofile.io/d/zD2RHe

Have a look at your tables, an if you have the same x-coordinate but with the different type (i.e im my table wild, but in yours tame) - so we immediately could retrieve the private key for #110

PS. The table includes only x-coordinates. Without distance it is useless, but helpful to find cross-collision with others.

What is the best way to compare TXT lists?  I'm going to separate wild and tame in two different files, merge+sort with my own files and use uniq -d to find duplicates.

Code:

grep 'type:0' DP28.txt|cut -d " " -f 1 > remote_tame.txt
grep 'type:1' DP28.txt|cut -d " " -f 1 > remote_wild.txt

cat local_tame.txt remote_wild.txt | sort | uniq -d
cat local_wild.txt remote_tame.txt | sort | uniq -d

# Inserting a remote wild in local tame for testing
echo 000d4230841b31f02659885bd7f6c72c >> local_tame_testing
cat local_tame_testing.txt remote_wild.txt | sort | uniq -d
000d4230841b31f02659885bd7f6c72c

[MrFreeDragon]

-snip-
What is the best way to compare TXT lists?  I'm going to separate wild and tame in two different files, merge+sort with my own files and use uniq -d to find duplicates.
-snip-

I uploaded tames and wilds in different files: https://gofile.io/d/trLIMy
However I see you have already made a bash script to separate them

To compare txt files for unique records you can also can use sets by python: set(A)&set(B) --> set of unique records, where A and B are lists from different txt files.

[WanderingPhilospher]

Jean_Luc, I want to look at the table which is saved to workfile. But as I understood, only 128bit are saved for X-coordinate and 126bit for distance (together with 1 bit for sign and 1 bit for kangaroo type).

Anyway, what is the easiest way to receive the whole table in txt format. I easily could read from binary file the head, dp, start/stop ranges, x/y coordinates for key. After that the hash table is saved with a lot of 0 bytes....
Can you just briefly describe the hash table structure which is saved to binary file?

if you still haven't managed to export the workfile, here are the changes I made to the code to export the DPs to txt.

The X-coord is 128+18 bits and distance 126bits. The X-coordinate could be re-generated from the distance if necessary.

https://github.com/PatatasFritas/FriedKangaroo/commit/1669df5f91ef2cc8a7619b21f66883fa164ab602

Any way, to export everything, headers and all so that it is like a text work file that can be merged with another text work file?

[COBRAS]

@JeanLuc and other folks who has knowledge in this area..
From what I realized that DP is just the x coordinate with a certain number of leading zeros .. like a brilliant among stones.
Kangaroo algorithm, creates a tribe of tame and a tribe of wild kangaroos.
Tame kangaroos are tied to a range, and wild to the desired public key.
Now the idea itself .. Why can not we use the experience of previous work?
What I mean. For example, we’ll start accumulating experience with a 54-bit key
The range where this private key located is
40000000000000
7fffffffffffff
and seek public key 0385a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963
we can shift the range to 0
and subtract the beginning of the range from the public key
(0x85a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963,0x0eb400323654cec63999b56f4ba44e8b21ab92d9d697fabe4666df3678585669)
-
(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)
=
(b1f8ba606a61026d1ecaa93d9e9ceb12260c33e92809ed1ecb0850a2856accc1,ac46d892583d7fdd24a25a229b6ea8d17add77b1f410a9d30441e0acbec19c74)
and range
0
3fffffffffffff
as result we will have key 0x2ABE1F9B67E114
if we add range we can regenerate real key
0x2ABE1F9B67E114+0x40000000000000=0x6ABE1F9B67E114
So we have a saved working file, where there are DP both tame and wild kangaroos in range 0-3fffffffffffff
DP of wild kangaroos we do not need more  so they are tied to the public key.
We can cut only tame kangaroos points from the work file and save to a new file.
And this tame will be correct for next puzzle because they are in the same range as next pazzle(after shifting ofcourse)
So we can use this file like initial to next pazzle
Next 59bit Puzzle..
range
800000000000000
fffffffffffffff
and seek public key 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
do the same thing, shift the range to 0 and subtract the beginning of the range from the public key
(0x48e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d,0xd094fcabf8995e2a25c73298a9f7419720db622daff89c67fd5535f6ac29720f)
-
(8991225911b9132d28f5c6bc763ceab7d18c37060e8bd1d7ed44db7560788c1e,da8b4d987cc9ac9b27b8763559b136fa36969c84fdef9e11635c42228e8f0ef1)
=
(2b90a8680d08cf81e15e209acadbb16b7bdff19787d6d13ca6a7852fee8d1013,447a29425ea9773471ad9810d21a976cf5bd4bdb46d0c8ae537591dce43252f2)
and range
0
7ffffffffffffff
Don`t forget that we already have some tame DPs on this range(0-3fffffffffffff), so we should find collision faster!
result key is 0x7C07A1825367BBE
add range and real key
0x7C07A1825367BBE+0x800000000000000=0xFC07A1825367BBE
than do the same, cut from work file only tame kangaroos, save and solve next pazzle...
In this case, after each puzzle, we will already have more and more DP points from tame kangaroos.
What you think?

Etar, can You explain how You get coordinates for starting point of range ?

40000000000000
7fffffffffffff
and seek public key 0385a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963
we can shift the range to 0
and subtract the beginning of the range from the public key
(0x85a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963,0x0eb400323654cec63999b56f4ba44e8b21ab92d9d697fabe4666df3678585669)
-
(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)
=
(b1f8ba606a61026d1ecaa93d9e9ceb12260c33e92809ed1ecb0850a2856accc1,ac46d892583d7fdd24a25a229b6ea8d17add77b1f410a9d30441e0acbec19c74)
and range
0
3fffffffffffff

I was "crack" my brain but cant understand how get this coordinates

(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)

for this starting point  - 40000000000000

 

Please.

With respect to you !!!


BR !

[patatasfritas]

Example with 40bits key

pubkey: 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4
priv: 0xe9ae4933d6

We get a wild DP from savefile, x-coord and distance

Code:

2bff14d4321506319af572ab7604e22f2d172 0000000000000000000000100d3439c4

Distance: 0x100d3439c4
Starting point (offset): 2^39 = 0x8000000000

Code:

0xe9ae4933d6 + 0x100d3439c4  - 2^39 = 0x79bb7d6d9a

The tame distance 0x79bb7d6d9a returns X-coord 0000157f1985299f1bda6646dd76bff14d4321506319af572ab7604e22f2d172.

[Etar]

Example with 40bits key

pubkey: 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4
priv: 0xe9ae4933d6

We get a wild DP from savefile, x-coord and distance

Code:

2bff14d4321506319af572ab7604e22f2d172 0000000000000000000000100d3439c4

Distance: 0x100d3439c4
Starting point (offset): 2^39 = 0x8000000000

Code:

0xe9ae4933d6 + 0x100d3439c4  - 2^39 = 0x79bb7d6d9a

The tame distance 0x79bb7d6d9a returns X-coord 0000157f1985299f1bda6646dd76bff14d4321506319af572ab7604e22f2d172.

I agree that you can tame wild kangaroos.

-snip-
I was "crack" my brain but cant understand how get this coordinates

(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)

for this starting point  - 40000000000000
-snip-

it is just 40000000000000 * G = (public key of 40000000000000)
You not need to do this, as say MrFreeDragon DP already shifted.

[patatasfritas]

In "wsplit" mode, the time and count should be reset after every save? When I merged all split files the total time are incorrect.

Code:

kangaroo -ws -d 22 -w 70/70-22 -wsplit -wi 30 70.txt

kangaroo -winfo 70/70-22_29May20_0
  Count     : 17936959488 2^34.062
  Time      : 20s

kangaroo -winfo 70/70-22_29May20_084011
  Count     : 42612829184 2^35.311
  Time      : 50s

kangaroo -winfo 70/70-22_29May20_092015
  Count     : 704108078080 2^39.357
  Time      : 14:12

What is the best way to combine all the save files?

I added a "Directory Merge" option to merge more than two files at once (https://github.com/PatatasFritas/FriedKangaroo/commit/f36c560135710f9956677eb3dcda78ffd1ccb0a4)