Quote from: Geshma on Today at 05:27:57 PM

Quote from: kTimesG on Today at 09:42:25 AM

Quote from: Geshma on February 06, 2025, 09:54:26 PM

its a bit mumbled up , wanted your perspective , and not working also as intended , be gentle:

Quote from: kTimesG on October 17, 2024, 12:08:08 AM

maybe speed up your Python.

What are you trying to do? It looks like you made some changes to the Python Kangaroo I posted 4 months ago that worked fine (sort of). What are the theoretical bases for your changes though? Some things to consider:

1. I stated several times the code is just for learning purposes. It has its own limitations and had some bugs as well, in edge-cases.
2. Python is very slow, even when using GMP.
3. Kangaroo with only 2 kang types takes longer to solve.
4. Kangaroo that doesn't take advantage of curve symmetry takes longer to solve.
5. Once you change jump tables, alpha, etc. you should really, really know what you're doing, and why. Point doublings (kang == jump_point) are not supported, for private reasons (that code was shrinked down from a larger implementation, I never need to bother with point doublings in any of my algorithms).

Thanks for the input and insight , kang == jump point , enlighten me please.

Code:

import time
import os
import sys
import random
import gmpy2
from math import log2, sqrt, log
from secrets import randbelow

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)

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

Z=Point(0,0)

def add(P,Q,p=modulo):
if P==Z:return Q
if Q==Z:return P
if P.x==Q.x:
if P.y!=Q.y or P.y==0:return Z
else:m=3*P.x*P.x*gmpy2.invert(2*P.y,p)%p
else:dx=Q.x-P.x;dy=Q.y-P.y;inv_dx=gmpy2.invert(dx,p);m=dy*inv_dx%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=3*P.x*P.x*gmpy2.invert(2*P.y,p)%p;x=(m*m-2*P.x)%p;y=(m*(P.x-x)-P.y)%p;return Point(x,y)

def mul(k,P=modulo):
R=0,0
while k:
if k&1:R=add(R,P)
P=add(P,P);k>>=1
return R

def mulk(k,P=Point(Gx,Gy),p=modulo):
if k==0:return Z
if k==1:return P
result=Z;current=P
while k>0:
if k%2==1:result=add(result,current,p)
current=mul2(current,p);k=k//2
return result

def X2Y(X,y_parity,p=modulo):
X_cubed=gmpy2.powmod(X,3,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 generate_powers_of_two(hop_modulo):
return [gmpy2.mpz(1 << pw) for pw in range(hop_modulo)]

def handle_solution(solution):
HEX = "%064x" % abs(solution)
dec = int(HEX, 16)
print(f"\n\033[32m[+] PUZZLE SOLVED \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("\nPrivate Key (decimal): " + str(dec))
file.write("\nPrivate Key (hex): " + HEX)
file.write(f"\n{'-' * 100}\n")
return True

def search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two):
solved = False
t_values = [lower_range_limit + randbelow(upper_range_limit - lower_range_limit) for _ in range(Nt)]
T = [mulk(ti) for ti in t_values]
dt = [gmpy2.mpz(0) for _ in range(Nt)]
w_values = [randbelow(upper_range_limit - lower_range_limit) for _ in range(Nw)]
W = [add(W0, mulk(wk)) for wk in w_values]
dw = [gmpy2.mpz(0) for _ in range(Nw)]
print('[+] Tame and wild herds prepared.')
Hops, Hops_old = 0, 0
tame_dps = {}
wild_dps = {}
last_print_time = time.time()
while not solved:
for k in range(Nt):
Hops += 1
pw = int(T[k].x % hop_modulo)
dt[k] = powers_of_two[pw]
if T[k].x % DP_rarity == 0:
x = T[k].x
if x in wild_dps:
solution = wild_dps[x] - t_values[k]
solved = handle_solution(solution)
return solved
tame_dps[x] = t_values[k]
t_values[k] += dt[k]
T[k] = add(P[pw], T[k])
for k in range(Nw):
Hops += 1
pw = int(W[k].x % hop_modulo)
dw[k] = powers_of_two[pw]
if W[k].x % DP_rarity == 0:
x = W[k].x
if x in tame_dps:
solution = w_values[k] - tame_dps[x]
solved = handle_solution(solution)
return solved
wild_dps[x] = w_values[k]
w_values[k] += dw[k]
W[k] = add(P[pw], W[k])

current_time = time.time()
elapsed_time = current_time - starttime
if current_time - last_print_time >= 5:
time_since_last = current_time - last_print_time
hops_since_last = Hops - Hops_old
hops_per_second = hops_since_last / time_since_last if time_since_last > 0 else 0
last_print_time = current_time
Hops_old = Hops
hours, rem = divmod(elapsed_time, 3600)
minutes, seconds = divmod(rem, 60)
elapsed_time_str = f"{int(hours):02d}:{int(minutes):02d}:{int(seconds):02d}"
hops = f'{log2(Hops):.2f}' if Hops > 0 else '0.00'
print(f'[+] [Hops: 2^{hops} <-> {hops_per_second:.0f} h/s] [{elapsed_time_str}]', end='\r', flush=True)

print('\r[+] Hops:', Hops)
print('[+] Average time to solve: %.2f sec' % ((time.time()-starttime)))

# Configuration for the puzzle
puzzle = 40
compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"
kangaroo_power = puzzle // 5
lower_range_limit = 2 ** (puzzle - 1)
upper_range_limit = (2**puzzle) - 1
DP_rarity = 1 << ((puzzle - 1) // 2 - 2) // 2 + 2
hop_modulo = round(log(2**puzzle)+5)
Nt = Nw = 2**kangaroo_power
powers_of_two = generate_powers_of_two(hop_modulo)

if len(compressed_public_key) == 66:
X = gmpy2.mpz(int(compressed_public_key[2:66], 16))
Y = X2Y(X, int(compressed_public_key[:2]) - 2)
else:
print("[error] Public key length invalid!")
sys.exit(1)

W0 = Point(X, Y)
P = [Point(Gx, Gy)]
for _ in range(puzzle ** 2):
P.append(add(P[-1], P[-1]))

# Start kangaroo search
starttime = time.time()
print(f"[+] Puzzle: {puzzle}")
print(f"[+] Lower range limit: {lower_range_limit}")
print(f"[+] Upper range limit: {upper_range_limit}")
print(f"[+] DP: 2^{int(log2(DP_rarity))}({DP_rarity:x})")
print(f"[+] Expected Hops: 2^{log2(2.13 * sqrt(1 << (puzzle-1))):.2f} ({int(2.13 * sqrt(1 << (puzzle-1)))})")

search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two)
print(f"[+] Total time: {time.time() - starttime:.2f} seconds")

Kangaroo: Fri Feb 7 22:00:56 2025
P-table prepared
Puzzle: 40
Lower range limit: 549755813888
Upper range limit: 1099511627775
DP: 2^10(400)
Expected Hops: 2^20.59 (1579299)
Tame and wild herds prepared.
[Hops: 2^20.43 <-> 282835 h/s] [00:00:05]
PUZZLE SOLVED
Private key (dec): 1003651412950
Total time: 5.59 seconds

You can also try my script for learning process.

But I won't give you false hope that this script can solve anything above 60 soon. It's simply beyond the reach of python's capabilities. Grin