krashfire (OP)
Member
Offline
Activity: 127
Merit: 14
Life aint interesting without any cuts and bruises
|
|
May 13, 2024, 07:01:30 AM |
|
Hi, im hoping to get some advice on how i can fine tune, optimized or enhance my code further to calculate the 256 bit private key. your advice is very much appreciated. import random from math import gcd
# Function to extract public key coordinates from hex string def extract_public_key_coordinates(public_key): try: x, y = public_key.split(',') print("Public key coordinates extracted successfully.") return int(x, 16), y except ValueError: print("Error: Invalid public key format.") return None, None
# Function for Pollard's Rho factorization def pollard_rho_factorization(n, limit=1000000): print("Performing Pollard's Rho factorization...") def f(x): return (x ** 2 + 1) % n
x = random.randint(1, n - 1) y = x d = 1
while d == 1: x = f(x) y = f(f(y)) d = gcd(abs(x - y), n)
return d if d != n else None
# Function to perform the Kangaroo algorithm with factors def kangaroo_algorithm(g, h, n, factors, B): print("Performing Kangaroo algorithm...") P = 0 Q = 0 wild_kangaroos = [(random.randint(1, n - 1), random.randint(1, n - 1)) for _ in range(10)] # Multiple parallel wild kangaroos wild_jump_size = random.randint(1, B // 10) # Randomized wild kangaroo step size
while True: for wild_x, wild_y in wild_kangaroos: u = wild_x v = wild_y for _ in range(wild_jump_size): u = (u * g) % n v = (v * h) % n d = gcd(u - v, n) if 1 < d < n: return d if d == 1: alpha = kangaroo_attack(P, Q, g, n, h, B) # Using kangaroo_attack if alpha is not None: return alpha P += B Q += B else: return d
# Simple Kangaroo Attack (Floyd's Cycle Detection Algorithm) def kangaroo_attack(P, Q, g, n, h, B): print("Performing Kangaroo attack...") u = P v = Q u_iterations = 0 v_iterations = 0
while True: # Tame Kangaroo u = (u * g) % n u_iterations += 1
# Wild Kangaroo v = (v * h) % n v_iterations += 1
if u == v: # Collision detected, solve for alpha alpha = (P - Q) * pow(g, -1, n) % n # Inverse of g modulo n return alpha
if max(u_iterations, v_iterations) > B: # Maximum iterations reached without collision return None
if __name__ == "__main__": # Example usage public_key = "d6xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx,3xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" x, y_hex = extract_public_key_coordinates(public_key)
if x is not None and y_hex is not None: # Convert y-coordinate from hex to integer try: y = int(y_hex, 16) print("Y-coordinate converted to integer successfully.") except ValueError: print("Error: Unable to convert y-coordinate to integer.")
# Perform factorization using Pollard's Rho try: factors = [pollard_rho_factorization(number) for number in [x, y, x + y]] print("Factorization complete:", factors) except Exception as e: print("Error during factorization:", e)
# Parameters for Kangaroo algorithm p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 g = 55066263022277343669578718895168534326250603453777594175500187360389116729240 h = y # Use the integer value of y B = 2**42 # Adjust based on your system's memory constraints
# Find private key using the Kangaroo algorithm with factors try: private_key = kangaroo_algorithm(g, h, n, factors, B) print("Private Key:", private_key) except Exception as e: print("Error during Kangaroo algorithm:", e) else: print("Error: Public key extraction failed.")
|
KRASH
|
|
|
COBRAS
Member
Offline
Activity: 1017
Merit: 23
|
|
May 14, 2024, 01:26:12 AM |
|
Imposible to dolve 256 bit
and in python imposible to solve 100 bit
|
[
|
|
|
satashi_nokamato
Jr. Member
Offline
Activity: 50
Merit: 3
|
|
May 14, 2024, 01:35:36 PM |
|
How do you set the range to search for the key? Also what is h and which y should we use in this line "h = y # Use the integer value of y" ?
|
|
|
|
krashfire (OP)
Member
Offline
Activity: 127
Merit: 14
Life aint interesting without any cuts and bruises
|
|
May 15, 2024, 03:45:48 AM |
|
How do you set the range to search for the key? Also what is h and which y should we use in this line "h = y # Use the integer value of y" ?
Here's a simplified explanation of how the Kangaroo algorithm works in this context: Tame Kangaroos: These kangaroos make small jumps and keep track of their positions as they move along the curve. They're responsible for exploring the region near the expected position of 𝑘 k and 𝑄 Q. Wild Kangaroos: These kangaroos make large jumps and are used to cover a wider range of possible positions of 𝑘 k and 𝑄 Q. Collision Detection: The algorithm looks for collisions, which occur when a tame kangaroo and a wild kangaroo land on the same point on the curve. This indicates a potential match for 𝑘 k and 𝑄 Q. Private Key Extraction: Once a collision is detected, you can extract the private key 𝑘 k from the positions of the kangaroos at the collision point. The key concept here is that you're not searching through a numerical range of 𝑘 k values linearly. Instead, you're using kangaroos to explore the curve in a smart way, leveraging collisions to pinpoint the private key without exhaustively trying every possible 𝑘 k value. h = y means the public key xy coordinates. in this part we are just using y.
|
KRASH
|
|
|
nomachine
Member
Offline
Activity: 476
Merit: 35
|
|
May 16, 2024, 11:39:03 AM Last edit: May 16, 2024, 11:59:52 AM by nomachine |
|
I have 205288 hops per second in python on single core my friend...... It will work from 1 - 256 bit . But it is impossible to solve any Puzzle above 50 with this for a lifetime. import time import os import sys import random 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) 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 (dec) : {dec} \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( "\n-------------------------------------------------------------------------------------------------------------------------------------------\n" ) file.close() return True else: return False
def check(P, Pindex, DP_rarity, A, Ak, B, Bk): modulo_val = P.x % DP_rarity if modulo_val == 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()
# Memoization dictionary memo = {}
while not solved: for k in range(Nt): Hops += 1 pw = T[k].x % hop_modulo if pw not in memo: memo[pw] = powers_of_two[pw] dt[k] = memo[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 if pw not in memo: memo[pw] = powers_of_two[pw] dw[k] = memo[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)
# Configuration for the puzzle puzzle = 40 compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4" kangaroo_power = 4 lower_range_limit = 2 ** (puzzle - 1) upper_range_limit = (2**puzzle) - 1
DP_rarity = 1 << int(((puzzle - 2*kangaroo_power)/2 - 2)) hop_modulo = ((puzzle - 1) // 2) + kangaroo_power Nt = Nw = 2**kangaroo_power
# Precompute powers of two for faster access powers_of_two = generate_powers_of_two(hop_modulo)
T, t, dt = [], [], [] W, w, dw = [], [], []
if len(compressed_public_key) == 66: X = gmpy2.mpz(compressed_public_key[2:66], 16) Y = X2Y(X, gmpy2.mpz(compressed_public_key[:2]) - 2) else: print("[error] pubkey len(66/130) invalid!")
W0 = Point(X,Y) starttime = oldtime = time.time()
print(f"[+] [Puzzle]: {puzzle}") print(f"[+] [Lower range limit]: {lower_range_limit}") print(f"[+] [Upper range limit]: {upper_range_limit}")
#Random seed Config seed = os.urandom(9).hex() print(f"[+] [Random seed]: {seed}") random.seed(seed)
Hops = 0
P = [PG] for k in range(255): P.append(mul2(P[k])) print('[+] P-table prepared')
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))) - Kangaroo: Thu May 16 13:33:48 2024
- [Puzzle]: 40
- [Lower range limit]: 549755813888
- [Upper range limit]: 1099511627775
- [Random seed]: 9b76a9623bd76fb8cc
- P-table prepared
- tame and wild herds are prepared
- Hops: 205288 h/s
- total time: 6.92 sec
- PUZZLE SOLVED: Thu May 16 13:33:55 2024
- Private key (dec) : 1003651412950
- Hops: 1416585
- Average time to solve: 6.92 sec
It needs to be converted into C++ or Rust so that it can solve problems up to puzzle 120.
|
bc1qdwnxr7s08xwelpjy3cc52rrxg63xsmagv50fa8
|
|
|
krashfire (OP)
Member
Offline
Activity: 127
Merit: 14
Life aint interesting without any cuts and bruises
|
|
May 16, 2024, 11:57:28 AM |
|
i have created twist attack on ecdsa secp256k1. can read about Twist Attack on ECDSA SECP256k1 here. https://github.com/demining/Twist-AttackIt gets the partial private key correctly. my issue now is how to write the code to get to the full private key. PM Me Bruhhh.... im lost. from fastecdsa.curve import secp256k1 from fastecdsa.point import Point from fastecdsa.keys import gen_private_key, get_public_key from sympy import mod_inverse
# Generate a private key private_key = gen_private_key(secp256k1)
# Get the corresponding public key public_key = get_public_key(private_key, secp256k1)
# Print the private key and its bit length print("Original Private Key:", hex(private_key)) print("Private Key Bit Length:", private_key.bit_length())
# Print the public key coordinates (x, y) print("Original Public Key (x, y):", public_key.x, public_key.y)
# Twist Attack n = secp256k1.q # Order of the curve Gx, Gy = public_key.x, public_key.y
# Calculate the twist point twist_x = Gx twist_y = (-Gy) % secp256k1.p print("twist_y:", hex(twist_y))
# Perform twist attack to find the partial private key partial_private_key = (twist_y * mod_inverse(Gy, n)) % n
# Print the partial private key and its bit length print("Partial Private Key:", hex(partial_private_key)) print("Partial Private Key Bit Length:", partial_private_key.bit_length())
|
KRASH
|
|
|
greenAlien
Newbie
Offline
Activity: 12
Merit: 0
|
|
May 16, 2024, 12:54:27 PM |
|
I have 205288 hops per second in python on single core my friend...... It will work from 1 - 256 bit . But it is impossible to solve any Puzzle above 50 with this for a lifetime. import time import os import sys import random 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) 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 (dec) : {dec} \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( "\n-------------------------------------------------------------------------------------------------------------------------------------------\n" ) file.close() return True else: return False
def check(P, Pindex, DP_rarity, A, Ak, B, Bk): modulo_val = P.x % DP_rarity if modulo_val == 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()
# Memoization dictionary memo = {}
while not solved: for k in range(Nt): Hops += 1 pw = T[k].x % hop_modulo if pw not in memo: memo[pw] = powers_of_two[pw] dt[k] = memo[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 if pw not in memo: memo[pw] = powers_of_two[pw] dw[k] = memo[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)
# Configuration for the puzzle puzzle = 40 compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4" kangaroo_power = 4 lower_range_limit = 2 ** (puzzle - 1) upper_range_limit = (2**puzzle) - 1
DP_rarity = 1 << int(((puzzle - 2*kangaroo_power)/2 - 2)) hop_modulo = ((puzzle - 1) // 2) + kangaroo_power Nt = Nw = 2**kangaroo_power
# Precompute powers of two for faster access powers_of_two = generate_powers_of_two(hop_modulo)
T, t, dt = [], [], [] W, w, dw = [], [], []
if len(compressed_public_key) == 66: X = gmpy2.mpz(compressed_public_key[2:66], 16) Y = X2Y(X, gmpy2.mpz(compressed_public_key[:2]) - 2) else: print("[error] pubkey len(66/130) invalid!")
W0 = Point(X,Y) starttime = oldtime = time.time()
print(f"[+] [Puzzle]: {puzzle}") print(f"[+] [Lower range limit]: {lower_range_limit}") print(f"[+] [Upper range limit]: {upper_range_limit}")
#Random seed Config seed = os.urandom(9).hex() print(f"[+] [Random seed]: {seed}") random.seed(seed)
Hops = 0
P = [PG] for k in range(255): P.append(mul2(P[k])) print('[+] P-table prepared')
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))) - Kangaroo: Thu May 16 13:33:48 2024
- [Puzzle]: 40
- [Lower range limit]: 549755813888
- [Upper range limit]: 1099511627775
- [Random seed]: 9b76a9623bd76fb8cc
- P-table prepared
- tame and wild herds are prepared
- Hops: 205288 h/s
- total time: 6.92 sec
- PUZZLE SOLVED: Thu May 16 13:33:55 2024
- Private key (dec) : 1003651412950
- Hops: 1416585
- Average time to solve: 6.92 sec
It needs to be converted into C++ or Rust so that it can solve problems up to puzzle 120. not a bad working code! Are you thinking on implementing multi threading? I know this is not comparable with GPU but its not bad at all Congrats!
|
|
|
|
COBRAS
Member
Offline
Activity: 1017
Merit: 23
|
|
May 17, 2024, 03:48:31 AM |
|
i have created twist attack on ecdsa secp256k1. can read about Twist Attack on ECDSA SECP256k1 here. https://github.com/demining/Twist-AttackIt gets the partial private key correctly. my issue now is how to write the code to get to the full private key. PM Me Bruhhh.... im lost. from fastecdsa.curve import secp256k1 from fastecdsa.point import Point from fastecdsa.keys import gen_private_key, get_public_key from sympy import mod_inverse
# Generate a private key private_key = gen_private_key(secp256k1)
# Get the corresponding public key public_key = get_public_key(private_key, secp256k1)
# Print the private key and its bit length print("Original Private Key:", hex(private_key)) print("Private Key Bit Length:", private_key.bit_length())
# Print the public key coordinates (x, y) print("Original Public Key (x, y):", public_key.x, public_key.y)
# Twist Attack n = secp256k1.q # Order of the curve Gx, Gy = public_key.x, public_key.y
# Calculate the twist point twist_x = Gx twist_y = (-Gy) % secp256k1.p print("twist_y:", hex(twist_y))
# Perform twist attack to find the partial private key partial_private_key = (twist_y * mod_inverse(Gy, n)) % n
# Print the partial private key and its bit length print("Partial Private Key:", hex(partial_private_key)) print("Partial Private Key Bit Length:", partial_private_key.bit_length())
Explain were you see partial privkey correctly ? I not see any parts of privkey in partial privkey ps as I know twist attack and defining twist,-attack he is bla bla bla about special base point or public keys I not remember this exact, but in your dcrypt you have only one possible twist point but attack and defining use many this points
|
[
|
|
|
nomachine
Member
Offline
Activity: 476
Merit: 35
|
|
June 15, 2024, 12:55:25 PM Last edit: June 15, 2024, 07:23:54 PM by nomachine |
|
not a bad working code! Are you thinking on implementing multi threading? I know this is not comparable with GPU but its not bad at all Congrats! Here you go import time import os import sys import random import gmpy2 import multiprocessing from math import log2, sqrt, log from multiprocessing import Pool, cpu_count
os.system("cls||clear") t = time.ctime() sys.stdout.write(f"\033[?25l") sys.stdout.write(f"\033[01;33m[+]\033[32m KANGAROO: \033[01;33m{t}\n") sys.stdout.flush()
modulo = gmpy2.mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F) Gx = gmpy2.mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798) Gy = gmpy2.mpz(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8) PG = (Gx, Gy)
Z = (0, 0) # zero-point, infinite in real x, y - plane
def add(P, Q, p=modulo): Px, Py = P Qx, Qy = Q if P == Z: return Q elif Q == Z: return P elif Px == Qx and (Py != Qy or Py == 0): return Z elif Px == Qx: m = (3 * Px * Px) * gmpy2.invert(2 * Py, p) % p else: m = (Qy - Py) * gmpy2.invert(Qx - Px, p) % p x = (m * m - Px - Qx) % p y = (m * (Px - x) - Py) % p return (x, y)
def mul2(P, p=modulo): Px, Py = P if P == Z: return Z m = gmpy2.f_mod(3 * Px * Px * gmpy2.invert(2 * Py, p), p) x = gmpy2.f_mod(m * m - 2 * Px, p) y = gmpy2.f_mod(m * (Px - x) - Py, p) return (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) 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 (dec) : {dec} \033[0m") dash_line = '-' * 140 with open("KEYFOUNDKEYFOUND.txt", "a") as file: file.write(f"\n{dash_line}") 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(f"\n{dash_line}") file.close() return True else: return False
def check(P, Pindex, DP_rarity, A, Ak, B, Bk): modulo_val = P[0] % DP_rarity if modulo_val == 0: A.append(gmpy2.mpz(P[0])) 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(thread_id, P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, result_queue, powers_of_two): 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)] Hops, Hops_old = 0, 0 t0 = time.time() # Memoization dictionary memo = {} solution_found = False # Flag to control the loop while not solution_found: for k in range(Nt): Hops += 1 pw = T[k][0] % hop_modulo if pw not in memo: memo[pw] = powers_of_two[pw] dt[k] = memo[pw] if check(T[k], t[k], DP_rarity, T, t, W, w): result_queue.put((thread_id, T[k], t[k], W[k], w[k])) solution_found = True # Set flag to exit loop break # Exit the for-loop t[k] += dt[k] T[k] = add(P[int(pw)], T[k]) if solution_found: # Break the while-loop if solution is found break for k in range(Nw): Hops += 1 pw = W[k][0] % hop_modulo if pw not in memo: memo[pw] = powers_of_two[pw] dw[k] = memo[pw] if check(W[k], w[k], DP_rarity, W, w, T, t): result_queue.put((thread_id, T[k], t[k], W[k], w[k])) solution_found = True # Set flag to exit loop break # Exit the for-loop w[k] += dw[k] W[k] = add(P[int(pw)], W[k]) if solution_found: # Break the while-loop if solution is found break t1 = time.time() elapsed_time = t1 - starttime if t1 - t0 > 1 and thread_id == 0: hops_per_second = (Hops - Hops_old) / (t1 - t0) * cores hours, rem = divmod(elapsed_time, 3600) minutes, seconds = divmod(rem, 60) elapsed_time_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}" p_2 = f'{log2(Hops*cores):.2f}' print(f'[+] [Hops: 2^{p_2} <-> {hops_per_second:.0f} h/s] [{elapsed_time_str}]', end='\r', flush=True) t0 = t1 Hops_old = Hops print('\r[+] Hops:', Hops* cores) print('[+] Average time to solve: %.2f sec' % ((time.time()-starttime)))
def main(): result_queue = multiprocessing.Queue() processes = [ multiprocessing.Process(target=search, args=(i, P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, result_queue, powers_of_two)) for i in range(cores) ] for p in processes: p.start() result = result_queue.get() for p in processes: p.terminate()
# Configuration for the puzzle cores = cpu_count() puzzle = 40 compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4" kangaroo_power = 3 lower_range_limit = 2 ** (puzzle - 1) upper_range_limit = (2**puzzle) - 1
DP_rarity = 1 << int(((puzzle - 2*kangaroo_power)/2 - 2)) hop_modulo = ((puzzle - 1) // 2) + kangaroo_power Nt = Nw = 2**kangaroo_power
# Precompute powers of two for faster access powers_of_two = generate_powers_of_two(hop_modulo)
T, t, dt = [], [], [] W, w, dw = [], [], [] A, Ak, B, Bk = [], [], [], [] print('[+] [Tame and Wild herds are prepared]')
if len(compressed_public_key) == 66: X = gmpy2.mpz(compressed_public_key[2:66], 16) Y = X2Y(X, gmpy2.mpz(compressed_public_key[:2]) - 2) else: print("[error] pubkey len(66/130) invalid!")
W0 = (X,Y) starttime = oldtime = time.time()
Hops = 0
P = [PG] for k in range(255): P.append(mul2(P[k])) print('[+] [P-table prepared]')
print(f"[+] [Using {cores} CPU cores for parallel search]") print(f"[+] [Puzzle: {puzzle}]") print(f"[+] [Lower range limit: {lower_range_limit}]") print(f"[+] [Upper range limit: {upper_range_limit}]") print(f"[+] [Expected Hops: 2^{log2(2.2 * sqrt(1 << (puzzle-1))):.2f} ({int(2.2 * sqrt(1 << (puzzle-1)))})]")
#Random seed Config seed = os.urandom(9).hex() print(f"[+] [Random seed: {seed}]") random.seed(seed)
if __name__ == '__main__': main()
- KANGAROO: Sat Jun 15 21:22:34 2024
- [Tame and Wild herds are prepared]
- [P-table prepared]
- [Using 12 CPU cores for parallel search]
- [Puzzle: 40]
- [Lower range limit: 549755813888]
- [Upper range limit: 1099511627775]
- [Expected Hops: 2^20.64 (1631201)]
- [Random seed: 0932dc777428d6f3b9]
- [Hops: 2^22.21 <-> 2443414 h/s] [00:00:02]
- total time: 2.18 sec
- PUZZLE SOLVED: Sat Jun 15 21:22:36 2024
- Private key (dec) : 1003651412950
- Hops: 5254560
- Average time to solve: 2.18 sec
But I won't give you false hope that this script can solve anything above 50 soon. It's simply beyond the reach of python's capabilities. You have to program in C++ yourself if the current scripts do not meet your needs.
|
bc1qdwnxr7s08xwelpjy3cc52rrxg63xsmagv50fa8
|
|
|
nomachine
Member
Offline
Activity: 476
Merit: 35
|
|
July 17, 2024, 06:33:08 PM |
|
Here is Kangaroo C++ in one single file: kangaroo.cpp #include <gmp.h> #include <gmpxx.h> #include <chrono> #include <ctime> #include <fstream> #include <iomanip> #include <iostream> #include <random> #include <vector> #include <set>
using namespace std;
typedef array<mpz_class, 2> Point;
const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16); const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16); const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16); const Point PG = {Gx, Gy}; const Point Z = {0, 0};
auto starttime = chrono::high_resolution_clock::now();
Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) { if (P == Z) return Q; if (Q == Z) return P; const mpz_class& Px = P[0]; const mpz_class& Py = P[1]; const mpz_class& Qx = Q[0]; const mpz_class& Qy = Q[1]; if (Px == Qx && (Py != Qy || Py == 0)) return Z; mpz_class m, num, denom, inv; if (Px == Qx) { num = 3 * Px * Px; denom = 2 * Py; } else { num = Qy - Py; denom = Qx - Px; } mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t()); m = (num * inv) % p; mpz_class x = (m * m - Px - Qx) % p; if (x < 0) x += p; mpz_class y = (m * (Px - x) - Py) % p; if (y < 0) y += p; return {x, y}; }
Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) { Point R = Z; Point current = P; mpz_class k_copy = k; while (k_copy > 0) { if (k_copy % 2 == 1) { R = add(R, current, p); } current = add(current, current, p); k_copy >>= 1; } return R; }
mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) { mpz_class X_cubed = (X * X * X) % p; mpz_class tmp = (X_cubed + mpz_class(7)) % p; mpz_class Y; mpz_class exp = (p + mpz_class(1)) / mpz_class(4); mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t()); if ((Y % 2) != y_parity) { Y = p - Y; } return Y; }
bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity, std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W, const std::vector<mpz_class>& w) { if (P[0] % DP_rarity == 0) { T.push_back(P); t.push_back(Pindex); std::set<mpz_class> T_set; for (const auto& tp : T) T_set.insert(tp[0]); for (const auto& match : W) { auto it = find(T.begin(), T.end(), match); if (it != T.end()) { int index = distance(T.begin(), it); mpz_class tP = t[index]; mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))]; mpz_class dec = abs(tP - wP); auto end = chrono::system_clock::now(); time_t end_time = chrono::system_clock::to_time_t(end); cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r"; cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl; ofstream file("KEYFOUNDKEYFOUND.txt", ios::app); file << "\n" << string(140, '-') << endl; file << "SOLVED " << ctime(&end_time); file << "Private Key (decimal): " << dec << endl; file << "Private Key (hex): " << dec.get_str(16) << endl; file << string(140, '-') << endl; file.close(); return true; } } } return false; }
vector<mpz_class> generate_powers_of_two(int hop_modulo) { vector<mpz_class> powers(hop_modulo); for (int pw = 0; pw < hop_modulo; ++pw) { powers[pw] = mpz_class(1) << pw; } return powers; }
string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo, const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& powers_of_two) { vector<Point> T(Nt, Z), W(Nw, Z); vector<mpz_class> t(Nt), w(Nw);
gmp_randclass rand(gmp_randinit_default);
for (int k = 0; k < Nt; ++k) { t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit); T[k] = mul(t[k]); }
for (int k = 0; k < Nw; ++k) { w[k] = rand.get_z_range(upper_range_limit - lower_range_limit); W[k] = add(W0, mul(w[k])); }
long long Hops = 0, Hops_old = 0; auto t0 = chrono::high_resolution_clock::now(); vector<mpz_class> memo(hop_modulo);
for (int pw = 0; pw < hop_modulo; ++pw) { memo[pw] = powers_of_two[pw]; }
bool solved = false; while (!solved) { for (int k = 0; k < (Nt + Nw); ++k) { ++Hops; if (k < Nt) { mpz_class pw = T[k][0] % hop_modulo; solved = comparator(T[k], t[k], DP_rarity, T, t, W, w); if (solved) break; t[k] += memo[pw.get_ui()]; T[k] = add(P[pw.get_ui()], T[k], modulo); } else { int n = k - Nw; mpz_class pw = W[n][0] % hop_modulo; solved = comparator(W[n], w[n], DP_rarity, W, w, T, t); if (solved) break; w[n] += memo[pw.get_ui()]; W[n] = add(P[pw.get_ui()], W[n], modulo); } }
auto t1 = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count(); if (elapsed_seconds > 1.0) { double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds; auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime); int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count(); int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count(); int seconds = (elapsed_time % chrono::minutes(1)).count(); stringstream elapsed_time_str; elapsed_time_str << setfill('0') << setw(2) << hours << ":" << setfill('0') << setw(2) << minutes << ":" << setfill('0') << setw(2) << seconds; double p_2 = log2(Hops); cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0) << hops_per_second << " h/s] [" << elapsed_time_str.str() << "]" << flush; t0 = t1; Hops_old = Hops; } }
cout << "\r[+] Hops: " << Hops << endl; auto end = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count(); return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec"; }
int main() { int puzzle = 50; string compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"; int kangaroo_power = 6; mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1); mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;
mpz_class DP_rarity = mpz_class(1) << ((puzzle - 2 * kangaroo_power) / 2 - 2); int hop_modulo = ((puzzle - 1) / 2) + kangaroo_power;
int Nt = 1 << kangaroo_power; int Nw = 1 << kangaroo_power;
vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);
mpz_class X, Y; if (compressed_public_key.length() == 66) { X = mpz_class(compressed_public_key.substr(2), 16); Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2); } else { cout << "[error] pubkey len(66/130) invalid!" << endl; return 1; }
Point W0 = {X, Y}; auto starttime = chrono::high_resolution_clock::now(); time_t currentTime = time(nullptr); cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(¤tTime) << "\033[0m" << "\r"; cout << "[+] [Puzzle]: " << puzzle << endl; cout << "[+] [Lower range limit]: " << lower_range_limit << endl; cout << "[+] [Upper range limit]: " << upper_range_limit << endl; cout << "[+] [EC Point Coordinate X]: " << X << endl; cout << "[+] [EC Point Coordinate Y]: " << Y << endl; mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1)); double log_expected_hops = log2(expected_hops.get_d()); cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2) << log_expected_hops << " (" << expected_hops << ")]" << endl;
vector<Point> P = {PG}; P.reserve(256); for (int k = 0; k < 255; ++k) { P.push_back(add(P[k], P[k])); }
unsigned long seed = static_cast<unsigned long>(time(nullptr)); gmp_randclass rand(gmp_randinit_default); rand.seed(seed);
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);
cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;
return 0; } Build command: g++ -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -lgmp -lgmpxx #./kangaroo - KANGAROO: Wed Jul 17 20:26:11 2024
- [Puzzle]: 50
- [Lower range limit]: 562949953421312
- [Upper range limit]: 1125899906842623
- [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
- [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
- [Expected Hops: 2^25.50 (47453132)]
- [Hops: 2^24.81 <-> 460999 h/s] [00:01:04]
- PUZZLE SOLVED: Wed Jul 17 20:27:15 2024
- Private key (dec): 611140496167764
- Hops: 29560288
- Average time to solve: 64 sec
More than 460K hops per second on a single core.
|
bc1qdwnxr7s08xwelpjy3cc52rrxg63xsmagv50fa8
|
|
|
COBRAS
Member
Offline
Activity: 1017
Merit: 23
|
|
July 18, 2024, 03:21:37 AM |
|
Here is Kangaroo C++ in one single file: kangaroo.cpp #include <gmp.h> #include <gmpxx.h> #include <chrono> #include <ctime> #include <fstream> #include <iomanip> #include <iostream> #include <random> #include <vector> #include <set>
using namespace std;
typedef array<mpz_class, 2> Point;
const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16); const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16); const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16); const Point PG = {Gx, Gy}; const Point Z = {0, 0};
auto starttime = chrono::high_resolution_clock::now();
Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) { if (P == Z) return Q; if (Q == Z) return P; const mpz_class& Px = P[0]; const mpz_class& Py = P[1]; const mpz_class& Qx = Q[0]; const mpz_class& Qy = Q[1]; if (Px == Qx && (Py != Qy || Py == 0)) return Z; mpz_class m, num, denom, inv; if (Px == Qx) { num = 3 * Px * Px; denom = 2 * Py; } else { num = Qy - Py; denom = Qx - Px; } mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t()); m = (num * inv) % p; mpz_class x = (m * m - Px - Qx) % p; if (x < 0) x += p; mpz_class y = (m * (Px - x) - Py) % p; if (y < 0) y += p; return {x, y}; }
Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) { Point R = Z; Point current = P; mpz_class k_copy = k; while (k_copy > 0) { if (k_copy % 2 == 1) { R = add(R, current, p); } current = add(current, current, p); k_copy >>= 1; } return R; }
mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) { mpz_class X_cubed = (X * X * X) % p; mpz_class tmp = (X_cubed + mpz_class(7)) % p; mpz_class Y; mpz_class exp = (p + mpz_class(1)) / mpz_class(4); mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t()); if ((Y % 2) != y_parity) { Y = p - Y; } return Y; }
bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity, std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W, const std::vector<mpz_class>& w) { if (P[0] % DP_rarity == 0) { T.push_back(P); t.push_back(Pindex); std::set<mpz_class> T_set; for (const auto& tp : T) T_set.insert(tp[0]); for (const auto& match : W) { auto it = find(T.begin(), T.end(), match); if (it != T.end()) { int index = distance(T.begin(), it); mpz_class tP = t[index]; mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))]; mpz_class dec = abs(tP - wP); auto end = chrono::system_clock::now(); time_t end_time = chrono::system_clock::to_time_t(end); cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r"; cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl; ofstream file("KEYFOUNDKEYFOUND.txt", ios::app); file << "\n" << string(140, '-') << endl; file << "SOLVED " << ctime(&end_time); file << "Private Key (decimal): " << dec << endl; file << "Private Key (hex): " << dec.get_str(16) << endl; file << string(140, '-') << endl; file.close(); return true; } } } return false; }
vector<mpz_class> generate_powers_of_two(int hop_modulo) { vector<mpz_class> powers(hop_modulo); for (int pw = 0; pw < hop_modulo; ++pw) { powers[pw] = mpz_class(1) << pw; } return powers; }
string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo, const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& powers_of_two) { vector<Point> T(Nt, Z), W(Nw, Z); vector<mpz_class> t(Nt), w(Nw);
gmp_randclass rand(gmp_randinit_default);
for (int k = 0; k < Nt; ++k) { t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit); T[k] = mul(t[k]); }
for (int k = 0; k < Nw; ++k) { w[k] = rand.get_z_range(upper_range_limit - lower_range_limit); W[k] = add(W0, mul(w[k])); }
long long Hops = 0, Hops_old = 0; auto t0 = chrono::high_resolution_clock::now(); vector<mpz_class> memo(hop_modulo);
for (int pw = 0; pw < hop_modulo; ++pw) { memo[pw] = powers_of_two[pw]; }
bool solved = false; while (!solved) { for (int k = 0; k < (Nt + Nw); ++k) { ++Hops; if (k < Nt) { mpz_class pw = T[k][0] % hop_modulo; solved = comparator(T[k], t[k], DP_rarity, T, t, W, w); if (solved) break; t[k] += memo[pw.get_ui()]; T[k] = add(P[pw.get_ui()], T[k], modulo); } else { int n = k - Nw; mpz_class pw = W[n][0] % hop_modulo; solved = comparator(W[n], w[n], DP_rarity, W, w, T, t); if (solved) break; w[n] += memo[pw.get_ui()]; W[n] = add(P[pw.get_ui()], W[n], modulo); } }
auto t1 = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count(); if (elapsed_seconds > 1.0) { double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds; auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime); int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count(); int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count(); int seconds = (elapsed_time % chrono::minutes(1)).count(); stringstream elapsed_time_str; elapsed_time_str << setfill('0') << setw(2) << hours << ":" << setfill('0') << setw(2) << minutes << ":" << setfill('0') << setw(2) << seconds; double p_2 = log2(Hops); cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0) << hops_per_second << " h/s] [" << elapsed_time_str.str() << "]" << flush; t0 = t1; Hops_old = Hops; } }
cout << "\r[+] Hops: " << Hops << endl; auto end = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count(); return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec"; }
int main() { int puzzle = 50; string compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"; int kangaroo_power = 6; mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1); mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;
mpz_class DP_rarity = mpz_class(1) << ((puzzle - 2 * kangaroo_power) / 2 - 2); int hop_modulo = ((puzzle - 1) / 2) + kangaroo_power;
int Nt = 1 << kangaroo_power; int Nw = 1 << kangaroo_power;
vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);
mpz_class X, Y; if (compressed_public_key.length() == 66) { X = mpz_class(compressed_public_key.substr(2), 16); Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2); } else { cout << "[error] pubkey len(66/130) invalid!" << endl; return 1; }
Point W0 = {X, Y}; auto starttime = chrono::high_resolution_clock::now(); time_t currentTime = time(nullptr); cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(¤tTime) << "\033[0m" << "\r"; cout << "[+] [Puzzle]: " << puzzle << endl; cout << "[+] [Lower range limit]: " << lower_range_limit << endl; cout << "[+] [Upper range limit]: " << upper_range_limit << endl; cout << "[+] [EC Point Coordinate X]: " << X << endl; cout << "[+] [EC Point Coordinate Y]: " << Y << endl; mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1)); double log_expected_hops = log2(expected_hops.get_d()); cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2) << log_expected_hops << " (" << expected_hops << ")]" << endl;
vector<Point> P = {PG}; P.reserve(256); for (int k = 0; k < 255; ++k) { P.push_back(add(P[k], P[k])); }
unsigned long seed = static_cast<unsigned long>(time(nullptr)); gmp_randclass rand(gmp_randinit_default); rand.seed(seed);
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);
cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;
return 0; } Build command: g++ -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -lgmp -lgmpxx #./kangaroo - KANGAROO: Wed Jul 17 20:26:11 2024
- [Puzzle]: 50
- [Lower range limit]: 562949953421312
- [Upper range limit]: 1125899906842623
- [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
- [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
- [Expected Hops: 2^25.50 (47453132)]
- [Hops: 2^24.81 <-> 460999 h/s] [00:01:04]
- PUZZLE SOLVED: Wed Jul 17 20:27:15 2024
- Private key (dec): 611140496167764
- Hops: 29560288
- Average time to solve: 64 sec
More than 460K hops per second on a single core. Hi bro. Send me please info what you promise ?
|
[
|
|
|
greenAlien
Newbie
Offline
Activity: 12
Merit: 0
|
|
July 22, 2024, 07:56:30 AM |
|
Is there any way to have this running on macOS natively ? It would be awesome to try the new M processors with it.
I have tried to port your version but some libraries are missing for macOS thats a pity.
|
|
|
|
nomachine
Member
Offline
Activity: 476
Merit: 35
|
|
July 23, 2024, 07:55:31 AM Last edit: July 23, 2024, 10:51:40 AM by nomachine |
|
Is there any way to have this running on macOS natively ? It would be awesome to try the new M processors with it.
I have tried to port your version but some libraries are missing for macOS thats a pity.
kangaroo.cpp #include <gmp.h> #include <gmpxx.h> #include <chrono> #include <ctime> #include <fstream> #include <iomanip> #include <iostream> #include <random> #include <vector> #include <array> #include <set> #include <sstream>
using namespace std;
typedef array<mpz_class, 2> Point;
const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16); const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16); const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16); const Point PG = {Gx, Gy}; const Point Z = {0, 0};
auto starttime = chrono::high_resolution_clock::now();
Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) { if (P == Z) return Q; if (Q == Z) return P; const mpz_class& P0 = P[0]; const mpz_class& P1 = P[1]; const mpz_class& Q0 = Q[0]; const mpz_class& Q1 = Q[1]; mpz_class lmbda, num, denom, inv; if (P != Q) { num = Q1 - P1; denom = Q0 - P0; } else { if (P1 == 0) return Z; num = 3 * P0 * P0; denom = 2 * P1; } mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t()); lmbda = (num * inv) % p; mpz_class x = (lmbda * lmbda - P0 - Q0) % p; if (x < 0) x += p; mpz_class y = (lmbda * (P0 - x) - P1) % p; if (y < 0) y += p; return {x, y}; }
Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) { Point R = Z; Point current = P; mpz_class k_copy = k; while (k_copy > 0) { if (k_copy % 2 == 1) { R = add(R, current, p); } current = add(current, current, p); k_copy >>= 1; } return R; }
mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) { mpz_class X_cubed = (X * X * X) % p; mpz_class tmp = (X_cubed + mpz_class(7)) % p; mpz_class Y; mpz_class exp = (p + mpz_class(1)) / mpz_class(4); mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t()); if ((Y % 2) != y_parity) { Y = p - Y; } return Y; }
bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity, std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W, const std::vector<mpz_class>& w) { mpz_class result; mpz_fdiv_r(result.get_mpz_t(), P[0].get_mpz_t(), DP_rarity.get_mpz_t()); if (result != 0) return false;
T.push_back(P); t.push_back(Pindex);
// Create a set of Points from T for fast lookup std::set<Point> T_set(T.begin(), T.end());
// Create a set of Points from W for quick existence check std::set<Point> W_set(W.begin(), W.end());
// Iterate through W and check if each element is in T for (const auto& match : W_set) { if (T_set.find(match) != T_set.end()) { auto it = find(T.begin(), T.end(), match); int index = distance(T.begin(), it); mpz_class tP = t[index]; mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))]; mpz_class dec = abs(tP - wP);
// Measure time once and reuse it auto end = chrono::system_clock::now(); time_t end_time = chrono::system_clock::to_time_t(end); cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r"; cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl;
// Open file once, write all data, and close it static std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app); file << "\n" << string(140, '-') << endl; file << "SOLVED " << ctime(&end_time); file << "Private Key (decimal): " << dec << endl; file << "Private Key (hex): " << dec.get_str(16) << endl; file << string(140, '-') << endl;
return true; } }
return false; }
vector<mpz_class> generate_powers_of_two(int hop_modulo) { vector<mpz_class> powers(hop_modulo); for (int pw = 0; pw < hop_modulo; ++pw) { powers[pw] = mpz_class(1) << pw; } return powers; }
string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo, const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& powers_of_two) { vector<Point> T(Nt, Z), W(Nw, Z); vector<mpz_class> t(Nt), w(Nw);
gmp_randclass rand(gmp_randinit_default);
for (int k = 0; k < Nt; ++k) { t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit); T[k] = mul(t[k]); }
for (int k = 0; k < Nw; ++k) { w[k] = rand.get_z_range(upper_range_limit - lower_range_limit); W[k] = add(W0, mul(w[k])); }
long long Hops = 0, Hops_old = 0; auto t0 = chrono::high_resolution_clock::now(); vector<mpz_class> memo(hop_modulo);
for (int pw = 0; pw < hop_modulo; ++pw) { memo[pw] = powers_of_two[pw]; }
bool solved = false; while (!solved) { for (int k = 0; k < (Nt + Nw); ++k) { ++Hops; if (k < Nt) { mpz_class pw = T[k][0] % hop_modulo; solved = comparator(T[k], t[k], DP_rarity, T, t, W, w); if (solved) break; t[k] += memo[pw.get_ui()]; T[k] = add(P[pw.get_ui()], T[k], modulo); } else { int n = k - Nw; mpz_class pw = W[n][0] % hop_modulo; solved = comparator(W[n], w[n], DP_rarity, W, w, T, t); if (solved) break; w[n] += memo[pw.get_ui()]; W[n] = add(P[pw.get_ui()], W[n], modulo); } }
auto t1 = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count(); if (elapsed_seconds > 1.0) { double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds; auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime); int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count(); int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count(); int seconds = (elapsed_time % chrono::minutes(1)).count(); stringstream elapsed_time_str; elapsed_time_str << setfill('0') << setw(2) << hours << ":" << setfill('0') << setw(2) << minutes << ":" << setfill('0') << setw(2) << seconds; double p_2 = log2(Hops); cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0) << hops_per_second << " h/s] [" << elapsed_time_str.str() << "]" << flush; t0 = t1; Hops_old = Hops; } }
cout << "\r[+] Hops: " << Hops << endl; auto end = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count(); return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec"; }
int main() { int puzzle = 50; string compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"; int kangaroo_power = 6; mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1); mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;
mpz_class DP_rarity = mpz_class(1) << ((puzzle - 2 * kangaroo_power) / 2 - 2); int hop_modulo = ((puzzle - 1) / 2) + kangaroo_power;
int Nt = 1 << kangaroo_power; int Nw = 1 << kangaroo_power;
vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);
mpz_class X, Y; if (compressed_public_key.length() == 66) { X = mpz_class(compressed_public_key.substr(2), 16); Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2); } else { cout << "[error] pubkey len(66/130) invalid!" << endl; return 1; }
Point W0 = {X, Y}; auto starttime = chrono::high_resolution_clock::now(); time_t currentTime = time(nullptr); cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(¤tTime) << "\033[0m" << "\r"; cout << "[+] [Puzzle]: " << puzzle << endl; cout << "[+] [Lower range limit]: " << lower_range_limit << endl; cout << "[+] [Upper range limit]: " << upper_range_limit << endl; cout << "[+] [EC Point Coordinate X]: " << X << endl; cout << "[+] [EC Point Coordinate Y]: " << Y << endl; mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1)); double log_expected_hops = log2(expected_hops.get_d()); cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2) << log_expected_hops << " (" << expected_hops << ")]" << endl;
vector<Point> P = {PG}; P.reserve(256); for (int k = 0; k < 255; ++k) { P.push_back(add(P[k], P[k])); }
unsigned long seed = static_cast<unsigned long>(time(nullptr)); gmp_randclass rand(gmp_randinit_default); rand.seed(seed);
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);
cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;
return 0; } clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % system_profiler SPSoftwareDataType Software: System Software Overview: System Version: macOS 13.6.1 (22G313) Kernel Version: Darwin 22.6.0 Boot Volume: macOS Boot Mode: Normal User Name: nomachine (nomachine) Secure Virtual Memory: Enabled System Integrity Protection: Enabled Time since boot: 1 day, 14 hours, 11 minutes nomachine@iMac Desktop % nano kangaroo.cpp nomachine@iMac Desktop % clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % ./kangaroo - KANGAROO: Tue Jul 23 08:50:41 2024
- [Puzzle]: 50
- [Lower range limit]: 562949953421312
- [Upper range limit]: 1125899906842623
- [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
- [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
- [Expected Hops: 2^25.50 (47453132)]
- [Hops: 2^24.82 <-> 469162 h/s] [00:01:03]
- PUZZLE SOLVED: Tue Jul 23 08:51:44 2024
- Private key (dec): 611140496167764
- Hops: 29560288
- Average time to solve: 63 sec
|
bc1qdwnxr7s08xwelpjy3cc52rrxg63xsmagv50fa8
|
|
|
greenAlien
Newbie
Offline
Activity: 12
Merit: 0
|
|
July 23, 2024, 12:46:27 PM |
|
Is there any way to have this running on macOS natively ? It would be awesome to try the new M processors with it.
I have tried to port your version but some libraries are missing for macOS thats a pity.
kangaroo.cpp #include <gmp.h> #include <gmpxx.h> #include <chrono> #include <ctime> #include <fstream> #include <iomanip> #include <iostream> #include <random> #include <vector> #include <array> #include <set> #include <sstream>
using namespace std;
typedef array<mpz_class, 2> Point;
const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16); const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16); const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16); const Point PG = {Gx, Gy}; const Point Z = {0, 0};
auto starttime = chrono::high_resolution_clock::now();
Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) { if (P == Z) return Q; if (Q == Z) return P; const mpz_class& P0 = P[0]; const mpz_class& P1 = P[1]; const mpz_class& Q0 = Q[0]; const mpz_class& Q1 = Q[1]; mpz_class lmbda, num, denom, inv; if (P != Q) { num = Q1 - P1; denom = Q0 - P0; } else { if (P1 == 0) return Z; num = 3 * P0 * P0; denom = 2 * P1; } mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t()); lmbda = (num * inv) % p; mpz_class x = (lmbda * lmbda - P0 - Q0) % p; if (x < 0) x += p; mpz_class y = (lmbda * (P0 - x) - P1) % p; if (y < 0) y += p; return {x, y}; }
Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) { Point R = Z; Point current = P; mpz_class k_copy = k; while (k_copy > 0) { if (k_copy % 2 == 1) { R = add(R, current, p); } current = add(current, current, p); k_copy >>= 1; } return R; }
mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) { mpz_class X_cubed = (X * X * X) % p; mpz_class tmp = (X_cubed + mpz_class(7)) % p; mpz_class Y; mpz_class exp = (p + mpz_class(1)) / mpz_class(4); mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t()); if ((Y % 2) != y_parity) { Y = p - Y; } return Y; }
bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity, std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W, const std::vector<mpz_class>& w) { mpz_class result; mpz_fdiv_r(result.get_mpz_t(), P[0].get_mpz_t(), DP_rarity.get_mpz_t()); if (result != 0) return false;
T.push_back(P); t.push_back(Pindex);
// Create a set of Points from T for fast lookup std::set<Point> T_set(T.begin(), T.end());
// Create a set of Points from W for quick existence check std::set<Point> W_set(W.begin(), W.end());
// Iterate through W and check if each element is in T for (const auto& match : W_set) { if (T_set.find(match) != T_set.end()) { auto it = find(T.begin(), T.end(), match); int index = distance(T.begin(), it); mpz_class tP = t[index]; mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))]; mpz_class dec = abs(tP - wP);
// Measure time once and reuse it auto end = chrono::system_clock::now(); time_t end_time = chrono::system_clock::to_time_t(end); cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r"; cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl;
// Open file once, write all data, and close it static std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app); file << "\n" << string(140, '-') << endl; file << "SOLVED " << ctime(&end_time); file << "Private Key (decimal): " << dec << endl; file << "Private Key (hex): " << dec.get_str(16) << endl; file << string(140, '-') << endl;
return true; } }
return false; }
vector<mpz_class> generate_powers_of_two(int hop_modulo) { vector<mpz_class> powers(hop_modulo); for (int pw = 0; pw < hop_modulo; ++pw) { powers[pw] = mpz_class(1) << pw; } return powers; }
string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo, const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& powers_of_two) { vector<Point> T(Nt, Z), W(Nw, Z); vector<mpz_class> t(Nt), w(Nw);
gmp_randclass rand(gmp_randinit_default);
for (int k = 0; k < Nt; ++k) { t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit); T[k] = mul(t[k]); }
for (int k = 0; k < Nw; ++k) { w[k] = rand.get_z_range(upper_range_limit - lower_range_limit); W[k] = add(W0, mul(w[k])); }
long long Hops = 0, Hops_old = 0; auto t0 = chrono::high_resolution_clock::now(); vector<mpz_class> memo(hop_modulo);
for (int pw = 0; pw < hop_modulo; ++pw) { memo[pw] = powers_of_two[pw]; }
bool solved = false; while (!solved) { for (int k = 0; k < (Nt + Nw); ++k) { ++Hops; if (k < Nt) { mpz_class pw = T[k][0] % hop_modulo; solved = comparator(T[k], t[k], DP_rarity, T, t, W, w); if (solved) break; t[k] += memo[pw.get_ui()]; T[k] = add(P[pw.get_ui()], T[k], modulo); } else { int n = k - Nw; mpz_class pw = W[n][0] % hop_modulo; solved = comparator(W[n], w[n], DP_rarity, W, w, T, t); if (solved) break; w[n] += memo[pw.get_ui()]; W[n] = add(P[pw.get_ui()], W[n], modulo); } }
auto t1 = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count(); if (elapsed_seconds > 1.0) { double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds; auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime); int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count(); int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count(); int seconds = (elapsed_time % chrono::minutes(1)).count(); stringstream elapsed_time_str; elapsed_time_str << setfill('0') << setw(2) << hours << ":" << setfill('0') << setw(2) << minutes << ":" << setfill('0') << setw(2) << seconds; double p_2 = log2(Hops); cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0) << hops_per_second << " h/s] [" << elapsed_time_str.str() << "]" << flush; t0 = t1; Hops_old = Hops; } }
cout << "\r[+] Hops: " << Hops << endl; auto end = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count(); return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec"; }
int main() { int puzzle = 50; string compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"; int kangaroo_power = 6; mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1); mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;
mpz_class DP_rarity = mpz_class(1) << ((puzzle - 2 * kangaroo_power) / 2 - 2); int hop_modulo = ((puzzle - 1) / 2) + kangaroo_power;
int Nt = 1 << kangaroo_power; int Nw = 1 << kangaroo_power;
vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);
mpz_class X, Y; if (compressed_public_key.length() == 66) { X = mpz_class(compressed_public_key.substr(2), 16); Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2); } else { cout << "[error] pubkey len(66/130) invalid!" << endl; return 1; }
Point W0 = {X, Y}; auto starttime = chrono::high_resolution_clock::now(); time_t currentTime = time(nullptr); cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(¤tTime) << "\033[0m" << "\r"; cout << "[+] [Puzzle]: " << puzzle << endl; cout << "[+] [Lower range limit]: " << lower_range_limit << endl; cout << "[+] [Upper range limit]: " << upper_range_limit << endl; cout << "[+] [EC Point Coordinate X]: " << X << endl; cout << "[+] [EC Point Coordinate Y]: " << Y << endl; mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1)); double log_expected_hops = log2(expected_hops.get_d()); cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2) << log_expected_hops << " (" << expected_hops << ")]" << endl;
vector<Point> P = {PG}; P.reserve(256); for (int k = 0; k < 255; ++k) { P.push_back(add(P[k], P[k])); }
unsigned long seed = static_cast<unsigned long>(time(nullptr)); gmp_randclass rand(gmp_randinit_default); rand.seed(seed);
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);
cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;
return 0; } clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % system_profiler SPSoftwareDataType Software: System Software Overview: System Version: macOS 13.6.1 (22G313) Kernel Version: Darwin 22.6.0 Boot Volume: macOS Boot Mode: Normal User Name: nomachine (nomachine) Secure Virtual Memory: Enabled System Integrity Protection: Enabled Time since boot: 1 day, 14 hours, 11 minutes nomachine@iMac Desktop % nano kangaroo.cpp nomachine@iMac Desktop % clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % ./kangaroo - KANGAROO: Tue Jul 23 08:50:41 2024
- [Puzzle]: 50
- [Lower range limit]: 562949953421312
- [Upper range limit]: 1125899906842623
- [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
- [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
- [Expected Hops: 2^25.50 (47453132)]
- [Hops: 2^24.82 <-> 469162 h/s] [00:01:03]
- PUZZLE SOLVED: Tue Jul 23 08:51:44 2024
- Private key (dec): 611140496167764
- Hops: 29560288
- Average time to solve: 63 sec
It works like a champ! I could solve it in 55 secs using a M1 Pro. I guess this is only using one thread, did you try with multithreading? The M processors are doing some voodoo magic when using multi threading
|
|
|
|
|