Quote from: nomachine on May 08, 2024, 01:52:55 PM

Quote from: kTimesG on May 08, 2024, 01:18:48 PM

I can't squeeze out more than 852.000 affine point additions per second

I have 249457 hops per second in python converting this script with cpython into .so

Code:

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

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

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

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

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

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

   x = (m * m - P.x - Q.x) % p
   y = (m * (P.x - x) - P.y) % p
   return Point(x, y)

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

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

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

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

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

# Generate a list of powers of two for faster access

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

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

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

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

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

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

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

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

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

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

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

#Random seed Config
seed = os.urandom(9)
print(f"[+] [Random seed]: {seed}")
random.seed(seed)

Hops = 0
N_tests = 1

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

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

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

It normally goes to 207301 h/s

Imagine this in Rust, how fast would it go? Grin

Quote from: Tepan on May 07, 2024, 12:53:58 PM

u128

Quote from: kTimesG on May 08, 2024, 01:18:48 PM

const uint64_t

uint64 in C & u128 in Rust not work for Puzzle 130 (try to deal with dinosaur numbers)

BigUint/BIGINT from SSL works or GMP can be used Wink

okay good information here, i'll learn that for P#130, thankyou.