Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[RetiredCoder]

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 five 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
See "diagram.jpg" for details. Also there are several other good option sets, one of them is used in the application by default, check the sources.

5 - SOTA+. This method is the same as SOTA, but also uses cheap second point.
When we calculate "NextPoint = PreviousPoint + JumpPoint" we can also quickly calculate "PreviousPoint - JumpPoint" because inversion is the same.
If inversion calculation takes a lot of time, this second point is cheap for us and we can use it to improve K.
Using cheap point costs only (1MUL+1SQR)/2. K is approximately 1.02 for this method (assuming cheap point is free and not counted as 1op).
Or you can pay 1MUL+1SQR and get K about 0.99 (preferable for GPU implementation).
Or you can pay only (1MUL+1SQR)/4 and get K about 1.05.
Again, I couldn’t find any papers about this method applied to Kangaroo, 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 high ranges.
Next part will demonstrate a good way to handle loops.

PS. Please don't post any stupid messages here, I will remove them; also don't post AI-generated messages and other spam.

[RetiredCoder]

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.

[RetiredCoder]

Here is my research about using kangaroo methods to solve ECDLP, Part 3.

RCKangaroo software, Windows/Linux:
Open source:  https://github.com/RetiredC/RCKangaroo

This software demonstrates fast implementation of SOTA method and advanced loop handling on Nvidia cards.

[b0dre]

v1.1: improved collision handling, best K=1.15.

When gpu test version?

[RetiredCoder]

When gpu test version?

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

[mamuu]

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.

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.

[RetiredCoder]

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.

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.

[mamuu]

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

[RetiredCoder]

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

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

[Tepan]

Hi!
can it tested on MacOS ?

[b0dre]

Hi!
can it tested on MacOS ?

Windows only and You need Visual Studio with MFC

[RetiredCoder]

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

[mamuu]

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

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

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.

[RetiredCoder]

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.

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.

[Etar]

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.

[RetiredCoder]

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

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.

[RetiredCoder]

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!

[COBRAS]

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!

Thank you RetiredCoder for part 1,2.

[RetiredCoder]

I see a lot talking about GPU, yes for brute force calculation it seems relevant, but due to this issue of parallelism with multi tasks it seems to be the CPU and ram that count, am I right in saying that?

Of course you can use CPU instead of GPU if you don't care about speed.
You can do many things if you don't care about speed, for example, you can use Python instead of C++ to make life easier.

[RetiredCoder]

Please don't spam my github repos, you waste your time.