Bitcointalk Mobile Browser presented by IRLBTC™

<< >> (p.5)

Author

Topic: Pollard's kangaroo ECDLP solver (Read 62392 times)

arulbero

Legendary

Offline

Activity: 2023
Merit: 2267

Re: Pollard's kangaroo ECDLP solver

May 04, 2020, 09:36:13 PM

#81

Recap of my tests:

1)

normal generation of jumps

20000 walks
num_jumps: 32 + 32
max_length of each walk = 32
jumpbit = 20

7516 loops of length 2, 118 of length 4:

(7516+118+4+2) 20000 = 38,2 % of the walks have a loop before 32 steps

7516/20000 = 37,58% of the walks have a loop with 2 only points

[7516, 0, 118, 0, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

----------------------------------------------------------------------------------------------------------------------------------------------------

2)

if(next_jump != -prev_jump): ok
else
next_jump = prev_jump #(you double the previous jump)

20000 walks
num_jumps: 32 + 32
max_length of each walk = 32
jumpbit = 20

0 loops of length 2, only 139 loops of length 4 and 7 of length 6:

(139+7+9+1+3) 20000 = 0,795 % against 38,2%!

[0, 0, 139, 0, 7, 0, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

----------------------------------------------------------------------------------------------------------------------------------------------------

3)

if(next_jump != -prev_jump): ok
else
next_jump = -sign(next_jump)*floor(distAvg)*G #a different step, with the opposite sign of the normal step

20000 walks
num_jumps: 32 + 32
max_length of each walk = 32
jumpbit = 20

0 loops of length 2, only 128 loops of length 4 and 6 of length 6, 2 of length 8:

(128 + 1 + 6 +2 + 1 + 1) 20000 = 0,695% of the walks have a loop before 32 steps

[0, 0, 128, 1, 6, 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

-------------------------------------------------------------------------------------------------------------------------------------------------------

4)

if(next_jump != -prev_jump): ok
else
next_jump = prev_jump #(you double the previous jump)

20000 walks
num_jumps: 64 + 64
max_length of each walk = 32
jumpbit = 20

0 loops of length 2, only 40 loops of length 4:

(40+1+1) 20000 = 0,21 % of the walks enter in a loop in less than 32 steps

[0, 0, 0, 40, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

loops of length 4 are of "second order":

probability that (a+b+c+d=0) = (1/128)*(127/128)*(1/128)
probability that each sequence of 4 consecutive points don't create a loop = (1 - (1/128)*(127/128)*(1/128))^32
probability to find a loop in a walk of 32 steps: 1 - (1 - (1/128)*(127/128)*(1/128))^32 = 0.001936

expected value of number of walks with a loop of 4 points: 2000 * 0.001936 = 38,7
-------------------------------------------------------------------------------------------------------------------------------------------------------

5)

if(next_jump != -prev_jump): ok
else
next_jump = prev_jump #(you double the previous jump)

20000 walks
num_jumps: 64 + 64
max_length of each walk = 128
jumpbit = 20

157 loops of length 4, only 4 loops of length 6:

(157+4+2+1+1+1+1+1+1+2+1+1+1+1+1+1+1) 20000 = 0,89% of the walks enter in a loop in less than 128 steps

[0, 0, 157, 0, 4, 0, 2, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 05:57:07 AM
Last edit: May 05, 2020, 08:13:00 AM by Jean_Luc

#82

Hi,

Thanks for this detailed report, very interesting !
I did few quick tests with a logic slightly different than yours, still only positive jump in the table and a I get the next one if equal to the last one.

Code:

#ifdef USE_SYMMETRY
// Limit cycle
if( jmp == herd[g].lastJump ) jmp = (herd[g].lastJump + 1) % NB_JUMP;
#endif

After 100 trials, DP=5, 40bit search, 2048 kangaroos:

With symmetry: Here only cycles or natural path collisions which have a distinguished point on it are detected.
The average length of walks is Avg/2048 = 2^20.614/2048 = 783

NB_JUMP = 32
[100] 2^20.263 Dead:44 Avg:2^20.823 DeadAvg:71.7 (2^20.614)

NB_JUMP = 64
[100] 2^19.985 Dead:17 Avg:2^20.662 DeadAvg:28.4 (2^20.614)

NB_JUMP = 128
[100] 2^19.346 Dead:4 Avg:2^20.581 DeadAvg:19.6 (2^20.614)

NB_JUMP = 256
[100] 2^20.938 Dead:20 Avg:2^20.510 DeadAvg:15.1 (2^20.614)

Then above 256 the dead average seems to converge to ~15, which should be the natural collision rate when using symmetry for this configuration.

No symmetry: Here we have only natural collisions in same herd, which is independent of the table size.

NB_JUMP = 64
[100] 2^22.203 Dead:5 Avg:2^21.098 DeadAvg:1.3 (2^21.097)

NB_JUMP = 128
[100] 2^19.432 Dead:0 Avg:2^21.044 DeadAvg:1.2 (2^21.097)

NB_JUMP = 256
[100] 2^20.805 Dead:1 Avg:2^20.959 DeadAvg:1.4 (2^21.097)

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 11:30:51 AM
Last edit: May 05, 2020, 12:15:25 PM by Jean_Luc

#83

I committed the code for the GPU.
Symmetry is not enabled by default, you have to edit the Constants.h file and comment out the USE_SYMMETRY define.

Code:

// Use symmetry
//#define USE_SYMMETRY

You can change the jump table size in the same file but high number decrease GPU performance.

Code:

// Number of random jumps
// Max 512 for the GPU
#define NB_JUMP 32

Unfortunately, symmetry on large range without killing GPU performance seems difficult as lots of kangaroo end in infinite cycle.
After all, the title of the article was: "Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval"
They well mention this problem of cycle in the article.

The trick of saving the last jump avoid cycle of 2, but not the others.
May be solution could be to precompute a random jump table in order to minimize cycles, but it could be difficult for large random walks of 2^dp. If we recreate kangaroo at each ~2^dp iterations, the creation of a kangaroo is expensive.
Symmetry can bring a maximum gain of sqrt(2) = ~1.41 , so to win, we have to find a way to do all the job in less than 41%.

HardwareCollector

Member

Offline

Activity: 144
Merit: 10

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 12:59:20 PM

#84

@Jean_Luc

Below are the CPU/GPU results for an interval 70-bit in size with and without the use of symmetry. So far, the use of symmetry is not looking too good for intervals greater than ~45-bit in size.

AMD Ryzen 7 1800X CPU without Symmetry:

Code:

./kangaroo -t 16 -d 16 in70.txt
Kangaroo v1.4beta
Start:1FFFFFFFFFFFFFFFFF
Stop :3FFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 16
Range width: 2^70
Jump Avg distance: 2^35.02
Number of kangaroos: 2^14.00
Suggested DP: 20
Expected operations: 2^36.15
Expected RAM: 89.6MB
DP size: 16 [0xffff000000000000]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 9: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 10: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 8: 1024 kangaroos
SolveKeyCPU Thread 5: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 15: 1024 kangaroos
SolveKeyCPU Thread 12: 1024 kangaroos
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 11: 1024 kangaroos
SolveKeyCPU Thread 13: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
SolveKeyCPU Thread 14: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
[53.01 MK/s][GPU 0.00 MK/s][Count 2^36.10][Dead 0][26:31 (Avg 23:55)][91.4MB]
Key# 0 Pub: 0x0290E6900A58D33393BC1097B5AED31F2E4E7CBD3E5466AF958665BC0121248483
Priv: 0x349B84B6431A6C4EF1

Done: Total time 26:32

AMD Ryzen 7 1800X CPU with Symmetry:

Code:

./kangaroo -t 16 -d 16 in70.txt
Kangaroo v1.4gamma
Start:1FFFFFFFFFFFFFFFFF
Stop :3FFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 16
Range width: 2^70
Jump Avg distance: 2^34.00
Number of kangaroos: 2^14.00
Suggested DP: 20
Expected operations: 2^35.55
Expected RAM: 59.7MB
DP size: 16 [0xffff000000000000]
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 5: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
SolveKeyCPU Thread 8: 1024 kangaroos
SolveKeyCPU Thread 9: 1024 kangaroos
SolveKeyCPU Thread 11: 1024 kangaroos
SolveKeyCPU Thread 10: 1024 kangaroos
SolveKeyCPU Thread 12: 1024 kangaroos
SolveKeyCPU Thread 13: 1024 kangaroos
SolveKeyCPU Thread 15: 1024 kangaroos
SolveKeyCPU Thread 14: 1024 kangaroos
[35.34 MK/s][GPU 0.00 MK/s][Count 2^39.22][Dead 416][05:39:09 (Avg 23:47)][99.6MB]
Key# 0 [1S]Pub: 0x0290E6900A58D33393BC1097B5AED31F2E4E7CBD3E5466AF958665BC0121248483
Priv: 0x349B84B6431A6C4EF1
[ 0] 2^39.219 Dead:416 Avg:2^39.219 (2^35.554)

Done: Total time 05:39:10

Nvidia RTX 2070 GPU without Symmetry:

Code:

./kangaroo -t 0 -d 14 -gpu -gpuId 0 in70.txt
Kangaroo v1.4gamma
Start:1FFFFFFFFFFFFFFFFF
Stop :3FFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^70
Jump Avg distance: 2^33.97
Number of kangaroos: 2^20.17
Suggested DP: 14
Expected operations: 2^36.40
Expected RAM: 423.2MB
DP size: 14 [0xfffc000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (117.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos in 7948.8ms
[857.53 MK/s][GPU 857.53 MK/s][Count 2^35.58][Dead 1][01:08 (Avg 01:45)][243.9MB]
Key# 0 [1S]Pub: 0x0290E6900A58D33393BC1097B5AED31F2E4E7CBD3E5466AF958665BC0121248483
Priv: 0x349B84B6431A6C4EF1
[ 0] 2^35.606 Dead:1 Avg:2^35.606 DeadAvg:1.0 (2^36.400)

Done: Total time 01:18

Nvidia RTX 2070 GPU with Symmetry still running:

Code:

./kangaroo -t 0 -d 14 -gpu -gpuId 0 in70.txt
Kangaroo v1.4gamma (with symmetry)
Start:1FFFFFFFFFFFFFFFFF
Stop :3FFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^70
Jump Avg distance: 2^34.98
Number of kangaroos: 2^20.17
Suggested DP: 14
Expected operations: 2^36.06
Expected RAM: 333.8MB
DP size: 14 [0xfffc000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos in 8044.0ms
[826.63 MK/s][GPU 826.63 MK/s][Count 2^39.99][Dead 1845][25:06 (Avg 01:26)][27.0MB]

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 01:20:57 PM

#85

Thanks for the tests Wink

Stop your program, it will never ends if you have let the NB_JUMP to 32 and even with 512 I don't know if it will end Wink

The second test with CPU is not displaying: "Kangaroo v1.4gamma (with symmetry)" ?
Did you git pull between the correction I made concerning this (commit at 13:22 UTC+2) ?

HardwareCollector

Member

Offline

Activity: 144
Merit: 10

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 01:33:57 PM

#86

Quote from: Jean_Luc on May 05, 2020, 01:20:57 PM

Thanks for the tests Wink

Stop your program, it will never ends if you have let the NB_JUMP to 32 and even with 512 I don't know if it will end Wink

The second test with CPU is not displaying: "Kangaroo v1.4gamma (with symmetry)" ?
Did you git pull between the correction I made concerning this (commit at 13:22 UTC+2) ?

No, it was from yesterdays commit, now running CPU tests with latest commit.

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 01:41:58 PM

#87

OK, i you want to test large range and symmetry, put 512 in the NB_JUMP...

I'm currently working on the save work options:

Code:

-w workfile: Specify file to save work into
-i workfile: Specify file to load work from
-wi workInterval: Periodic interval (in seconds) for saving work

Concerning optimization of the complexity, I will investigate on the Wild compression and Tame/Wild ratio which seems more promising to me...

HardwareCollector

Member

Offline

Activity: 144
Merit: 10

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 01:46:58 PM

#88

Quote from: Jean_Luc on May 05, 2020, 01:41:58 PM

OK, i you want to test large range and symmetry, put 512 in the NB_JUMP...

I'm currently working on the save work options:

Code:

-w workfile: Specify file to save work into
-i workfile: Specify file to load work from
-wi workInterval: Periodic interval (in seconds) for saving work

Concerning optimization of the complexity, I will investigate on the Wild compression and Tame/Wild ratio which seems more promising to me...

That's very good, the save work option will be very useful when testing [95-105]-bit intervals

Kpot87

Jr. Member

Offline

Activity: 43
Merit: 1

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 03:10:07 PM

#89

Quote from: HardwareCollector on May 05, 2020, 01:46:58 PM

Quote from: Jean_Luc on May 05, 2020, 01:41:58 PM

OK, i you want to test large range and symmetry, put 512 in the NB_JUMP...

I'm currently working on the save work options:

Code:

-w workfile: Specify file to save work into
-i workfile: Specify file to load work from
-wi workInterval: Periodic interval (in seconds) for saving work

Concerning optimization of the complexity, I will investigate on the Wild compression and Tame/Wild ratio which seems more promising to me...

That's very good, the save work option will be very useful when testing [95-105]-bit intervals

And also multiPubKey search at one time

HardwareCollector

Member

Offline

Activity: 144
Merit: 10

Re: Pollard's kangaroo ECDLP solver

May 05, 2020, 06:34:22 PM

#90

Not looking too good either on the CPU side of things with symmetry enabled; I terminated the application after 4.5 hours.

AMD Ryzen 7 1800X CPU with Symmetry:

Code:

./kangaroo -t 21 -d 16 in70.txt
Kangaroo v1.4gamma (with symmetry)
Start:1FFFFFFFFFFFFFFFFF
Stop :3FFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 21
Range width: 2^70
Jump Avg distance: 2^34.96
Number of kangaroos: 2^14.39
Suggested DP: 20
Expected operations: 2^35.59
Expected RAM: 61.4MB
DP size: 16 [0xffff000000000000]
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 5: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
SolveKeyCPU Thread 9: 1024 kangaroos
SolveKeyCPU Thread 8: 1024 kangaroos
SolveKeyCPU Thread 12: 1024 kangaroos
SolveKeyCPU Thread 10: 1024 kangaroos
SolveKeyCPU Thread 11: 1024 kangaroos
SolveKeyCPU Thread 13: 1024 kangaroos
SolveKeyCPU Thread 14: 1024 kangaroos
SolveKeyCPU Thread 17: 1024 kangaroos
SolveKeyCPU Thread 19: 1024 kangaroos
SolveKeyCPU Thread 15: 1024 kangaroos
SolveKeyCPU Thread 18: 1024 kangaroos
SolveKeyCPU Thread 16: 1024 kangaroos
SolveKeyCPU Thread 20: 1024 kangaroos
[44.34 MK/s][GPU 0.00 MK/s][Count 2^39.28][Dead 277][04:32:02 (Avg 19:29)][32.4MB]

COBRAS

Member

Offline

Activity: 1131
Merit: 25

Re: Pollard's kangaroo ECDLP solver

May 06, 2020, 06:42:35 AM

#91

@Luc. Hello.

Please make sure that if the code does not find the privkey , it is switched to the next one. And you can make the code downgrade dimension of pubkey automaticaly ??

Huh

I'm looking forward to the release.

BIIG THANK YOU !!!!

[

arulbero

Legendary

Offline

Activity: 2023
Merit: 2267

Re: Pollard's kangaroo ECDLP solver

May 06, 2020, 06:59:48 PM

#92

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.

MrFreeDragon

Sr. Member

Offline

Activity: 443
Merit: 350

Re: Pollard's kangaroo ECDLP solver

May 06, 2020, 07:46:32 PM

#93

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

Quote

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.

Visual Private Key Generator - https://btckeygen.com

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 05:11:16 AM

#94

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...

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 06:37:06 AM

#95

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 ?

COBRAS

Member

Offline

Activity: 1131
Merit: 25

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 09:58:28 AM

#96

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?

[

arulbero

Legendary

Offline

Activity: 2023
Merit: 2267

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 11:52:12 AM

#97

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

Thanks for the reading Wink

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

MrFreeDragon

Sr. Member

Offline

Activity: 443
Merit: 350

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 12:55:36 PM

#98

Quote from: Jean_Luc on May 07, 2020, 05: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

Visual Private Key Generator - https://btckeygen.com

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 01:08:04 PM

#99

Quote from: arulbero on May 07, 2020, 11: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....

j2002ba2

Full Member

Offline

Activity: 212
Merit: 468

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 02:37:15 PM

#100

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

Quote

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.

Pages: « 1 2 3 4 [5] 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 ... 146 »

Page 4

Viewing Page: 5