#67 You can solve puzzles using mathematical methods, only requiring 58 to the power of 7 Calculation.
Go get it!
its a bit mumbled up , wanted your perspective , and not working also as intended , be gentle:
import os
import math
import time
import bisect
from gmpy2 import gmpy2
# --------------------------
# Field and Group Operations (unchanged)
# --------------------------
class S: # Scalar field (secp256k1 order)
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
gmp_N = gmpy2.mpz(N)
@staticmethod
def add(a, b):
return gmpy2.mod(gmpy2.add(a, b), S.gmp_N)
@staticmethod
def sub(a, b):
return gmpy2.mod(gmpy2.sub(a, b), S.gmp_N)
@staticmethod
def mul(a, b):
return gmpy2.mod(gmpy2.mul(a, b), S.gmp_N)
class F: # Prime field (secp256k1 field)
P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
gmp_P = gmpy2.mpz(P)
gmp_P4 = gmpy2.mpz((P + 1) // 4)
@staticmethod
def add(a, b):
return gmpy2.mod(gmpy2.add(a, b), F.gmp_P)
@staticmethod
def sub(a, b):
return gmpy2.mod(gmpy2.sub(a, b), F.gmp_P)
@staticmethod
def mul(a, b):
return gmpy2.mod(gmpy2.mul(a, b), F.gmp_P)
@staticmethod
def pow(b, e):
return gmpy2.powmod(b, e, F.gmp_P)
@staticmethod
def sqrt(a):
return gmpy2.powmod(a, F.gmp_P4, F.gmp_P)
@staticmethod
def inv(a):
return gmpy2.invert(a, F.gmp_P)
# -----------------
# Point Operations (unchanged)
# -----------------
class Point:
def __init__(self, x, y, parity=-1):
self.x = x
self.y = y if parity == -1 else self.calc_y(x, parity)
def __eq__(self, other):
return self.x == other.x and self.y == other.y
@classmethod
def uncompress(cls, s):
parity, xh = int(s[:2], 16), s[2:]
if parity not in [2, 3]:
raise ValueError("Invalid parity byte")
return Point(int(xh, 16), 0, parity % 2)
@staticmethod
def calc_y(x, parity):
y_sq = F.add(F.pow(x, 3), 7)
y = F.sqrt(y_sq)
return y if (y % 2) == parity else F.P - y
class JPoint:
def __init__(self, x, y, z):
self.x = x
self.y = y
self.z = z
def affine(self):
iz = F.inv(self.z)
iz2 = F.mul(iz, iz)
return Point(F.mul(self.x, iz2), F.mul(self.y, F.mul(iz, iz2)))
def double(self):
if self.y == 0:
return JPoint(0, 0, 0)
y2 = F.mul(self.y, self.y)
s = F.mul(4 * self.x, y2)
m = F.mul(3 * F.mul(self.x, self.x), F.mul(self.z, F.mul(self.z, self.z)))
x = F.sub(F.mul(m, m), F.mul(2, s))
y = F.sub(F.mul(m, F.sub(s, x)), F.mul(8, F.mul(y2, y2)))
z = F.mul(2 * self.y, self.z)
return JPoint(x, y, z)
def add(self, q):
if self.y == 0:
return q
if q.y == 0:
return self
z1z1 = F.mul(self.z, self.z)
z2z2 = F.mul(q.z, q.z)
u1 = F.mul(self.x, z2z2)
u2 = F.mul(q.x, z1z1)
s1 = F.mul(self.y, F.mul(q.z, z2z2))
s2 = F.mul(q.y, F.mul(self.z, z1z1))
if u1 == u2:
return self.double() if s1 == s2 else JPoint(0, 0, 1)
h = F.sub(u2, u1)
r = F.sub(s2, s1)
h2 = F.mul(h, h)
h3 = F.mul(h, h2)
x = F.sub(F.sub(F.mul(r, r), h3), F.mul(2, F.mul(u1, h2)))
y = F.sub(F.mul(r, F.sub(F.mul(u1, h2), x)), F.mul(s1, h3))
z = F.mul(h, F.mul(self.z, q.z))
return JPoint(x, y, z)
def mul(self, n):
result = JPoint(0, 0, 1)
current = self
while n > 0:
if n % 2 == 1:
result = result.add(current)
current = current.double()
n //= 2
return result
class Group:
G = Point(
0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
)
@staticmethod
def mul(p: Point, k):
return JPoint(p.x, p.y, 1).mul(k).affine()
@staticmethod
def add(p: Point, q: Point):
if p.x == q.x:
raise ValueError("Points with same x-coordinate")
m = F.mul(F.sub(p.y, q.y), F.inv(F.sub(p.x, q.x)))
x = F.sub(F.sub(F.mul(m, m), p.x), q.x)
y = F.sub(F.mul(m, F.sub(p.x, x)), p.y)
return Point(x, y)
# ------------------
# Enhanced Kangaroo Algorithm with Adjustments
# ------------------
class Kangaroo:
def __init__(self, start, end, dp_bits=14, herd_size=1024):
# 1. Initialize critical range parameters FIRST
self.start = start
self.end = end
self.range = end - start + 1
self.interval_size = self.range # Key parameter
self.max_intervals = 1 # Now properly defined
# 2. Store target reference for herd initialization
self.target = None # Will be set in solve()
# 3. Configure jumps and DPs
self.dp_mask = (1 << dp_bits) - 1
self.herd_size = herd_size
self.tame_points = [] # Initialize tame_points here
self.wild_points = [] # Initialize wild_points here
# 4. Initialize jump parameters. This is the code change.
self.base_alpha = self.herd_size * math.sqrt(self.range) / 2
self.current_alpha = self.base_alpha
self.adaptation_interval = 1000 # How often to adjust alpha
self.jump_history = [] # To track jumps
self._update_jump_table() # Initialize jumps
def _update_jump_table(self):
"""Generate geometrically increasing jumps"""
self.jump_dists = []
max_step = int(self.current_alpha)
step = 1
while len(self.jump_dists) < 12 and step <= max_step:
self.jump_dists.append(step)
step *= 4
# Add final large step to prevent stagnation
self.jump_dists.append(max_step)
self.jump_points = [Group.mul(Group.G, d) for d in self.jump_dists]
def _search_interval(self, interval):
"""Fixed initialization using stored target"""
# Tame kangaroos spread through range
step_size = self.range // self.herd_size
tame = [Group.mul(Group.G, self.start + i*step_size)
for i in range(self.herd_size)]
t_dist = [self.start + i*step_size for i in range(self.herd_size)]
# Wild kangaroos start from TARGET + offsets
wild = [Group.add(self.target, Group.mul(Group.G, i))
for i in range(self.herd_size)]
w_dist = [i for i in range(self.herd_size)]
return tame, t_dist, wild, w_dist
def _adapt_jump_strategy(self):
if len(self.jump_history) >= self.adaptation_interval:
avg_jump = sum(self.jump_history[-self.adaptation_interval:]) / self.adaptation_interval
if avg_jump < self.current_alpha / 4:
self.current_alpha = max(self.base_alpha / 4, self.current_alpha * 0.9)
else:
self.current_alpha = min(self.base_alpha * 4, self.current_alpha * 1.1)
self._update_jump_table()
self.jump_history = []
def _update_jump_table(self):
self.jump_dists = []
max_step = max(1, int(self.current_alpha))
# Generate jumps optimized for small steps
a, b = 1, 1
while len(self.jump_dists) < 8 and a <= max_step:
self.jump_dists.append(a)
a, b = b, a + b
# Fill remaining with 1s to ensure coverage
while len(self.jump_dists) < 8:
self.jump_dists.append(1)
self.jump_points = [Group.mul(Group.G, d) for d in self.jump_dists]
def _search_interval(self, interval):
offset = self.start + interval * self.interval_size
P = Group.mul(Group.G, offset)
v = max(1, self.interval_size // self.herd_size)
tame = []
wild = []
t_dist = []
w_dist = []
for i in range(self.herd_size):
tame_pos = offset + i * v
tame.append(Group.mul(Group.G, tame_pos))
t_dist.append(tame_pos)
wild_pos = (tame_pos + (self.range // 2)) % S.N # Wild starts offset by half range
wild.append(Group.mul(Group.G, wild_pos))
w_dist.append(wild_pos)
return tame, t_dist, wild, w_dist
def solve(self, target):
self.target = target # Critical: store target reference
try:
for interval in range(self.max_intervals): # Now works
tame, t_dist, wild, w_dist = self._search_interval(interval)
ops = 0
start_time = time.time()
while True:
# Process tame herd
for i in range(self.herd_size):
if (tame
.x & self.dp_mask) == 0:
parity = tame.y % 2
entry = (tame.x, parity)
idx = bisect.bisect_left(self.tame_points, entry)
if idx < len(self.tame_points) and self.tame_points[idx][:2] == entry:
candidate = S.sub(t_dist, self.tame_points[idx][2])
if Group.mul(Group.G, candidate) == target:
return candidate
bisect.insort(self.tame_points, (tame.x, parity, t_dist))
j = tame.x % len(self.jump_dists)
tame = Group.add(tame, self.jump_points[j])
t_dist = S.add(t_dist, self.jump_dists[j])
self.jump_history.append(self.jump_dists[j])
# Process wild herd
for i in range(self.herd_size):
if (wild.x & self.dp_mask) == 0:
parity = wild.y % 2
entry = (wild.x, parity)
idx = bisect.bisect_left(self.wild_points, entry)
if idx < len(self.wild_points) and self.wild_points[idx][:2] == entry:
candidate = S.sub(w_dist, self.wild_points[idx][2])
if Group.mul(Group.G, candidate) == target:
return candidate
bisect.insort(self.wild_points, (wild.x, parity, w_dist))
j = wild.x % len(self.jump_dists)
wild = Group.add(wild, self.jump_points[j])
w_dist = S.add(w_dist, self.jump_dists[j])
self.jump_history.append(self.jump_dists[j])
ops += 2 * self.herd_size
self._adapt_jump_strategy()
if time.time() - start_time > 2:
print(f"Interval {interval} | Ops: {ops:,} | Tame: {len(self.tame_points)} | Wild: {len(self.wild_points)}")
start_time = time.time()
except KeyboardInterrupt:
print("\nSearch halted by user")
return None
# ----------
# Interface
# ----------
def run_puzzle(start, end, pubkey_hex):
try:
target = Point.uncompress(pubkey_hex)
kang = Kangaroo(start, end)
print(f"Searching range {hex(start)}-{hex(end)} ({(end-start+1):,} keys)")
start_time = time.time()
result = kang.solve(target)
if result is not None:
calc_point = Group.mul(Group.G, result)
print(f"\nFound candidate: {hex(result)}")
print(f"Target X: {target.x:064x}")
print(f"Calculated X: {calc_point.x:064x}")
print(f"Y Parity Match: {calc_point.y%2 == target.y%2}")
if calc_point.x == target.x:
print("Full Verification:", calc_point.y == target.y)
else:
print("Warning: False positive detected")
else:
print("\nNo valid solution found")
print(f"Time elapsed: {time.time()-start_time:.2f}s")
except KeyboardInterrupt:
print("\nOperation cancelled by user")
if __name__ == "__main__":
run_puzzle(0x1000000, 0x1ffffff, "03057fbea3a2623382628dde556b2a0698e32428d3cd225f3bd034dca82dd7455a")
