Quote from: mamuu on November 15, 2024, 04:17:37 PM

Quote from: RetiredCoder on November 09, 2024, 01:19:33 PM

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

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)

Dontbeatool2

Posts

Merits