Pollard's kangaroo ECDLP solver

[NotATether]

How can we know what happen with higher bits or large range ?

I'm currently working on increasing the maximum range - when that's done I'll release the code so you guys can test this for yourselves.

[fxsniper]

reference with this kangaroo python script
http://bitchain.pl/100btc/pollard_kangaroo.txt

easy to understand how kangaroo. works

What value in hex they random for match
calculate from what formula? (or them random)

tame.txt

Code:

25231ba5231e46285d928fa2bef328227c1c510bcdabb7dd8b0161eec5bbae98 74319
25f3154199d497085b1798b6786d52fd74944ff4cd891844e923aab8e4561eb8 69734
7c6d52862d161ddbf90c5d1649397d3276471876b9ca4fed98e322b8c42648f0 77088
f02ba4892f446cb051104c5840c4f62ef94f6941e826277c531daa1848e9d420 57009
9f34d91a41d61c0e0d26d8ce856640020c12daccd076150787cbd16d3e78ef98 74399
8a0866dd4452056244d588f101c4801d856781a02b777f72439124dbb2b5a908 61382
15e4b924f87ef2c65e83ab1cbc501c7d0fec4227c10254e517c4af646af2eb00 57049

wild.txt

Code:

d280dc5d4915740ccf80bda64e07455fc58eaba90d9072589f726f5763ecf788 14021
b8e2cb115afb3f652e9b5451750d1b0e83659ea29b670380c7a76716ede4dfb0 27618
e7f9306469bdfbbf6099dd520c0a1469deb0a7cd61b1851d69d46b2e2cf6fe98 27874
076681af5c9838ce36787b84afc19bf5c0faf5c3bf0c6faff63959af3844f3f0 35316
a67e03aff0b98a930762dc399b46b69ed6104e97069eddce107ee77e3f889cf0 16981
15e4b924f87ef2c65e83ab1cbc501c7d0fec4227c10254e517c4af646af2eb00 5539
5a24b5bcc6b4f5a02620c2daa903cd81f568f426a41b1c1dc8c18f8a049622b0 28299
9f0e02a15a6dc2be1b338f9f4b0ea95e887d5e6eef30007e4d63d0729093d910 12160
e12b8339a1086c3c58bd69adf6516af5f2f0ec21d71666073aed56a97d6d09c0 28619

match
15e4b924f87ef2c65e83ab1cbc501c7d0fec4227c10254e517c4af646af2eb00 57049

15e4b924f87ef2c65e83ab1cbc501c7d0fec4227c10254e517c4af646af2eb00 5539




Study kangaroo
https://github.com/Telariust/pollard-kangaroo
setup option flag_verbose   

flag_verbose   = 2   # 0, 1, 2

warning show verbose work show a lot of information

both script do same but feel   pollard-kangaroo-multi.py work better pollard_kangaroo.txt

[fxsniper]

if anyone try using python script and require to use gmpy2 library

http://bitchain.pl/100btc/pollard_kangaroo.txt
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo.py
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.py

or use BSGS and script use gmpy2
or other script generate bitcoin address and use gmpy2 to accelerate calculate for faster

use library gmpy2 make calculate faster

install gmpy2 on linux

need to install  libgmp first after that then install gmpy2 normal

Code:

apt-get install libgmp-dev
apt-get install libmpfr-dev
apt-get install libmpc-dev

pip install gmpy2

install gmpy2  on anaconda (windows 10)
Anaconda Individual Edition or Miniconda
use conda install
command

Code:

conda install gmpy2

install gmpy2  on python windows 10
download gmpy2 from this url
https://www.lfd.uci.edu/~gohlke/pythonlibs/
choose version macth with you python version
example download
gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl

command

Code:

pip install gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl

[bigvito19]

if anyone try using python script and require to use gmpy2 library

http://bitchain.pl/100btc/pollard_kangaroo.txt
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo.py
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.py

or use BSGS and script use gmpy2
or other script generate bitcoin address and use gmpy2 to accelerate calculate for faster

use library gmpy2 make calculate faster

install gmpy2 on linux

need to install  libgmp first after that then install gmpy2 normal

Code:

apt-get install libgmp-dev
apt-get install libmpfr-dev
apt-get install libmpc-dev

pip install gmpy2

install gmpy2  on anaconda (windows 10)
Anaconda Individual Edition or Miniconda
use conda install
command

Code:

conda install gmpy2

install gmpy2  on python windows 10
download gmpy2 from this url
https://www.lfd.uci.edu/~gohlke/pythonlibs/
choose version macth with you python version
example download
gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl

command

Code:

pip install gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl

Everyone just about knows of that old version of kangaroo with python already. We are on the new version of kangaroo that uses distinguished points (DP) method now.

[fxsniper]

Everyone just about knows of that old version of kangaroo with python already. We are on the new version of kangaroo that uses distinguished points (DP) method now.

Thanks
rights that old python code, I just use learning about how Kangaroo it works (easy to show how it work and read code on one files or print show display data how it works for use this tools better

For real use use JeanLucPons Kangaroo with GPU is faster
https://github.com/JeanLucPons/Kangaroo

However old python code may be interesting if someone can use python connect and work with AI. tensor flow and Keras do deep learning work with kangaroo I mean modify to work beater

[itod]

However old python code may be interesting if someone can use python connect and work with AI. tensor flow and Keras do deep learning work with kangaroo I mean modify to work beater

What has AI to do with finding the private keys? AI can not help at all with kangaroos.

[fxsniper]

However old python code may be interesting if someone can use python connect and work with AI. tensor flow and Keras do deep learning work with kangaroo I mean modify to work beater

What has AI to do with finding the private keys? AI can not help at all with kangaroos.

I don't really know much

if we still use pure kangaroo , now we still stuck with high bits high range high keyspace

kangaroo need to jump a lot may be too many days jumps and jumps to new position scan

I don't know how kangaroo use pubkey XY to calculate but point XY use for calculate

Can possible to create dataset use method private key generate with public point and train AI to give some value and use kangaroo to get point to jump or do something like that ?
Use AI. predict key space and give it to kangaroo ?

Any idea?

still need to AI. expert help to analysist

[NotATether]

both script do same but feel   pollard-kangaroo-multi.py work better pollard_kangaroo.txt

Very educational scripts you shared. It's dumbed down enough for someone to follow along the different stages (preparing the tame and wild herds within two different ranges, showing how the jump table of G points is made, converting the DP mask to a difficulty etc. which I leaned doesn't have to have all bits adjacent to it.


Something that's bothering me about Jean_Luc's program though is how we stuff the kangaroo type in the distance 128-bit number but we have a separate member "kIdx" in ITEM and DP structs that can be modulus'ed by 2 to give the kangaroo type - The kangaroos in a vector alternate between wild and time, which corresponds to what these scripts are showing.

It's also sending some useless stuff over the network to Kangaroo servers, e.g "h" the hash table index, this is useless because the hash table is local to one host, but it's stuffed in the "x" 128-bit member so it's sent anyway. Same with the kangaroo type which is already embedded in the lowest by of "kIdx", it makes no sense to put it in a hash entry struct as well, hash entries aren't even sent across the network. Nitty gritty details that complicate transitioning it to unsigned 256 bit.

[fxsniper]

both script do same but feel   pollard-kangaroo-multi.py work better pollard_kangaroo.txt

Very educational scripts you shared. It's dumbed down enough for someone to follow along the different stages (preparing the tame and wild herds within two different ranges, showing how the jump table of G points is made, converting the DP mask to a difficulty etc. which I leaned doesn't have to have all bits adjacent to it.


Something that's bothering me about Jean_Luc's program though is how we stuff the kangaroo type in the distance 128-bit number but we have a separate member "kIdx" in ITEM and DP structs that can be modulus'ed by 2 to give the kangaroo type - The kangaroos in a vector alternate between wild and time, which corresponds to what these scripts are showing.

It's also sending some useless stuff over the network to Kangaroo servers, e.g "h" the hash table index, this is useless because the hash table is local to one host, but it's stuffed in the "x" 128-bit member so it's sent anyway. Same with the kangaroo type which is already embedded in the lowest by of "kIdx", it makes no sense to put it in a hash entry struct as well, hash entries aren't even sent across the network. Nitty gritty details that complicate transitioning it to unsigned 256 bit.

That script can show newbies who interest or want to know how it works just setting to show message on working
script is one file easy to read too
old script but record to try use it study, try use with low key space and low number of puzzle under 40 bits fast to found and learn how it works

and What mean Kangaroo limited 120 bits
However all Kangaroo version have limited for 120 bits only right both  Jean_Luc's program have problem with  limited 120 bits.
if we solve puzzle #120 already so, What next?
how can extend 120 bits

or that mean limited wide of range scan for 120 bit and for high bit like 160 bits  need to split 2 keyspace or 4 keyspace and scan each method use program something like that

Do I miss understands.

[WanderingPhilospher]

both script do same but feel   pollard-kangaroo-multi.py work better pollard_kangaroo.txt

It's also sending some useless stuff over the network to Kangaroo servers, e.g "h" the hash table index, this is useless because the hash table is local to one host, but it's stuffed in the "x" 128-bit member so it's sent anyway. Same with the kangaroo type which is already embedded in the lowest by of "kIdx", it makes no sense to put it in a hash entry struct as well, hash entries aren't even sent across the network. Nitty gritty details that complicate transitioning it to unsigned 256 bit.

if we solve puzzle #120 already so, What next?
how can extend 120 bits

or that mean limited wide of range scan for 120 bit and for high bit like 160 bits  need to split 2 keyspace or 4 keyspace and scan each method use program something like that

Do I miss understands.

Currently with JLPs program you can search up to #125 of the puzzle.  There is only enough "room" to store the #125s distance traveled (private key)

[NotATether]

Where in the warping cyberspace is "PRIx64" defined? 

Kangaroo.cpp, line 169, function SetDP(int size) [I think that's the name of it off the top of my head]

Code:

::printf("DP size: %d [0x%" PRIx64 "]\n",dpSize,dMask);

This is ostensibly supposed to be the Unix format code for a 64-bit hex number, but it's not defined anywhere in the program. Could it be in a standard header file?

I have to change it to 256-bit (4 64-bit format codes strung together) because I wound up having to increase the DP size to 256 bits as well because I didn't feel like having ANOTHER field just for a truncated lowest-64 bits of the kangaroo position, especially when said field is shoved inside Int.bits64[3] of a 128-bit kangaroo and all the code references that.

There are 2 more occurrences of this which you can see with https://github.com/JeanLucPons/Kangaroo/search?q=PRIx64&type=

[fxsniper]

Where in the warping cyberspace is "PRIx64" defined? 

Kangaroo.cpp, line 169, function SetDP(int size) [I think that's the name of it off the top of my head]

Code:

::printf("DP size: %d [0x%" PRIx64 "]\n",dpSize,dMask);

This is ostensibly supposed to be the Unix format code for a 64-bit hex number, but it's not defined anywhere in the program. Could it be in a standard header file?

I have to change it to 256-bit (4 64-bit format codes strung together) because I wound up having to increase the DP size to 256 bits as well because I didn't feel like having ANOTHER field just for a truncated lowest-64 bits of the kangaroo position, especially when said field is shoved inside Int.bits64[3] of a 128-bit kangaroo and all the code references that.

There are 2 more occurrences of this which you can see with https://github.com/JeanLucPons/Kangaroo/search?q=PRIx64&type=

Could you help to fork update to version 256bit (for use up to #160 puzzle)?
may be work better than limited to fit 120 bits

JeanLucPons still on forum, Can possible to update? or may be limited because of have some problem technic when use work with high bits or not?

[bigvito19]

Where in the warping cyberspace is "PRIx64" defined?  

Kangaroo.cpp, line 169, function SetDP(int size) [I think that's the name of it off the top of my head]

Code:

::printf("DP size: %d [0x%" PRIx64 "]\n",dpSize,dMask);

This is ostensibly supposed to be the Unix format code for a 64-bit hex number, but it's not defined anywhere in the program. Could it be in a standard header file?

I have to change it to 256-bit (4 64-bit format codes strung together) because I wound up having to increase the DP size to 256 bits as well because I didn't feel like having ANOTHER field just for a truncated lowest-64 bits of the kangaroo position, especially when said field is shoved inside Int.bits64[3] of a 128-bit kangaroo and all the code references that.

There are 2 more occurrences of this which you can see with https://github.com/JeanLucPons/Kangaroo/search?q=PRIx64&type=

Could you help to fork update to version 256bit (for use up to #160 puzzle)?
may be work better than limited to fit 120 bits

JeanLucPons still on forum, Can possible to update? or may be limited because of have some problem technic when use work with high bits or not?

How can we know what happen with higher bits or large range ?

I'm currently working on increasing the maximum range - when that's done I'll release the code so you guys can test this for yourselves.

I think he is trying to do that now

[NotATether]

I think he trying is doing that now

Yeah it's at the closing stages.


For what it's worth, I did find the occurrence of where PRIx64 is defined, it was in <inttypes.h>  and it's value is a format code "llx". That file also has several other format code definitions for printf().

The file itself can be viewed at http://www.qnx.com/developers/docs/6.5.0/index.jsp?topic=%2Fcom.qnx.doc.dinkum_en_c99%2Finttypes.html

I better find the correct format code sequence on Win32 to chain 4 64-bit hex numbers though, I want to get that right the first time since I only have Linux machines handy to test with.

[WanderingPhilospher]

I think he trying is doing that now

Yeah it's at the closing stages.


For what it's worth, I did find the occurrence of where PRIx64 is defined, it was in <inttypes.h>  and it's value is a format code "llx". That file also has several other format code definitions for printf().

The file itself can be viewed at http://www.qnx.com/developers/docs/6.5.0/index.jsp?topic=%2Fcom.qnx.doc.dinkum_en_c99%2Finttypes.html

I better find the correct format code sequence on Win32 to chain 4 64-bit hex numbers though, I want to get that right the first time since I only have Linux machines handy to test with.

I remember having an export issue and one of these solved it:

%0I64x or %016llx

May or may not be what you are looking for though with the chaining...

[WanderingPhilospher]

I better find the correct format code sequence on Win32 to chain 4 64-bit hex numbers though, I want to get that right the first time since I only have Linux machines handy to test with.

Int.CPP file:

Code:

std::string Int::GetC64Str(int nbDigit) {

  char tmp[256];
  char bStr[256];
  tmp[0] = '{';
  tmp[1] = 0;
  for (int i = 0; i< nbDigit; i++) {
    if (bits64[i] != 0) {
#ifdef WIN64
      sprintf(bStr, "0x%016I64XULL", bits64[i]);
#else
      sprintf(bStr, "0x%" PRIx64  "ULL", bits64[i]);

I was thinking to create a new union:

Code:

union int128_s {

  uint8_t  i8[16];
  uint16_t i16[8];
  uint32_t i32[4];
  uint64_t i64[2];

};


typedef union int128_s int128_t;

#define safe_free(x) if(x) {free(x);x=NULL;}

// We store only 128 (+18) bit a the x value which give a probabilty a wrong collision after 2^73 entries

typedef struct {

  int128_t  x;    // Poisition of kangaroo (128bit LSB)
  int128_t  d;    // Travelled distance (b127=sign b126=kangaroo type, b125..b0 distance

into:

union int256_s {

  uint8_t  i8[32];
  uint16_t i16[16];
  uint32_t i32[8];
  uint64_t i64[4];

I have seen something in another code that allows 256...I'll keep looking.

[NotATether]

That format code looks just about right.

~snip

into:

union int256_s {

  uint8_t  i8[32];
  uint16_t i16[16];
  uint32_t i32[8];
  uint64_t i64[4];
}

This is basically what I have in my local copy along with replacing all int128_t with int256_t.

In other news I installed CUDA toolkit on the T4 after I installed Ubuntu Nvidia drivers, and now the drivers aren't working (D'oh!!!) so now I have to reinstall the OS on that to wipe NVIDIA's mess off of it.

Why does driver installation have to be so complicated? Distros aren't helping by having their own versions of nvidia-drivers in their repos 

[Bobermart]

Question, i have say 1000 keys in my config, does it crack them all simultaneously?

Also if i wanted to check the entire keyspace for 128bit keys (yes i know this makes it astronomically harder and likely impossible) what would the first two lines of config file look like?

Its currently

0
FFFFFFFFFFFFFFFFFFFFFFFFF




Sorry for the newbie questions, this is for a school project, so help would be appreciated.

[fxsniper]

Question, i have say 1000 keys in my config, does it crack them all simultaneously?

Also if i wanted to check the entire keyspace for 128bit keys (yes i know this makes it astronomically harder and likely impossible) what would the first two lines of config file look like?

Its currently

0
FFFFFFFFFFFFFFFFFFFFFFFFF




Sorry for the newbie questions, this is for a school project, so help would be appreciated.

try this

example puzzle #40


puzzle40.txt

Code:

8000000000
FFFFFFFFFF
03A2EFA402FD5268400C77C20E574BA86409EDEDEE7C4020E4B9F0EDBEE53DE0D4

command  puzzle40.bat

Code:

Kangaroo.exe -ws  -o result40.txt -w puzzle40.work -wi 300 puzzle40.txt

then check fiel   result40.txt

[fxsniper]

recommend use sample file   puzzle32.txt

https://github.com/JeanLucPons/Kangaroo/blob/master/puzzle32.txt


more testing file

for longer test

puzzle #65  = 3-10 minute up to you CPU or GPU

command  puzzle65.bat

Code:

Kangaroo.exe -ws  -o result65.txt -w puzzle65.work -wi 300 puzzle65.txt

GPU

Code:

Kangaroo.exe -ws -gpu -o result65.txt -w puzzle65.work -wi 300 puzzle65.txt

puzzle65.txt

Code:

10000000000000000
1ffffffffffffffff
0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b

capital same

Code:

10000000000000000
1FFFFFFFFFFFFFFFF
0230210C23B1A047BC9BDBB13448E67DEDDC108946DE6DE639BCC75D47C0216B1B