Pollard's kangaroo ECDLP solver - page 77.

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: MisterCooper on January 08, 2021, 04:31:37 PM

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

you can use the:

-m maxStep: number of operations before give up the search (maxStep*expected operation)

and the program will move to next pubkey if not found within -m operations

bigvito19

full member

Activity: 706

Merit: 111

Quote from: MisterCooper on January 08, 2021, 04:31:37 PM

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

For now it only search for 1 key at a time. When the first key is found then it goes to the next one.

MisterCooper

newbie

Activity: 30

Merit: 0

Today I tested Kangaroo 2.2 on the Ubuntu. Everything works great! Thanks a lot Jean_Luc!
Most of the participants in this discussion are programmers, and I have a question for you. How do you loop the MultiPubKey?
I would really like to search the list using different public keys in one specific range.

$upermoney

newbie

Activity: 23

Merit: 0

Anyone have luck installing Kangaroo on vast.ai platform? The Linux CUDA installation seems somewhat complex is there a streamlined process of exactly what to install?

dextronomous

full member

Activity: 431

Merit: 105

DP: 626,941,151 TP: 14,389,459,189,655,514

how much percentage of 120th puzzle should these dp and tp have reached, anyone?
thanks

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: bigvito19 on January 02, 2021, 08:46:59 AM

Can someone explain the ht max, ht min, ht avg, ht sdev means. Is that like how many times a DP has occurred in the table?

HT stands for Hash Table, it is used to store the kangaroo positions and distances. The statistics HT max, min, avg, sdev are just maximum, minimum, average and standard deviations of the number of kangaroos in each DP. The DP (1st argument pos) is slightly transformed (1st argument x passed to Convert() to get h) into keys (h in HashTable::Add(h,e)) in the hash table.

bigvito19

full member

Activity: 706

Merit: 111

Can someone explain the ht max, ht min, ht avg, ht sdev means. Is that like how many times a DP has occurred in the table?

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Here was the post I was talking about:

https://bitcointalksearch.org/topic/m.54564299

Anywho, like I said, I did not know that you could search for the same private key, in the same range, using the same distinguished point ( example = -d 29) and solve the exact same private key with two entirely different tame and wild points/coords and distances.

I also did not know that you could solve a 3 digit private key, example 0x1A2. in a keyspace search range such as 1A012BE379AC91023ADF:1A012BFFFFFFFFFFFFFF

And before anyone says that the program shifts down to zero, I wasn't using JLPs kangaroo program which shifts down, and the actual tame wild points/coords were obviously the same and the distances were like tame 1A012BE379AC91023ADF and wild 1A012BE3789A91023ADF

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: arulbero on December 31, 2020, 03:49:27 AM

Quote from: WanderingPhilospher on December 30, 2020, 03:29:51 PM

For the really smart people out there...I had read somewhere that a pubkey may have 2 X coordinates, maybe 3 X coordinates, can't really remember.

Each pubkey has only 1 X coordinate and 1 Y coordinate. And only 1 private key.

There are 2 pubkeys that share the same X coordinate (for each valid X coordinate) but they have different Y coordinates:

if A = (X,Y) then B = -A = (X, p-Y)

(p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1)

There are 3 pubkeys that share the same Y coordinate (for each valid Y coordinate) but they have different X coordinates:

if A = (X,Y) then B = k*A = (beta*X, Y) and C = k*k*A = (beta*beta*X, Y)

(k = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
and beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee)

There are about 2^256 points on secp256k1, (to be precise n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141) and Fp (the field of the coordinates X e Y) has about the same size;

that means that about 1/3 of the all possible values of Y are valid Y coordinates (are coordinates of a point/pub key) and about 1/2 of all the possible values of X are valid X coordinates.

That's all.

So within the Kangaroo program, with a Tame file:

Code:

4308F55406236F06FBBB5A328499E9F2787C64AC7779FD387BFBD803C0000000 00000000000000000000000000000000004448E8FD4C2B40AAF6E5C2D6A8A1E5

Are neither one of those the X coord? I read somewhere in this thread, that the above 4308F55406236F06FBBB5A328499E9F2787C64AC7779FD387BFBD803C0000000 was an X coord (034308f55406236f06fbbb5a328499e9f2787c64ac7779fd387bfbd803c0000000). Is that not true?

Because what I was saying, is that I have found the same exact private key, with different tame and wild coords/distances.

Meaning, if I was searching for private key 0x17A57BE2, using the Kangaroo program, I solved with different tame and wild files, example:

first solve tame:

Code:

4308F55406236F06FBBB5A328499E9F2787C64AC7779FD387BFBD803C0000000 00000000000000000000000000000000004448E8FD4C2B40AAF6E5C2D6A8A1E5[

first solve wild:

Code:

4308F55406236F06FBBB5A328499E9F2787C64AC7779FD387BFBD803C0000000 00000000000000000000000000000000000008E8FD4C2B40AAF6E5C2D6A8A1E5[

second solve tame:

Code:

DDD6055558606CB730B603F4ECF20B497A709FECF23671612A742FFBC0000000 000000000000000000000000000000000058D5A2BF77F6FA6D631B606B604BCE

second solve wild:

Code:

DDD6055558606CB730B603F4ECF20B497A709FECF23671612A742FFBC0000000 0000000000000000000000000000000000000002BF77F6FA6D631B606B604BCE

those are examples, not the actual wild and tame files I solved the one private key with.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: NotATether on December 31, 2020, 06:09:16 AM

Quote from: arulbero on December 31, 2020, 03:49:27 AM

that means that about 1/3 of the all possible values of Y are valid Y coordinates (are coordinates of a point/pub key) and about 1/2 of all the possible values of X are valid X coordinates.

Maybe we can use that as an optimization and go through all the X values, and check that (X² + 7) mod p gives a cubed number which would imply a valid Y. This would eliminate half of the search space. Similarly we can go through all the Y values and calculate Y³ mod p is a square number which implies a valid X and eliminate 2/3s of the search space.

Since the invalid points derived for each X and Y don't overlap, we have already removed 1/2 * 2/3 = 1/3 of the total possible search space like that.

256/3 128/3 64/3 does sound better than 256/2 128/2 64/2

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: NotATether on December 31, 2020, 06:09:16 AM

Since the invalid points derived for each X and Y don't overlap, we have already removed 1/2 * 2/3 = 1/3 of the total possible search space like that.

No, because all the tame and the wild move directly (jump) between the points (with valid coordinates); the points are about 2^256:

(1/2 * 2^256 X coordinates) * (2 valid Y coordinates) = 2^256 points.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: arulbero on December 31, 2020, 03:49:27 AM

that means that about 1/3 of the all possible values of Y are valid Y coordinates (are coordinates of a point/pub key) and about 1/2 of all the possible values of X are valid X coordinates.

Maybe we can use that as an optimization and go through all the X values, and check that (X² + 7) mod p gives a cubed number which would imply a valid Y. This would eliminate half of the search space. Similarly we can go through all the Y values and calculate Y³ mod p is a square number which implies a valid X and eliminate 2/3s of the search space.

Since the invalid points derived for each X and Y don't overlap, we have already removed 1/2 * 2/3 = 1/3 of the total possible search space like that.

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: WanderingPhilospher on December 30, 2020, 03:29:51 PM

For the really smart people out there...I had read somewhere that a pubkey may have 2 X coordinates, maybe 3 X coordinates, can't really remember.

Each pubkey has only 1 X coordinate and 1 Y coordinate. And only 1 private key.

There are 2 pubkeys that share the same X coordinate (for each valid X coordinate) but they have different Y coordinates:

if A = (X,Y) then B = -A = (X, p-Y)

(p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1)

There are 3 pubkeys that share the same Y coordinate (for each valid Y coordinate) but they have different X coordinates:

if A = (X,Y) then B = k*A = (beta*X, Y) and C = k*k*A = (beta*beta*X, Y)

(k = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
and beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee)

There are about 2^256 points on secp256k1, (to be precise n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141) and Fp (the field of the coordinates X e Y) has about the same size;

that means that about 1/3 of the all possible values of Y are valid Y coordinates (are coordinates of a point/pub key) and about 1/2 of all the possible values of X are valid X coordinates.

That's all.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: WanderingPhilospher on December 30, 2020, 03:29:51 PM

For the really smart people out there...I had read somewhere that a pubkey may have 2 X coordinates, maybe 3 X coordinates, can't really remember. But as I've been dabbling with Kangaroo program on and off for almost a year now, I know I have found same pub/priv key in same range, with two different tame and wild distances. I have also found keys let's say 12 bit keys, in ranges of upward of 64 bit range. And those were all with the same distinguished points. I wonder if one could find more tame and wild distances/coords by changing the distinguished point value, in the same range.

Anywho, just interesting to find same pub/priv key with different tame and wild distances/coords.

I always wanted to ask what's the probability of different distinguished points to the same pub/priv key.

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

For the really smart people out there...I had read somewhere that a pubkey may have 2 X coordinates, maybe 3 X coordinates, can't really remember. But as I've been dabbling with Kangaroo program on and off for almost a year now, I know I have found same pub/priv key in same range, with two different tame and wild distances. I have also found keys let's say 12 bit keys, in ranges of upward of 64 bit range. And those were all with the same distinguished points. I wonder if one could find more tame and wild distances/coords by changing the distinguished point value, in the same range.

Anywho, just interesting to find same pub/priv key with different tame and wild distances/coords.

$upermoney

newbie

Activity: 23

Merit: 0

Quote from: WanderingPhilospher on December 28, 2020, 11:55:43 AM

Quote from: $upermoney on December 28, 2020, 11:24:32 AM

Quote from: NotATether on December 28, 2020, 03:28:56 AM

Quote from: $upermoney on December 27, 2020, 09:00:47 PM

I want to test this on a private key I already know. How do I set up the in.txt file if I wanted to use 90% of the key, but change the last to 00000000 through FFFFFFFF?

The start and the end ranges of the key go in the first and second lines of the input file respectively, and you change the last digits of the range to your start and end keys.

Here Jean_Luc has an uncompressed and compressed public key on the third and fourth lines. You can use either as long as you type it after the range.

Quote from: https://github.com/JeanLucPons/Kangaroo

Structure of the input file:

All values are in hex format
Public keys can be given either in compressed or uncompressed format
Start range
End range
Key #1
Key #2
...
ex

Code:

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
0335BB25364370D4DD14A9FC2B406D398C4B53C85BE58FCC7297BD34004602EBEC

Yes this is exactly what I did but was not finding it. Lots of dead kangaroos and it just kept running even though it should have taken less than a few seconds? I only had 000000 - FFFFFF at the end

Would have to see your key and range (and possibly your command line info) to verify that you didn't load something wrong or if in fact the program didn't find a key it should have.

Nevermind I was using the wrong private key. Is there a reason https://iancoleman.io/bitcoin-key-compression/ doesn't list the private key in HEX format?

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: $upermoney on December 28, 2020, 11:24:32 AM

Quote from: NotATether on December 28, 2020, 03:28:56 AM

Quote from: $upermoney on December 27, 2020, 09:00:47 PM

I want to test this on a private key I already know. How do I set up the in.txt file if I wanted to use 90% of the key, but change the last to 00000000 through FFFFFFFF?

The start and the end ranges of the key go in the first and second lines of the input file respectively, and you change the last digits of the range to your start and end keys.

Here Jean_Luc has an uncompressed and compressed public key on the third and fourth lines. You can use either as long as you type it after the range.

Quote from: https://github.com/JeanLucPons/Kangaroo

Structure of the input file:

All values are in hex format
Public keys can be given either in compressed or uncompressed format
Start range
End range
Key #1
Key #2
...
ex

Code:

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
0335BB25364370D4DD14A9FC2B406D398C4B53C85BE58FCC7297BD34004602EBEC

Yes this is exactly what I did but was not finding it. Lots of dead kangaroos and it just kept running even though it should have taken less than a few seconds? I only had 000000 - FFFFFF at the end

Would have to see your key and range (and possibly your command line info) to verify that you didn't load something wrong or if in fact the program didn't find a key it should have.

$upermoney

newbie

Activity: 23

Merit: 0

Quote from: NotATether on December 28, 2020, 03:28:56 AM

Quote from: $upermoney on December 27, 2020, 09:00:47 PM

I want to test this on a private key I already know. How do I set up the in.txt file if I wanted to use 90% of the key, but change the last to 00000000 through FFFFFFFF?

The start and the end ranges of the key go in the first and second lines of the input file respectively, and you change the last digits of the range to your start and end keys.

Here Jean_Luc has an uncompressed and compressed public key on the third and fourth lines. You can use either as long as you type it after the range.

Quote from: https://github.com/JeanLucPons/Kangaroo

Structure of the input file:

All values are in hex format
Public keys can be given either in compressed or uncompressed format
Start range
End range
Key #1
Key #2
...
ex

Code:

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
0335BB25364370D4DD14A9FC2B406D398C4B53C85BE58FCC7297BD34004602EBEC

Yes this is exactly what I did but was not finding it. Lots of dead kangaroos and it just kept running even though it should have taken less than a few seconds? I only had 000000 - FFFFFF at the end

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: $upermoney on December 27, 2020, 09:00:47 PM

I want to test this on a private key I already know. How do I set up the in.txt file if I wanted to use 90% of the key, but change the last to 00000000 through FFFFFFFF?

The start and the end ranges of the key go in the first and second lines of the input file respectively, and you change the last digits of the range to your start and end keys.

Here Jean_Luc has an uncompressed and compressed public key on the third and fourth lines. You can use either as long as you type it after the range.

Quote from: https://github.com/JeanLucPons/Kangaroo

Structure of the input file:

All values are in hex format
Public keys can be given either in compressed or uncompressed format
Start range
End range
Key #1
Key #2
...
ex

Code:

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
0335BB25364370D4DD14A9FC2B406D398C4B53C85BE58FCC7297BD34004602EBEC

$upermoney

newbie

Activity: 23

Merit: 0

I want to test this on a private key I already know. How do I set up the in.txt file if I wanted to use 90% of the key, but change the last to 00000000 through FFFFFFFF?

Topic: Pollard's kangaroo ECDLP solver - page 77. (Read 60189 times)