krashfire (OP)
Member
Offline
Activity: 119
Merit: 11
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: 886
Merit: 22
|
|
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: 119
Merit: 11
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: 311
Merit: 16
|
|
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.
|
|
|
|
krashfire (OP)
Member
Offline
Activity: 119
Merit: 11
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: 8
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: 886
Merit: 22
|
|
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: 311
Merit: 16
|
|
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.
|
|
|
|
|