Pollard's kangaroo ECDLP solver

[dextronomous]

is there a bsgs gpu version out there, anywhere guys?
any news under the sun, love to read something new and great
once again in here,

 

[1715566565]

1715566565

[1715566565]

1715566565

[1715566565]

1715566565

[dptrdm]

How can i use saved work file for another public key?

[bigvito19]

How can i use saved work file for another public key?

You can't do that, you will have to start over with a new public key.

[bigvito19]

is there a bsgs gpu version out there, anywhere guys?
any news under the sun, love to read something new and great
once again in here,

 

Its not a BSGS with a GPU yet and no new updates yet.

[alevlaslo]

where the processed keys are stored, why the RAM consumption has not increased in 8 days, only 5.5 MB ?

[bigvito19]

where the processed keys are stored, why the RAM consumption has not increased in 8 days, only 5.5 MB ?

You got your DP set at 64, you got to go through 2^64 keys to get a DP, lower your DP so you can collect more DP's. Then you need to save your DP's, example:

Kangaroo.exe -ws -w save.work -wi 30 in.txt

[brainless]

Jeanluc not apear from
Last Active:   October 31, 2020, 10:19:32 AM

any one have in contact with him, live not infected covid19, all ok with him,
from june most GPU developer are goes offline, like BitCrack, Alek-76, Telaurist, other same worked on forked, all offline from long time, no more GPU based developments,
any comments ?

[MrFreeDragon]

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?

[gmaxwell]

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.

[mamuu]

-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://bitcointalk.org/index.php?topic=5245379.msg55214449#msg55214449

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)

[pehu]

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 

[paniker]

Anyone get a pub #64 ?

[$upermoney]

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?

[NotATether]

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.

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]

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.

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

[WanderingPhilospher]

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.

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]

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.

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]

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.

[bigvito19]

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.

[arulbero]

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.