Pollard's kangaroo ECDLP solver

[WanderingPhilospher]

Thanks for replying .. i learned a lot from this .. what I'm still confused about, is how to implement this in practical terms, like say if i want to find a key in the first 160 bit .. you know, that silly range with a lot of leading zeros .. i consider it our only safe haven in this gigantic keyspace .. if i want to use kangaroo to find collisions , how could i use addition/substraction of pub key to look there? Isn't this method gonna look for 256 bit keys anyway? I understood from your explanation how easy it is to use one public key to get well ahead of usual brute force prv key tools .. but does generating so many keys on kangaroo lead to a find in the first 160 bits? or the entire keyspace?

Excuse my ignorance im way better in other things but not kangaroo .. i even went all the way to automate all the other brute force tools so I don't have to waste anymore time on something that is highly unlikely to find stuff any time soon .. but your last reply got me thinking we might have a greater advantage this way .. i might even be able to automate search on kangaroo as well if it really could lower search down to 2^128 .. im currently doing some thorough reading hoping to get the hang of this specific point 👉 "finding colliding keys in the first 160 bits"

There is no magic to ensure any address will be in the first 160 bits other than division, but that would take many keys like 2^96 keys to ensure that. 2^256(bit range)/2^96(keys) = 2^160 bit range (the first with many leading zeros).

Kangaroo basically creates many (millions or as many as needed to solve for privkey) of offset pubs/addresses. It stores only the ones you tell it to via a mask/distinguished points...either x amount of leading or trailing 0s. It stores the tame ones (x point and actual privkey) and wild ones (x point and offset of actual privkey); when the x points match with tame and wild, the key is solved. So unlike bruteforce that checks a privkey and then dumps it, kangaroo stores the ones you tell it to via the distinguished point argument.

To solve a key in the giant 2^256 range, kangaroo program needs to check roughly 2^128 points/privkey and applicable pubkey (for leading or trailing 0s) So if you used a DP of 40, then the program would roughly store 2^88 (128-40) points (x points) and applicable privkey (distances).

As a real world example, I am currently searching for the 120 puzzle in the 110 bit range, using a DP of 25. I divided 120's pubkey by 1,024 (2^10) which generates 1,024 new pubkeys related to the original pubkey, but only 1 (at most 2) of the new pubkeys are in the 110 bit range (the remaining pubkeys are spread out over the entire key space). So I will generate enough Tame points first and then run back through the range looking for Wilds. I expect to need to store 2^31 (110/2 + 1 - 25) total points and distances to solve the key, which will take an estimated checking of 2^56(ish) total keys. Now if I tried to bruteforce the same key, it could take me up to 2^110 total keys to check.

But here is a more interesting question, if I have 1 address and 2^96 other privkeys can unlock it, if I take the same address (if I know the pubkey) and create 2^20 more addresses that relate to the address, are there now 2^116 privkeys that will unlock the original address?? Or possibly even more when you factor in uncom and com pubkeys->ripemd160?? Hmmmmm...

[1714479108]

1714479108

[1714479108]

1714479108

[1714479108]

1714479108

[CrunchyF]

As a real world example, I am currently searching for the 120 puzzle in the 110 bit range, using a DP of 25. I divided 120's pubkey by 1,024 (2^10) which generates 1,024 new pubkeys related to the original pubkey, but only 1 (at most 2) of the new pubkeys are in the 110 bit range (the remaining pubkeys are spread out over the entire key space). So I will generate enough Tame points first and then run back through the range looking for Wilds. I expect to need to store 2^31 (110/2 + 1 - 25) total points and distances to solve the key, which will take an estimated checking of 2^56(ish) total keys. Now if I tried to bruteforce the same key, it could take me up to 2^110 total keys to check.

Hi WanderingPhilospher ,

Can u explain a little more your algorithm of dividing the pubkey before doing the Kangaroo search?
Because if i well understand when you reduce the range to 2^110 (division by 1024)

You will have to do an average of (cf Jean luc formula) :

2.08*sqrt(k2-k1) =  2.08*sqrt(2^(120-10)-2^(119-10)) = 5.29*10^16 ops

but as you say only 1 or 2 of the dividing split range will contains a pubkey with (pubkey+n)%1024==0
so you will have to repeat the search 512 times and do an average of

(1024/2)*5.29*10^16=5.42*10^19 ops  before having a collision.

But with the initial config of the kangaroo you will only have:

2.08*sqrt(k2-k1)=1.69*10^18 to do (32 times less)

[WanderingPhilospher]

As a real world example, I am currently searching for the 120 puzzle in the 110 bit range, using a DP of 25. I divided 120's pubkey by 1,024 (2^10) which generates 1,024 new pubkeys related to the original pubkey, but only 1 (at most 2) of the new pubkeys are in the 110 bit range (the remaining pubkeys are spread out over the entire key space). So I will generate enough Tame points first and then run back through the range looking for Wilds. I expect to need to store 2^31 (110/2 + 1 - 25) total points and distances to solve the key, which will take an estimated checking of 2^56(ish) total keys. Now if I tried to bruteforce the same key, it could take me up to 2^110 total keys to check.

Hi WanderingPhilospher ,

Can u explain a little more your algorithm of dividing the pubkey before doing the Kangaroo search?
Because if i well understand when you reduce the range to 2^110 (division by 1024)

You will have to do an average of (cf Jean luc formula) :

2.08*sqrt(k2-k1) =  2.08*sqrt(2^(120-10)-2^(119-10)) = 5.29*10^16 ops

but as you say only 1 or 2 of the dividing split range will contains a pubkey with (pubkey+n)%1024==0
so you will have to repeat the search 512 times and do an average of

(1024/2)*5.29*10^16=5.42*10^19 ops  before having a collision.

But with the initial config of the kangaroo you will only have:

2.08*sqrt(k2-k1)=1.69*10^18 to do (32 times less)

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!

[CrunchyF]

As a real world example, I am currently searching for the 120 puzzle in the 110 bit range, using a DP of 25. I divided 120's pubkey by 1,024 (2^10) which generates 1,024 new pubkeys related to the original pubkey, but only 1 (at most 2) of the new pubkeys are in the 110 bit range (the remaining pubkeys are spread out over the entire key space). So I will generate enough Tame points first and then run back through the range looking for Wilds. I expect to need to store 2^31 (110/2 + 1 - 25) total points and distances to solve the key, which will take an estimated checking of 2^56(ish) total keys. Now if I tried to bruteforce the same key, it could take me up to 2^110 total keys to check.

Hi WanderingPhilospher ,

Can u explain a little more your algorithm of dividing the pubkey before doing the Kangaroo search?
Because if i well understand when you reduce the range to 2^110 (division by 1024)

You will have to do an average of (cf Jean luc formula) :

2.08*sqrt(k2-k1) =  2.08*sqrt(2^(120-10)-2^(119-10)) = 5.29*10^16 ops

but as you say only 1 or 2 of the dividing split range will contains a pubkey with (pubkey+n)%1024==0
so you will have to repeat the search 512 times and do an average of

(1024/2)*5.29*10^16=5.42*10^19 ops  before having a collision.

But with the initial config of the kangaroo you will only have:

2.08*sqrt(k2-k1)=1.69*10^18 to do (32 times less)

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.

Yes but when i speak about ops (operations to do) , i speak about group additions (Kangaroo jumps). Checking for DP in the hashtable is negligible in time compared to the cost of grop operation
I d'ont understand how you avoid the additions when you check the 1024 pubkey at once.

[WanderingPhilospher]

Yes but when i speak about ops (operations to do) , i speak about group additions (Kangaroo jumps). Checking for DP in the hashtable is negligible in time compared to the cost of grop operation

Right, group operations = kangaroo jumps/keys checked/group additions/etc. We are speaking the same language. If you run the program, it will show you the expected operations. That is what I am talking about.

I d'ont understand how you avoid the additions when you check the 1024 pubkey at once.

Classified

But there are a few ways you can do this, you just have to tinker and experiment with code.

But again, I am hoping for a combination of things to occur as has occurred at lower bit ranges during tests and trials, but the biggest thing is, more group ops during the tame only run = less group ops needed during wild only run. Factor that with running all pubs concurrently, I am hoping for better than 2^60.5 total group ops.

EDIT: after rereading what you posted and what I responded with, I think I missed the mark.
I am not avoiding any additions or group ops by running all pubkeys at once.
Think of it this way...if you are running the slowest of slow python script (which I have done during test startup) and you create a file with 1,024 pubkeys (or however many you want), and the program reads the file and every pubkey and then starts adding or subtracting to create new points/pubkeys, it is not skipping or avoiding additions or subtractions. Let's say you want the script to offset each pubkey in the file by adding 0x1, sequentially up to 0x1000, it would work like this:
pub1 in file = add 0x1
pub2 in file = add 0x1
...
pub 1024 in file = add 0x1
_____________________
pub1 in file = add 0x2
pub2 in file = add 0x2
...
pub 1024 in file = add 0x2
_____________________
pub1 in file = add 0x1000
pub2 in file = add 0x1000
...
pub 1024 in file = add 0x1000

The program is not avoiding any additions, in this case of using a python script, it is looping; pub1 +, pub2 +....pub1024+, rinse and repeat.
Does that make sense?

[fxsniper]

It is possible to found key on other range?

my testing with puzzle#32 (32bit key)
all wide 31-32 bit can found key on many point collision

and it can found on 40bit range or higher that key
if on low bit key that pubkey*genpoint can collision on many point on 256bit range

but for puzzle #120 may be can found on range 121 bit or 160 bit

The problem is 120bit is too much wide
 

[WanderingPhilospher]

It is possible to found key on other range?

my testing with puzzle#32 (32bit key)
all wide 31-32 bit can found key on many point collision

and it can found on 40bit range or higher that key
if on low bit key that pubkey*genpoint can collision on many point on 256bit range

but for puzzle #120 may be can found on range 121 bit or 160 bit

The problem is 120bit is too much wide
 

Yes, you can find any smaller bit key in it's range or in a range larger than it's original range.
Quick example, searching for private key 1 (0x1):
you can find it by finding key 2 - key 1 (0x2-0x1), or key 3 - key 2 (0x3-0x2), or move a lot higher up, 0xffffffffff - 0xfffffffffe = 0x1

[Evillo]

As a real world example, I am currently searching for the 120 puzzle in the 110 bit range, using a DP of 25. I divided 120's pubkey by 1,024 (2^10) which generates 1,024 new pubkeys related to the original pubkey, but only 1 (at most 2) of the new pubkeys are in the 110 bit range (the remaining pubkeys are spread out over the entire key space). So I will generate enough Tame points first and then run back through the range looking for Wilds. I expect to need to store 2^31 (110/2 + 1 - 25) total points and distances to solve the key, which will take an estimated checking of 2^56(ish) total keys. Now if I tried to bruteforce the same key, it could take me up to 2^110 total keys to check.

Hi WanderingPhilospher ,

Can u explain a little more your algorithm of dividing the pubkey before doing the Kangaroo search?
Because if i well understand when you reduce the range to 2^110 (division by 1024)

You will have to do an average of (cf Jean luc formula) :

2.08*sqrt(k2-k1) =  2.08*sqrt(2^(120-10)-2^(119-10)) = 5.29*10^16 ops

but as you say only 1 or 2 of the dividing split range will contains a pubkey with (pubkey+n)%1024==0
so you will have to repeat the search 512 times and do an average of

(1024/2)*5.29*10^16=5.42*10^19 ops  before having a collision.

But with the initial config of the kangaroo you will only have:

2.08*sqrt(k2-k1)=1.69*10^18 to do (32 times less)

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!

When you say concurrently are you saying you're playing with code in the same language or switched to golang? Im thinking of rewriting it in Go but a little hesitant coz i always have that idea that c/c++ are still faster than Go

[ajeev]

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 m little bit confused can you please provide me some example

[NotATether]

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

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

241.5 would represent the floating-point equivalent of the even private key (in this example), and 241 would represent the odd public key (note: no decimal point in the even number).

There is an assumption in the excerpt that I quoted in a.a's post, that the parity of the last bit of the PK is already known - and it's only known here because the key has already been found.

But for unsolved pubkeys, the last bit is obviously unknown, so it is impossible to know whether to subtract by 0x241 [even] or 0x241 + (1*2^(-1===n-1)) [odd].

[ajeev]

Here is no magic, here is script to shiftdown pubkey:

Code:

import random
import math
import hashlib
import base58
def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )    
    """
    inv1 = 1
    inv2 = 0
    n=1
    while p != 1 and p!=0:        
        quotient = x // p
        
        inv1, inv2 = inv2, inv1 - inv2 * quotient
        x, p = p, x % p        
        n = n+1
    
    return inv2

def dblpt(pt, p):
    """
    Calculate pt+pt = 2*pt
    """
    if pt is None:
        return None
    (x,y)= pt
    if y==0:
        return None 
    
    slope= 3*pow(x,2,p)*pow(2*y,p-2,p)
    
    
    xsum= pow(slope,2,p)-2*x 
    
    ysum= slope*(x-xsum)-y  
    
    return (xsum%p, ysum%p)

def addpt(p1,p2, p):
    """
    Calculate p1+p2
    """
    if p1 is None or p2 is None:
        return None
    (x1,y1)= p1
    (x2,y2)= p2
    if x1==x2:
        return dblpt(p1, p)
        
    # calculate (y1-y2)/(x1-x2)  modulus p
    
    slope=(y1-y2)*pow(x1-x2,p-2,p)
    
    
    xsum= pow(slope,2,p)-(x1+x2)
   
    ysum= slope*(x1-xsum)-y1
    
    
    return (xsum%p, ysum%p)

def ptmul(pt,a, p):
    """
    Calculate pt*a
    """
    scale= pt    
    acc=None
   
    
    while a:
        
        if a&1:
            if acc is None:
                acc= scale 
                
            else:     
                acc= addpt(acc,scale, p)                
               
        scale= dblpt(scale, p)
        a >>= 1
        
            
   
    return acc

def ptdiv(pt,a,p,n):  
    """
    Calculate pt/a
    """   
    divpt=inverse(a, n)%n    
    return ptmul(pt, divpt, p)


def isoncurve(pt,p):
    """
    returns True when pt is on the secp256k1 curve
    """
    (x,y)= pt
    return (y**2 - x**3 - 7)%p == 0


def getuncompressedpub(compressed_key):
    """
    returns uncompressed public key
    """
    y_parity = int(compressed_key[:2]) - 2    
    x = int(compressed_key[2:], 16)
    a = (pow(x, 3, p) + 7) % p
    y = pow(a, (p+1)//4, p)    
    if y % 2 != y_parity:
        y = -y % p        
    return (x,y)

def compresspub(uncompressed_key):
    """
    returns uncompressed public key
    """
    (x,y)=uncompressed_key
    y_parity = y&1 
    head='02'
    if y_parity ==1:
        head='03'    
    compressed_key = head+'{:064x}'.format(x)       
    return compressed_key

def hash160(hex_str):
    sha = hashlib.sha256()
    rip = hashlib.new('ripemd160')
    sha.update(hex_str)
    rip.update( sha.digest() )    
    return rip.hexdigest()  # .hexdigest() is hex ASCII
    
def getbtcaddr(pubkeyst):
    
    hex_str = bytearray.fromhex(pubkeyst)
    # Obtain key:
    key_hash = '00' + hash160(hex_str)

    # Obtain signature:

    sha = hashlib.sha256()
    sha.update( bytearray.fromhex(key_hash) )
    checksum = sha.digest()
    sha = hashlib.sha256()
    sha.update(checksum)
    checksum = sha.hexdigest()[0:8]

    return (base58.b58encode( bytes(bytearray.fromhex(key_hash + checksum)) )).decode('utf-8')

def checkpub(realpub, temppub, id):
    localpt = ptmul(temppub, 1024, p)
    localaddpt = ptmul(g, id, p)
    respub= addpt(localpt,localaddpt, p)
    print ("respub-> ", compresspub(respub))
    
#secp256k1 constants
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
g= (Gx,Gy)


compressed_key='0234c1fd04d301be89b31c0442d3e6ac24883928b45a9340781867d4232ec2dbdf'
point=getuncompressedpub(compressed_key)

print(getbtcaddr("04%064x%064x"%point))
print(getbtcaddr(compressed_key))
divisor = 2**3
newpub=ptdiv(point,divisor,p,n)

(partGx,partGy)=ptdiv(g,divisor,p,n)
print ("1 Fraction part-> (%x,%064x)" % (partGx,partGy))

with open('pub.txt', 'w') as f:
    f.write("04%064x%064x"%newpub)
    f.write('\n')
    print ("Compressed NewPUB (",0,")-> ", compresspub(newpub),"addr",getbtcaddr(compresspub(newpub)))
    i=1
    (pointx,pointy)=(partGx,partGy)
    while i<divisor:
        (newpubtempx,newpubtempy) = addpt(newpub,(pointx,p-pointy), p)
        f.write("04%064x%064x"%(newpubtempx,newpubtempy))
        f.write('\n')
        print ("Compressed NewPUB (",i,")-> ", compresspub((newpubtempx,newpubtempy)),"addr",getbtcaddr(compresspub((newpubtempx,newpubtempy))))
        (pointx,pointy) = addpt((pointx,pointy),(partGx,partGy), p)   
        i=i+1

   

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

[NotATether]

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:

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 Time flies, doesn't it? In fact, most of the people on this thread aren't around anymore.

[GR Sasa]

Did everyone gave up on the challenges/puzzles?   

[NotATether]

Did everyone gave up on the challenges/puzzles?   

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

[Evillo]

Did everyone gave up on the challenges/puzzles?    

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

[NotATether]

Did everyone gave up on the challenges/puzzles?    

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.

[Evillo]

Did everyone gave up on the challenges/puzzles?    

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

[NotATether]

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

[Evillo]

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 🤔

[ajeev]

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