Post
Topic
Board Development & Technical Discussion
Re: Solving ECDLP with Kangaroos - Part 1
by
Dontbeatool2
on 02/04/2025, 16:40:58 UTC
Hi all,

Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source:  https://github.com/RetiredC/Kang-1

This 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 Smiley

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)