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

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

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)

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.

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...

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

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)

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].

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

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.

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

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....

Did everyone gave up on the challenges/puzzles?   

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

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

i m little bit confused can you please provide me some example

This makes actually no sense, because the underlying principle is different.

example:

Puzzle 11
https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000483

038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b

halving the publickey:
03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d

03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 is the result, when the privatekey of puzzle 11 is even and
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d if the the privatekey of puzzle 11 is odd.

02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is the correct one, as the privatekey of puzzle 11 is odd  
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000241

So if you do 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d + 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d, you get 038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b (untested, I guess you need also adding the Generatorpoint for + 1 as we do 241 + 241 + 1 = 483)

So what is 03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 then? It is 241.5.
241.5 + 241.5 = 483

So, where do we find 241.5?

https://privatekeys.pw/key/7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b1e5f

How did I find it? key middle range minus half of our privatekey: 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 - 0x241 => tada

So from complexity of 11 bits, i just needed to check 10 bits now.

If I divide by 32, I actually do what?

2 * 2 * 2 * 2 * 2 = 32

So we are halving the public key 5 times. This means, that when we do this on key 11, we get 32 keys, from where one of them has the correct endsequence of the private key. So we have to check all keys if they are in the range of 2^6. If we get one, than we know how the first 6 bits of the privatekey are. We can from here determine the last 5 bits easily. I am not interested in the other ranges, as i have now a total valid privatekey

I will need to run/check all of the new 1,024 pub keys through the range.
With JLP's Kangaroo program, I would need to do this one pubkey at a time. However, I modified some code to allow me to run and check all 1,024 pubkeys at once/concurrently.
A few thoughts about this...I am hoping with double the needed tame points, the less wild group ops needed for a collision. I have completed tests at lower bits and this was the case however,
this is a much larger range and untested.

Keeping the math simpler (at least for me):
The original 120 bit range (reduced to 119 bit range): 119/2 + 1 = 2^60.5 expected group ops
In the 110 bit range (reduced to 109 bit range): 109/2 + 1 = 2^55.5 expected group ops
So straight up, 109 bit range = 32 times less but as you stated (and I know) I have to check all 1,024 new pubkeys. I am hoping by having at least double the amount of required tames plus being able to check all pubs concurrently, I can beat the original 2^60.5 expected group ops.
I have beaten the averages in lower bit ranges (up to 84 bit range) but this is new territory. We shall see what happens!