Hi all,
Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source:
https://github.com/RetiredC/Kang-1This software demonstrates various ways to solve the ECDLP using Kangaroos.
The required number of operations is approximately K * sqrt(range), where K is a coefficient that depends on the method used.
This software demonstrates four methods:
1 - Classic. The simplest method. There are two groups of kangaroos: tame and wild.
As soon as a collision between any tame and wild kangaroos happens, the ECDLP is solved.
In practice, K is approximately 2.10 for this method.
2 - 3-way. A more advanced method. There are three groups of kangaroos: tame, wild1, and wild2.
As soon as a collision happens between any two types of kangaroos, the ECDLP is solved.
In practice, K is approximately 1.60 for this method.
3 - Mirror. This method uses two groups of kangaroos and the symmetry of the elliptic curve to improve K.
Another trick is to reduce the range for wild kangaroos.
In practice, K is approximately 1.30 for this method.
The main issue with this method is that the kangaroos loop continuously.
4 - SOTA. This method uses three groups of kangaroos and the symmetry of the elliptic curve.
In practice, K is approximately 1.15 for this method. The main issue is the same as in the Mirror method.
I couldn’t find any papers about this method, so let's assume that I invented it
Important note: this software handles kangaroo looping in a very simple way.
This method is bad for large ranges higher than 100 bits.
Next part will demonstrate a good way to handle loops.
PS. Please don't post any stupid messages here, I will remove them.
Hello.
I find it difficult to understand C or C++ language in math operations.
Instead, I develop algorithms with the Fastecdsa Library in Python. I then switch to C or C++ for performance and then use it with GPU performance.
When I tried to read your article, I tried to understand what the value of K is based on. If I see this rule of 4 algorithm you mentioned (such as Fastecdsa or Sagemath in Python), I can join your conversation more.
Just wanted to point out. I am following your topic.
Thank you very much.
import threading
from hashlib import sha256
from ecdsa import SECP256k1, ellipticcurve
from binascii import unhexlify
import random
# Elliptic Curve Parameters
curve = SECP256k1.curve
G = SECP256k1.generator
order = SECP256k1.order
# Puzzle 135 Compressed Public Key
pubkey_hex = '02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16'
pubkey_bytes = unhexlify(pubkey_hex)
def decompress_pubkey(pubkey_bytes):
prefix = pubkey_bytes[0]
x = int.from_bytes(pubkey_bytes[1:], 'big')
alpha = (x ** 3 + 7) % curve.p()
beta = pow(alpha, (curve.p() + 1) // 4, curve.p())
y = beta if (beta % 2 == 0 and prefix == 2) or (beta % 2 == 1 and prefix == 3) else curve.p() - beta
return ellipticcurve.Point(curve, x, y)
P_target = decompress_pubkey(pubkey_bytes)
# Puzzle 135 Range
lower_bound = int("4000000000000000000000000000000000", 16)
upper_bound = int("7fffffffffffffffffffffffffffffffff", 16)
# Generate fixed step table
def generate_step_table(n=64):
random.seed(42)
return [random.randint(1 << 16, 1 << 20) for _ in range(n)]
# Step function using point hash
def step_function(P, table):
h = int(sha256(P.x().to_bytes(32, 'big') + P.y().to_bytes(32, 'big')).hexdigest(), 16)
idx = h % len(table)
s = table[idx]
return s, s * G
# Walk logic
def kangaroo_walk(start_scalar, start_point, table, max_iters=500000):
X = start_point
a = start_scalar
visited = {}
for _ in range(max_iters):
s, sG = step_function(X, table)
X = X + sG
a = (a + s) % order
if (X.x() & ((1 << 20) - 1)) == 0:
key = (X.x(), X.y())
if key in visited:
return visited[key], a, key
visited[key] = a
return None, a, None
# Threaded worker
def kangaroo_thread(thread_id, table):
secret_scalar = random.randint(lower_bound, upper_bound)
wild_point = secret_scalar * G
_, wild_a, wild_key = kangaroo_walk(0, wild_point, table)
tame_point = upper_bound * G
_, tame_a, tame_key = kangaroo_walk(upper_bound, tame_point, table)
if tame_key and wild_key and tame_key == wild_key:
recovered = (tame_a - wild_a) % order
if recovered == secret_scalar:
print(f"[Thread {thread_id}] SUCCESS: Recovered key {hex(recovered)} matches {hex(secret_scalar)}")
else:
print(f"[Thread {thread_id}] Collision found but recovery failed.")
else:
print(f"[Thread {thread_id}] No collision found in this walk.")
# Main launcher
def run_kangaroo_threads(num_threads=10):
step_table = generate_step_table()
threads = []
for i in range(num_threads):
t = threading.Thread(target=kangaroo_thread, args=(i, step_table))
t.start()
threads.append(t)
for t in threads:
t.join()
# Run all
if __name__ == "__main__":
run_kangaroo_threads(10)
This was closest I came with python hope it helps still raw.
Hi all,
Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source:
https://github.com/RetiredC/Kang-1This software demonstrates various ways to solve the ECDLP using Kangaroos.
The required number of operations is approximately K * sqrt(range), where K is a coefficient that depends on the method used.
This software demonstrates four methods:
1 - Classic. The simplest method. There are two groups of kangaroos: tame and wild.
As soon as a collision between any tame and wild kangaroos happens, the ECDLP is solved.
In practice, K is approximately 2.10 for this method.
2 - 3-way. A more advanced method. There are three groups of kangaroos: tame, wild1, and wild2.
As soon as a collision happens between any two types of kangaroos, the ECDLP is solved.
In practice, K is approximately 1.60 for this method.
3 - Mirror. This method uses two groups of kangaroos and the symmetry of the elliptic curve to improve K.
Another trick is to reduce the range for wild kangaroos.
In practice, K is approximately 1.30 for this method.
The main issue with this method is that the kangaroos loop continuously.
4 - SOTA. This method uses three groups of kangaroos and the symmetry of the elliptic curve.
In practice, K is approximately 1.15 for this method. The main issue is the same as in the Mirror method.
I couldn’t find any papers about this method, so let's assume that I invented it
Important note: this software handles kangaroo looping in a very simple way.
This method is bad for large ranges higher than 100 bits.
Next part will demonstrate a good way to handle loops.
PS. Please don't post any stupid messages here, I will remove them.
Hello.
I find it difficult to understand C or C++ language in math operations.
Instead, I develop algorithms with the Fastecdsa Library in Python. I then switch to C or C++ for performance and then use it with GPU performance.
When I tried to read your article, I tried to understand what the value of K is based on. If I see this rule of 4 algorithm you mentioned (such as Fastecdsa or Sagemath in Python), I can join your conversation more.
Just wanted to point out. I am following your topic.
Thank you very much.
sorry posted wrong script previously this is raw script with the new methods:
import threading
import multiprocessing
import hashlib
import cupy as cp
from ecdsa import SECP256k1, ellipticcurve
from binascii import unhexlify
import os
# === CONFIGURATION ===
NUM_THREADS = 10
BATCH_SIZE = 1_000_000
LOG_DIR = "./logs"
MATCH_LOG = os.path.join(LOG_DIR, "135match.txt")
PROGRESS_LOG = os.path.join(LOG_DIR, "kangaroo_progress.log")
# === ECDSA SETUP ===
curve = SECP256k1.curve
G = SECP256k1.generator
order = SECP256k1.order
# Puzzle 135 compressed public key
pubkey_hex = '02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16'
pubkey_bytes = unhexlify(pubkey_hex)
def decompress_pubkey(pubkey_bytes):
prefix = pubkey_bytes[0]
x = int.from_bytes(pubkey_bytes[1:], 'big')
alpha = (x ** 3 + 7) % curve.p()
beta = pow(alpha, (curve.p() + 1) // 4, curve.p())
y = beta if (beta % 2 == 0 and prefix == 2) or (beta % 2 == 1 and prefix == 3) else curve.p() - beta
return ellipticcurve.Point(curve, x, y)
P_target = decompress_pubkey(pubkey_bytes)
# Puzzle 135 keyspace
lower_bound = int("4000000000000000000000000000000000", 16)
upper_bound = int("7fffffffffffffffffffffffffffffffff", 16)
keyspace = upper_bound - lower_bound
# === LOGGING SETUP ===
os.makedirs(LOG_DIR, exist_ok=True)
log_lock = threading.Lock()
def log_progress(message):
with log_lock:
with open(PROGRESS_LOG, "a") as f:
f.write(message + "\n")
print(message)
def log_match(scalar_hex):
with log_lock:
with open(MATCH_LOG, "a") as f:
f.write(scalar_hex + "\n")
print(f"[MATCH FOUND] {scalar_hex}")
# === STEP TABLE ===
def generate_step_table(n=256):
cp.random.seed(42)
return cp.array(cp.random.randint(1 << 12, 1 << 20, size=(n, 3), dtype=cp.uint64))
def step_function_3jump(P, table):
h = int(hashlib.sha256(P.x().to_bytes(32, 'big') + P.y().to_bytes(32, 'big')).hexdigest(), 16)
idx = h % table.shape[0]
steps = table[idx]
s1, s2, s3 = int(steps[0]), int(steps[1]), int(steps[2])
total = s1 + s2 + s3
return total, s1 * G + s2 * G + s3 * G
# === KANGAROO WALK ===
def kangaroo_walk(start_scalar, start_point, table, max_iters=500000):
X = start_point
a = start_scalar
visited = {}
for _ in range(max_iters):
s, sG = step_function_3jump(X, table)
X = X + sG
a = (a + s) % order
if (X.x() & ((1 << 20) - 1)) == 0:
key = (X.x(), X.y())
if key in visited:
return visited[key], a, key
visited[key] = a
return None, a, None
# === WORKER FUNCTION ===
def kangaroo_worker(proc_id, start_base, step_table):
threads = []
def thread_func(thread_id, thread_offset):
batch_start = start_base + thread_offset * BATCH_SIZE
batch_end = min(batch_start + BATCH_SIZE, upper_bound)
secret_scalar = batch_start
wild_point = secret_scalar * G
_, wild_a, wild_key = kangaroo_walk(0, wild_point, step_table)
tame_point = upper_bound * G
_, tame_a, tame_key = kangaroo_walk(upper_bound, tame_point, step_table)
if tame_key and wild_key and tame_key == wild_key:
recovered = (tame_a - wild_a) % order
if recovered == secret_scalar:
log_match(hex(recovered))
else:
log_progress(f"[Proc {proc_id}][Thread {thread_id}] Collision mismatch.")
else:
log_progress(f"[Proc {proc_id}][Thread {thread_id}] Range {hex(batch_start)} - {hex(batch_end)} completed with no match.")
for i in range(NUM_THREADS):
t = threading.Thread(target=thread_func, args=(i, i))
t.start()
threads.append(t)
for t in threads:
t.join()
# === MULTIPROCESS CONTROL ===
def launch_processes(total_batches=5):
step_table = generate_step_table()
processes = []
for i in range(total_batches):
start = lower_bound + i * NUM_THREADS * BATCH_SIZE
if start >= upper_bound:
break
p = multiprocessing.Process(target=kangaroo_worker, args=(i, start, step_table))
p.start()
processes.append(p)
for p in processes:
p.join()
# === START ===
if __name__ == "__main__":
launch_processes(total_batches=5)
Hi all,
Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source:
https://github.com/RetiredC/Kang-1This software demonstrates various ways to solve the ECDLP using Kangaroos.
The required number of operations is approximately K * sqrt(range), where K is a coefficient that depends on the method used.
This software demonstrates four methods:
1 - Classic. The simplest method. There are two groups of kangaroos: tame and wild.
As soon as a collision between any tame and wild kangaroos happens, the ECDLP is solved.
In practice, K is approximately 2.10 for this method.
2 - 3-way. A more advanced method. There are three groups of kangaroos: tame, wild1, and wild2.
As soon as a collision happens between any two types of kangaroos, the ECDLP is solved.
In practice, K is approximately 1.60 for this method.
3 - Mirror. This method uses two groups of kangaroos and the symmetry of the elliptic curve to improve K.
Another trick is to reduce the range for wild kangaroos.
In practice, K is approximately 1.30 for this method.
The main issue with this method is that the kangaroos loop continuously.
4 - SOTA. This method uses three groups of kangaroos and the symmetry of the elliptic curve.
In practice, K is approximately 1.15 for this method. The main issue is the same as in the Mirror method.
I couldn’t find any papers about this method, so let's assume that I invented it
Important note: this software handles kangaroo looping in a very simple way.
This method is bad for large ranges higher than 100 bits.
Next part will demonstrate a good way to handle loops.
PS. Please don't post any stupid messages here, I will remove them.
Hello.
I find it difficult to understand C or C++ language in math operations.
Instead, I develop algorithms with the Fastecdsa Library in Python. I then switch to C or C++ for performance and then use it with GPU performance.
When I tried to read your article, I tried to understand what the value of K is based on. If I see this rule of 4 algorithm you mentioned (such as Fastecdsa or Sagemath in Python), I can join your conversation more.
Just wanted to point out. I am following your topic.
Thank you very much.
Here is my best shot at nailing Sota+ It is still raw but if it helps:
import threading
import multiprocessing
import hashlib
import cupy as cp
from ecdsa import SECP256k1, ellipticcurve
from binascii import unhexlify
import os
# === CONFIGURATION ===
NUM_THREADS = 10
BATCH_SIZE = 1_000_000
LOG_DIR = "./logs"
MATCH_LOG = os.path.join(LOG_DIR, "135match.txt")
PROGRESS_LOG = os.path.join(LOG_DIR, "kangaroo_progress.log")
USE_SOTA_PLUS = True # Toggle SOTA+ mode
# === ECDSA SETUP ===
curve = SECP256k1.curve
G = SECP256k1.generator
order = SECP256k1.order
p = curve.p()
pubkey_hex = '02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16'
pubkey_bytes = unhexlify(pubkey_hex)
def decompress_pubkey(pubkey_bytes):
prefix = pubkey_bytes[0]
x = int.from_bytes(pubkey_bytes[1:], 'big')
alpha = (x ** 3 + 7) % p
beta = pow(alpha, (p + 1) // 4, p)
y = beta if (beta % 2 == 0 and prefix == 2) or (beta % 2 == 1 and prefix == 3) else p - beta
return ellipticcurve.Point(curve, x, y)
P_target = decompress_pubkey(pubkey_bytes)
lower_bound = int("4000000000000000000000000000000000", 16)
upper_bound = int("7fffffffffffffffffffffffffffffffff", 16)
keyspace = upper_bound - lower_bound
# === LOGGING ===
os.makedirs(LOG_DIR, exist_ok=True)
log_lock = threading.Lock()
def log_progress(message):
with log_lock:
with open(PROGRESS_LOG, "a") as f:
f.write(message + "\n")
print(message)
def log_match(scalar_hex):
with log_lock:
with open(MATCH_LOG, "a") as f:
f.write(scalar_hex + "\n")
print(f"[MATCH FOUND] {scalar_hex}")
# === STEP TABLE ===
def generate_step_table(n=256):
cp.random.seed(42)
return cp.array(cp.random.randint(1 << 12, 1 << 20, size=(n, 3), dtype=cp.uint64))
def step_function_sota(P, table):
h = int(hashlib.sha256(P.x().to_bytes(32, 'big') + P.y().to_bytes(32, 'big')).hexdigest(), 16)
idx = h % table.shape[0]
steps = table[idx]
s1, s2, s3 = int(steps[0]), int(steps[1]), int(steps[2])
total = s1 + s2 + s3
direction = h & 1 # 50/50 split for forward/inverse
jump = s1 * G + s2 * G + s3 * G
if USE_SOTA_PLUS and direction == 1:
jump = ellipticcurve.Point(curve, jump.x(), (-jump.y()) % p)
total = -total % order
return total, jump
# === WALK ===
def kangaroo_walk(start_scalar, start_point, table, max_iters=500000):
X = start_point
a = start_scalar
visited = {}
for _ in range(max_iters):
s, sG = step_function_sota(X, table)
X = X + sG
a = (a + s) % order
if (X.x() & ((1 << 20) - 1)) == 0:
key = (X.x(), X.y())
if key in visited:
return visited[key], a, key
visited[key] = a
return None, a, None
# === THREAD WORKER ===
def kangaroo_worker(proc_id, start_base, step_table):
threads = []
def thread_func(thread_id, thread_offset):
batch_start = start_base + thread_offset * BATCH_SIZE
batch_end = min(batch_start + BATCH_SIZE, upper_bound)
secret_scalar = batch_start
wild_point = secret_scalar * G
_, wild_a, wild_key = kangaroo_walk(0, wild_point, step_table)
tame_point = upper_bound * G
_, tame_a, tame_key = kangaroo_walk(upper_bound, tame_point, step_table)
if tame_key and wild_key and tame_key == wild_key:
recovered = (tame_a - wild_a) % order
if recovered == secret_scalar:
log_match(hex(recovered))
else:
log_progress(f"[Proc {proc_id}][Thread {thread_id}] Collision mismatch.")
else:
log_progress(f"[Proc {proc_id}][Thread {thread_id}] Range {hex(batch_start)} - {hex(batch_end)} complete.")
for i in range(NUM_THREADS):
t = threading.Thread(target=thread_func, args=(i, i))
t.start()
threads.append(t)
for t in threads:
t.join()
# === MULTIPROCESS CONTROL ===
def launch_processes(total_batches=5):
step_table = generate_step_table()
processes = []
for i in range(total_batches):
start = lower_bound + i * NUM_THREADS * BATCH_SIZE
if start >= upper_bound:
break
p = multiprocessing.Process(target=kangaroo_worker, args=(i, start, step_table))
p.start()
processes.append(p)
for p in processes:
p.join()
# === START ===
if __name__ == "__main__":
launch_processes(total_batches=5)
