Pollard's kangaroo ECDLP solver

[WanderingPhilospher]

Quick someone give me sample start and end range with public keys, I think my 256-bit extension mod is done but I need to test it.

for testing right
40 bit far from private key very fast to found easy

03E87E83F871DF1439B7873B4AE449D15306CAFC53E03A06FFFB534B3BF25B58D8

Those three 40-bit inputs found the private key successfully.

The 64-bit input took too much time I need to run it on my GPU rig to see if it's functioning.

Can you post a link here to the list of puzzle transactions for easy reference? I remember it was pasted in some other thread but it's easier for me to check it here on this one.

Specifically I want to test this with #125 and #160 to make sure my 256-bit handling is working. (My hashtable index tweak is working great!  )

https://raw.githubusercontent.com/JeanLucPons/Kangaroo/master/puzzle32.txt

Code:

#120 ( 17s2b9ksz5y7abUm92cHwG8jEPCzK3dLnT )
800000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630

#125 ( 1PXAyUB8ZoH3WD8n5zoAthYjN15yN5CVq5 )
10000000000000000000000000000000
1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
0233709EB11E0D4439A729F21C2C443DEDB727528229713F0065721BA8FA46F00E

#130 ( 1Fo65aKq8s8iquMt6weF1rku1moWVEd5Ua )
200000000000000000000000000000000
3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
03633CBE3EC02B9401C5EFFA144C5B4D22F87940259634858FC7E59B1C09937852

#135 ( 16RGFo6hjq9ym6Pj7N5H7L1NR1rVPJyw2v )
4000000000000000000000000000000000
7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02145D2611C823A396EF6712CE0F712F09B9B4F3135E3E0AA3230FB9B6D08D1E16

#140 ( 1QKBaU6WAeycb3DbKbLBkX7vJiaS8r42Xo )
80000000000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
031F6A332D3C5C4F2DE2378C012F429CD109BA07D69690C6C701B6BB87860D6640

#145 ( 19GpszRNUej5yYqxXoLnbZWKew3KdVLkXg )
1000000000000000000000000000000000000
1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
03AFDDA497369E219A2C1C369954A930E4D3740968E5E4352475BCFFCE3140DAE5

#150 ( 1MUJSJYtGPVGkBCTqGspnxyHahpt5Te8jy )
20000000000000000000000000000000000000
3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
03137807790EA7DC6E97901C2BC87411F45ED74A5629315C4E4B03A0A102250C49

#155 ( 1AoeP37TmHdFh8uN72fu9AqgtLrUwcv2wJ )
400000000000000000000000000000000000000
7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
035CD1854CAE45391CA4EC428CC7E6C7D9984424B954209A8EEA197B9E364C05F6

#160 ( 1NBC8uXJy1GiJ6drkiZa1WuKn51ps7EPTv )
8000000000000000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02E0A8B039282FAF6FE0FD769CFBC4B6B4CF8758BA68220EAC420E32B91DDFA673

[fxsniper]

Quick someone give me sample start and end range with public keys, I think my 256-bit extension mod is done but I need to test it.

for testing right
40 bit far from private key very fast to found easy


40bit
23D4A09295BE678B21A5F1DCEAE1F634A69C1B41775F680EBF8164266471401B
23D4A09295BE678B21A5F1DCEAE1F634A69C1B41775F680EBF8166266471401B
03CA5606A1E820E7A2F6BB3AB090E8ADE7B04A7E0B5909A68DDA2744AE3B8ECBFA

40bit
B09C765FA3DC6AD138A8D0DA17CD94306FBC32ACB3D67BC093936761CCC48769
B09C765FA3DC6AD138A8D0DA17CD94306FBC32ACB3D67BC093936961CCC48769
0294FF933DA0498859959225ED6A50D709A4D9C678705D72E9202A4852C8084D85

40bit
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77D4C2A2ED0C99C1232
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77D4C2A30D0C99C1232
03E87E83F871DF1439B7873B4AE449D15306CAFC53E03A06FFFB534B3BF25B58D8


64bit
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77E4C2A2FD0C99C1232
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77C4C2A2FD0C99C1232
03E87E83F871DF1439B7873B4AE449D15306CAFC53E03A06FFFB534B3BF25B58D8

Those three 40-bit inputs found the private key successfully.

The 64-bit input took too much time I need to run it on my GPU rig to see if it's functioning.

Can you post a link here to the list of puzzle transactions for easy reference? I remember it was pasted in some other thread but it's easier for me to check it here on this one.

Specifically I want to test this with #125 and #160 to make sure my 256-bit handling is working. (My hashtable index tweak is working great!  )

Code:

Key# 0 [1S]Pub:  0x03E87E83F871DF1439B7873B4AE449D15306CAFC53E03A06FFFB534B3BF25B58D8 
       Priv: 0x6B29781E725708AE4D94E13730A2718EE3383EA5D911E77D4C2A2FD0C99C1232 

64 bit is found in 2 minite

sorry for use wrong number

for testing  (fast found)

private key is  =  48470744558466837119591892246032931505798916835461120051988009871155176149554
and I start before
64 bit mean 2**64 = 18446744073709551616

start = 48470744558466837119591892246032931505798916835461120051988009871155176149554-18446744073709551616
end = 48470744558466837119591892246032931505798916835461120051988009871155176149554+18446744073709551616

6B29781E725708AE4D94E13730A2718EE3383EA5D911E77E4C2A2FD0C99C1232
6B29781E725708AE4D94E13730A2718EE3383EA5D911E77C4C2A2FD0C99C1232

just for fast testing  (found on two minute)

I found some time use time long 1 hour or not found

Can possible make kangaroo print out found private key in case use output file 
because when use output file is no show found key
some time test and kangaroo finish not tell anything but output found key is on file by command success

[fxsniper]

Code:

#120 ( 17s2b9ksz5y7abUm92cHwG8jEPCzK3dLnT )
800000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630
 

puzzle # 120
very long time

yesterday from now 1 night 2 kangaroo write save work file to 1GB and 4GB
now I close for works

[WanderingPhilospher]

Code:

#120 ( 17s2b9ksz5y7abUm92cHwG8jEPCzK3dLnT )
800000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630
 

puzzle # 120
very long time

yesterday from now 1 night 2 kangaroo write save work file to 1GB and 4GB
now I close for works

You must be using one helluva low -d setting to run up a 1 and 4GB file with one GPU.  Look at estimated RAM, do you have enough space to save it all and then to merge at your current -d setting?

[bigvito19]

Code:

#120 ( 17s2b9ksz5y7abUm92cHwG8jEPCzK3dLnT )
800000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630
 

puzzle # 120
very long time

yesterday from now 1 night 2 kangaroo write save work file to 1GB and 4GB
now I close for works

You must be using one helluva low -d setting to run up a 1 and 4GB file with one GPU.  Look at estimated RAM, do you have enough space to save it all and then to merge at your current -d setting?

Of course it will take a long if you're using a low -d setting.

[fxsniper]

I testing kangaroo with full address and start kespace point from private key 1099511627776 (meddle) very fast to found in 1 minute or 2

now I try to split scan for fast, last time use full range is very log and not see any update

may be try split each 2099511627776

I try to made small simple utilities to remember my random save on text file
random start point and make each 2099511627776 and scan

I think kangaroo jump by next and next side not jump dynamic move to around all

int(2**120/2*40) = 26584559915698317458076141205606891520 (slot) time to scan (OMG.)

random count slot first and multiply to start point and remember number used

hope random found by fast

what possibility between use large range  800000000000000000000000000000...ffffffffffffffffffffffffffffff
and split range

if choose split what rage size that performance

2**120 = 1329227995784915872903807060280344576

1329227995784915872903807060280344576/10000 time = size 132922799578491593660272018980864  (2*107)
or
1329227995784915872903807060280344576/1000000000000000 = size 1329227995784915976192  (2**70)

[fxsniper]

option -d
distinguished point (DP) method
That mean DP method is long size between 2 leg right
on image
https://raw.githubusercontent.com/JeanLucPons/Kangaroo/master/DOC/paths.jpg
I am understand correct?
if use high distinguished point how long kangaroo jump to collision hit
how can make it work with low resource, I try full range it use a lot of storage save work may be make it slow
now I think may be not save work for can possible help work too fast than

[WanderingPhilospher]

option -d
distinguished point (DP) method
That mean DP method is long size between 2 leg right
on image
https://raw.githubusercontent.com/JeanLucPons/Kangaroo/master/DOC/paths.jpg
I am understand correct?
if use high distinguished point how long kangaroo jump to collision hit
how can make it work with low resource, I try full range it use a lot of storage save work may be make it slow
now I think may be not save work for can possible help work too fast than

Like I said, the program will give you an estimated RAM usage.  If you are using save option, that is how much storage space you will need. 

Another way to look at it. If you are trying the full range of #120, you will need to perform 2^60 + 1 = 2^61. Now, take the -d you are or may want to use and subtract that from 2^61. So if you are using -d 30, you will need to save 2^31 points. If you are using -d 10, you will need to save 2^51 points. The lower your -d, the more storage space/RAM (if not using the save option) you will need.

[fxsniper]

Like I said, the program will give you an estimated RAM usage.  If you are using save option, that is how much storage space you will need. 

Another way to look at it. If you are trying the full range of #120, you will need to perform 2^60 + 1 = 2^61. Now, take the -d you are or may want to use and subtract that from 2^61. So if you are using -d 30, you will need to save 2^31 points. If you are using -d 10, you will need to save 2^51 points. The lower your -d, the more storage space/RAM (if not using the save option) you will need.

Thank you
I will try again tonight

[NotATether]

Confirmed that my custom Kangaroo mods function properly with 125 bit, 160 bit and 256 bit ranges on CPU, I will keep you guys updated as I fix up GPU/networking/merge.

[WanderingPhilospher]

Confirmed that my custom Kangaroo mods function properly with 125 bit, 160 bit and 256 bit ranges on CPU, I will keep you guys updated as I fix up GPU/networking/merge.

We appreciate it.

Seems like it is more difficult than what I had thought.  JLP said it was an easy 'mod' to take it to 256 bits.

I was thinking one just needed to store/save the point and distances in a 256 format versus the current 128.  Program I use is much easier...it's 256 and I can just change the size limit to store how ever many characters in the point and distance rows.

For this kangaroo program... for the tames, the distance is a private key and the point is that private keys pubkey, so the program already knows the full point/pubkey, it has already calculated it, but pubkey was choked down to 32 characters to save RAM/file storage space... it was just a matter of storing the full pubkey (64 chars) and padding the private key/distance with zeros to equal 64 characters.

[NotATether]

Confirmed that my custom Kangaroo mods function properly with 125 bit, 160 bit and 256 bit ranges on CPU, I will keep you guys updated as I fix up GPU/networking/merge.

We appreciate it.

Thank you.

Seems like it is more difficult than what I had thought.  JLP said it was an easy 'mod' to take it to 256 bits.

It's not that, I'm just working under shitty environmental conditions e.g we just had a major power outage yesterday that lasted the entire day, and the internet's so $@&#ing slow here   This was supposed to be a one-week gig.

I *feel* that it's almost done but when we apply DevOps Borat's Law "To estimate project duration we apply Celsius to Fahrenheit formula. C is internal estimate and F is what we tell PM: C x 9/5+ 32 = F days." I estimate I am about 75% of the way there.  

Silly project management.

I was thinking one just needed to store/save the point and distances in a 256 format versus the current 128.  Program I use is much easier...it's 256 and I can just change the size limit to store how ever many characters in the point and distance rows.

The problem is that there are three different representations of big (>64) bits in the Kangaroo program, a fixed-width 4-element array used in CUDA solver, the int128_t struct you showed me earlier and that Int class which is artificially masked to 125 bits, and all of these occurrences have to be expanded or otherwise decrippled.

And a bunch of unrelated stuff are shoved into the distance Int variables do all of those have to either be moved somewhere else or otherwise phased out (hence my deterministic hashtable index function using XOR of all the 64-bit parts, because apparently that used to be in bits64[2] of the distance variable!)

Kangaroo type also had to be moved out to a 32-bit variable. Sign bit was completely removed, it was only needed because Int arithmetic already %modulus's down negative numbers obtained from arithmetic overflow.

For this kangaroo program... for the tames, the distance is a private key and the point is that private keys pubkey, so the program already knows the full point/pubkey, it has already calculated it, but pubkey was choked down to 32 characters to save RAM/file storage space... it was just a matter of storing the full pubkey (64 chars) and padding the private key/distance with zeros to equal 64 characters.

May I ask which custom program is it you are referring to?


Things like this are a step backwards, why does it assume my CUDA lives in cuda-8.0/ ?

Code:

# make gpu=1
cd obj &&mkdir -p SECPK1
cd obj && mkdir -p GPU
/usr/local/cuda-8.0/bin/nvcc -maxrregcount=0 --ptxas-options=-v --compile --compiler-options -fPIC -ccbin /usr/bin/g++-4.8 -m64 -O2 -I/usr/local/cuda-8.0/include -gencode=arch=compute_,code=sm_ -o obj/GPU/GPUEngine.o -c GPU/GPUEngine.cu
make: /usr/local/cuda-8.0/bin/nvcc: Command not found
make: *** [Makefile:75: obj/GPU/GPUEngine.o] Error 127

[fxsniper]

Code:

# make gpu=1
cd obj &&mkdir -p SECPK1
cd obj && mkdir -p GPU
/usr/local/cuda-8.0/bin/nvcc -maxrregcount=0 --ptxas-options=-v --compile --compiler-options -fPIC -ccbin /usr/bin/g++-4.8 -m64 -O2 -I/usr/local/cuda-8.0/include -gencode=arch=compute_,code=sm_ -o obj/GPU/GPUEngine.o -c GPU/GPUEngine.cu
make: /usr/local/cuda-8.0/bin/nvcc: Command not found
make: *** [Makefile:75: obj/GPU/GPUEngine.o] Error 127

How I can compile kangaroo on windows?
upper command is compile on linux right?

[NotATether]

Code:

# make gpu=1
cd obj &&mkdir -p SECPK1
cd obj && mkdir -p GPU
/usr/local/cuda-8.0/bin/nvcc -maxrregcount=0 --ptxas-options=-v --compile --compiler-options -fPIC -ccbin /usr/bin/g++-4.8 -m64 -O2 -I/usr/local/cuda-8.0/include -gencode=arch=compute_,code=sm_ -o obj/GPU/GPUEngine.o -c GPU/GPUEngine.cu
make: /usr/local/cuda-8.0/bin/nvcc: Command not found
make: *** [Makefile:75: obj/GPU/GPUEngine.o] Error 127

How I can compile kangaroo on windows?
upper command is compile on linux right?

For some reason nobody updated the CUDA path so you need to edit the Makefile yourself and find the line that says

Code:

CUDA = /usr/local/cuda-8.0

And replace it with

Code:

CUDA = /usr/local/cuda

The CUDA installer creates a symlink at /usr/local/cuda to whatever the actual installed CUDA version is.

[fxsniper]

For some reason nobody updated the CUDA path so you need to edit the Makefile yourself and find the line that says

Code:

CUDA = /usr/local/cuda-8.0

And replace it with

Code:

CUDA = /usr/local/cuda

The CUDA installer creates a symlink at /usr/local/cuda to whatever the actual installed CUDA version is.

Can kangaroo compile with CUDA 10.1 or 11 ?
I don't have cuda 8.0

[WanderingPhilospher]

For some reason nobody updated the CUDA path so you need to edit the Makefile yourself and find the line that says

Code:

CUDA = /usr/local/cuda-8.0

And replace it with

Code:

CUDA = /usr/local/cuda

The CUDA installer creates a symlink at /usr/local/cuda to whatever the actual installed CUDA version is.

Can kangaroo compile with CUDA 10.1 or 11 ?
I don't have cuda 8.0

Yes

[fxsniper]

I try this version
https://github.com/JeanLucPons/Kangaroo

on my linux subsystem (windows 10)

I compile with command  make success
make

and use
./kangaroo -gpu in.txt

I got message

GPU code not compiled, use -DWITHGPU when compiling.

gpu meter not show

[GPU 0.00 MK/s]

How I can compile with gpu code?

[NotATether]

I try this version
https://github.com/JeanLucPons/Kangaroo

on my linux subsystem (windows 10)

I compile with command  make success
make

and use
./kangaroo -gpu in.txt

I got message

GPU code not compiled, use -DWITHGPU when compiling.

Did you just type "make" or "make gpu=1"? (What will work is "make gpu=1 ccap=52" or 61 or 75 or whatever your CUDA compute cap is)

By the way. WSL speed will be slower than just compiling it on Windows itself, because WSL emulates system calls. The GPUs will also not be recognized unless you install the Ubuntu(?) WSL drivers from NVIDIA's download page, the Windows drivers don't work from WSL.

[fxsniper]

Did you just type "make" or "make gpu=1"? (What will work is "make gpu=1 ccap=52" or 61 or 75 or whatever your CUDA compute cap is)

By the way. WSL speed will be slower than just compiling it on Windows itself, because WSL emulates system calls. The GPUs will also not be recognized unless you install the Ubuntu(?) WSL drivers from NVIDIA's download page, the Windows drivers don't work from WSL.

I use "make" only
make can compile success and can run kangaroo but can not using option -gpu
show error GPU code not compiled, use -DWITHGPU when compiling.

Code:

make gpu=1
mkdir -p obj
cd obj &&       mkdir -p SECPK1
cd obj && mkdir -p GPU
/usr/local/cuda-8.0/bin/nvcc -maxrregcount=0 --ptxas-options=-v --compile --compiler-options -fPIC -ccbin /usr/bin/g++-4.8 -m64 -O2 -I/usr/local/cuda-8.0/include -gencode=arch=compute_,code=sm_ -o obj/GPU/GPUEngine.o -c GPU/GPUEngine.cu
make: /usr/local/cuda-8.0/bin/nvcc: Command not found
make: *** [Makefile:75: obj/GPU/GPUEngine.o] Error 127

Code:

make gpu=1 ccap=52
cd obj &&       mkdir -p SECPK1
cd obj && mkdir -p GPU
/usr/local/cuda-8.0/bin/nvcc -maxrregcount=0 --ptxas-options=-v --compile --compiler-options -fPIC -ccbin /usr/bin/g++-4.8 -m64 -O2 -I/usr/local/cuda-8.0/include -gencode=arch=compute_52,code=sm_52 -o obj/GPU/GPUEngine.o -c GPU/GPUEngine.cu
make: /usr/local/cuda-8.0/bin/nvcc: Command not found
make: *** [Makefile:75: obj/GPU/GPUEngine.o] Error 127

I will try on real Ubuntu on small harddisk try install

[NotATether]

~snip

Did you do this first?

For some reason nobody updated the CUDA path so you need to edit the Makefile yourself and find the line that says

Code:

CUDA = /usr/local/cuda-8.0

And replace it with

Code:

CUDA = /usr/local/cuda

The CUDA installer creates a symlink at /usr/local/cuda to whatever the actual installed CUDA version is.