Optimizing the Pollard Rho Kangaroo Algorithm for 256-bit Keys

Hey, I could really use some tips on how to tweak, optimize, or improve my code for calculating a 256-bit private key. Any suggestions would be awesome.

Imposible to dolve 256 bit and in python imposible to solve 100 bit

How do you set the range to search for the key? Also what is h and which y should we use in this line  "h = y  # Use the integer value of y" ?

Here's a simplified explanation of how the Kangaroo algorithm works in this context: Tame Kangaroos: These kangaroos make small jumps and keep track of their positions as they move along the curve. They're responsible for exploring the region near the expected position of 𝑘 k and 𝑄 Q. Wild Kangaroos: These kangaroos make large jumps and are used to cover a wider range of possible positions of 𝑘 k and 𝑄 Q. Collision Detection: The algorithm looks for collisions, which occur when a tame kangaroo and a wild kangaroo land on the same point on the curve. This indicates a potential match for 𝑘 k and 𝑄 Q. Private Key Extraction: Once a collision is detected, you can extract the private key 𝑘 k from the positions of the kangaroos at the collision point. The key concept here is that you're not searching through a numerical range of 𝑘 k values linearly. Instead, you're using kangaroos to explore the curve in a smart way, leveraging collisions to pinpoint the private key without exhaustively trying every possible 𝑘 k value. h = y means the public key xy coordinates. in this part we are just using y.

I have 205288 hops per second in python on single core my friend...... It will work from 1 - 256 bit . But it is impossible to solve any Puzzle above 50 with this for a lifetime. Kangaroo: Thu May 16 13:33:48 2024 [Puzzle]: 40 [Lower range limit]: 549755813888 [Upper range limit]: 1099511627775 [Random seed]: 9b76a9623bd76fb8cc P-table prepared tame and wild herds are prepared Hops: 205288 h/s total time: 6.92 sec PUZZLE SOLVED: Thu May 16 13:33:55 2024 Private key (dec) : 1003651412950 Hops: 1416585 Average time to solve: 6.92 sec It needs to be converted into C++ or Rust so that it can solve problems up to puzzle 120.

i have created twist attack on ecdsa secp256k1. can read about Twist Attack on ECDSA SECP256k1 here. https://github.com/demining/Twist-Attack It gets the partial private key correctly. my issue now is how to write the code to get to the full private key. PM Me Bruhhh.... im lost.

not a bad working code! Are you thinking on implementing multi threading? I know this is not comparable with GPU but its not bad at all Congrats!

Explain were you see partial privkey correctly ? I not see any parts of privkey in partial privkey ps as I know twist attack and defining twist,-attack he is bla bla bla about special base point or public keys I not remember this exact, but in your dcrypt you have only one possible twist point but attack and defining use many this points

Here you go KANGAROO: Sat Jun 15 21:22:34 2024 [Tame and Wild herds are prepared] [P-table prepared] [Using 12 CPU cores for parallel search] [Puzzle: 40] [Lower range limit: 549755813888] [Upper range limit: 1099511627775] [Expected Hops: 2^20.64 (1631201)] [Random seed: 0932dc777428d6f3b9] [Hops: 2^22.21 <-> 2443414 h/s] [00:00:02] total time: 2.18 sec PUZZLE SOLVED: Sat Jun 15 21:22:36 2024 Private key (dec) : 1003651412950 Hops: 5254560 Average time to solve: 2.18 sec But I won't give you false hope that this script can solve anything above 50 soon. It's simply beyond the reach of python's capabilities. You have to program in C++ yourself if the current scripts do not meet your needs.

Here is Kangaroo C++ in one single file: kangaroo.cpp Build command: #./kangaroo KANGAROO: Wed Jul 17 20:26:11 2024 [Puzzle]: 50 [Lower range limit]: 562949953421312 [Upper range limit]: 1125899906842623 [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982 [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531 [Expected Hops: 2^25.50 (47453132)] [Hops: 2^24.81 <-> 460999 h/s] [00:01:04] PUZZLE SOLVED: Wed Jul 17 20:27:15 2024 Private key (dec): 611140496167764 Hops: 29560288 Average time to solve: 64 sec More than 460K hops per second on a single core.

Hi bro. Send me please info what you promise ?

Is there any way to have this running on macOS natively ? It would be awesome to try the new M processors with it. I have tried to port your version but some libraries are missing for macOS thats a pity.

kangaroo.cpp nomachine@iMac Desktop % system_profiler SPSoftwareDataType Software:     System Software Overview:       System Version: macOS 13.6.1 (22G313)       Kernel Version: Darwin 22.6.0       Boot Volume: macOS       Boot Mode: Normal       User Name: nomachine (nomachine)       Secure Virtual Memory: Enabled       System Integrity Protection: Enabled       Time since boot: 1 day, 14 hours, 11 minutes nomachine@iMac Desktop % nano kangaroo.cpp nomachine@iMac Desktop % clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % ./kangaroo KANGAROO: Tue Jul 23 08:50:41 2024 [Puzzle]: 50 [Lower range limit]: 562949953421312 [Upper range limit]: 1125899906842623 [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982 [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531 [Expected Hops: 2^25.50 (47453132)] [Hops: 2^24.82 <-> 469162 h/s] [00:01:03] PUZZLE SOLVED: Tue Jul 23 08:51:44 2024 Private key (dec): 611140496167764 Hops: 29560288 Average time to solve: 63 sec

It works like a champ! I could solve it in 55 secs using a M1 Pro. I guess this is only using one thread, did you try with multithreading? The M processors are doing some voodoo magic when using multi threading

Multithreading Implementation kangaroo.cpp # ./kangaroo_solver KANGAROO: Sun Mar  9 18:51:42 2025 [Puzzle]: 50 [Lower range limit]: 562949953421312 [Upper range limit]: 1125899906842623 [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982 [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531 [Expected Hops: 2^25.50 (47453132)] [Hops: 2^24.53 <-> 2864370 h/s] [00:00:08] PUZZLE SOLVED: Sun Mar  9 18:51:51 2025 Private key (dec): 611140496167763 Hops: 26245248 Average time to solve: 8 sec P.S. I'm not sure if the hops are calculated correctly. They should be multiplied by the number of cores.

I've been waiting for this for a long time. So what is the real speed on 12 cores? 40Mh/s?

It depends on the exact processor, memory, etc. I'm not overly enthusiastic about the GMP method. This all needs to be done using SIMD intrinsics, which are available in all modern C or C++ compilers.

is it possible to break a 107 bit key using kangaroo in python ?

next idea or a good must have s there any way to have this running on windows with gpus in network?  i have several computers at my disposal that i could combine from home, would it be possible to work with all the graphics cards together

if you are going to live forever and you need a public key to use kangaroo