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.
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.
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.