Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 15. (Read 56355 times)

member
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
August 18, 2022, 06:20:22 PM
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 😉
newbie
Activity: 2
Merit: 1
August 17, 2022, 05:51:36 PM
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?
member
Activity: 406
Merit: 45
August 17, 2022, 04:01:35 AM
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
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
August 15, 2022, 01:06:44 AM
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.
member
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
August 14, 2022, 05:44:01 PM
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
member
Activity: 72
Merit: 19
August 13, 2022, 04:15:00 PM
-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

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.
member
Activity: 316
Merit: 34
August 13, 2022, 05:35:17 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

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 ?
member
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
August 01, 2022, 08:46:51 AM
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
member
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
July 30, 2022, 11:36:27 AM
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!
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
July 29, 2022, 11:46:47 PM
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...
jr. member
Activity: 48
Merit: 11
July 29, 2022, 10:00:24 AM
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)

newbie
Activity: 14
Merit: 0
July 29, 2022, 08:52:58 AM
from fastecdsa import curve
from fastecdsa.point import Point
import bit

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

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)


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
member
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
July 24, 2022, 07:07:46 PM
I think if it was that easy to crack 64, someone would have tweaked the version to become 64bit .. but looks like it's already been done in secret but still unsolvable, or no one has the knowledge to do it yet .. tools like bitcrack and keyhunt makes me regret not taking cpp seriously back in my enthusiastic days .. but overall, devs like these taught me a lot more than i thought i know about bitcoin

As a C++ dev, I can tell you that the language is not the obsticle to designing these programs, but it's the knowledge required for curves, finite fields, groups, etc AND implementing all that in C++ or even JS, I'm sure I left out a ton of number theory topics from this list that are required studying as well [not to mention that GPU programming is done in a completely different language that is extremely difficult to debug].


So basically the biggest barriers are knowledge of cryptography, extensive Math, and gpu-specific programming 🤔
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
July 23, 2022, 07:14:50 AM
I think if it was that easy to crack 64, someone would have tweaked the version to become 64bit .. but looks like it's already been done in secret but still unsolvable, or no one has the knowledge to do it yet .. tools like bitcrack and keyhunt makes me regret not taking cpp seriously back in my enthusiastic days .. but overall, devs like these taught me a lot more than i thought i know about bitcoin

As a C++ dev, I can tell you that the language is not the obsticle to designing these programs, but it's the knowledge required for curves, finite fields, groups, etc AND implementing all that in C++ or even JS, I'm sure I left out a ton of number theory topics from this list that are required studying as well [not to mention that GPU programming is done in a completely different language that is extremely difficult to debug].
member
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
July 22, 2022, 04:05:28 AM
Did everyone gave up on the challenges/puzzles?  Huh Huh  Undecided Cry

Well, if zeilar managed to clear 20% of the keyspace for #120, it should not be too hard for someone to construct a DC and put an end to that key.

Or maybe puzzle solving is becoming more like mining, where it's only done when BTC price is profitable, only without those pesky ASICs and difficulty levels, hmmmm....


Or maybe 120 and 64 are the roofs in current technology .. it really seems so hard to crack those two .. been trying it for months now using multiple workarounds and tweaks but they're still out there unsolvable .. not to mention that the more resources you put into this, the more you realize you need even more resources .. hats off to Satoshi, this puzzle proved that best case scenario is you can only crack a private key of 119 bits out of the PRACTICAL staggering 256 bits .. cracking bitcoin is simply impossible, at least for this generation and under current tech

115 bits is the ceiling, actually, when you have the public key - as Pollard's Kangaroo uses a faster iterative algorithm to guess the private key.

63 when you only have the address. But then again, Bitcrack's linear search is not optimized, and I suspect that a GPU farm could solve #64 if only it had a 64-bit version of Bitcrack (the current version uses only 32-bit words) and an optional bit pattern filter to filter out long sequences of zeros and ones.

I think if it was that easy to crack 64, someone would have tweaked the version to become 64bit .. but looks like it's already been done in secret but still unsolvable, or no one has the knowledge to do it yet .. tools like bitcrack and keyhunt makes me regret not taking cpp seriously back in my enthusiastic days .. but overall, devs like these taught me a lot more than i thought i know about bitcoin
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
July 19, 2022, 08:42:44 AM
Did everyone gave up on the challenges/puzzles?  Huh Huh  Undecided Cry

Well, if zeilar managed to clear 20% of the keyspace for #120, it should not be too hard for someone to construct a DC and put an end to that key.

Or maybe puzzle solving is becoming more like mining, where it's only done when BTC price is profitable, only without those pesky ASICs and difficulty levels, hmmmm....


Or maybe 120 and 64 are the roofs in current technology .. it really seems so hard to crack those two .. been trying it for months now using multiple workarounds and tweaks but they're still out there unsolvable .. not to mention that the more resources you put into this, the more you realize you need even more resources .. hats off to Satoshi, this puzzle proved that best case scenario is you can only crack a private key of 119 bits out of the PRACTICAL staggering 256 bits .. cracking bitcoin is simply impossible, at least for this generation and under current tech

115 bits is the ceiling, actually, when you have the public key - as Pollard's Kangaroo uses a faster iterative algorithm to guess the private key.

63 when you only have the address. But then again, Bitcrack's linear search is not optimized, and I suspect that a GPU farm could solve #64 if only it had a 64-bit version of Bitcrack (the current version uses only 32-bit words) and an optional bit pattern filter to filter out long sequences of zeros and ones.
member
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
July 19, 2022, 05:37:26 AM
Did everyone gave up on the challenges/puzzles?  Huh Huh  Undecided Cry

Well, if zeilar managed to clear 20% of the keyspace for #120, it should not be too hard for someone to construct a DC and put an end to that key.

Or maybe puzzle solving is becoming more like mining, where it's only done when BTC price is profitable, only without those pesky ASICs and difficulty levels, hmmmm....


Or maybe 120 and 64 are the roofs in current technology .. it really seems so hard to crack those two .. been trying it for months now using multiple workarounds and tweaks but they're still out there unsolvable .. not to mention that the more resources you put into this, the more you realize you need even more resources .. hats off to Satoshi, this puzzle proved that best case scenario is you can only crack a private key of 119 bits out of the PRACTICAL staggering 256 bits .. cracking bitcoin is simply impossible, at least for this generation and under current tech
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
July 17, 2022, 11:53:26 PM
Did everyone gave up on the challenges/puzzles?  Huh Huh  Undecided Cry

Well, if zeilar managed to clear 20% of the keyspace for #120, it should not be too hard for someone to construct a DC and put an end to that key.

Or maybe puzzle solving is becoming more like mining, where it's only done when BTC price is profitable, only without those pesky ASICs and difficulty levels, hmmmm....
member
Activity: 177
Merit: 14
July 17, 2022, 01:49:42 PM
Did everyone gave up on the challenges/puzzles?  Huh Huh  Undecided Cry
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
July 17, 2022, 01:13:01 AM
In this example i use pubkey  0234c1fd04d301be89b31c0442d3e6ac24883928b45a9340781867d4232ec2dbdf, privkey is 0x67 and upper range is 2^7
Divisor is 2^3, so new upper range is 2^7-2^3=2^4
In file pub.txt you will find all pubkeys and their number is equil to divisor.
if you try to find all this keys in range 0x1:0xf you will see that only one pubkey will be lie in range
And this pubkey is 03d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a with privkey 0xC
To produce real privkey need multiply privkey by divisor
0xC*0x8 = 0x60
After this need add to result founded public key number (7)
Totaly privekey = 0x60 +0x7=0x67



can you please tell me how to increase the upper range in this code

To increase the upper range, you must either supply a public key with a larger value private key, or you can tweak the "divisor" constant in the code and make it lower, because divisor makes the upper range smaller:

Quote
In this example i use pubkey  0234c1fd04d301be89b31c0442d3e6ac24883928b45a9340781867d4232ec2dbdf, privkey is 0x67 and upper range is 2^7
Divisor is 2^3, so new upper range is 2^7-2^3=2^4

PS. I totally forgot about that drama on that page of this thread Tongue Time flies, doesn't it? In fact, most of the people on this thread aren't around anymore.
Pages:
Jump to: