Pollard's kangaroo ECDLP solver

[wedom]

from fastecdsa import curve
from fastecdsa.point import Point
import bit

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)

G = curve.secp256k1.G
N = curve.secp256k1.q
DIV = '02AE3482B19E840288CC9B302AD9F5DC017AB796D3690CC8029017A8AF3503BE8E'
pubkey = '03ec0f4d728d248698a59d3a50a0469da06fdb8019700dfc5de9eae2dd93fc2bc8'

Q = pub2point(pubkey)
R = pub2point(DIV)
z= Q / R

print(z)


-----------------------------------------
>>>    z= Q / R
TypeError: unsupported operand type(s) for /: 'Point' and 'Point'




CAN ANYONE HELP,HOW TO CORRECT THIS

THANKS

You can't divide a point by a point. A point can only be multiplied by a number. In this case we are multiplying by an inverse number, thus imitating the division of a point by a number.

Code:

from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)

DIV = 123456789
d = pow(DIV, N - 2, N)

pubkey = '03ec0f4d728d248698a59d3a50a0469da06fdb8019700dfc5de9eae2dd93fc2bc8'
Q = pub2point(pubkey)
z = Q * d

print(z)

[1714511036]

1714511036

[1714511036]

1714511036

[1714511036]

1714511036

[NotATether]

Guys, do you think I should convert these [my] python scripts into a library, with it's own PIP page and docs? So that people no longer make fundamental errors when using them and then calling me for tech support...

[Evillo]

Guys, do you think I should convert these [my] python scripts into a library, with it's own PIP page and docs? So that people no longer make fundamental errors when using them and then calling me for tech support...

Lol Yess!

[Evillo]

Guys, do you think I should convert these [my] python scripts into a library, with it's own PIP page and docs? So that people no longer make fundamental errors when using them and then calling me for tech support...

It's good idea, i think you should do it. Make sure setup script include version of required dependency (e.g. numpy==1.23.1 or numpy>=1.20,<=1.23 rather than numpy) to save headache in future if dependency API changed.

Good idea .. due to things like this, i once spent 2 hours trying to fully install a library .. a lot of searching and navigating through stackexchange and quora.. such a waste of time and energy

[brainless]

-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

When using Python, I use FastEcdsa(https://github.com/AntonKueltz/fastecdsa) library and mathematics similar to Sage. But can I do the math faster? I want to understand.
The FastEcdsa Library is fast, but I don't know if it uses the gmpy2 you suggested. My python script uses 17% of the CPU as a result. I wanted to write with Anaconda (for GPU), but I could not find a gpu running as fast as C or I could not.

Thank you MrFreeDragon .

No. you can't be faster then GPU on your CPU.

if i explain your word in easy example commands for new gpu based develop application/repo, by jean luc or other developer, could be develop, or if any one know already developed can post links and refferance

here are some example aspected commands
./vs-pub -c  -gpu -input in.txt -output out.txt -add 0250863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 #pubkey
./vs-pub -c  -gpu -input in.txt -output out.txt -mul 123456789 # its privatekey in num (not hex)
./vs-pub -c  -gpu -input in.txt -output out.txt -sub 0250863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 #pubkey
./vs-pub -c  -gpu -input in.txt -output out.txt -sub 0250863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 -r (reverse like
02508... pubkey substract to all listed pubkey inside in.txt
-c is compressed pubkey
-u is uncompressed pubkey
-input is load of compressed/uncompressed pubkeys list
-output is results output to file
-r is reverse of sub ( listed pubkey in command minus(-) in.txt (pubkeys)

had any cuda dev  worked on these commnand based some scripts ?

[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

When using Python, I use FastEcdsa(https://github.com/AntonKueltz/fastecdsa) library and mathematics similar to Sage. But can I do the math faster? I want to understand.
The FastEcdsa Library is fast, but I don't know if it uses the gmpy2 you suggested. My python script uses 17% of the CPU as a result. I wanted to write with Anaconda (for GPU), but I could not find a gpu running as fast as C or I could not.

Thank you MrFreeDragon .

No. you can't be faster then GPU on your CPU.

if i explain your word in easy example commands for new gpu based develop application/repo, by jean luc or other developer, could be develop, or if any one know already developed can post links and refferance

here are some example aspected commands
./vs-pub -c  -gpu -input in.txt -output out.txt -add 0250863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 #pubkey
./vs-pub -c  -gpu -input in.txt -output out.txt -mul 123456789 # its privatekey in num (not hex)
./vs-pub -c  -gpu -input in.txt -output out.txt -sub 0250863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 #pubkey
./vs-pub -c  -gpu -input in.txt -output out.txt -sub 0250863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 -r (reverse like
02508... pubkey substract to all listed pubkey inside in.txt
-c is compressed pubkey
-u is uncompressed pubkey
-input is load of compressed/uncompressed pubkeys list
-output is results output to file
-r is reverse of sub ( listed pubkey in command minus(-) in.txt (pubkeys)

had any cuda dev  worked on these commnand based some scripts ?

I haven't tried the command version.
but the last time I checked, there was a cuda-based large number library. development continued.

https://github.com/NVlabs/CGBN

I've been searching the Elliptic Curve Arithmetic library to experiment on cuda.

[Evillo]

Speaking of faster .. i have a question that is bugging me ..common sense would suggest that gpu is always faster by many folds than cpu .. but how in the hell is my cpu faster?! Here is what i did..
Tried kangaroo on gtx 1070 : GREAT speed
Tried keyhunt BSGS mode: just way faster?!?!
What gives? How come a gpu program would yield test results in more time than a cpu one? Am i doing something wrong concerning the gpu part? I only stick to default commands on both .. except that keyhunt BSGS uses as much memory as you want it to as long as you have enough for it .. which gives you a speed pump with every increase in memory allocation!

If anyone tried both too and got the same thing please enlighten me. Thnx

[NotATether]

What gives? How come a gpu program would yield test results in more time than a cpu one? Am i doing something wrong concerning the gpu part? I only stick to default commands on both .. except that keyhunt BSGS uses as much memory as you want it to as long as you have enough for it .. which gives you a speed pump with every increase in memory allocation!

That's basically what's going on.

GPUs have about as much on-board memory as a small computer has RAM. CUDA can only use the onboard memory, because there is a large performance penalty in moving data between host and device that will neutralize any "hacks" and "tricks" the code does.

[fxsniper]

What gives? How come a gpu program would yield test results in more time than a cpu one? Am i doing something wrong concerning the gpu part? I only stick to default commands on both .. except that keyhunt BSGS uses as much memory as you want it to as long as you have enough for it .. which gives you a speed pump with every increase in memory allocation!

you need to know how it works
I am not an expert but I understand basic and overview (not sure I understand clear all)

kangaroo and BSGS both have some different technic and some parts same technic
kangaroo work like blind two people walk to hits each other if both walks hit your found key but if not never found a key kangaroo is a technic walk to hit spot it fast when using GPU but if blind walk in a small room with hit easy but both blind walking in a football field or in sea, kangaroo not use much memory on PC but using fast speed to walk that is calculated point to jump by use GPU make blind  walk faster until hits
if kangaroo use wrong jump it will take time a lot and never hit mostly is still have a problem when walk in space

BSGS uses store million/billion points in memory that it is made to use more memory
babystep gientstep,  babystep is small point quantity million point start if choose babystep large size will using large memory on PC, and then giant step is babystep to move next position next and next until cover your spot
point quantity 1 million lines using storage save on disk 70MB and point 10 million using space 700MB and 100 million use 7GB storage save on harddisk so, on memory it same if boomfile is large will use on memory large
if use a small size babystep will using time compare using 1 million and use 2.5 hundred thousand 4 time
maybe imagine using table in excel spredsheet first table is babastep and change the table to giantstep
or maybe imagine like raining in a small area and clouds move to hit your spot if large could rain in a wide area using large memory

gtx 1070 has 8GB memory
kangaroo uses GPU and use 8GB on the card
but BSGS use memory on PC if have 32GB or 64GB will be can use large size of babystep

first time I doubt why not make BSGS use on GPU for faster
try BSGS solver for Cuda ( Purebasic v5.31)
understand try iceland2k14/bsgs/v1_fastecdsa

[isaah23]

Can anyone explain, there is any chance to use it in btc mainnet?
There is any vulnerability addresses in blockchain that can be hacked with kangaroo ecdlp solver?
Or it's nearly impossible to retrieve private key only from public key and outgoing transactions?

[Evillo]

Can anyone explain, there is any chance to use it in btc mainnet?
There is any vulnerability addresses in blockchain that can be hacked with kangaroo ecdlp solver?
Or it's nearly impossible to retrieve private key only from public key and outgoing transactions?

I tried with more than 45k public keys of top btc wallets but as i expected, months and months passed without a single private key retrieved .. because in such case you are searching the entire range of private keys using your public keys with kangaroo .. and no animal in the world could ever jump that high 😉

[Evillo]

What gives? How come a gpu program would yield test results in more time than a cpu one? Am i doing something wrong concerning the gpu part? I only stick to default commands on both .. except that keyhunt BSGS uses as much memory as you want it to as long as you have enough for it .. which gives you a speed pump with every increase in memory allocation!

That's basically what's going on.

GPUs have about as much on-board memory as a small computer has RAM. CUDA can only use the onboard memory, because there is a large performance penalty in moving data between host and device that will neutralize any "hacks" and "tricks" the code does.

Got it .. thanks 👍

[bigvito19]

Can anyone explain, there is any chance to use it in btc mainnet?
There is any vulnerability addresses in blockchain that can be hacked with kangaroo ecdlp solver?
Or it's nearly impossible to retrieve private key only from public key and outgoing transactions?

I tried with more than 45k public keys of top btc wallets but as i expected, months and months passed without a single private key retrieved .. because in such case you are searching the entire range of private keys using your public keys with kangaroo .. and no animal in the world could ever jump that high 😉

You was searching 45k public keys at the same time with kangaroo?

[fxsniper]

Can anyone explain, there is any chance to use it in btc mainnet?
There is any vulnerability addresses in blockchain that can be hacked with kangaroo ecdlp solver?
Or it's nearly impossible to retrieve private key only from public key and outgoing transactions?

I tried with more than 45k public keys of top btc wallets but as i expected, months and months passed without a single private key retrieved .. because in such case you are searching the entire range of private keys using your public keys with kangaroo .. and no animal in the world could ever jump that high 😉

You was searching 45k public keys at the same time with kangaroo?

kangaroo can search only one public key each time if have multiple pubkey setups first pubkey will be search
kangaroo can not search multiple keys in the same time because it is use pubkey that search to calculate multiply number for the search
if search multiple pubkey at the same time that means your kangaroo program or script will be worked by calculating multiply many key in the same time
JeanLucPons Kangaroo and another kangaroo in Github work by searching one key

first time I looking for kangaroo or other program that can search multiple pubkey in same time too but not have one becuase it is work by one pubkey search

[Evillo]

Can anyone explain, there is any chance to use it in btc mainnet?
There is any vulnerability addresses in blockchain that can be hacked with kangaroo ecdlp solver?
Or it's nearly impossible to retrieve private key only from public key and outgoing transactions?

I tried with more than 45k public keys of top btc wallets but as i expected, months and months passed without a single private key retrieved .. because in such case you are searching the entire range of private keys using your public keys with kangaroo .. and no animal in the world could ever jump that high 😉

You was searching 45k public keys at the same time with kangaroo?

kangaroo can search only one public key each time if have multiple pubkey setups first pubkey will be search
kangaroo can not search multiple keys in the same time because it is use pubkey that search to calculate multiply number for the search
if search multiple pubkey at the same time that means your kangaroo program or script will be worked by calculating multiply many key in the same time
JeanLucPons Kangaroo and another kangaroo in Github work by searching one key

first time I looking for kangaroo or other program that can search multiple pubkey in same time too but not have one becuase it is work by one pubkey search

I know all that ..for multi keys i never use kangaroo i use keyhunt BSGS mode .. it can search millions of pubkeys at a time but .. and that's a big but .. every single pubkey you add to the list, is gonna cut your speed greatly.. so it's a tradeoff .. but still, result is it would take eternity for you to calculate even a single key out of this .. like i said, tried for several months uninterrupted and got nothing .. nil .. zilch .. the 2^256 range is unimaginably large that even quantum computers would look like an infant trying to squeeze a mountain with its palm

[Milo22]

Can anyone explain, there is any chance to use it in btc mainnet?
There is any vulnerability addresses in blockchain that can be hacked with kangaroo ecdlp solver?
Or it's nearly impossible to retrieve private key only from public key and outgoing transactions?

I tried with more than 45k public keys of top btc wallets but as i expected, months and months passed without a single private key retrieved .. because in such case you are searching the entire range of private keys using your public keys with kangaroo .. and no animal in the world could ever jump that high 😉

Did you use this Kangaroo tool? Because when I use it with multiple keys it doesn't pass to the next one if the previous key is not in the specified range. I don't know if it's only my problem or I should use a command or something.

[BHWallet]

So there are 2^96 different private keys in the entire 2^256 space that can "unlock" for example this address: 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (Puzzle 64)? Can anyone confirm this?

[CrunchyF]

So there are 2^96 different private keys in the entire 2^256 space that can "unlock" for example this address: 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (Puzzle 64)? Can anyone confirm this?

Yes exactly and for a simple fact :

16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (and every other wallet address of this type) is encoded on 160 bits (and not on 256 bits like the majority of other crypto parameters in bitcoin protocol)
16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN is base58 encoded and is 3ee4133d991f52fdf6a25c9834e0745ac74248a4 (20*8bytes = 160bits) in hexadecimal
(
Unlike public keys that are encoded on 256 bits

a simple wallet address (p2pkh) is simply obtained by the function hash160(public_key)

So if you have the possibility to browse the entire 1-2^256 space and to compute the hash160 function for every hash160(public_key)  derived from 1-2^256 private keys you will find an average of 2^(256-160) = 2^96 public key with hash160=16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN .


But even if 2^96 seems big its far away smaller from 2^256. And it's pretty impossible to have a collision between two random public key in the using age of bitcoin.

But theoretically if you find any public key derived from a private key with hash160(public_key)=  '16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN' or = to any other non zero wallet address you will able to unlock the coins.

Because the verification in the bitcoin protocol to prove that you are the owner of the private key is simply "have you signed the transaction with the private key associated to a public key that gives 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (or any other target address) with hash160 function

[Evillo]

So there are 2^96 different private keys in the entire 2^256 space that can "unlock" for example this address: 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (Puzzle 64)? Can anyone confirm this?

Yes exactly and for a simple fact :

16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (and every other wallet address of this type) is encoded on 160 bits (and not on 256 bits like the majority of other crypto parameters in bitcoin protocol)
16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN is base58 encoded and is 3ee4133d991f52fdf6a25c9834e0745ac74248a4 (20*8bytes = 160bits) in hexadecimal
(
Unlike public keys that are encoded on 256 bits

a simple wallet address (p2pkh) is simply obtained by the function hash160(public_key)

So if you have the possibility to browse the entire 1-2^256 space and to compute the hash160 function for every hash160(public_key)  derived from 1-2^256 private keys you will find an average of 2^(256-160) = 2^96 public key with hash160=16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN .


But even if 2^96 seems big its far away smaller from 2^256. And it's pretty impossible to have a collision between two random public key in the using age of bitcoin.

But theoretically if you find any public key derived from a private key with hash160(public_key)=  '16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN' or = to any other non zero wallet address you will able to unlock the coins.

Because the verification in the bitcoin protocol to prove that you are the owner of the private key is simply "have you signed the transaction with the private key associated to a public key that gives 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN (or any other target address) with hash160 function

Couldn't have said it better .. in theory, there are enormous amount of private keys that open one single wallet .. i read somewhere that they found some collisions but were empty wallets .. however, there have been no claims about finding any UTOX with collisions .. although i tend to expect that even when found, it will never be announced .. it would hurt the technology and hurt bitcoin specifically

[Cricktor]

a simple wallet address (p2pkh) is simply obtained by the function hash160(public_key)

So if you have the possibility to browse the entire 1-2^256 space and to compute the hash160 function for every hash160(public_key)  derived from 1-2^256 private keys you will find an average of 2^(256-160) = 2^96 public key with hash160=16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN .

For the public address (p2pkh) you perform the following two nested hash functions RIPEMD160(SHA256(public_key)) as far as I remember.

It doesn't spoil your further calculation too much, but the valid range for private keys is any 256-bit number from 0x1 to 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140. Anyway, you're in the correct ballpark.