Using Kangaroo Methods for ECDLP Solutions

Hey everyone, Just wanted to share my findings on using kangaroo methods to tackle ECDLP. This is Part 1 of my research. Check out the open-source software I made: https://github.com/RetiredC/Kang-1 It showcases different approaches to solving the ECDLP using Kangaroos. The operation count is roughly K * sqrt(range), where K varies based on the method. Here's a quick rundown of the methods included: 1 Classic method. It's straightforward. We have two types of kangaroos: tame and wild. Once they collide, we solve the ECDLP. Typically, K is around 2.10 for this one.

Continuing with Part 2 of my kangaroo methods research. You can find it here: https://github.com/RetiredC/Kang-2 In this part, I've introduced a new technique for managing kangaroo loops. It applies to all ranges and DP values and doesn’t raise the number of operations needed. The only thing required is a compact list of visited points, which can be coded efficiently on GPUs. I'll show more in Part 3.

And here’s Part 3, focusing on RCKangaroo software for Windows and Linux. The code is available here: https://github.com/RetiredC/RCKangaroo This version implements a fast SOTA method along with improved loop handling specifically for Nvidia cards.

When can we expect a GPU test version?

That's in Part 3, so it might take a bit more time.

Hi there. I struggle with C or C++ math operations in those languages are tough for me. I stick to Python and the Fastecdsa Library for developing algorithms. I switch to C or C++ later for performance, and then I can use GPU speed. I tried reading your article but I’m confused about K’s value. If you could clarify the rule of 4 algorithm, I’d be more in sync with you. Just wanted to share my thoughts. Following this topic closely!

I prefer C++ for speed, which helps me test tons of points to figure out K accurately. CUDA is even faster but it complicates research, so I only use it for final testing. I added a diagram today to make it clearer.

Hey, I checked out the diagram. If we call the public key big X, what happens to X in the elliptic curve process when K is 1.15?

Look at 'Ec.cpp', it's relevant: https://en.bitcoin.it/wiki/Secp256k1

Is this compatible with MacOS?

Only Windows for now. You’ll need Visual Studio with MFC.

Right, that’s correct. Windows, VS MFC C++, taking it back to the old school.

Hi all. I might have misunderstood something here. I'm familiar with elliptic curve operations and signature algorithms. I get the attack methods too. Just trying to grasp your explanation better. I feel some bias here, but still appreciate your effort.

I’ve got a new method that requires only 1.15*sqrt(N) operations (not just theoretical). Check out this paper for methods that need 2*sqrt(N) and 1.714*sqrt(N): https://arxiv.org/pdf/1501.07019 Or this one for 1.36*sqrt(N): https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf The best K I found in literature is 1.275, but it usually performs a bit worse in practice. If you know any papers discussing kangaroo methods with K=1.15 or lower, let me know.

What’s the point of calculating K? Increasing the number of kangaroos just sends K skyrocketing. With 65536 kangaroos in the classic method, K hits 3.07, and on GPU it could easily shoot to 10 due to DP overhead. Your experiments seem too controlled to me.

Exactly, high DP overhead pushes K up, especially with many kangaroos. Better to keep the number of kangaroos low relative to sqrt(range). Using 64K kangaroos for a 32-bit range is a bad move since all kangs would just take one jump each, and then DP>0 adds too much overhead. On GPU, it’s different since you tackle larger ranges, so K stays decent. There are many ways to adjust parameters to minimize K.

Thanks for the support, everyone! I'm slowly getting my ideas out there. Here’s Part 2 of 3: Check it out here: https://github.com/RetiredC/Kang-2 This part covers my new kangaroo looping method, applicable for all ranges and DP values without increasing operation count. Just need a brief list of visited points for efficient GPU coding. I’ll show more in Part 3.

Thanks a ton, RetiredCoder, for parts 1 and 2!

Sure, you can always use CPU instead of GPU if speed isn’t a concern. There’s a lot you can do without speed being a priority, like using Python instead of C++ for easier development.

Please don't spam my GitHub repos, it’s just wasting your time.