Pollard's kangaroo ECDLP solver - page 69.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: Bobermart on March 12, 2021, 02:08:01 AM

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.

If you have 1000 keys in your input file, and you don't know if they exist in the range or not, you will have to use the -m option or the program will search for the first key from now until infinity times infinity...

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: Bobermart on March 12, 2021, 06:54:46 AM

So what did original 2009 - 2012 bitcoin wallets generate? 64bit keys?

I am not aware of any wallet software (Bitcoin Core or otherwise) that used anything other than 256-bit keys.

At one point in time, people made private keys out of so called "brain wallets" which are just random strings SHA256'ed into a hash that generated public and private keys. [Some people even used public base58 addresses as input to SHA256.]

Bobermart

newbie

Activity: 3

Merit: 0

Quote from: NotATether on March 12, 2021, 06:24:56 AM

Quote from: Bobermart on March 12, 2021, 03:52:45 AM

Ok thanks, so lets say i wanted to attempt to solve/crack a private key for a 128bit key, or 256bit key, is there a setting, or how do i program it to crack that, or is it just automatic?

By using

0
FFFFFFFFFFFFFFFFFFFFFFFFF

will that check the entire keyspace of a standard 128bit key?

The size to search in (and the keys which can be cracked) is determined by (end range - start range), second - first line.

Any range bigger than 125 bits currently isn't possible. The range variable itself has 126 bits free but there is some operation I can't recall right now that's done on it which limits the range to 125 bits.

I'm working on a patch to fix this. I have no ETA for it though, but I would like to get it ready within a week or two.

Excellent! i look forward to this, i would donate for this.

So what did original 2009 - 2012 bitcoin wallets generate? 64bit keys?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: Bobermart on March 12, 2021, 03:52:45 AM

Ok thanks, so lets say i wanted to attempt to solve/crack a private key for a 128bit key, or 256bit key, is there a setting, or how do i program it to crack that, or is it just automatic?

By using

0
FFFFFFFFFFFFFFFFFFFFFFFFF

will that check the entire keyspace of a standard 128bit key?

The size to search in (and the keys which can be cracked) is determined by (end range - start range), second - first line.

Any range bigger than 125 bits currently isn't possible. The range variable itself has 126 bits free but there is some operation I can't recall right now that's done on it which limits the range to 125 bits.

I'm working on a patch to fix this. I have no ETA for it though, but I would like to get it ready within a week or two.

EDIT: Wheee, I have to play GPU availability roulette again, this sucks Angry

fxsniper

member

Activity: 406

Merit: 47

Quote from: Bobermart on March 12, 2021, 03:52:45 AM

Ok thanks, so lets say i wanted to attempt to solve/crack a private key for a 128bit key, or 256bit key, is there a setting, or how do i program it to crack that, or is it just automatic?

By using

0
FFFFFFFFFFFFFFFFFFFFFFFFF

will that check the entire keyspace of a standard 128bit key?

Can you code?

for very high 128bit key, or 256bit key you need to upgrade or find the way works better and smart than current kangaroo for reduce time use find key

now puzzle 120 bits keys still un solve

Bobermart

newbie

Activity: 3

Merit: 0

Quote from: NotATether on March 12, 2021, 03:47:47 AM

Quote from: Bobermart on March 12, 2021, 02:08:01 AM

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

Yes (if for loop iteration counts as simultaneous Grin

Only the GPU truly cracks the keys simultaneously up to a certain number at once)

Quote from: Bobermart on March 12, 2021, 02:08:01 AM

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

Yeah that looks about right, if it doesn't work, pad them with zeros on the left until they are 64 characters long each.

Quote from: Bobermart on March 12, 2021, 02:08:01 AM

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

That's very cool, first time I saw one interested in discrete log solvers.

Ok thanks, so lets say i wanted to attempt to solve/crack a private key for a 128bit key, or 256bit key, is there a setting, or how do i program it to crack that, or is it just automatic?

By using

0
FFFFFFFFFFFFFFFFFFFFFFFFF

will that check the entire keyspace of a standard 128bit key?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: Bobermart on March 12, 2021, 02:08:01 AM

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

Yes (if for loop iteration counts as simultaneous Grin

Only the GPU truly cracks the keys simultaneously up to a certain number at once)

Quote from: Bobermart on March 12, 2021, 02:08:01 AM

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

Yeah that looks about right, if it doesn't work, pad them with zeros on the left until they are 64 characters long each.

Quote from: Bobermart on March 12, 2021, 02:08:01 AM

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

That's very cool, first time I saw one interested in discrete log solvers.

fxsniper

member

Activity: 406

Merit: 47

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

fxsniper

member

Activity: 406

Merit: 47

Quote from: Bobermart on March 12, 2021, 02:08:01 AM

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

Bobermart

newbie

Activity: 3

Merit: 0

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.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

That format code looks just about right.

Quote from: WanderingPhilospher on March 11, 2021, 09:02:50 PM

~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 Undecided

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote

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.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: NotATether on March 11, 2021, 06:55:49 PM

Quote from: bigvito19 on March 11, 2021, 08:30:29 AM

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 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...

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: bigvito19 on March 11, 2021, 08:30:29 AM

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 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.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: fxsniper on March 10, 2021, 08:59:17 PM

Quote from: NotATether on March 10, 2021, 01:36:55 PM

Where in the warping cyberspace is "PRIx64" defined? Huh

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?

Quote from: NotATether on March 06, 2021, 08:35:03 AM

Quote from: fxsniper on March 06, 2021, 03:23:21 AM

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

fxsniper

member

Activity: 406

Merit: 47

Quote from: NotATether on March 10, 2021, 01:36:55 PM

Where in the warping cyberspace is "PRIx64" defined? Huh

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?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Where in the warping cyberspace is "PRIx64" defined? Huh

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=

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: fxsniper on March 10, 2021, 06:35:22 AM

Quote from: NotATether on March 10, 2021, 05:04:16 AM

Quote from: fxsniper on March 07, 2021, 11:42:27 PM

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)

fxsniper

member

Activity: 406

Merit: 47

Quote from: NotATether on March 10, 2021, 05:04:16 AM

Quote from: fxsniper on March 07, 2021, 11:42:27 PM

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.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: fxsniper on March 07, 2021, 11:42:27 PM

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.

Topic: Pollard's kangaroo ECDLP solver - page 69. (Read 58537 times)