Topic: Solving ECDLP with Kangaroos - Part 1, 2 (Read 673 times)

Thank you RetiredCoder for part 1,2.

First of all, thank you guys for all your support!  
Slowly, but I keep working on making my ideas public, here is Part 2 of 3:

Open source:  https://github.com/RetiredC/Kang-2

In this part I propose a new method to handle kangaroo looping, it works for all ranges and DP values and does not increase the number of required operations, the only requirement is keeping a short list of visited points which can be coded efficiently on GPU as well, and I will demonstrate it in Part 3.
Take care!

Correct, if you set a large number of kangaroos, DP overhead will be high and K will be high.
The number of kangaroos must be small related to sqrt(range), for example, it's a bad idea to use 64K kangaroos to solve 32bit range because total number of jumps of all kangs to solve 32bit is about 64K so it's just one jump for every kang, and DP>0 will cause a big overhead.
On GPU you have a lot of kangs but you will solve high ranges so K will be good.
There are many ways to get high K, you can play with parameters and find out how to keep it small.
The reason to calculate K is to see what parameters are the best.

And what is the meaning of calculating K? As soon as you increase the number of kangaroos, your K will fly into space.
With 65536 kangaroos  in the classic version K will be 3.07
And when using the GPU, K increases even more due to dp overhead, in this case you will easily reach k=10
Your experiment is purely laboratory conditions, in real life on the GPU, the number of kangaroos is huge.

I propose a new method to solve ECDLP with 1.15*sqrt(N) operations (real, not theoretical).
You can read this paper to see methods with 2*sqrt(N) and 1.714*sqrt(N) required ops:
https://arxiv.org/pdf/1501.07019
Or this paper with 1.36*sqrt(N) required ops:
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf
The best K that I can find in papers is 1.275 (theoretical, in practice it's always a bit worse).
If you know papers describing kangaroo methods with K=1.15 or lower - let me know.

Hello.
I think I misunderstood.
I know Elliptic Curve operations and the Signature algorithm, I know the applicable attack methods.
I'm trying to find out what you're trying to explain.
I think you have a prejudice. Nevertheless, thank you for your work.

Correct.
Windows, VS MFC C++.
Oldschool hardcore 

Windows only and You need Visual Studio with MFC

Hi!
can it tested on MacOS ?

Check "Ec.cpp", this one:
https://en.bitcoin.it/wiki/Secp256k1

Hello.
I analysed the diagram.
if we call pubkey the big X
according to the diagram
Tame , Wild and K, what kind of an elliptic curve process is applied to X when K = 1.15
Thank you

I use C++ because it's faster so I can test thousands of points to measure K carefully. CUDA is even faster of course, but it's difficult to use it for research, so I use it only at the last stage.
Yes, it's not an easy topic, so today I added "diagram.jpg" to show how it works.

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.

It's part #3, the last one, so not very soon.

When gpu test version?

Reserved for Part 3.

Here is my research about using kangaroo methods to solve ECDLP, Part 2.
Open source:  https://github.com/RetiredC/Kang-2

In this part I propose a new method to handle kangaroo looping, it works for all ranges and DP values and does not increase the number of required operations, the only requirement is keeping a short list of visited points which can be coded efficiently on GPU as well, and I will demonstrate it in Part 3.

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.