Bitcoin Forum

02b5c3acff8a44ff0948bf094d949d1d39734318a752e6215169a835f72314a79a

 import random
import hashlib
from sage.crypto.util import ascii_to_bin
from sage.arith.misc import random_prime
from sage.crypto.util import ascii_to_bin
from sage.crypto.util import bin_to_ascii

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

E = EllipticCurve(GF(p), [0, 7]) 

r = 0x
s = 0x
z = 0x


G = E.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8))   # Base point

def egcd(a, b):

    if a == 0:

        return (b, 0, 1)

    else:

        g, y, x = egcd(b % a, a)

        return (g, x - (b // a) * y, y)

def modinv(a, m):

    g, x, y = egcd(a, m)

    if g != 1:

        raise Exception('modular inverse does not exist')

    else:

        return x % m


def make_public(r, s, z):
    R = E.lift_x(Integer(r))
    w = int(modinv(s, n))
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    u_n2 = modinv(u2, n) % n
    u_n1 = - u1 * modinv(u2, n) % n
    
    pub = u_n1 * G + u_n2 * R
    pub2 = u_n1 * G + u_n2 * (-R)
    return pub, pub2



def calc_u(r, s, z):
    mod_s = modinv(s, n) % n
    u1 = mod_s * z % n
    u2 = mod_s * r % n
    print("u1 =", hex(u1), "n-u1 =", hex(n - u1))
    print("u2 =", hex(u2), "n-u2 =", hex(n - u2))
    return u1, u2
u1, u2 = calc_u(r, s, z)

def verify(r, s, z, pub, k):
    w = int(modinv(s, n))
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    D = u1 * G + u2 * pub
    x, y = D.xy()
    x = int(x)

    if (r % n) == (x % n):
        print(f"Signature k matches: {hex(k)} ")
        return True
    else:
        print(f"Signature k is invalid {hex(k)} ")
        return False

# Calculate the modular inverse of s (w = s^(-1) mod n)
g, x, y = egcd(s, n)
w = x % n

def find_k(r, s, z, pub):
    # Step 1: Calculate w = s^(-1) mod n
    w = int(modinv(s, n))
    
    # Step 2: Calculate u1 and u2
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    
    # Step 3: Recover the elliptic curve point R
    R = u1 * G + u2 * pub
    
    # Extract x-coordinate from R
    x_R, _ = R.xy()
    x_R = int(x_R)
    
    # Calculate k
    k = (x_R - z) * modinv(w, n) % n
    print("k:",k)
    
    return k

# Call the function to find k
k = find_k(r, s, z, pub1)
print("Found k:", hex(k))

pub1, pub2 = make_public(r, s, z)
print("public_key1", pub1)
print("pub1_x=", hex(pub1.xy()[0]))
print("public_key2", pub2)
print("pub2_x=", hex(pub2.xy()[0]))
print("Step 1: Calculate g, x, y using extended Euclidean algorithm")
print("g:", hex(g))
print("x:", hex(x))
print("y:", hex(y))
print("Step 2: Calculate w (modular inverse of s)")
print("Calculated w:", hex(w))
print()


def find_k_bruteforce(r, s, z, pub):
    i = 1
    while True:
        k_candidate = (r * i + z) * modinv(s, n) % n
        
        # Verify the signature using the candidate k
        if verify(r, s, z, pub, k_candidate):
            print("Found k:", hex(k_candidate))
            break
        else:
            print(f"Attempt {i}: Incorrect k value {hex(k_candidate)}")
        
        i += 1  # Increment the attempt counter

# Call the function to find k using brute force
find_k_bruteforce(r, s, z, pub1)

def find_private_key(r, s, z, k, pub):
    # Calculate w = s^(-1) mod n
    w = int(modinv(s, n))
    
    # Calculate u1 and u2
    u1 = int((z * w) % n)
    u2 = int((r * w) % n)
    
    # Recover the elliptic curve point R
    R = u1 * G + u2 * pub
    
    # Extract x-coordinate from R
    x_R, _ = R.xy()
    x_R = int(x_R)
    
    # Calculate private key d
    d = (k * x_R - z) * modinv(r, n) % n
    
    return d

def find_private_key_bruteforce(r, s, z, k, pub, i):
    k_candidate = (r * i + z) * modinv(s, n) % n
    
    # Calculate private key d
    d = (k_candidate * r - z) * modinv(k_candidate, n) % n
    
    return d

# Call the function to find k using the formula-based approach
k_formula = find_k(r, s, z, pub1)
d_formula = find_private_key(r, s, z, k_formula, pub1)
print("Private key (formula-based):", hex(d_formula))

# Call the function to find k using brute force
k_bruteforce = find_k_bruteforce(r, s, z, pub1)
i_bruteforce = 1
d_bruteforce = find_private_key_bruteforce(r, s, z, k_bruteforce, pub1, i_bruteforce)
print(f"Private key (brute-force attempt {i_bruteforce}):", hex(d_bruteforce))

guessed_k_values = []
i = 1

while True:
    k = (r * i + z) * modinv(s, n) % n
    # Calculate R using the guessed k value
    guessed_R = k * G
    guessed_k_values.append((i, k, guessed_R))

    # Check if the guessed R value matches the original r value
    if guessed_R.xy()[0] == r:
        print(f"The correct k value ({k}) for iteration {i} is found.")
        # Calculate the private key using the correct k value
        d_bruteforce = find_private_key_bruteforce(r, s, z, k, pub1, i)
        print(f"Corresponding private key: {hex(d_bruteforce)}")
        break  # Exit the loop if the correct k is found

    i += 1  # Increment the iteration counter

import time
import os
import sys
import random
import secp256k1 as ice
import gmpy2

if os.name == 'nt':
    os.system('cls')
else:
    os.system('clear')
t = time.ctime()
sys.stdout.write(f"\033[?25l")
sys.stdout.write(f"\033[01;33m[+] Kangaroo: {t}\n")
sys.stdout.flush()

modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = gmpy2.mpz(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

# Define Point class
class Point:
    def __init__(self, x=0, y=0):
        self.x = gmpy2.mpz(x)
        self.y = gmpy2.mpz(y)

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x, y - plane

def add(P, Q, p=modulo):
    if P == Z:
        return Q
    elif Q == Z:
        return P
    elif P.x == Q.x and (P.y != Q.y or P.y == 0):
        return Z
    elif P.x == Q.x:
        m = (3 * P.x * P.x) * gmpy2.invert(2 * P.y, p) % p
    else:
        m = (Q.y - P.y) * gmpy2.invert(Q.x - P.x, p) % p
   
    x = (m * m - P.x - Q.x) % p
    y = (m * (P.x - x) - P.y) % p
    return Point(x, y)

def mul2(P, p=modulo):
    if P == Z:
        return Z
    m = gmpy2.f_mod(3 * P.x * P.x * gmpy2.invert(2 * P.y, p), p)
    x = gmpy2.f_mod(m * m - 2 * P.x, p)
    y = gmpy2.f_mod(m * (P.x - x) - P.y, p)
    return Point(x, y)

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p), p)

def X2Y(X, y_parity, p=modulo):
    X_cubed = gmpy2.powmod(X, 3, p)
    X_squared = gmpy2.powmod(X, 2, p)
    tmp = gmpy2.f_mod(X_cubed + 7, p)
    Y = gmpy2.powmod(tmp, gmpy2.f_div(gmpy2.add(p, 1), 4), p)
    if y_parity == 1:
        Y = gmpy2.f_mod(-Y, p)
    return Y


def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        HEX = "%064x" % abs(Ak[sol_kt] - Bk[sol_kw])
        dec = int(HEX, 16)
        wifc = ice.btc_pvk_to_wif(HEX)
        wifu = ice.btc_pvk_to_wif(HEX, False)
        caddr = ice.privatekey_to_address(0, True, dec)
        uaddr = ice.privatekey_to_address(0, False, dec)
        total_time = time.time() - starttime
        print('\n[+] total time: %.2f sec' % (total_time))
        t = time.ctime()
        print(f"\033[32m[+] PUZZLE SOLVED: {t} \033[0m")
        print(f"\033[32m[+] Private key (wif) Compressed : {wifc} \033[0m")
        with open("KEYFOUNDKEYFOUND.txt", "a") as file:
            file.write("\n\nSOLVED " + t)
            file.write(f"\nTotal Time: {total_time:.2f} sec")
            file.write(f"\nRandom seed: {seed}")
            file.write("\nPrivate Key (decimal): " + str(dec))
            file.write("\nPrivate Key (hex): " + HEX)
            file.write("\nPrivate key (wif) Compressed : " + wifc)
            file.write("\nPrivate key (wif) Uncompressed: " + wifu)
            file.write("\nBitcoin address Compressed: " + caddr)
            file.write("\nBitcoin address Uncompressed: " + uaddr)
            file.write(
                "\n-------------------------------------------------------------------------------------------------------------------------------------------\n"
            )
        file.close()
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(gmpy2.mpz(P.x))
        Ak.append(gmpy2.mpz(Pindex))
        return comparator(A, Ak, B, Bk)
    else:
        return False

# Generate a list of powers of two for faster access

def generate_powers_of_two(hop_modulo):
    return [gmpy2.mpz(1 << pw) for pw in range(hop_modulo)]

def search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two):
    solved = False
    t = [gmpy2.mpz(lower_range_limit + gmpy2.mpz(random.randint(0, upper_range_limit - lower_range_limit))) for _ in range(Nt)]
    T = [mulk(ti) for ti in t]
    dt = [gmpy2.mpz(0) for _ in range(Nt)]
    w = [gmpy2.mpz(random.randint(0, upper_range_limit - lower_range_limit)) for _ in range(Nw)]
    W = [add(W0, mulk(wk)) for wk in w]
    dw = [gmpy2.mpz(0) for _ in range(Nw)]
    print('[+] tame and wild herds are prepared')
    Hops, Hops_old = 0, 0
    t0 = time.time()   
    while not solved:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = powers_of_two[pw]
            solved = check(T[k], t[k], DP_rarity, T, t, W, w)
            if solved: break
            t[k] += dt[k]
            T[k] = add(P[int(pw)], T[k])
        if solved: break
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = powers_of_two[pw]
            solved = check(W[k], w[k], DP_rarity, W, w, T, t)
            if solved: break
            w[k] += dw[k]
            W[k] = add(P[int(pw)], W[k])
        if solved: break
        t1 = time.time()
        if (t1 - t0) > 5:
            print('\r[+] Hops: %.0f h/s' % ((Hops - Hops_old) / (t1 - t0)), end='', flush=True)
            t0 = t1
            Hops_old = Hops
    print('[+] Hops:', Hops)
    return 'sol. time: %.2f sec' % (time.time() - starttime)

puzzles = [\
    ('0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69',32),\
    ('03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4',40),\
    ('025e466e97ed0e7910d3d90ceb0332df48ddf67d456b9e7303b50a3d89de357336',44),\
    ('026ecabd2d22fdb737be21975ce9a694e108eb94f3649c586cc7461c8abf5da71a',45),\
    ('03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6',50),\
    ('0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b',65),\
    ('03633cbe3ec02b9401c5effa144c5b4d22f87940259634858fc7e59b1c09937852',130)]

puzzle = 45
for elem in puzzles:
    s, n = elem
    if puzzle == n: break

kangaroo_power = puzzle // 10
DP_rarity = 1 << int(((puzzle -  2*kangaroo_power)/2 - 2))
hop_modulo = ((puzzle - 1) // 2) + kangaroo_power
Nt = Nw = 2**kangaroo_power

X = gmpy2.mpz(s[2:66], 16)
Y = X2Y(X, gmpy2.mpz(s[:2]) - 2)

W0 = Point(X,Y)
starttime = oldtime = time.time()
search_range = 2**(puzzle-1)

lower_range_limit = 2 ** (puzzle - 1)
upper_range_limit = (2 ** puzzle) - 1

print(f"[+] [Puzzle]: {puzzle}")
print(f"[+] [Lower range limit]: {lower_range_limit}")
print(f"[+] [Upper range limit]: {upper_range_limit}")

# Precompute powers of two for faster access
powers_of_two = generate_powers_of_two(hop_modulo)

# Initialize variables
T, t, dt = [], [], []
W, w, dw = [], [], []

#Random seed Config
dd = list(str(random.randint(1,2**256)))
random.shuffle(dd); random.shuffle(dd)
seed = int(''.join(dd))
print(f"[+] [Random seed]: {seed}")
random.seed(seed)

Hops = 0
N_tests = 1

P = [PG]
for k in range(255): P.append(mul2(P[k]))   
print('[+] P-table prepared')

for k in range(N_tests):
    solved = False
    search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two)

print('[+] Average time to solve: %.2f sec' % ((time.time()-starttime)/N_tests))