Pollard's kangaroo ECDLP solver - page 140.

sssergy2705

copper member

Activity: 205

Merit: 1

Quote from: Jean_Luc on May 07, 2020, 09:50:17 AM

I committed the mods. Linux user can try them. (Edit: or Windows user who compile,
I updated project files)

Good afternoon.
You can make statistics at the end of the work cycle.
It is very inconvenient to leaf through all the console output if there are several keys in the input file.

Jean_Luc

sr. member

Activity: 462

Merit: 701

Many thanks for this test @HardwareCollector and @MrFreeDragon Wink

Yes this is a bit tricky and this extra delay delay can be due to the overload of the dp. I will add note on the README about that.

First the suggested dp is a bad approximation, it needs improvement, you have to tune it manually according to available RAM and expected operation, the goal is to be as close as possible to 2sqrt(N).

When you continue a job on a different configuration, depending on how much kangaroo you have, the overload will be different, each kangaroo need 2^dp (in average) to reach a distinguished point. So if you continue on a configuration with much more kangaroo, the overload will be much higher and during the merge, it will add a count but only count/(nbKangaroo*2^dp) distinguished points to the hashtable.

Each time you do a merge, the count recorded in the merge will get an error of ~nbKangaroo*2^dp which is the counting granularity of actual distinguished point which will impact the estimation...

Another things is that when you merge 2 work files with a different dp bits, the lowest will be saved.

If you overload the dp bits by hand using -d and you choose a larger one (let's say +2), you will benefit only of 1 distinguished point on 4 in the hashtable.

Quote from: MrFreeDragon on May 07, 2020, 06:05:29 PM

I tried to continue the job 7 times - for the 1st time 2080ti solved the key for the extra 1 minute (with total operations 2^41.9), but all other 6 attempts I stopped while they reach 2^42.3 group operations (actually 2 times more than the expected).

However I'm also a bit surprised here, i would need more info to try to understand, especially number of kangaroo of each configuration and evolution of the number of distinguished point bits in the work files...

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: Jean_Luc on May 07, 2020, 09:50:17 AM

I committed the mods. Linux user can try them. (Edit: or Windows user who compile,
I updated project files)

./kangaroo -w save.work -wi 10 in.txt (Save work file every 10 sec)
./kangaroo -w save2.work -wi 10 in.txt (Save work file every 10 sec)
-snip
Thanks to test

I made the test with separate works on GPU, merge, continue on CPU, transfer to another machine with another GPU and return back. I did not save kangaroos, only the work (so kangaroos were created again).

The test was made with 2^80 range (for info: to solve it on 4xRTX2080ti i need only 6-8 minutes).

1) I started the job with 1xRTX2080ti and had expected operations 2^41.38 and about 38min time --> made work1 for 22 min (2^40.37 operations)
2) Started the same job from the beginning on the same 1xRTX2080ti and made work2 for 2min (2^36.5 operations)
3) Merged work1 and work2 to work3, and started work3 for 1 minute
4) Continued the job on CPU (4 threads) - started and stop 3 times.
5) Transferred the job to another machine with Tesla T4 (expected time there to finish was 1:16hour with expected operations 2^41.26). I started on Tesla (continued) with 2^40.84 operations saving the work to the same file, after 7 minutes stops and start again.
6) Tesla T4 did not finish the work for expected time and operations. Actually it finished the work with total time 2:22 hour (1 hour more as expected) and with total operations 2^42.26 - actually 2 times more.

While Tesla T4 was trying to finish the job, I copied the current work file from Tesla T4 machine back to 2080ti and continued the job on the same machine there I start (continued from 2^41. Cool

I tried to continue the job 7 times - for the 1st time 2080ti solved the key for the extra 1 minute (with total operations 2^41.9), but all other 6 attempts I stopped while they reach 2^42.3 group operations (actually 2 times more than the expected).

Suggested DP on 2080ti was 18, but on Tesla T4 it was 19, however DP size was also 18 (as was started). So I do not think that different machines use different distinguish points pattern.

The feature to save work, merge work and continue work is a very good. Does this option takes care about hardware configuration change? The idea was to implement "a pause" button, and continue the "movie" later, or later on another screen.

As you developed these, probably you could understand what was the reason for such 2 times longer delay?
- Just no luck
- Creation of new kangaroos many times (instead of saving them and continue the full job)
- Configuration change (2080ti, then CPU, and then Tesla T4)

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Jean_Luc, does this command $ ./kangaroo -wm save.work save2.work save3.work mean that two work files (save.work and save2.work) merged to the 3d file save3.work, and later all the further work is saved to save3.work file? I understood it like this.

I expected to see normal txt tables in work files

Distinguished points with distance, X, and kangaroo type. So my intention was to perform the search for the known public key (in the same range), then stop the work and manually change all the "wild" values in DP to "tame" values. After that re-start the program for the "unknown" public key. So, i wanted to test the idea about RangeWidth^(1/3) group operations (cube root instead of square root) if we have RangeWidth^(1/3) distinguished points at start.

Quote from: arulbero on May 07, 2020, 01:44:03 PM

-snip-
With 90-bit space, you need to perform 2^60 operations to get 2^30 DP and then only 2^30 operations to retrieve each key.
But if you need to find only 2^10 private keys, it is faster to run 2^10 times the program -> 2^10*2^46 = 2^56 operations.

Make sense if all the job is performed by one machine... However if the precomputation work is delegated to "free" machines/servers/users, we could benefit from these operations Wink

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: MrFreeDragon on May 07, 2020, 01:31:17 PM

Quote from: arulbero on May 07, 2020, 10:04:08 AM

Quote from: MrFreeDragon on May 07, 2020, 07:55:36 AM

For the range [a,b] if we have pre-calculated (b-a)^(1/3) distinguished points, we would need only (b-a)^(1/3) group operations in order to find the collision. But precomputation requires (b-a)^(2/3) group operations (performed once as a preliminary stage).

If you can store (b-a)^2/3 distinguished points,
the best things to do is to generate 1*G, 2*G, 3*G, ...., (b-a)^2/3 * G.
-snip-

That method requires (b-a)^2/3 group operations to find (b-a)^1/3 distinguished points. So, only cube root from the length should be stored, but not square root compared to baby step giant step.

Then it is much better.

With 90-bit space, you need to perform 2^60 operations to get 2^30 DP and then only 2^30 operations to retrieve each key.

But if you need to find only 2^10 private keys, it is faster to run 2^10 times the program -> 2^10*2^46 = 2^56 operations.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 07, 2020, 10:04:08 AM

Quote from: MrFreeDragon on May 07, 2020, 07:55:36 AM

For the range [a,b] if we have pre-calculated (b-a)^(1/3) distinguished points, we would need only (b-a)^(1/3) group operations in order to find the collision. But precomputation requires (b-a)^(2/3) group operations (performed once as a preliminary stage).

If you can store (b-a)^2/3 distinguished points,
the best things to do is to generate 1*G, 2*G, 3*G, ...., (b-a)^2/3 * G.
-snip-

That method requires (b-a)^2/3 group operations to find (b-a)^1/3 distinguished points. So, only cube root from the length should be stored, but not square root compared to baby step giant step.

HardwareCollector

member

Activity: 144

Merit: 10

@Jean_Luc

Saving and merging the work across multiple machines seem to work well, tested with 80 and 85 bit intervals. Next test is to compare the run times against a single powerful machine for 90-bit intervals.

Btckeypuzzle

newbie

Activity: 5

Merit: 0

To: Jean_Luc

CPU "as-is" test results:

Code:

-w save.work -wi 10 in.txt

Kangaroo v1.4notready
Start:0
Stop :FFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 4
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^12.00
Suggested DP: 16
Expected operations: 2^29.62
Expected RAM: 12.5MB
DP size: 16 [0xFFFF000000000000]
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
[7.26 MK/s][GPU 0.00 MK/s][Count 2^25.68][Dead 0][11s (Avg 01:53)][2.0/4.1MB]
SaveWork: save.work...............done [2.0 MB] [00s] Thu May 07 18:58:36 2020
[5.81 MK/s][GPU 0.00 MK/s][Count 2^26.78][Dead 0][23s (Avg 02:22)][2.1/4.3MB]
SaveWork: save.work...............done [2.1 MB] [00s] Thu May 07 18:58:50 2020
[5.47 MK/s][GPU 0.00 MK/s][Count 2^27.46][Dead 0][38s (Avg 02:31)][2.1/4.4MB]
SaveWork: save.work...............done [2.1 MB] [00s] Thu May 07 18:59:04 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^27.80][Dead 0][49s (Avg 02:31)][2.1/4.5MB]
SaveWork: save.work...............done [2.1 MB] [00s] Thu May 07 18:59:14 2020

Key# 0 [1S]Pub:  0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305F
EF82A
       Priv: 0x378ABDEC51BC5D

[  0] 2^27.923 Dead:0 Avg:2^27.923 DeadAvg:0.0 (2^29.621)

Done: Total time 53s

Code:

-w save2.work -wi 10 in.txt

Kangaroo v1.4notready
Start:0
Stop :FFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 4
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^12.00
Suggested DP: 16
Expected operations: 2^29.62
Expected RAM: 12.5MB
DP size: 16 [0xFFFF000000000000]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
[7.27 MK/s][GPU 0.00 MK/s][Count 2^25.97][Dead 0][13s (Avg 01:53)][2.0/4.1MB]
SaveWork: save2.work...............done [2.0 MB] [00s] Thu May 07 19:08:13 2020
[5.84 MK/s][GPU 0.00 MK/s][Count 2^26.97][Dead 0][27s (Avg 02:21)][2.1/4.3MB]
SaveWork: save2.work...............done [2.1 MB] [00s] Thu May 07 19:08:27 2020
[5.48 MK/s][GPU 0.00 MK/s][Count 2^27.56][Dead 0][41s (Avg 02:30)][2.1/4.5MB]
SaveWork: save2.work...............done [2.1 MB] [00s] Thu May 07 19:08:42 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^27.87][Dead 0][51s (Avg 02:31)][2.1/4.6MB]
SaveWork: save2.work...............done [2.1 MB] [00s] Thu May 07 19:08:51 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.10][Dead 0][01:00 (Avg 02:31)][2.1/4.7MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.22][Dead 0][01:05 (Avg 02:31)][2.1/4.7MB]

SaveWork: save2.work...............done [2.1 MB] [00s] Thu May 07 19:09:05 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.33][Dead 0][01:10 (Avg 02:31)][2.2/4.8MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.41][Dead 0][01:14 (Avg 02:31)][2.2/4.8MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.48][Dead 0][01:18 (Avg 02:31)][2.2/4.9MB]

SaveWork: save2.work...............done [2.2 MB] [00s] Thu May 07 19:09:18 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.58][Dead 0][01:24 (Avg 02:31)][2.2/4.9MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.66][Dead 0][01:28 (Avg 02:31)][2.2/5.0MB]

SaveWork: save2.work...............done [2.2 MB] [00s] Thu May 07 19:09:29 2020
[5.44 MK/s][GPU 0.00 MK/s][Count 2^28.74][Dead 0][01:33 (Avg 02:31)][2.2/5.0MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.80][Dead 0][01:37 (Avg 02:31)][2.2/5.1MB]
[5.44 MK/s][GPU 0.00 MK/s][Count 2^28.87][Dead 0][01:42 (Avg 02:31)][2.2/5.1MB]

SaveWork: save2.work...............done [2.2 MB] [00s] Thu May 07 19:09:43 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.96][Dead 0][01:49 (Avg 02:31)][2.2/5.2MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^29.02][Dead 0][01:53 (Avg 02:31)][2.3/5.2MB]

SaveWork: save2.work...............done [2.3 MB] [00s] Thu May 07 19:09:54 2020
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.08][Dead 0][01:58 (Avg 02:31)][2.3/5.3MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^29.12][Dead 0][02:02 (Avg 02:31)][2.3/5.3MB]
[5.46 MK/s][GPU 0.00 MK/s][Count 2^29.19][Dead 0][02:08 (Avg 02:31)][2.3/5.4MB]

SaveWork: save2.work...............done [2.3 MB] [00s] Thu May 07 19:10:08 2020
[5.46 MK/s][GPU 0.00 MK/s][Count 2^29.24][Dead 0][02:12 (Avg 02:31)][2.3/5.5MB]
[5.46 MK/s][GPU 0.00 MK/s][Count 2^29.28][Dead 0][02:16 (Avg 02:31)][2.3/5.5MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^29.34][Dead 0][02:22 (Avg 02:31)][2.3/5.6MB]

SaveWork: save2.work...............done [2.3 MB] [00s] Thu May 07 19:10:23 2020
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.39][Dead 0][02:27 (Avg 02:31)][2.3/5.6MB]
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.43][Dead 0][02:31 (Avg 02:31)][2.3/5.7MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^29.48][Dead 0][02:36 (Avg 02:31)][2.3/5.7MB]

SaveWork: save2.work...............done [2.4 MB] [00s] Thu May 07 19:10:37 2020
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.53][Dead 0][02:42 (Avg 02:31)][2.4/5.8MB]
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.56][Dead 0][02:45 (Avg 02:31)][2.4/5.8MB]
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.58][Dead 0][02:48 (Avg 02:31)][2.4/5.8MB]

SaveWork: save2.work...............done [2.4 MB] [00s] Thu May 07 19:10:47 2020
[5.41 MK/s][GPU 0.00 MK/s][Count 2^29.60][Dead 0][02:50 (Avg 02:32)][2.4/5.9MB]
[5.40 MK/s][GPU 0.00 MK/s][Count 2^29.62][Dead 0][02:53 (Avg 02:32)][2.4/5.9MB]
[5.41 MK/s][GPU 0.00 MK/s][Count 2^29.64][Dead 0][02:56 (Avg 02:32)][2.4/5.9MB]
[5.43 MK/s][GPU 0.00 MK/s][Count 2^29.66][Dead 0][02:58 (Avg 02:32)][2.4/5.9MB]

SaveWork: save2.work...............done [2.4 MB] [00s] Thu May 07 19:10:57 2020
[5.40 MK/s][GPU 0.00 MK/s][Count 2^29.68][Dead 0][03:00 (Avg 02:32)][2.4/6.0MB]
[5.42 MK/s][GPU 0.00 MK/s][Count 2^29.70][Dead 0][03:02 (Avg 02:32)][2.4/6.0MB]

Key# 0 [1S]Pub:  0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305F
EF82A
       Priv: 0x378ABDEC51BC5D

[  0] 2^29.711 Dead:0 Avg:2^29.711 DeadAvg:0.0 (2^29.621)

Done: Total time 03:04

Code:

-wm save.work save2.work save3.work

Kangaroo v1.4notready
Loading: save.work
MergeWork: [HashTalbe1 2.1/4.6MB] [00s]
Loading: save2.work
MergeWork: [HashTalbe2 2.1/4.6MB] [00s]
Merging...
Range width: 2^56

SaveWork: save3.work...............done [2.5 MB] [00s] Thu May 07 19:19:00 2020
Dead kangaroo: 2
Total f1+f2: count 2^30.01 [03:47]

Code:

-i save.work

Kangaroo v1.4notready
Loading: save.work
Start:0
Stop :FFFFFFFFFFFFFF
Keys :1
LoadWork: [HashTalbe 2.1/4.6MB] [00s]
Number of CPU thread: 4
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^12.00
Suggested DP: 16
Expected operations: 2^29.62
Expected RAM: 12.5MB
DP size: 16 [0xFFFF000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
[7.25 MK/s][GPU 0.00 MK/s][Count 2^28.10][Dead 0][01:00 (Avg 01:53)][2.1/4.7MB]
[6.64 MK/s][GPU 0.00 MK/s][Count 2^28.19][Dead 0][01:03 (Avg 02:04)][2.1/4.7MB]
[6.15 MK/s][GPU 0.00 MK/s][Count 2^28.27][Dead 0][01:07 (Avg 02:14)][2.2/4.8MB]
[5.86 MK/s][GPU 0.00 MK/s][Count 2^28.37][Dead 0][01:12 (Avg 02:20)][2.2/4.8MB]
[5.66 MK/s][GPU 0.00 MK/s][Count 2^28.44][Dead 0][01:16 (Avg 02:25)][2.2/4.9MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^28.52][Dead 0][01:19 (Avg 02:29)][2.2/4.9MB]
[5.52 MK/s][GPU 0.00 MK/s][Count 2^28.61][Dead 0][01:25 (Avg 02:29)][2.2/5.0MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^28.71][Dead 0][01:31 (Avg 02:29)][2.2/5.0MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^28.77][Dead 0][01:34 (Avg 02:29)][2.2/5.1MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^28.82][Dead 0][01:38 (Avg 02:29)][2.2/5.1MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^28.89][Dead 0][01:43 (Avg 02:29)][2.2/5.2MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^28.96][Dead 0][01:48 (Avg 02:29)][2.2/5.2MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.03][Dead 0][01:53 (Avg 02:29)][2.3/5.3MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.08][Dead 0][01:57 (Avg 02:29)][2.3/5.3MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.13][Dead 0][02:01 (Avg 02:29)][2.3/5.4MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.19][Dead 0][02:07 (Avg 02:29)][2.3/5.4MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.25][Dead 0][02:12 (Avg 02:29)][2.3/5.5MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.29][Dead 0][02:16 (Avg 02:29)][2.3/5.5MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.33][Dead 0][02:20 (Avg 02:29)][2.3/5.6MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.38][Dead 0][02:25 (Avg 02:29)][2.3/5.6MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.43][Dead 0][02:30 (Avg 02:29)][2.3/5.7MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.47][Dead 0][02:34 (Avg 02:29)][2.3/5.7MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.51][Dead 0][02:38 (Avg 02:29)][2.4/5.8MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.54][Dead 0][02:42 (Avg 02:29)][2.4/5.8MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.59][Dead 0][02:47 (Avg 02:29)][2.4/5.9MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.63][Dead 0][02:52 (Avg 02:29)][2.4/5.9MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.66][Dead 0][02:56 (Avg 02:29)][2.4/6.0MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.70][Dead 0][03:00 (Avg 02:29)][2.4/6.0MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.74][Dead 0][03:05 (Avg 02:29)][2.4/6.1MB]

Key# 0 [1S]Pub:  0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305F
EF82A
       Priv: 0x378ABDEC51BC5D

[  0] 2^29.325 Dead:0 Avg:2^29.325 DeadAvg:0.0 (2^29.621)

Done: Total time 03:08

Jean_Luc

sr. member

Activity: 462

Merit: 701

No the jump are now with a fixed seed in order to avoid incompatibility with work files.

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Jean_Luc on May 07, 2020, 09:50:17 AM

I committed the mods. Linux user can try them. (Edit: or Windows user who compile,
I updated project files)

./kangaroo -w save.work -wi 10 in.txt (Save work file every 10 sec)
./kangaroo -w save2.work -wi 10 in.txt (Save work file every 10 sec)

Merge 2 files:

Code:

pons@linpons:~/Kangaroo$ ./kangaroo -wm save.work save2.work save3.work
Kangaroo v1.4notready
Loading: save.work
MergeWork: [HashTalbe1 2.3/5.7MB] [00s]
Loading: save2.work
MergeWork: [HashTalbe2 2.3/5.7MB] [00s]
Merging...
Range width: 2^56

SaveWork: save3.work...............done [2.5 MB] [00s] Thu May  7 16:38:03 2020
Dead kangaroo: 0
Total f1+f2: count 2^29.03 [30s]

During the merge the key can also be solved, you can share your work files !

You save the jumps too or only the DP? I mean the array of NB_JUMPS jumps.

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: MrFreeDragon on May 07, 2020, 07:55:36 AM

For the range [a,b] if we have pre-calculated (b-a)^(1/3) distinguished points, we would need only (b-a)^(1/3) group operations in order to find the collision. But precomputation requires (b-a)^(2/3) group operations (performed once as a preliminary stage).

If you can store (b-a)^2/3 distinguished points,
the best things to do is to generate 1*G, 2*G, 3*G, ...., (b-a)^2/3 * G.
In this way you can use the BSGS algorithm, that is faster than kangaroo (less steps - on average 2^(N/2) - and each step is faster because the points are consecutive)

For each public key P, if you try with these (b-a)^1/3 giant steps:

P-1*(b-a)^2/3*G, P-2*(b-a)^2/3*G, P-3*(b-a)^2/3*G, ..., P -(b-a)^1/3*(b-a)^2/3*G = P - (b-a)*G you will recover for sure the private key (on average in 0.5*(b-a)^(1/3) steps).

You have divided the interval into (b-a)^1/3 sub-intervals each with length = (b-a)^2/3

In case you have to find a key in a 45-bit space, you can shift the interval in [-(b-a)/2, (b-a)/2] and use only half baby steps (1*G, ..., 2^29*G) instead of 2^30 steps. And you need on average 2^14 steps to recover the key. Then in a space of 2^n points you need only 2^((n/3)-1) steps (if you have precomputed 2^((2*n/3)-1) points)

In case you have to find a key in a 90-bit space and you have only 2^29 precomputed points, you need no more than 2^60 giant steps (2^60 sub-intervals to search through) to find a key, on average 2^59 giant steps. Then much better kangaroo.

In any case for large space (like 90 bits), (b-a)^(2/3) means 2^60, too much.

If you want to find many public keys in 69 bits, you need to store 2^46 points, too much.

If you want to find many public keys in 2^45 bits, you need to store 2^30 points, ok, you have enough space to store them. But finding public keys in 2^23 steps or in 2^15 is similar, it takes less than 1 sec for each key. Unless you need to find millions of public keys, there is no difference.

Jean_Luc

sr. member

Activity: 462

Merit: 701

I committed the mods. Linux user can try them. (Edit: or Windows user who compile,
I updated project files)

./kangaroo -w save.work -wi 10 in.txt (Save work file every 10 sec)
./kangaroo -w save2.work -wi 10 in.txt (Save work file every 10 sec)

Merge 2 files:

Code:

pons@linpons:~/Kangaroo$ ./kangaroo -wm save.work save2.work save3.work
Kangaroo v1.4notready
Loading: save.work
MergeWork: [HashTalbe1 2.3/5.7MB] [00s]
Loading: save2.work
MergeWork: [HashTalbe2 2.3/5.7MB] [00s]
Merging...
Range width: 2^56

SaveWork: save3.work...............done [2.5 MB] [00s] Thu May  7 16:38:03 2020
Dead kangaroo: 0
Total f1+f2: count 2^29.03 [30s]

During the merge the key can also be solved, you can share your work files !

Code:

pons@linpons:~/Kangaroo$ ./kangaroo -wm save.work save2.work save3.work
Kangaroo v1.4notready
Loading: save.work
MergeWork: [HashTalbe1 2.5/6.5MB] [00s]
Loading: save2.work
MergeWork: [HashTalbe2 2.5/6.5MB] [00s]
Merging...
Range width: 2^56

Key# 0 [1S]Pub:  0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305FEF82A 
       Priv: 0x378ABDEC51BC5D 
Dead kangaroo: 1
Total f1+f2: count 2^29.78 [50s]

Restart a work file:
pons@linpons:~/Kangaroo$ ./kangaroo -i save.work

If you use the -ws option, it saves all the kangaroo state, so you restart exactly where you are and you avoid kangaroo creation.

Hope that I have no added too much bugs

Thanks to test

j2002ba2

full member

Activity: 206

Merit: 450

Quote from: arulbero on May 06, 2020, 01:59:48 PM

This might be interesting:

https://www.researchgate.net/publication/339319953_Using_Equivalent_Class_to_Solve_Interval_Discrete_Logarithm_Problem

https://link.springer.com/chapter/10.1007%2F978-3-030-41579-2_23

Quote

To accelerate solving IDLP, we first introduce the concept of jumping distance and expanding factor to decide whether to perform the class operation or not. When the value of the expanding factor is greater than a given value, the class operation will be performed, such that each decision on jumps is locally optimal. The improved method takes an average of (1+o(1))√N times of class operation, where N is the size of a given interval.

Looks like this paper is about solving DLP in Z*, not ECDLP. Furthermore the wild and tame jumps differ, which leads to significant memory requirements. Not suitable for GPU as well.

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: arulbero on May 07, 2020, 06:52:12 AM

Did you read the article? I can't, did you pay for reading it?

No just the abstract.

@cobras: Check your grid size, may be too large....

@MrFreeDragon:

For the fist step I add:

Code:

 -w workfile: Specify file to save work into (current processed key only)
 -i workfile: Specify file to load work from (current processed key only)
 -wi workInterval: Periodic interval (in seconds) for saving work
 -ws: Save kangaroos in the work file
 -wm file1 file2 destfile: Merge work file

I almost ended, still need few checks and port to linux....

All concerning multiple keys, tame arrays, advanced merge, ... will come later....

The current modification is quite heavy. I hope to not introduce bugs....

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: Jean_Luc on May 07, 2020, 12:11:16 AM

-snip-
Anyway, the save/load/merge file operations are almost ended, commit probably tomorrow...

The current code creates only jump table, and kangaroo's start positions (same size wild and tame), no distinguished points are created (at start)
Can you add to the code the switch: W, T, both there T - create ONLY tame kangaroos (and also hashtable check collision off), W - create only wild kangaroos (with turned on check collision in hashtable), Both - current mode there both herds are created and collision check on.

If you have the option to save the current status, the idea is to start the code just for the creation of tame kangaroos (created randomly) and find as many distinguished points as possible. No need to check for collisions at this stage, no need for pseudo-random walks. The whole job is just to create the DP and collect the starting hashtable with T kangaroos for the next stage.

The next stage includes the re-start in 'W' mode there all the DPs (created at the 1st stage) are loaded and program just creates wild kangaroos and perform pseudo-random walks as usual. This stage also could be run in 'Both' mode there both herds will be created (however for the tame we would have a pre-calculated distinguished points).

Yes, the pre-calculation stage in 'T' mode would require some long time, however it is not a problem if several keys should be found within the same large range.

For the range [a,b] if we have pre-calculated (b-a)^(1/3) distinguished points, we would need only (b-a)^(1/3) group operations in order to find the collision. But precomputation requires (b-a)^(2/3) group operations (performed once as a preliminary stage).

EDIT:
source (see 2nd paragraph on page 6): https://eprint.iacr.org/2014/565.pdf

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Jean_Luc on May 07, 2020, 12:11:16 AM

Thanks for the reading Wink

Yes this is a good idea to do symmetry class switch after a certain distance in order to limit cycles but:

- We have only a small jump table size, so the probability of cycle is high and for large range, random walks are long.
The distance to choose should be as lower as possible in order to not loose the benefit of symmetry (41% max).

- This trick does not prevent at all from cycle of length 2 so we have to keep the lastjump trick also.

The last jump and the symmetry class switch has an impact of ~10% on the perf (global memory access and extra operations)
To implement this, this is a supplementary global memory access, a supplementary branch, and a supplementary local array...

But, however interesting to test Wink

Did you read the article? I can't, did you pay for reading it?

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Hello !

Then I run a 1.4Beta, I see this:

2011.96 MK/s][GPU 1983.21 MK/s][Count 2^41.09][Dead 0][28:28 (Avg 05:22:52)][7.9MB] GPUEngine: Kernel: too many resources requested for launch
GPUEngine: Kernel: too many resources requested for launch
GPUEngine: Kernel: too many resources requested for launch

....

GPUEngine: Kernel: too many resources requested for launch
[http://594.74 MK/s][GPU 565.90 MK/s][Count 2^41.17][Dead 0][31:57 (Avg 18:12:15)][8.5MB] GPUEngine: Kernel: too many resources requested for launch
GPUEngine: Kernel: too many resources requested for launch
GPUEngine: Kernel: too many resources requested for launch
GPUEngine: Kernel: too many resources requested for launch////

...

[2325.51 MK/s][GPU 2296.74 MK/s][Count 2^41.22][Dead 0][32:53 (Avg 04:39:20)][8.7MB] GPUEngine: Kernel: too many resources requested for launch
GPUEngine: Kernel: too many resources requested for launch
GPUEngine: Kernel: too many resources requested for launch

etc...

What code can't be launched ? Is this a mistake or can't I not worry about it?

Jean_Luc

sr. member

Activity: 462

Merit: 701

Thanks for the test.
And what about the average ?
Did you test this new jump table on in40_1000.txt to see if it improves something ?

Jean_Luc

sr. member

Activity: 462

Merit: 701

Hi,

Thanks for the reading Wink

Yes this is a good idea to do symmetry class switch after a certain distance in order to limit cycles but:

- We have only a small jump table size, so the probability of cycle is high and for large range, random walks are long.
The distance to choose should be as lower as possible in order to not loose the benefit of symmetry (41% max).

- This trick does not prevent at all from cycle of length 2 so we have to keep the lastjump trick also.

The last jump and the symmetry class switch has an impact of ~10% on the perf (global memory access and extra operations)
To implement this, this is a supplementary global memory access, a supplementary branch, and a supplementary local array...

But, however interesting to test Wink

Anyway, the save/load/merge file operations are almost ended, commit probably tomorrow...

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 06, 2020, 01:59:48 PM

This might be interesting:

https://www.researchgate.net/publication/339319953_Using_Equivalent_Class_to_Solve_Interval_Discrete_Logarithm_Problem

https://link.springer.com/chapter/10.1007%2F978-3-030-41579-2_23

Quote

To accelerate solving IDLP, we first introduce the concept of jumping distance and expanding factor to decide whether to perform the class operation or not. When the value of the expanding factor is greater than a given value, the class operation will be performed, such that each decision on jumps is locally optimal. The improved method takes an average of (1+o(1))√N times of class operation, where N is the size of a given interval.

Yes, interesting. Thank you!
As far as I understood the number of operations is (1+o(1))sqrt(N). But how can we estimate o(1)? It is some constant time > 0, and no need to be close to 0, could be 0.5-0.8 as well.
In abstract they say that:

Quote

assume that computing the inverse of an element is easier than the multiplication of two elements in a group, and define an equivalent class to be the pair consisting of element and its inverse. So, a kangaroo jump can be performed between equivalent classes through pre-computation on these classes

This is exactly the thing discussed here by you earlier: to use inverse which easy to calculate (because of the range shift - we can shift the range down to 0 as the middle, or to order as the middle)

Also that paper was first online on 18 February 2020 - some fresh one.

Topic: Pollard's kangaroo ECDLP solver - page 140. (Read 60189 times)