Pollard's kangaroo ECDLP solver

[digaran]

Hello there, where is the private key for #120?

it is

Code:

02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630

and the coins were pulled on 2023/02/27

Cool story, but I asked about the Private key not public key,  he claimed to know stuff, So I tested him. 😉

[1714473847]

1714473847

[citb0in]

Sure. Understood. That's why I warned about this user, this is a new user registration and he's posting always URL and writing non-sens stuff to attract users clicking on his phishing links.

[kalos15btc]

i have questions about kangaroo algo, i tested it on cpu ; 30mk per s. not like bsgs 7Terrak per sec is that okey or im missing some configuration on kangaroo ? why we dont use bsgs since its faster than kangaroo ? and one more question, is kangaroo work random or sequencial ? if i put a range he will work sequ thank you

[JDScreesh]

WOW! Somebody (maybe the owner) increased the unsolved puzzles prizes again by x10 😱
Now the puzzle #66 prize is 6.6 BTC, #67 is 6.7 BTC... and so on .... puzzle # 160 prize is now 16 BTC 👍🏼🥳

[Lolo54]

WOW! Somebody (maybe the owner) increased the unsolved puzzles prizes again by x10 😱
Now the puzzle #66 prize is 6.6 BTC, #67 is 6.7 BTC... and so on .... puzzle # 160 prize is now 16 BTC 👍🏼🥳

waouuhhh yes exactly I just saw that indeed OP raised the bonus of all #Puzzles by X10 it makes you want even more especially for the lowest ones it becomes very very interesting 

[digaran]

What happens if the number of dead kangaroos exceed the total kangaroo count?
And why do I see average as a few minutes sometimes and as million years other times? Is it a good sign if the average time is low?

[WanderingPhilospher]

What happens if the number of dead kangaroos exceed the total kangaroo count?
And why do I see average as a few minutes sometimes and as million years other times? Is it a good sign if the average time is low?

Usually means you are in a very small range.

Would need to see your commands/flags you are passing to the program as well as input to understand more.

[AshrafCsr]

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

Hi Eter,
It is possible to automatically printed output number of decimal; which are reduced.

[WanderingPhilospher]

Hi Eter,
It is possible to automatically printed output number of decimal; which are reduced.

Yes, are you wanting to print all results to a .txt file?

[AshrafCsr]

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)

# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
def shiftdown(pubkey, divisor, file, convert=True):
    Q = pub2point(pubkey) if convert else pubkey
    # k = 1/divisor
    k = pow(divisor, N - 2, N)
    for i in range(divisor):
        P = Q - (i * G)
        P = k * P
        if (P.y % 2 == 0):
            prefix = "02"
        else:
            prefix = "03"
        hx = hex(P.x)[2:].zfill(64)
        hy = hex(P.y)[2:].zfill(64)
        file.write(prefix+ " " + hx+"\n") # Writes compressed key to file
    file.write("\n") # Writes compressed key to file

with open("input.txt", "r") as f, open("output.txt", "w") as outf:
    line = f.readline().strip()
    while line != '':
        outf.write("original: " +line + "\n")
        shiftdown(line, pow(2,1), outf)
        line = f.readline().strip()

input:

Code:

02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4

..d13 is 4 and ...fe4 is 5

output:

original: 02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413

original: 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
03 5699b93fc6e1bd29e09a328d657a607b4155b61a6b5fcbedd7c12df7c67df8f5
02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5

02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 is 2

Because i know 4 is even, i know it has to be the first pubkey. Because i know 5 is odd, I know it has to be the second key.

The problem is, that in bigger numbers, you can not determine if it is odd or even.

See,if I add the pubkey of 3

original: 02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 -> pubkey of 3
02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413 -> not the halve
02 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 -> pubkey of 1

original: 02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13 -> pubkey of 4
02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 -> odd pubkey of 5
02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413 -> even pubkey of 3

original: 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4 -> pubkey of 5
03 5699b93fc6e1bd29e09a328d657a607b4155b61a6b5fcbedd7c12df7c67df8f5 -> not the halve
02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5-> pubkey of 2

You see... You can not determine from the halve if it is the correct one.

Hi,
It is possible to automatically printed output number of decimal; which are reduced.

[NotATether]

I suggest using a more efficient way to generate the downscaled public keys by utilizing the add and double operations of elliptic curve cryptography. Here is a modified version of the shiftdown function:

Code:

def shiftdown(pubkey, divisor, file, convert=True):
    Q = pub2point(pubkey) if convert else pubkey
    # k = 1/divisor
    k = pow(divisor, N - 2, N)
    R = Point.identity(curve=curve.secp256k1)
    for i in range(divisor):
        R += Q # Equivalent to subtracting (divisor - i) * G
        P = k * R
        if (P.y % 2 == 0):
            prefix = "02"
        else:
            prefix = "03"
        hx = hex(P.x)[2:].zfill(64)
        hy = hex(P.y)[2:].zfill(64)
        file.write(prefix+ " " + hx+"\n") # Writes compressed key to file
    file.write("\n") # Writes compressed key to file

This modified version adds the public key Q to a running variable R, which is initially the identity element. On each loop iteration, R is incremented by Q using the add operation, which is much faster than subtracting a multiple of G. Then, the public key P is computed by multiplying R by the inverse of the divisor modulo N, using the pow function. Finally, P is written to the output file in compressed form, as before. This algorithm has a time complexity of O(divisor), which is much faster than the original algorithm's O(divisor^2) time complexity.

That AI-generated version of my shiftdown is horseshit and will promptly be reported for spam. (Although it is also possible that you just pasted my code and stole the attribution for it.)

[sssergy2705]

That AI-generated version of my shiftdown is horseshit and will promptly be reported for spam.

Chat gpt version 4 considers the second option to be more visual and productive in terms of using intermediate results. 

[NotATether]

That AI-generated version of my shiftdown is horseshit and will promptly be reported for spam.

Chat gpt version 4 considers the second option to be more visual and productive in terms of using intermediate results. 

On a more serious note, don't use that script. It's slow. I made a C++ shiftdown that is 8x faster than this Python on a single thread, using GMP.

PM me if you want the download. It is not FOSS.

[AshrafCsr]

Hi Eter,
It is possible to automatically printed output number of decimal; which are reduced.

Yes, are you wanting to print all results to a .txt file?

Hi,
I wanted to automatically printed output number of decimal; which are reduced through bit range.
As like: https://github.com/iceland2k14/quick/blob/main/PubSub.py

Could you please help me.

[sssergy2705]

Hi Eter,
It is possible to automatically printed output number of decimal; which are reduced.

Yes, are you wanting to print all results to a .txt file?

Hi,
I wanted to automatically printed output number of decimal; which are reduced through bit range.
As like: https://github.com/iceland2k14/quick/blob/main/PubSub.py

Could you please help me.

This is impossible. you can print many keys, but the chance is small that it will be correct

[brainless]

Hi Eter,
It is possible to automatically printed output number of decimal; which are reduced.

Yes, are you wanting to print all results to a .txt file?

Hi,
I wanted to automatically printed output number of decimal; which are reduced through bit range.
As like: https://github.com/iceland2k14/quick/blob/main/PubSub.py

Could you please help me.

write in details ....

[AshrafCsr]

Hi Eter,
It is possible to automatically printed output number of decimal; which are reduced.

Yes, are you wanting to print all results to a .txt file?

Hi,
I wanted to automatically printed output number of decimal; which are reduced through bit range.
As like: https://github.com/iceland2k14/quick/blob/main/PubSub.py

Could you please help me.

write in details ....

Hi,
I have find range from script as below:
Initial Pub: 0329fb788204d6b2b6797859572db2eb8c66c43756d4946bcad497ddec61b94d27
       Priv: 0x1F3869ACC5B

Key# 1 Pub:  0x02C9056EA5EBB46309024FF22C9668C2BEC887A0B3D48567CDB8D940F25B3C44D1 # -1072723486254
       Priv: 0xF9C34D662D

Key# 1 Pub:  0x033005E37EE6F877F86793334752F41E9243631C263414615A9B25DC98F35CF251 # -536361743127
       Priv: 0x7CE1A6B316

Key# 1 Pub:  0x025196FA41B4A8D8A1D1C48BAAD791B5EF5CC8A489D510A2BF72B725E2423105F0 # -268180871563
       Priv: 0x3E70D3598B

As a result: divisor = 2**1 equivalent reduce is an 1 BIT range. So i wanted a output below example 0x02C9056EA5EBB46309024FF22C9668C2BEC887A0B3D48567CDB8D940F25B3C44D1 # -1072723486254

Please advice it is possible.

[Lolo54]

Hi,
I have find range from script as below:
Initial Pub: 0329fb788204d6b2b6797859572db2eb8c66c43756d4946bcad497ddec61b94d27
       Priv: 0x1F3869ACC5B

Key# 1 Pub:  0x02C9056EA5EBB46309024FF22C9668C2BEC887A0B3D48567CDB8D940F25B3C44D1 # -1072723486254
       Priv: 0xF9C34D662D

Key# 1 Pub:  0x033005E37EE6F877F86793334752F41E9243631C263414615A9B25DC98F35CF251 # -536361743127
       Priv: 0x7CE1A6B316

Key# 1 Pub:  0x025196FA41B4A8D8A1D1C48BAAD791B5EF5CC8A489D510A2BF72B725E2423105F0 # -268180871563
       Priv: 0x3E70D3598B

As a result: divisor = 2**1 equivalent reduce is an 1 BIT range. So i wanted a output below example 0x02C9056EA5EBB46309024FF22C9668C2BEC887A0B3D48567CDB8D940F25B3C44D1 # -1072723486254

Please advice it is possible.

Yes your results are correct. But this is possible because you know the initial private key otherwise you would have a problem your result would be wrong and your PubKey not found on the curve.
Try to perform the same operations with this pubkey 03770538afe9b82a6a4d6511ee28427f68ce2d4c4a2598fd5453232e304bedb9e0
and your result will be false very quickly where you will need +/-1 so 2^n for each operation then just for -10 bit 2^10 1024 operations X2 because +/- so 2048  (2048 pubkey of which only one will be on the curve with -10bit) 11 bit 4096 operations

[brainless]

Hi Eter,
It is possible to automatically printed output number of decimal; which are reduced.

Yes, are you wanting to print all results to a .txt file?

Hi,
I wanted to automatically printed output number of decimal; which are reduced through bit range.
As like: https://github.com/iceland2k14/quick/blob/main/PubSub.py

Could you please help me.

write in details ....

Hi,
I have find range from script as below:
Initial Pub: 0329fb788204d6b2b6797859572db2eb8c66c43756d4946bcad497ddec61b94d27
       Priv: 0x1F3869ACC5B

Key# 1 Pub:  0x02C9056EA5EBB46309024FF22C9668C2BEC887A0B3D48567CDB8D940F25B3C44D1 # -1072723486254
       Priv: 0xF9C34D662D

Key# 1 Pub:  0x033005E37EE6F877F86793334752F41E9243631C263414615A9B25DC98F35CF251 # -536361743127
       Priv: 0x7CE1A6B316

Key# 1 Pub:  0x025196FA41B4A8D8A1D1C48BAAD791B5EF5CC8A489D510A2BF72B725E2423105F0 # -268180871563
       Priv: 0x3E70D3598B

As a result: divisor = 2**1 equivalent reduce is an 1 BIT range. So i wanted a output below example 0x02C9056EA5EBB46309024FF22C9668C2BEC887A0B3D48567CDB8D940F25B3C44D1 # -1072723486254

Please advice it is possible.

if you have privatekey and pubkey, and like div, and get print in file result pubkey and prvkey, its possible

[unclevito]

Do anyone happen to know if the LHR function in a RTX card will slow up bitcrack or vanity search or kangaroo