Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[RetiredCoder]

I understand that. My point was that the entire complexity order is expressed in group operations, hence that "k", whatever value it has, needs to be multiplied by ~ 1.16 to bring it into the correct complexity order class, otherwise we're comparing apples to oranges.

No. It can be multiplied by 1.16 only if inverse calculation costs nothing, that assumption isn't always valid.

[kTimesG]

I understand that. My point was that the entire complexity order is expressed in group operations, hence that "k", whatever value it has, needs to be multiplied by ~ 1.16 to bring it into the correct complexity order class, otherwise we're comparing apples to oranges.

No. It can be multiplied by 1.16 only if inverse calculation costs nothing, that assumption isn't always valid.

You are right. If the inversion cost is not zero, then k should be multiplied straight up by 1.5 instead of 1.16, because k would not have any practical meaning anymore, as there's nothing relative to compare it against. I was offering the asymptotic minimum value to correct the O(), for a free inversion.

Or are you applying double standards, and in the case that INV takes an infinite amount of time, it doesn't matter whether you do one group op, two ops, or 9999999 ops?

[RetiredCoder]

I understand that. My point was that the entire complexity order is expressed in group operations, hence that "k", whatever value it has, needs to be multiplied by ~ 1.16 to bring it into the correct complexity order class, otherwise we're comparing apples to oranges.

According to your formula:
RATIO = (INV/N + 5.5M + 1.5S) / (INV/N + 5M + 1S)

You took one extreme case N=infinity and got RATIO=1.16
But if you take extreme cases, you should take another extreme case N=1, you will get RATIO=1.01
So I have no idea what you are trying to say...

[kTimesG]

According to your formula:
RATIO = (INV/N + 5.5M + 1.5S) / (INV/N + 5M + 1S)

You took one extreme case N=infinity and got RATIO=1.16
But if you take extreme cases, you should take another extreme case N=1, you will get RATIO=1.01
So I have no idea what you are trying to say...

Yeah, but you're not doing N = 1, it's more like N = 24 for every 36 additions. The ratio doesn't slowly go from 1 to 1.16, it's pretty rapid.

Anyway, I'm not a mathematician so I'll let the big guys decide what's what, if they ever get to do a proper analysis. FWIW, the analysis of the similar BSGS block inversion does what I did: ignores the inversion costs, reduces cost of every 2 group ops into something slightly above 1, and arriving at a sub-unitary "k" because of all that. You might say that N can't go big, but that only depends on the implementation. But it's OK...

[Kefir77]

I have the following problem when I launch the app: GPU 0, CallGpuKernel failed: an illegal memory access was encountered GPU 1, cudaMemcpy failed: an illegal memory access was encountered. What should I do in this case?

[atom13]

Hello everyone,
I’ve been searching for Puzzle 135 for almost a year now – and honestly, it’s been quite tough. It’s not always easy to keep believing and to stay motivated to keep going.
Since I haven’t been able to find a job for a year, I currently have a lot of time on my hands. I use this time to focus on the search for the puzzle until I hopefully find work again. To be honest, I wouldn’t spend my time on this otherwise – but it gives me a sense of hope.
If you look at the odds, it’s of course pretty unlikely that I’ll actually find it :-) What has your experience been like?

[neutron42]

Hi,

might be a stupid question this one but since there is no "save" option how should we start the program once we interrupt the work?
I have to switch off my PC at night (running on 2 rtx 3090) because of noise, heat etc... and the next morning I run the program again but it looks like every time it starts - it starts from the beginning?

I run it with the following parameters for #135:
RCKangaroo.exe -dp 18 -range 134 -start 4000000000000000000000000000000000 -pubkey 02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16

And it always begins with
184K/647392446434K, Time: 0d:00h:00m/606620d:07h:59m

[RetiredCoder]

I have the following problem when I launch the app: GPU 0, CallGpuKernel failed: an illegal memory access was encountered GPU 1, cudaMemcpy failed: an illegal memory access was encountered. What should I do in this case?

A few months ago I fixed an issue in RCGpuUtils.h:
https://github.com/RetiredC/RCKangaroo/commit/876909f002c8ceacee0614c650ce562b82e03a4d#diff-0057146448d93c71fe2acbf92d6fd2445878a75598f2d5d5f7093856f22174d5

So you can build it from source and check if it helps.

Hi,
might be a stupid question this one but since there is no "save" option how should we start the program once we interrupt the work?
I have to switch off my PC at night (running on 2 rtx 3090) because of noise, heat etc... and the next morning I run the program again but it looks like every time it starts - it starts from the beginning?

This software is not intended to crack #135/140/etc, that's why. Its purpose is to demonstrate SOTA method with the lowest K ever.
But you can add missing features by yourself since it's open-source.

[neutron42]

Thank you so much for your reply, I wish I could but that's totally different planet to me I'm afraid...

I read in this thread that you solved #130 so I assumed that you used this software - but I read it again today and noticed that you actually used only parts of it, I guess with tweaks and tools not publicly available...

Anyways, anybody knows if such a program (or a fork from RCKangaroo) exists that should work with puzzles such as 135, 140 etc??

[vdog99]

Thank You @RetiredCoder for the SOTA Method. Real Novel Way of Solving the Pollard Rho Algorithm. I am going over your code and have a few questions



1)  Why aren't you solving for Wild - Wild Collisions Though?

In Your Code you have a Comment which says recovery for k is impossible with wild1 - wild2 collisions in GpuKang.cpp.
-------------------------------------------------------------------------------------------------------------------------------------------
Maybe my Math is Wrong but Since the implementation enforces that all wild distances are even, the sums and differences of distances are also even. Therefore, the division by 2 is exact

-- Lets Look at the Collisions Based on SOTA Setup I download from your Github
G: Generator Point.
Q=k⋅G: Public Key.
H: Half-range value (2R−1, Int_HalfRange).

Tame (T): PT=DT⋅G.

Wild 1 (W1): Starts at
PA=Q−H⋅G. PW1=(k−H+DW1)⋅G.

Wild 2 (W2):
Starts at PB = H⋅G−Q. PW2=(−k+H+DW2)⋅G.

Standard (Pi=Pj) and Symmetric (Pi=−Pj) collisions.

A) Lets look at same herd Collisions (W1-W1) and (W2-W2) Collisions around 22.2% probability
-- Standard Collision: Useless (implies Di=Dj).
-- Symmetric Collision (Pi=−Pj): Solvable
    W1-W1:
                 (k−H+Di)=−(k−H+Dj)
                  2k=2H−(Di+Dj)
                  k=H−(Di+Dj)/2
  
   W2-W2:
                  (-k−H+Di)=−(-k−H+Dj)
                  2k= 2H + (Di+Dj)
                  k=H + (Di+Dj)/2

B) Lets look at Cross herd Collisions (W1-W2) and (W2-W1) Collisions around 22.2% probability
      Standard Collision (Pi=Pj): Solvable.
                                                          (k−H+Di)=(−k+H+Dj)
                                                           2k=2H+Dj−Di
                                                             k=H+(Dj−Di)/2


Seems like K is totally recoverable for Wild - Wild and Cross Wild Collissions


2) Shouldn't your Tame Herd be Centered to increase collision probability based on the diagram you posted?
    -- You do Calculate Int_TameOffset in RCKangaroo.cpp but offset is 0 always when I run it

Puzzle 75 Run Log Partial
-----------------------------
MAIN MODE

Solving public key
X: 726B574F193E374686D8E12BC6E4142ADEB06770E0A2856F5E4AD89F66044755
Y: 9B15322E6707090A4DB3F09C7E6632A26DB57F03EB07B40979FC01C827E1B0A3
Offset: 0000000000000000000000000000000000000000000004000000000000000000

Solving point: Range 74 bits, DP 14, start...
SOTA method, estimated ops: 2^37.202, RAM for DPs: 0.547 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 27.071.

[RetiredCoder]

1)  Why aren't you solving for Wild - Wild Collisions Though?
In Your Code you have a Comment which says recovery for k is impossible with wild1 - wild2 collisions in GpuKang.cpp.

1. If you check GpuKang.cpp, you won't find such comment.

2. I do check wild-wild collisions, see RcKangaroo.cpp ( https://github.com/RetiredC/RCKangaroo/blob/main/RCKangaroo.cpp#L230 ):
//if it's wild, we can find the key from the same type if distances are different

EDIT:
About your second question:
Zero offset is the best for this set, but other parameters are possible, check this:
https://github.com/RetiredC/Kang-1/blob/main/ExpKangDlg.cpp#L1215
You can try different parameters and see the results.

[kTimesG]

If you do SOTA+ in Python for a quick PoC a few things happen:

1. Amazement.
2. You start to wonder on the meaning of the Universe why it works,
3. Most likely, a few headaches.
4. You realize a lot of the parameters need to be perfectly suited to the problem size. jump table size, jumps max value? no one knows what they should look like. Just multiply by 32 the square root and good to go! Wild and Tame set sizes and min/max offsets? 42 is the answer.
5. You ultimately feel stupid for not being smart enough. All of those papers saying we can't go below 1.25, and still we're at 0.99 here. I mean, come on: cheap points = more DPs = faster solves. Or not? Or yes?
6. You play around with parameters, set sizes, crazy herds, small herds, mixed herd sizes, and you realize they all work more or less the same. Shit, it even works if we dump W2 totally, after all it's just mirroring W1, and W1/W2 collisions for huge sets are close to zero anyway. But we need to squeeze out the ultimate probabilities here, so maybe, yeah, just use even distances for everything, because it works better. Why? Just because.
7. Oh no, cycle detection and escape. Since no one's good at GPU programming anyway, this is definitely trivial, just do L0S7 and L3S1, make sure to detect symmetric endpoints to not mess around with the deterministic walk or big loop ins/outs. 2-cycles are, well, every 1 in 2N so let's handle them directly. Easy peasy, there you go, after all who cares that 4/6/8/10/12 cycles are all but guaranteed to happen the more we jump?
8. You realize science isn't an exact science.

[RetiredCoder]

If you do SOTA+ in Python for a quick PoC a few things happen:

1. Amazement.
2. You start to wonder on the meaning of the Universe why it works,
3. Most likely, a few headaches.
4. You realize a lot of the parameters need to be perfectly suited to the problem size. jump table size, jumps max value? no one knows what they should look like. Just multiply by 32 the square root and good to go! Wild and Tame set sizes and min/max offsets? 42 is the answer.
5. You ultimately feel stupid for not being smart enough. All of those papers saying we can't go below 1.25, and still we're at 0.99 here. I mean, come on: cheap points = more DPs = faster solves. Or not? Or yes?
6. You play around with parameters, set sizes, crazy herds, small herds, mixed herd sizes, and you realize they all work more or less the same. Shit, it even works if we dump W2 totally, after all it's just mirroring W1, and W1/W2 collisions for huge sets are close to zero anyway. But we need to squeeze out the ultimate probabilities here, so maybe, yeah, just use even distances for everything, because it works better. Why? Just because.
7. Oh no, cycle detection and escape. Since no one's good at GPU programming anyway, this is definitely trivial, just do L0S7 and L3S1, make sure to detect symmetric endpoints to not mess around with the deterministic walk or big loop ins/outs. 2-cycles are, well, every 1 in 2N so let's handle them directly. Easy peasy, there you go, after all who cares that 4/6/8/10/12 cycles are all but guaranteed to happen the more we jump?
8. You realize science isn't an exact science.

Yeah, but it's fun!
And it really works, no matter what these scientific papers say
And everyone can use sources (and some explanations) to understand the algo and may be improve it a bit if you are smart enough.

About #7 - yes, you can calculate estimated number of these cycles before the point is solved, and then don't care about too long cycles, they won't kill too many kangaroos

[vdog99]

1)  Why aren't you solving for Wild - Wild Collisions Though?
In Your Code you have a Comment which says recovery for k is impossible with wild1 - wild2 collisions in GpuKang.cpp.

1. If you check GpuKang.cpp, you won't find such comment.

2. I do check wild-wild collisions, see RcKangaroo.cpp ( https://github.com/RetiredC/RCKangaroo/blob/main/RCKangaroo.cpp#L230 ):
//if it's wild, we can find the key from the same type if distances are different

EDIT:
About your second question:
Zero offset is the best for this set, but other parameters are possible, check this:
https://github.com/RetiredC/Kang-1/blob/main/ExpKangDlg.cpp#L1215
You can try different parameters and see the results.

Okay I see you do W - W. All that above Work for the post was for nothing Lol


I meant line 262, (https://github.com/RetiredC/RCKangaroo/blob/main/RCKangaroo.cpp#L262)
Sorry I was going off Memory which is not what it used to be
-------------------------------------------------------   ---------------------------------------

if (w12) //in rare cases WILD and WILD2 can collide in mirror, in this case there is no way to find K
               ;// ToLog("W1 and W2 collides in mirror")


-- Cant you add a cheap byte y-parity flag and check for these to be more through and comprehensive? Is it worth it?

I'm a mathematician and a Software Developer but haven't had enough of CUDA Programming Experience, need to find a collaboration. Have some Ideas can Theoretically lower k significantly more. Definitely a genius idea using a Cheap Point. Why didn't i think of it lol

[atom13]

If you do SOTA+ in Python for a quick PoC a few things happen:

1. Amazement.
2. You start to wonder on the meaning of the Universe why it works,
3. Most likely, a few headaches.
4. You realize a lot of the parameters need to be perfectly suited to the problem size. jump table size, jumps max value? no one knows what they should look like. Just multiply by 32 the square root and good to go! Wild and Tame set sizes and min/max offsets? 42 is the answer.
5. You ultimately feel stupid for not being smart enough. All of those papers saying we can't go below 1.25, and still we're at 0.99 here. I mean, come on: cheap points = more DPs = faster solves. Or not? Or yes?
6. You play around with parameters, set sizes, crazy herds, small herds, mixed herd sizes, and you realize they all work more or less the same. Shit, it even works if we dump W2 totally, after all it's just mirroring W1, and W1/W2 collisions for huge sets are close to zero anyway. But we need to squeeze out the ultimate probabilities here, so maybe, yeah, just use even distances for everything, because it works better. Why? Just because.
7. Oh no, cycle detection and escape. Since no one's good at GPU programming anyway, this is definitely trivial, just do L0S7 and L3S1, make sure to detect symmetric endpoints to not mess around with the deterministic walk or big loop ins/outs. 2-cycles are, well, every 1 in 2N so let's handle them directly. Easy peasy, there you go, after all who cares that 4/6/8/10/12 cycles are all but guaranteed to happen the more we jump?
8. You realize science isn't an exact science.

Yeah, but it's fun!
And it really works, no matter what these scientific papers say
And everyone can use sources (and some explanations) to understand the algo and may be improve it a bit if you are smart enough.

About #7 - yes, you can calculate estimated number of these cycles before the point is solved, and then don't care about too long cycles, they won't kill too many kangaroos

No idea who you are, but you’re definitely not a normal scientist, programmer, or whatever :-)
What you’ve accomplished is downright inhuman – in the best possible way! I swear, normal people would need at least three coffee breaks, two nervous breakdowns, and one existential crisis to pull that off.
And you know what? I think only your profile picture truly captures who you are – a genius with a hint of madness and probably more processing power than my laptop. 😄

[RetiredCoder]

-- Cant you add a cheap byte y-parity flag and check for these to be more through and comprehensive? Is it worth it?

There is no way to calc privkey in this case, but you have sources so you can try and see why

No idea who you are, but you’re definitely not a normal scientist, programmer, or whatever :-)

[3d3@anm_e%aTWm3]

hi sir @RetiredCoder i tried running your program on bit 67 and managed to find the key, is the method i used applicable on bit 135 using 10 x rtx 4090
"root@Asus:~/RCKangaroo-3.0# ./rckangaroo -dp 16 -range 67 -start 700ffffffffffffff -end 730fc235c1942c1ae -pubkey 0212209f5ec514a1580a2937bd833979d933199fc230e204c6cdc58872b7d46f75
********************************************************************************
*                    RCKangaroo v3.0  (c) 2024 RetiredCoder                    *
********************************************************************************

This software is free and open-source: https://github.com/RetiredC
It demonstrates fast GPU implementation of SOTA Kangaroo method for solving ECDLP
Linux version
CUDA devices: 1, CUDA driver/runtime: 12.9/12.8
GPU 0: NVIDIA GeForce GTX 1050 Ti, 4.00 GB, 6 CUs, cap 6.1, PCI 1, L2 size: 1024 KB
Total GPUs for work: 1

MAIN MODE

Solving public key
X: 12209F5EC514A1580A2937BD833979D933199FC230E204C6CDC58872B7D46F75
Y: F0473484A9D3F348A15F196FA805E0CD4C87D668F10F0B0A29835C50BA6826F2
Offset: 00000000000000000000000000000000000000000000000700FFFFFFFFFFFFFF

Solving point: Range 67 bits, DP 16, start...
SOTA method, estimated ops: 2^33.702, RAM for DPs: 0.195 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 1.084. DP overhead is big, use less DP value if possible!
GPU 0: allocated 589 MB, 196608 kangaroos. OldGpuMode: Yes
GPUs started...
MAIN: Speed: 14 MKeys/s, Err: 0, DPs: 9K/213K, Time: 0d:00h:00m/0d:00h:16m
MAIN: Speed: 40 MKeys/s, Err: 0, DPs: 24K/213K, Time: 0d:00h:00m/0d:00h:05m
MAIN: Speed: 60 MKeys/s, Err: 0, DPs: 36K/213K, Time: 0d:00h:00m/0d:00h:03m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 48K/213K, Time: 0d:00h:00m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 60K/213K, Time: 0d:00h:00m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 75K/213K, Time: 0d:00h:01m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 87K/213K, Time: 0d:00h:01m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 99K/213K, Time: 0d:00h:01m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 111K/213K, Time: 0d:00h:01m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 123K/213K, Time: 0d:00h:01m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 135K/213K, Time: 0d:00h:01m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 150K/213K, Time: 0d:00h:02m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 162K/213K, Time: 0d:00h:02m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 174K/213K, Time: 0d:00h:02m/0d:00h:02m
MAIN: Speed: 82 MKeys/s, Err: 0, DPs: 186K/213K, Time: 0d:00h:02m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 198K/213K, Time: 0d:00h:02m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 213K/213K, Time: 0d:00h:02m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 225K/213K, Time: 0d:00h:03m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 237K/213K, Time: 0d:00h:03m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 249K/213K, Time: 0d:00h:03m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 264K/213K, Time: 0d:00h:03m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 276K/213K, Time: 0d:00h:03m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 288K/213K, Time: 0d:00h:03m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 300K/213K, Time: 0d:00h:04m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 312K/213K, Time: 0d:00h:04m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 324K/213K, Time: 0d:00h:04m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 339K/213K, Time: 0d:00h:04m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 351K/213K, Time: 0d:00h:04m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 363K/213K, Time: 0d:00h:04m/0d:00h:02m
MAIN: Speed: 81 MKeys/s, Err: 0, DPs: 375K/213K, Time: 0d:00h:05m/0d:00h:02m
Stopping work ...
Point solved, K: 2.088 (with DP and GPU overheads)


PRIVATE KEY: 00000000000000000000000000000000000000000000000730FC235C1942C1AE

[vdog99]

Solving for 135 using 10 RTX 4090 is Still takes a significant amount of time. Technically the maximum range constraint by code is 170 see defs.h
Cycles are calculate by Code so you can run and see the ETA.

135 Range means 2 x 2 x 2 (135 Times) = Very Large Number

[kTimesG]

Hey Doc!

I tried to pull off a DeLorean drift stunt only to end up with a lower bound k = 0.625 which shows up in a lot of set sizes arrangements (you're aware we can swap having larger tame intervals vs shorter wilds, right?).

Also a big takeaway was understanding WTF (why this font) is the relation between set sizes and jump deltas. Conclusion was simple: jump, baby, jump *everywhere*! Not too close, but watch out for the cliffs. And You know perfectly what I mean.

No idea what the deal with even distances even is of why it would ever help with anything (I'm still at 1% of conceptual grasping over all that code I can't even compile). Maybe because the naive approach is saying that W1 and W2 are always at an even distance? Hehe, everyone will say that I'm a stupid idiot and that they are indeed always at an even distance, because, well, both on 0's sideways. I can't wait to disprove them in under 2 lines of explanation how wrong they are!

But you know what? Cycles don't really need so much exhaustive burnout if you mastermind the behavioral headaches of roundabouts in a much more simpler way. No hoverboard needed.

Did I lost it?

[vdog99]

 k = 0.625  benchmark test?

 -- Wilds are always Even but the Tames are not