Pollard's kangaroo ECDLP solver - page 76.

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: 1162

Merit: 237

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: 1162

Merit: 237

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: 1932

Merit: 2077

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: 1932

Merit: 2077

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: 1162

Merit: 237

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: 1162

Merit: 237

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?

paniker

newbie

Activity: 49

Merit: 0

Anyone get a pub #64 ?

pehu

newbie

Activity: 1

Merit: 0

Can anybody please explain me everything step by step i want to try solve some puzzles with my gtx1080 just for fan i got windows and Ubuntu 18.04 on it
i type
1. sudo apt -get install git - DONE
2. sudo git clone https://github.com/JeanLucPons/Kangaroo.git - DONE
3. cd Kangaroo - DONE
4. make - DONE
And iam here what to do next ? I got a txt file with BTC Adresses what else should i have and how to transfer this file directly to a program . Thanks a lot

mamuu

member

Activity: 73

Merit: 19

Quote from: MrFreeDragon on October 19, 2020, 07:09:57 AM

Quote from: mamuu on October 19, 2020, 06:30:54 AM

-snip-
I have some functions in Python and it runs very slow compared to C.

The sage I want to do with the GPU is as follows

Code:

Pr = 115792089237316195423570985008687907853269984665640564039457584007908834671663

E = EllipticCurve (GF (P), [0,7])
N = E.order ()

G = E(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424) # on E

T = E(26864879445837655118481716049217967286489564259939711339119540571911158650839,29571359081268663540055655726653840143920402820693420787986280659961264797165) # on E

numInt = 5646546546563131314723897429834729834798237429837498237498237489273948728934798237489723489723984729837489237498237498237498237498273493729847

numMod = numInt %N

numInv = pow(numMod ,N-2,N) # detail -> https://stackoverflow.com/questions/59234775/how-to-calculate-2-to-the-power-of-a-large-number-modulo-another-large-number


numMod * G
numMod * T

(T-G) * numInv 



print (5*T)
print (2*G)

print (numMod * G)
print (numMod * (-G))

print (numMod * T)
print ((numMod-3) * (T-G))

Do you have any suggestions? What should I do ?
I wrote my question here because it is indirectly related to this project. Please forgive.

Hi! The slowest part in your python is inverse function. Try to implement gmpy2 inverse function (included in gmpy2) - it is C-based and very fast:

https://www.lfd.uci.edu/~gohlke/pythonlibs/#gmpy

You can find the details here: https://bitcointalksearch.org/topic/m.55214449

Hello MrFreeDragon
Is it possible to write the python code you show with Cython?
Thanks again, my work was faster than before.

Code:

import gmpy2

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0X483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx,Gy)
Z = Point(0,0) # zero-point, infinite in real x,y - plane

# return (g, x, y) a*x + b*y = gcd(x, y)
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def modinv(m, n = modulo):
    while m < 0:
        m += n
    g, x, _ = egcd(m, n)
    if g == 1:
        return x % n

    else: print (' no inverse exist')

def mul2(Pmul2, p = modulo):
    R = Point(0,0)
    #c = 3*Pmul2.x*Pmul2.x*modinv(2*Pmul2.y, p) % p
    c = 3*Pmul2.x*Pmul2.x*gmpy2.invert(2*Pmul2.y, p) % p
    R.x = (c*c-2*Pmul2.x) % p
    R.y = (c*(Pmul2.x - R.x)-Pmul2.y) % p
    return R

def add(Padd, Q, p = modulo):
    if Padd.x == Padd.y == 0: return Q
    if Q.x == Q.y == 0: return Padd
    if Padd == Q: return mul2(Q)
    R = Point()
    dx = (Q.x - Padd.x) % p
    dy = (Q.y - Padd.y) % p
    c = dy * gmpy2.invert(dx, p) % p     
    #c = dy * modinv(dx, p) % p
    R.x = (c*c - Padd.x - Q.x) % p
    R.y = (c*(Padd.x - R.x) - Padd.y) % p
    return R # 6 sub, 3 mul, 1 inv

def mulk(k, Pmulk, p = modulo):
    if k == 0: return Z
    if k == 1: return Pmulk
    if (k % 2 == 0): return mulk(k//2, mul2(Pmulk, p), p)
    return add(Pmulk, mulk((k-1)//2, mul2(Pmulk, p), p), p)

gmaxwell

staff

Activity: 4242

Merit: 8672

Tools like this are an interesting intellectual challenge but don't do much of anything interesting, actual keys are not vulnerable to these attacks.

As a result it's normal for interest to wax and wane.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

brainless, your message looks like a conspiracy theory. However it is really strange that many GPU developers are not active for a long time.
Do you think they are all working on some huge project?

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