Bitcoin puzzle transaction ~32 BTC prize to who solves it

[kTimesG]

If we have a probability of 1 in approximately 2 ** 50 to find Puzzle 135, why has it not been resolved?

The question is irrelevant since the premise is incorrect, you lost a factor of 300.000x there, out of the blue, without any reasonable explanation. E.g. your question is equivalent to "if the sun is green, why wasn't puzzle 135 found yet?"

Also, deleting your own posts (to remove your fake allegations from new eyes) shows a very low level of confidence of both you in yourself, and us in you.

Otherwise, I'd consider this non-sense just the usual trolling, by you and your clones. Don't you really have like, anything better to spend time with, then spreading misinformation?

Was not believing challenge can be worked - I own the changed address.

Congrats!

[pbies]

used kangaroo, solved in 28 min. with RTX 4070 GPU. idk if bsgs can even work above 70 bits, no RAM? ...

Was this kangaroo modified? And how?

[WanderingPhilospher]

Bro, provide your script ?

This is a jlp kangaroo, with precalculated tame kangaroos.
You can make them yourself. By running a kangaroo in the required range with the -m 3 parameter in a loop with a false public key. In this way you will accumulate a lot of DPs.
After that, you will only need wild kangaroos.

This requires modification(s) to JLPs script.

i see you people solve much much faster with saved DPs. good trick, but how big data grows until merge is slower?

There is no slow down by using pre-compiled workfile(s). Well, I should say, there is no slow down unless you have a very low budget CPU. There should be no "merging" required for an 80 bit range. Pre-compile the tames (convert all wilds to tames), in a single work file, and use the -i to load and save to it; no merger required. What DP did you use?? I think, maybe people are using to low of a DP. I used DP 20 and it did now take any time to load the workfile. A low DP is not needed since you should have many more tames needed to solve, quicker. When I ran it, for the actual challenge key, it took less than 30 seconds using a single RTX 4090. I think the workfile size was right at 200 MB.

[mcdouglasx]

If we have a probability of 1 in approximately 2 ** 50 to find Puzzle 135, why has it not been resolved?

The question is irrelevant since the premise is incorrect, you lost a factor of 300.000x there, out of the blue, without any reasonable explanation. E.g. your question is equivalent to "if the sun is green, why wasn't puzzle 135 found yet?"

Also, deleting your own posts (to remove your fake allegations from new eyes) shows a very low level of confidence of both you in yourself, and us in you.

Otherwise, I'd consider this non-sense just the usual trolling, by you and your clones. Don't you really have like, anything better to spend time with, then spreading misinformation?

I'm deleting my posts with references to you because I find you irrelevant, you're someone who attacks everyone who contradicts you in a derogatory manner, it's not worthy of respect and you show immaturity, however, you're here.
As for what I said, you want to bet that only by doing 2^50 there is at least 1 irrefutable chance of finding puzzle 135, tell me how much are you willing to risk? and I'll explain.
On the other hand, you can turn the page.

[COBRAS]

userland@localhost:~/ecctools$ ./modmath 0xb338087fab6153cbb64561e4b35082d41653e3b70a55b9b105deba9f3dc10479  / 0x20000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000
Result: 2d56cbf370cbeef9e80a

how Etar do it this   any body know how to get part of privkey(pubkey) in range 2**80 , use 2**361 ?

[citb0in]

If we have a probability of 1 in approximately 2 ** 50 to find Puzzle 135, why has it not been resolved?

The question is irrelevant since the premise is incorrect, you lost a factor of 300.000x there, out of the blue, without any reasonable explanation. E.g. your question is equivalent to "if the sun is green, why wasn't puzzle 135 found yet?"

Also, deleting your own posts (to remove your fake allegations from new eyes) shows a very low level of confidence of both you in yourself, and us in you.

Otherwise, I'd consider this non-sense just the usual trolling, by you and your clones. Don't you really have like, anything better to spend time with, then spreading misinformation?

Was not believing challenge can be worked - I own the changed address.

Congrats!

opchecksig aka COBRAS aka ... -indefinite- ...

[Etar]

how Etar do it this   any body know how to get part of privkey(pubkey) in range 2**80 , use 2**361 ?

Here is an example of a script that will allow you to learn how to work with points:

Code:

# (Gx,Gy)  is the secp256k1 generator point
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
import operator
import math

def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )   
    the modular inverse is a number such that:   
    (inverse(x, p) * x) % p  ==  1     
    you could think of this as: 1/x
    """
    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):
    """
    Scalar multiplication: calculate pt*a   
    basically adding pt to itself a times
    """
    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):   
    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
    if y_parity>1:
      #it is uncompresse dpub
      x = int(compressed_key[2:66], 16)
      y = int(compressed_key[66:130], 16)
      return (x,y)
   
    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
   
                                                         
rangeBegin = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
rangeEnd =   0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
pub_compressed = '03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7'
Bits = 361

(pubx,puby) = getuncompressedpub(pub_compressed)
(x,y) = ptmul((Gx,Gy),rangeBegin,p)
#substract rangeBegin from public key
(Shiftpubx,Shiftpuby) = addpt((pubx,puby), (x,(p-y)%p), p)
print ("Shifted pub> ",compresspub((Shiftpubx,Shiftpuby)))
#pub / (2**361)
(SPubx,SPuby) = ptdiv((Shiftpubx,Shiftpuby),2**361,p,n)
print ("Pub> ",compresspub((SPubx,SPuby)))

#Convert private key
kangarooPrivKey=0x2d56cbf370cbeef9e80a
RealPrivKey = (kangarooPrivKey * (2**361) + rangeBegin ) % n
print ("Key> %x"% RealPrivKey)

[farshadbbb]

maybe explain how use bsgs  squence mode?

[COBRAS]

how Etar do it this   any body know how to get part of privkey(pubkey) in range 2**80 , use 2**361 ?

Here is an example of a script that will allow you to learn how to work with points:

Code:

# (Gx,Gy)  is the secp256k1 generator point
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
import operator
import math

def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )    
    the modular inverse is a number such that:    
    (inverse(x, p) * x) % p  ==  1    
    you could think of this as: 1/x
    """
    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):
    """
    Scalar multiplication: calculate pt*a    
    basically adding pt to itself a times
    """
    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):  
    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
    if y_parity>1:
      #it is uncompresse dpub
      x = int(compressed_key[2:66], 16)
      y = int(compressed_key[66:130], 16)
      return (x,y)
    
    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
    
                                                        
rangeBegin = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
rangeEnd =   0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
pub_compressed = '03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7'
Bits = 361

(pubx,puby) = getuncompressedpub(pub_compressed)
(x,y) = ptmul((Gx,Gy),rangeBegin,p)
#substract rangeBegin from public key
(Shiftpubx,Shiftpuby) = addpt((pubx,puby), (x,(p-y)%p), p)
print ("Shifted pub> ",compresspub((Shiftpubx,Shiftpuby)))
#pub / (2**361)
(SPubx,SPuby) = ptdiv((Shiftpubx,Shiftpuby),2**361,p,n)
print ("Pub> ",compresspub((SPubx,SPuby)))

#Convert private key
kangarooPrivKey=0x2d56cbf370cbeef9e80a
RealPrivKey = (kangarooPrivKey * (2**361) + rangeBegin ) % n
print ("Key> %x"% RealPrivKey)

Thank you

maybe explain how use bsgs  squence mode?

yes, and how Etar soft work with 1 pubkey, not will all 1024 pubs then divide to 1024. I seen screen of work a soft, sequence mode work with 1 pibkey.

interesting

# (Gx,Gy)  is the secp256k1 generator point
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
import operator
import math

def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )    
    the modular inverse is a number such that:    
    (inverse(x, p) * x) % p  ==  1    
    you could think of this as: 1/x
    """
    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):
    """
    Scalar multiplication: calculate pt*a    
    basically adding pt to itself a times
    """
    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):  
    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
    if y_parity>1:
      #it is uncompresse dpub
      x = int(compressed_key[2:66], 16)
      y = int(compressed_key[66:130], 16)
      return (x,y)
    
    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
    
                                                        
rangeBegin =0x900# 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c74 8207a0daa16191d07a425d8080c276f9412472e0429e61bc355
rangeEnd =  0x1000# 0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c74 8207a0daa16191d07a425d8080c276f9412472e0429e61bc355
pub_compressed = "03175e159f728b865a72f99cc6c6fc846de0b93833fd2222ed73fce5b551e5b739"
Bits = 0x1000

(pubx,puby) = getuncompressedpub(pub_compressed)
(x,y) = ptmul((Gx,Gy),rangeBegin,p)
#substract rangeBegin from public key
(Shiftpubx,Shiftpuby) = addpt((pubx,puby), (x,(p-y)%p), p)
print ("Shifted pub> ",compresspub((Shiftpubx,Shiftpuby)))
#pub / (2**361)
(SPubx,SPuby) = ptdiv((Shiftpubx,Shiftpuby),2**23,p,n)
print ("Pub> ",compresspub((SPubx,SPuby)))

#Convert private key
kangarooPrivKey=0x700
RealPrivKey = (kangarooPrivKey * (2**23) + rangeBegin ) % n
print ("Key> %x"% RealPrivKey)

   

result:

Code:

Shifted pub>  026f12d86c1160191443c5f56ec6c2999edfa58e345e1534e650ed09523d82824c

./calculatefromkey 1000
privatekey: 0000000000000000000000000000000000000000000000000000000000001000
publickey compressed: 03175e159f728b865a72f99cc6c6fc846de0b93833fd2222ed73fce5b551e5b739


./calculatefromkey 700
privatekey: 0000000000000000000000000000000000000000000000000000000000000700
publickey compressed: 026f12d86c1160191443c5f56ec6c2999edfa58e345e1534e650ed09523d82824c

then put shifted key to input of a scrypt, result smaler again


rangeBegin =100
pub_compressed = "03779bd0a11d17ea0e00a6addbc6dbb9690ef24ff6ed5f3cddb2c3abcf04d409e0"

Shifted pub>  02540f37a73add0efafa3713cfc198fb26c6134bcf12eac07e9e2c4501caee8a44 <<< priv 0xf38


and again:

Shifted pub>  02798457977876ce1a77d889edc7fc1213774e3276fd9525bd6168305a0ddbc6a4 << priv ed4

Thank you for "nice toy" Etar

[damiankopacz87]

This is a jlp kangaroo, with precalculated tame kangaroos.
You can make them yourself. By running a kangaroo in the required range with the -m 3 parameter in a loop with a false public key. In this way you will accumulate a lot of DPs.
After that, you will only need wild kangaroos.

This requires modification(s) to JLPs script.

Hi, this sounds interesting to me. Are You able to provide link where that modifications are explained? Or is there maybe a repo with modified software? Thanks for help.

BR Damian

[Cricktor]

Was not believing challenge can be worked - I own the changed address.

Sign a Bitcoin message with the appropriate key, otherwise anybody can make such a claim. You could e.g. thank kTimesG for the coins of his little side challenge in your signed message. How about that?

It was a bit entertaining how few users in this thread were even capable to tackle kTimesG's little side challenge properly. And the usual suspects who post only BS and have no clue what they're doing didn't positively surprise either. It's good they confirm their spot on my ignore list from time to time. Makes following this thread a tiny bit easier.

At least, I also learned something new. So, thank you kTimesG for the side challenge and anybody else who posted valid and good descriptions how to handle such a case, much appreciated.

[opchecksig]

no I used some JLP fork, and dp 16. no other mod except for Python bot. I think key was special chosen to take longer to solve, thats why very close to start of range, hard to catch collision.

also lost more minutes on first attempt because script crashed when TX appeared, lucky I was awake to see and fix.

it was simple two lines to bring key from 512 bits to mod N and one more line to get back to good key. why some here complicate it so much or so amazed of smth that is normal, it's just bit operation and know that always any k same as z*N + k. so if key was one billion bits knpwn and 80 straight bits hidden, still same formula, still 80 bit problem ). ofc this only work if all other bits are known, not random.

ecdsa_sign
addr: 14q4SoQwENXXzsVT3GMwDrDUGiW5QZeiDg
msg: thank you kTimesG for the challenge
sig: G7Bm7OATl/QyeMZcaHRjoZTM+iAadi2sG2MQk0fHwZ3MJQxk9rq3EyAoXUfe5DNzUeA58/wXESv3Eenc6DXM9jU=

[WanderingPhilospher]

Can anyone tell me if their is a difference (result wise) of the following two snippets:

Code:

def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )   
    the modular inverse is a number such that:   
    (inverse(x, p) * x) % p  ==  1     
    you could think of this as: 1/x
    """
    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

and

Code:

def inverse(x, p):
    return pow(x, p - 2, p)

Hi, this sounds interesting to me. Are You able to provide link where that modifications are explained? Or is there maybe a repo with modified software? Thanks for help.

If you are using the unmodded JLP version, it will not allow the merging or using of two different public keys, so you need to change or comment out a few lines in the merge.cpp (I believe, I haven't used his program in quite a while)
So if you use a fake pub during the pre-compile stage and then use an actual pub, you will get an error.

How I used to do it using his program, run a range with a public key that was smaller than the range, then after solve (if you let it keep running it will) convert the wilds to tames (by adding the public key's private key, to the wild's "distances".) Etar had a program called "reconstructor" that worked great for this! I can't remember if it was publicly released or not; maybe it was in a google drive versus GitHub link.

After you have as many precompiled points as wanted, then call that workfile with the -i flag; -i workfile , using JLP's kangaroo program. That's how I used to precompile a workfile.

[COBRAS]

                                                      
rangeBegin = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c74 8207a0daa16191d07a425d8080c276f9412472e0429e61bc355
rangeEnd =   0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c74 8207a0daa16191d07a425d8080c276f9412472e0429e61bc355
pub_compressed = '03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7'
Bits = 361

Hi Bro, how get this ranges ?

Plz

To be honest I am really disappointed that the solver don't announce itself...

I know bitcoin should be anonymous, but what kind of Ungrateful person is he to not said at least thanks to ktimesG for his time and dedication to this topic.

@COBRAS You should better dedicate to another not-technical topic, as far i see this is not for you.

For anyone who really don't understand where are those 80 missing bits here we go:

Code:

minKey = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
maxKey = 0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355

if we remove all hexadecimal characters that match and keep only those who don't match we get:

Code:

e00000000000000000001
fffffffffffffffffffff

Those are 21 characters, each hexadecimal characters need 4 bits, then those 21 are 84 bits... so we need to remove those bits that are the same in both ranges

Code:

   E (hex) = 1110 (binary)
    F (hex) = 1111 (binary)
    1 (hex) = 0001 (binary)

from the left side we have E and F.
1110
1111
The first three are always 1 so we need to remove those 3

From the right side we have 1 and F
1111
0001

Only 1 bit (righest one) match so we also need to remove that

So from those 84 bits we need to remove 3 on the left and 1 on the right.

Using python:

Code:

>>> bin(int("e00000000000000000001",16))
'0b111000000000000000000000000000000000000000000000000000000000000000000000000000000001'
>>> bin(int("fffffffffffffffffffff",16))
'0b111111111111111111111111111111111111111111111111111111111111111111111111111111111111'

Real missing bits:
111 >> 0000000000000000000000000000000000000000000000000000000000000000000000000000000 0 << 1
111 >> 1111111111111111111111111111111111111111111111111111111111111111111111111111111 1 << 1

how to put my pubkey  to   pubkey of 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c74 8207a0daa16191d07a425d8080c276f9412472e0429e61bc355 , replace 0000000000000000000 with my pubkey,  and get sane result, like in your algorithm. Privkey of my pubkey isuncnown

?

[Etar]

Hi, this sounds interesting to me. Are You able to provide link where that modifications are explained? Or is there maybe a repo with modified software? Thanks for help.

https://github.com/Etayson/JLPKangaroo_OW_OT
There you will find both the source code and the compiled versions for Windows.
Based on original v1.7 JLP Kangaroo
OT version needed to accumulate tame kangaroos.
OW is only produced wild kangaroos and is needed to find the public key.
Also you need a program that will make changes (public key, range) to the working file with DPs. I'll post it later.

Can anyone tell me if their is a difference (result wise) of the following two snippets:

This script is good for learning to understand what is inside each function.

P.s. Here is a script that changes the public key and range in the working file.

Code:

import argparse
from math import log2
import os

HEADW = 0xFA6A8001  # work file
HEADERSIZE=156

def bytes_to_num(byte_data):   
    return int.from_bytes(byte_data, byteorder='little')
   

def checkhead(wf):
    head = bytes_to_num(wf.read(4))
    if head==HEADW:
        return head
    else:
        print('HEADER ERROR %08x %08x' % (head, HEADW))
        return False

def workinfo(workfile):   
    wf = open(workfile, 'rb')
    head = checkhead(wf)
    if not head:
        print('Invalid WorkFile Header')
        return False
    version = bytes_to_num(bytes(wf.read(4)))
    dp1 = bytes_to_num(bytes(wf.read(4)))
    RangeStart = bytes_to_num(bytes(wf.read(32)))
    RangeEnd = bytes_to_num(bytes(wf.read(32)))
    x = bytes_to_num(bytes(wf.read(32)))
    y = bytes_to_num(bytes(wf.read(32)))
    count = bytes_to_num(bytes(wf.read(8)))
    time = bytes_to_num(bytes(wf.read(8)))
    print(
        f'Header     : {head:08x}'
        f'\nVersion    : {version:d}'
        f'\nDP Bits    : {dp1}'
        f'\nStart      : {RangeStart:032x}'
        f'\nStop       : {RangeEnd:032x}'
        f'\nPubKey X   : {x:032x}'
        f'\nPubKey Y   : {y:032x}'
        f'\nCount      : 2^{log2(count):.3f}'       
        )     
    wf.close()
    return True
       
def getuncompressedpub(compressed_key):   
    p=2**256 - 2**32 - 977
    y_parity = int(compressed_key[:2],16) - 2
    if y_parity>1:     
      x = int(compressed_key[2:66], 16)
      y = int(compressed_key[66:130], 16)
      return (x,y)     
    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 MakeChanges(workfile, NewPubCompressed, NewRB, NewRE):
    if os.path.exists(f'{workfile}'):
        print('Old header:')
        if workinfo(workfile):       
            #make some changes
            (x,y)= getuncompressedpub(NewPubCompressed)   
            with open(workfile, 'r+b') as wf:           
                try:
                    wf.seek(12)
                    wf.write(NewRB.to_bytes(32, byteorder='little'))
                    wf.write(NewRE.to_bytes(32, byteorder='little'))
                    wf.write(x.to_bytes(32, byteorder='little'))
                    wf.write(y.to_bytes(32, byteorder='little')) 
                except Exception as e:
                    print(f'File error {e}')       
            print('New header:')
            workinfo(workfile)       
    else:
        print(f'File {workfile} is not exist')
        return


       
if __name__ == '__main__':   
    parser = argparse.ArgumentParser()
    parser.add_argument('-f', dest='workfile', type=str, required=True, help='WorkFile path')
    parser.add_argument('-pub', dest='pub', required=True, type=str, help='Compressed public key')
    parser.add_argument('-rb', dest='rb', required=True, type=str, help='Begin range')
    parser.add_argument('-re', dest='re', required=True, type=str, help='End range')
    args = parser.parse_args()

    if args.workfile:
        print(f'Workfile {args.workfile}')
        MakeChanges(args.workfile, args.pub, int(args.rb,16), int(args.re,16))

   

[kTimesG]

Code:

class Challenge:
    def __init__(self, num_bits: int, raw_key: bytes = None):
        mask = (1 << num_bits) - 1

        if raw_key is None:
            raw_key = os.urandom(32)

        print(f'rawKey = {raw_key.hex():032}')
        self.private_key = int.from_bytes(raw_key)
        self.private_key += S.N * TrueRandom(2 ** 512 // S.N, 256, 1).get_next()
        self.public_key = Group.mul(Group.G, self.private_key)

        self.shift = TrueRandom(self.private_key.bit_length() - num_bits, 8).get_next()

        mask_2 = mask << self.shift
        self.min_key = self.private_key & ~mask_2
        self.max_key = self.private_key | mask_2
        print(
            f'minKey = {self.min_key:064x}'
            f'\nmaxKey = {self.max_key:064x}'
            f'\nprvKey = {self.private_key:064x}'
            f'\nkShift = {self.shift}'
            f'\nPubKey:'
            f'\n\tX: {self.public_key.x:032x}'
            f'\n\tY: {self.public_key.y:032x}'
        )


def create_challenge():
    input_key = getpass('Private Key:')

    if not len(input_key):
        raw_private_key = None
    else:
        raw_private_key = int(input_key, 16).to_bytes(32)

    num_bits = 80

    challenge = Challenge(num_bits, raw_private_key)
    addr = private_key_to_addr(int.to_bytes(challenge.private_key % S.N, 32))
    print(f'BTC Address(c): {addr}')

    return challenge


class Validator:
    def __init__(self, min_key: int, max_key: int, public_key: Point):
        self.min_key = min_key
        self.max_key = max_key
        self.public_key = public_key

        self.range_mask, self.shift = self.extract_mask()
        print(f'Computed shift: {self.shift}')

        # subtract min_key bits: P = P - minKey*G
        subtractor_key = Group.mul(Group.G, -self.min_key)
        # todo - handle case pub_key == -sub_key -> middleKey == 0
        self.subtracted_key = Group.add(self.public_key, subtractor_key)
        # print(f'Subtracted PubKey:'
        #       f'\n\tX: {hex(self.subtracted_key.x):032}'
        #       f'\n\tY: {hex(self.subtracted_key.y):032}'
        #       )

        # right-shift key: ("divide" by the nth power of two)
        self.shift_inv = pow(1 << self.shift, -1, S.N)
        self.translated_key = Group.mul(self.subtracted_key, self.shift_inv)

        # print(f'Translated PubKey:'
        #       f'\n\tX: {hex(self.translated_key.x):032}'
        #       f'\n\tY: {hex(self.translated_key.y):032}'
        #       )

    def extract_mask(self, slow_count: bool = False):
        range_mask = self.min_key ^ self.max_key

        if slow_count:
            shift = 0
            while range_mask % 2 == 0:
                shift += 1
                range_mask >>= 1
        else:
            # if any '1' gets shifted, a '0' is left over
            shift = range_mask.bit_length() - range_mask.bit_count()
            range_mask >>= shift

        if range_mask.bit_count() != range_mask.bit_length():
            raise ValueError('Invalid mask')

        return range_mask, shift

    def validate(self, tries: int = 1000000, sequential: bool = False):
        range_mask, shift = self.extract_mask()
        mask_len = range_mask.bit_length()
        print(f'Range size: {mask_len} bits; shift: {shift}')

        tr = TrueRandom(range_mask, mask_len, 1)

        for i in range(tries):
            key_idx = (i + 1) if sequential else tr.get_next()
            expected_key = self.min_key | (key_idx << shift)

            subtracted_key = expected_key - self.min_key

            # in the scalar field, shifting and "division" are equivalent
            # because we know the parity before each division (shift) step
            shifted_key = subtracted_key >> shift
            divided_key = S.mul(subtracted_key, self.shift_inv)
            if shifted_key != divided_key:
                raise Exception(f'Failed!\n\t{hex(divided_key)}\n\t{hex(shifted_key)}')

            pub_key = Group.mul(Group.G, expected_key)
            print(f'Checking privKey: {expected_key % S.N:064x}')
            priv = Validator(self.min_key, self.max_key, pub_key).validate_private_key(divided_key)
            if priv != expected_key:
                raise Exception('Validation failed')

    def validate_private_key(self, private_key: int):
        print(f'Checking translated private key: {hex(private_key)}')
        if private_key != 0:
            sk = private_key << self.shift
            sk = Group.mul(Group.G, sk)
            # print(f'Shifted PubKey:'
            #       f'\n\tX: {hex(sk.x):032}'
            #       f'\n\tY: {hex(sk.y):032}'
            #       )

        private_key = self.min_key | (private_key << self.shift)
        public_key = Group.mul(Group.G, private_key)

        if public_key.x == self.public_key.x and public_key.y == self.public_key.y:
            return private_key

        print('Key validation failed')


def main():
    challenge = create_challenge()

    validator = Validator(challenge.min_key, challenge.max_key, challenge.public_key)
    validator.validate(tries=10)

    translated_private_key = (challenge.private_key - challenge.min_key) >> challenge.shift
    private_key = validator.validate_private_key(translated_private_key)

    if private_key == challenge.private_key:
        print(f'Private Key OK: {private_key % S.N:032x}')
    else:
        raise Exception('Key validation failed')


if __name__ == '__main__':
    main()

Can anyone tell me if their is a difference (result wise) of the following two snippets:

Code:

def inverse(x, p):
  ...

Code:

def inverse(x, p):
    return pow(x, p - 2, p)

XGCD is faster then FLT when implemented at machine-level instructions, but "pow(x, -1, N)" is the fastest in Python because it uses native big integers internally. Unless going with gmpy2.invert()...

[COBRAS]

priv = P_x / G_x

import hashlib
import ecdsa

# Бaзoвaя тoчкa G кpивoй SECP256K1
G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

# Гeнepaция ceкpeтнoгo ключa k
k = 0x1234567890abcdef

# Гeнepaция тoчки P кpивoй SECP256K1
P_x = (k * G_x) % (2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1)
P_y = (k * G_y) % (2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1)

# Bычиcлeниe oбpaтнoгo чиcлa G_x пo мoдyлю 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
G_x_inv = pow(G_x, -1, 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1)

# Пpoвepкa фopмyлы k = P_x / G_x
if k == (P_x * G_x_inv) % (2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1):
    print("Фopмyлa k = P_x / G_x вepнa")
else:
    print("Фopмyлa k = P_x / G_x нeвepнa")

# Bывoд тoчки P
print("Toчкa P:", (P_x, P_y))

# Bывoд ceкpeтнoгo ключa k
print("Ceкpeтный ключ k:", hex(k), hex((P_x * G_x_inv) % (2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1)))

[damiankopacz87]

P.s. Here is a script that changes the public key and range in the working file.

Code:

import argparse
from math import log2
import os

HEADW = 0xFA6A8001  # work file
HEADERSIZE=156

def bytes_to_num(byte_data):   
    return int.from_bytes(byte_data, byteorder='little')
   

def checkhead(wf):
    head = bytes_to_num(wf.read(4))
    if head==HEADW:
        return head
    else:
        print('HEADER ERROR %08x %08x' % (head, HEADW))
        return False

def workinfo(workfile):   
    wf = open(workfile, 'rb')
    head = checkhead(wf)
    if not head:
        print('Invalid WorkFile Header')
        return False
    version = bytes_to_num(bytes(wf.read(4)))
    dp1 = bytes_to_num(bytes(wf.read(4)))
    RangeStart = bytes_to_num(bytes(wf.read(32)))
    RangeEnd = bytes_to_num(bytes(wf.read(32)))
    x = bytes_to_num(bytes(wf.read(32)))
    y = bytes_to_num(bytes(wf.read(32)))
    count = bytes_to_num(bytes(wf.read(8)))
    time = bytes_to_num(bytes(wf.read(8)))
    print(
        f'Header     : {head:08x}'
        f'\nVersion    : {version:d}'
        f'\nDP Bits    : {dp1}'
        f'\nStart      : {RangeStart:032x}'
        f'\nStop       : {RangeEnd:032x}'
        f'\nPubKey X   : {x:032x}'
        f'\nPubKey Y   : {y:032x}'
        f'\nCount      : 2^{log2(count):.3f}'       
        )     
    wf.close()
    return True
       
def getuncompressedpub(compressed_key):   
    p=2**256 - 2**32 - 977
    y_parity = int(compressed_key[:2],16) - 2
    if y_parity>1:     
      x = int(compressed_key[2:66], 16)
      y = int(compressed_key[66:130], 16)
      return (x,y)     
    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 MakeChanges(workfile, NewPubCompressed, NewRB, NewRE):
    if os.path.exists(f'{workfile}'):
        print('Old header:')
        if workinfo(workfile):       
            #make some changes
            (x,y)= getuncompressedpub(NewPubCompressed)   
            with open(workfile, 'r+b') as wf:           
                try:
                    wf.seek(12)
                    wf.write(NewRB.to_bytes(32, byteorder='little'))
                    wf.write(NewRE.to_bytes(32, byteorder='little'))
                    wf.write(x.to_bytes(32, byteorder='little'))
                    wf.write(y.to_bytes(32, byteorder='little')) 
                except Exception as e:
                    print(f'File error {e}')       
            print('New header:')
            workinfo(workfile)       
    else:
        print(f'File {workfile} is not exist')
        return


       
if __name__ == '__main__':   
    parser = argparse.ArgumentParser()
    parser.add_argument('-f', dest='workfile', type=str, required=True, help='WorkFile path')
    parser.add_argument('-pub', dest='pub', required=True, type=str, help='Compressed public key')
    parser.add_argument('-rb', dest='rb', required=True, type=str, help='Begin range')
    parser.add_argument('-re', dest='re', required=True, type=str, help='End range')
    args = parser.parse_args()

    if args.workfile:
        print(f'Workfile {args.workfile}')
        MakeChanges(args.workfile, args.pub, int(args.rb,16), int(args.re,16))

   

Hi,
Thank You for posting link and description. Have You ever gentelmans thought about creating 110bit of DPs instead of 80bit like in recent challange? Is it even possible? How big shuld be work file for -m 3 in that case? It would take aprox 15 Years with 10k CUDA core card. Crazy idea, but thereafter ~33.000.000 possible ranges for #135 to check. Economicaly, there is no point in such a move, but I think that there are some romantic in here In theory, how long does it take to check new public key in precompiled 110bit work file? @Etar, how long does it take You to find new public key with 80bit precompiled workfile?

BR
Damian

[Etar]

@kTimesG, how many DPs did you manage to accumulate for the 80-bit range?
Have you tried expanding these points to the 110-130 bit range?

[kTimesG]

Hi,
Thank You for posting link and description. Have You ever gentelmans thought about creating 110bit of DPs instead of 80bit like in recent challange? Is it even possible? How big shuld be work file for -m 3 in that case? It would take aprox 15 Years with 10k CUDA core card. Crazy idea, but thereafter ~33.000.000 possible ranges for #135 to check. Economicaly, there is no point in such a move, but I think that there are some romantic in here In theory, how long does it take to check new public key in precompiled 110bit work file? @Etar, how long does it take You to find new public key with 80bit precompiled workfile?

https://cr.yp.to/dlog/cuberoot-20120919.pdf

Once you read and understand what it is written in that paper you should then understand what is the purpose and usefulness of precomputed DPs. Basically, it's the result of storing the output of many multiple solves on top of each other to help with future solves, it is not a magical way for simplifying the first solve, which is actually slower than usual if the purpose is building the DP database. And splitting the range to solve smaller ranges just increases the overall complexity, it does not reduce anything, on the contrary.

So, you can't really precompute #135 DPs if you can't first solve #135 in reasonable time, and repeat this process a lot of times.