This program offers a powerful solution for tackling the Elliptic Curve Discrete Logarithm Problem (ECDLP) within the context of SECP256K1. Here's a detailed overview of the features and functionality of this solver:
- Fixed-size arithmetic: Utilizes fixed-size arithmetic for efficient computation.
- Fast modular inversion: Implements fast modular inversion using Delayed Right Shift 62 bits.
- Fast modular multiplication: Utilizes 2 steps folding 512 bits to 256 bits reduction using 64-bit digits.
- Multi-GPU support: with CUDA optimisation via inline PTX assembly.
This program is based on https://github.com/JeanLucPons/Kangaroo.
The algorithm employs two herds of kangaroos, a tame herd, and a wild herd. When a kangaroo from each herd collides, the key can be solved. The distinguished points method with a hashtable is used to detect collisions efficiently. The algorithm iteratively updates the positions of the kangaroos until a collision is detected, leading to the solution of the ECDLP.
The input file follows a specific structure:
Start range
End range
Key #1
Key #2
...
For example:
0
FFFFFFFFFFFFFF
02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305FEF82A
To join the pool:
kangaroo -c 129.159.146.90
The probability of success after a certain number of group operations is illustrated, considering the range size (N). The plot provides insights into the likelihood of solving the ECDLP within a given range.
The distinguished point (DP) method offers an efficient approach for storing random walks and detecting collisions between them. It stores only points with an x value starting with a specified number of zero bits. However, there's a tradeoff when dealing with a large number of kangaroos and a small range, as it may lead to increased overhead and memory usage. Adjusting the DP mask size can help optimize performance.
Work files can be saved periodically using various options (-w, -wi, -ws). When restarting a work, the -i option can be used, and work files can be merged offline. Work files are compatible and can be merged if they have the same key and range. The -wss option enables using the server to make kangaroo backups, facilitating work continuity across different configurations or hardware setups.
# Install a CUDA driver
sudo apt-get install -y nvidia-open
# Install Nvidia CUDA Toolkit
wget https://developer.download.nvidia.com/compute/cuda/repos/ubuntu2404/x86_64/cuda-keyring_1.1-1_all.deb
sudo dpkg -i cuda-keyring_1.1-1_all.deb
sudo apt-get update
sudo apt-get -y install cuda-toolkit-12-6
# Install g++ and make
sudo apt-get install make g++
# Compile CPU-ONLY version
make
# Compile with GPU support:
make gpu=1 ccap=<integer> all