Pollard's kangaroo ECDLP solver - page 96.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: Jean_Luc on June 17, 2020, 11:05:07 AM

Implementing changing of G is rather an heavy task so I would like to have at least an estimation of the loss due to the fact that all paths of new DP will have all points multiple of 32.
We will probably also use DP28 or DP27 for #120

If you are going to change the DP size too, it can't work, because with more steps for each path you have to lower the jumps mean.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: Etar on June 17, 2020, 11:25:32 AM

What i have done using proposed arulbero method.. I solve pazzle 59 bit and save work. Then i tame all wild DPs with previous private key in file.
And multiply distance of each DP by 32
After that i compile kangaroo.exe where G*inv(32)= (a3c9d9de2ba89d61c63af260be9759d752b8bfef56ee41b2dab2b99871af38a8,b639cb2d3e0f1940d5e5333061d489159d1783ba821eaef15f78802d002f63fb)
I can`t say if new wild DP collide old tame from workfile or it is collsion with both new DPs but here is some test with pazzle 64bit

....

Thanks, but we need a test with at least 1000 public keys, to measure the difference.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: j2002ba2 on June 17, 2020, 11:24:11 AM

This would work properly only when the private key of P is zero mod 32. P=k*G, k=0 (mod 32).

Otherwise the point is guaranteed to not be in the interval.

The probability of being in the new interval is 1/32, which is about 3%. In all other 97% the algorithm would fail to find a point in any reasonable time.

If you somehow can deterministically move points from bigger interval to smaller, then no kangaroos are needed, ECDLP is solved. In the 1/32 case - in just 8 steps (!!!).

No, it is not like you say:

if you know that P lies in [1G,100G]

then you know that 2P lies in [2G,4G...,400G]

and that kP lies in [kG, k2G, k3G, ..., k100G]

that remains true even if k is inv(2), inv(3) and so on.

Etar

sr. member

Activity: 617

Merit: 312

What i have done using proposed arulbero method.. I solve pazzle 59 bit and save work. Then i tame all wild DPs with previous private key in file.
And multiply distance of each DP by 32
After that i compile kangaroo.exe where G*inv(32)= (a3c9d9de2ba89d61c63af260be9759d752b8bfef56ee41b2dab2b99871af38a8,b639cb2d3e0f1940d5e5333061d489159d1783ba821eaef15f78802d002f63fb)
I can`t say if new wild DP collide old tame from workfile or it is collsion with both new DPs but here is some test with pazzle 64bit

Code:

DPs JUST MOVED TO NEW INTERVAL WITHOUT SHIFTING PUB
P=P/32
Start:10000000000000000
Stop :1FFFFFFFFFFFFFFFF
Range width: 2^64
Expected operations: 2^33.08
DP size: 15 [0xFFFE000000000000]
[15.25 MK/s][GPU 0.00 MK/s][Count 2^32.37][Dead 0][06:56 (Avg 09:53)][9.2/30.2MB]
Key# 0 [1S]Pub:  0x0299A240D5FD67F0F9DBC558AF072E26B285B5DF1FACD1E9509A168A9523F53958
       Priv: 0x1A838B13505B26867
Done: Total time 06:56

REPEAT FOR MORE TEST
DPs JUST MOVED TO NEW INTERVAL WITHOUT SHIFTING PUB
P=P/32
Start:10000000000000000
Stop :1FFFFFFFFFFFFFFFF
Keys :1
Range width: 2^64
DP size: 15 [0xFFFE000000000000]
[15.27 MK/s][GPU 0.00 MK/s][Count 2^32.43][Dead 1][07:18 (Avg 09:52)][9.5/30.9MB]
Key# 0 [1S]Pub:  0x0299A240D5FD67F0F9DBC558AF072E26B285B5DF1FACD1E9509A168A9523F53958
       Priv: 0x1A838B13505B26867
Done: Total time 07:20

PUB SHIFTED AND DPs MOVED TO NEW INTERVAL
P=(P-0x10000000000000000*G)/32
Start:0
Stop :FFFFFFFFFFFFFFFF
Range width: 2^64
Expected operations: 2^33.08
DP size: 15 [0xFFFE000000000000]
[15.13 MK/s][GPU 0.00 MK/s][Count 2^33.46][Dead 1][14:35 (Avg 09:58)][15.1/42.9MB]
Key# 0 [1S]Pub:  0x02B0090246C76FA061A11AF1165F652344FDF191FBC74B4295E7DF2FEDB388B5C7
       Priv: 0xA838B13505B26867+0x10000000000000000=0x1A838B13505B26867
Done: Total time 14:37

REPEAT FOR MORE TEST
PUB SHIFTED AND DPs MOVED TO NEW INTERVAL
P=(P-0x10000000000000000*G)/32
Start:0
Stop :FFFFFFFFFFFFFFFF
Range width: 2^64
DP size: 15 [0xFFFE000000000000]
[15.21 MK/s][GPU 0.00 MK/s][Count 2^32.29][Dead 0][06:32 (Avg 09:55)][9.0/29.6MB]
Key# 0 [1S]Pub:  0x02B0090246C76FA061A11AF1165F652344FDF191FBC74B4295E7DF2FEDB388B5C7
       Priv: 0xA838B13505B26867+0x10000000000000000=0x1A838B13505B26867
Done: Total time 06:32

REPEAT FOR MORE TEST
PUB SHIFTED AND DPs MOVED TO NEW INTERVAL
P=(P-0x10000000000000000*G)/32
Start:0
Stop :FFFFFFFFFFFFFFFF
Range width: 2^64
Expected operations: 2^33.08
DP size: 15 [0xFFFE000000000000]
[15.16 MK/s][GPU 0.00 MK/s][Count 2^32.61][Dead 0][08:01 (Avg 09:57)][10.2/32.6MB]
Key# 0 [1S]Pub:  0x02B0090246C76FA061A11AF1165F652344FDF191FBC74B4295E7DF2FEDB388B5C7
       Priv: 0xA838B13505B26867+0x10000000000000000=0x1A838B13505B26867
Done: Total time 08:02

REPEAT FOR MORE TEST
PUB SHIFTED AND DPs MOVED TO NEW INTERVAL
P=(P-0x10000000000000000*G)/32
Start:0
Stop :FFFFFFFFFFFFFFFF
Range width: 2^64
Expected operations: 2^33.08
DP size: 15 [0xFFFE000000000000]
[14.86 MK/s][GPU 0.00 MK/s][Count 2^33.54][Dead 1][15:45 (Avg 10:09)][15.7/43.9MB]
Key# 0 [1S]Pub:  0x02B0090246C76FA061A11AF1165F652344FDF191FBC74B4295E7DF2FEDB388B5C7
       Priv: 0xA838B13505B26867+0x10000000000000000=0x1A838B13505B26867
Done: Total time 15:46


NORAML SOLVING WITH RIGHT G
Start:10000000000000000
Stop :1FFFFFFFFFFFFFFFF
Range width: 2^64
DP size: 15 [0xFFFE000000000000]
[20.33 MK/s][GPU 0.00 MK/s][Count 2^33.38][Dead 1][10:02 (Avg 07:25)][12.4/37.8MB]
Key# 0 [1S]Pub:  0x0230210C23B1A047BC9BDBB13448E67DEDDC108946DE6DE639BCC75D47C0216B1B
       Priv: 0x1A838B13505B26867
Done: Total time 10:02

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: arulbero on June 17, 2020, 10:46:40 AM

Quote from: j2002ba2 on June 17, 2020, 10:26:50 AM

Quote from: arulbero on June 17, 2020, 10:23:34 AM

Quote from: j2002ba2 on June 17, 2020, 10:20:20 AM

If you change the jumps old DPs are useless.

And I moved the point P in this new interval.

How?

I moved P in the interval C in this way: P -> P' = inv(32)*P

This would work properly only when the private key of P is zero mod 32. P=k*G, k=0 (mod 32).

Otherwise the point is guaranteed to not be in the interval.

The probability of being in the new interval is 1/32, which is about 3%. In all other 97% the algorithm would fail to find a point in any reasonable time.

If you somehow can deterministically move points from bigger interval to smaller, then no kangaroos are needed, ECDLP is solved. In the 1/32 case - in just 8 steps (!!!).

brainless

member

Activity: 330

Merit: 34

Quote from: Jean_Luc on June 17, 2020, 11:05:07 AM

It is necessary to use same jumps otherwise path are incompatible.
And the mean has also to be controlled.
Implementing changing of G is rather an heavy task so I would like to have at least an estimation of the loss due to the fact that all paths of new DP will have all points multiple of 32.
We will probably also use DP28 or DP27 for #120

finally you agree, to go back at normal work for 120 as worked for 115, no implements, no changes, no new developments, Huh

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: Jean_Luc on June 17, 2020, 11:05:07 AM

It is necessary to use same jumps otherwise path are incompatible.
And the mean has also to be controlled.
Implementing changing of G is rather an heavy task so I would like to have at least an estimation of the loss due to the fact that all paths of new DP will have all points multiple of 32.

I will do some tests tomorrow, but I fear that it is not worth it. For now don't work on it.

The mean is correct, the jumps are the same but the main point is:

each path must have the possibility to reach any point in the interval to maximize the probability, but in this case each path could reach only 1/32 of the points.

For example, only the paths starting from a multiple of 32 has the chance to collide with a old DPs, all the others haven't.

Jean_Luc

sr. member

Activity: 462

Merit: 696

It is necessary to use same jumps otherwise path are incompatible.
And the mean has also to be controlled.
Implementing changing of G is rather an heavy task so I would like to have at least an estimation of the loss due to the fact that all paths of new DP will have all points multiple of 32.
We will probably also use DP28 or DP27 for #120

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: j2002ba2 on June 17, 2020, 10:26:50 AM

Quote from: arulbero on June 17, 2020, 10:23:34 AM

Quote from: j2002ba2 on June 17, 2020, 10:20:20 AM

If you change the jumps old DPs are useless.

And I moved the point P in this new interval.

How?

I moved P in the interval C in this way: P -> P' = inv(32)*P

To be more precise: the wide of the interval is the same (2^119*G' = 2^114*G) as the old interval, and we use the same jumps (that look like they were x32 bigger, but they are not) and we perform the same number of steps for each path (2^25), then we shouldn't go out of the interval.

The points in this interval are closer (the distance between 2 consecutive points is (1/32)*G instead of G)

But you are right on a point: if we use the old jumps, from the point of view of G' they are all multiples of 32, each single path could visit only 1/32 of the points; in this case even if we used many kangaroos in parallel we would have to do more steps! Roll Eyes

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: arulbero on June 17, 2020, 10:23:34 AM

Quote from: j2002ba2 on June 17, 2020, 10:20:20 AM

If you change the jumps old DPs are useless.

And I moved the point P in this new interval.

How?

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: j2002ba2 on June 17, 2020, 10:20:20 AM

If you change the jumps old DPs are useless.

I didn't change the jumps, I changed only the interval. In this interval the points are more by a factor of 32. And I moved the point P in this new interval.

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: arulbero on June 17, 2020, 10:17:21 AM

Quote from: j2002ba2 on June 17, 2020, 10:10:48 AM

Quote from: arulbero on June 17, 2020, 08:26:46 AM

Jumps (the points) are the same, only their private keys are different;

instead of using, for example, 2543*G as jump, you use (2543*32)*G', where G' = inv(32)*G

It sounds quite useless to me.

To get the benefits of kangaroo algorithm, you need to use a specific mean step.

G' makes all the steps multiple of 32, visiting only 1/32 of the points. This is instant sqrt(32) times slowdown.

Why you are visiting only 1/32 of the points? You are working in a wider interval, then it is normal to use larger jumps.

The optimal would be increase the length of the jumps by sqrt(32) instead of 32, but you have to increase it.

If you change the jumps old DPs are useless.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: j2002ba2 on June 17, 2020, 10:10:48 AM

Quote from: arulbero on June 17, 2020, 08:26:46 AM

Jumps (the points) are the same, only their private keys are different;

instead of using, for example, 2543*G as jump, you use (2543*32)*G', where G' = inv(32)*G

It sounds quite useless to me.

To get the benefits of kangaroo algorithm, you need to use a specific mean step.

G' makes all the steps multiple of 32, visiting only 1/32 of the points. This is instant sqrt(32) times slowdown.

Why you are visiting only 1/32 of the points? You are working in a interval with more points, then it is normal to use larger jumps.

The optimal would be increase the length of the jumps by sqrt(32) instead of 32, but you have to increase it.

Quote from: j2002ba2 on June 17, 2020, 10:10:48 AM

If you do P' = inv(32)*P, then you have 1/32 chance that it lays in the target interval, so 1/32 chance to solve it, 31/32 chance that algorithm takes forever.

I didn't understand that.

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: arulbero on June 17, 2020, 08:26:46 AM

Jumps (the points) are the same, only their private keys are different;

instead of using, for example, 2543*G as jump, you use (2543*32)*G', where G' = inv(32)*G

It sounds quite useless to me.

To get the benefits of kangaroo algorithm, you need to use a specific mean step.

G' makes all the steps multiple of 32, visiting only 1/32 of the points. This is instant sqrt(32) times slowdown.

The other thing is transforming P.

If it stays the same or is translated, you get 32 times bigger interval, and sqrt(32) times slowdown.

If you do P' = inv(32)*P, then you have 1/32 chance that it lays in the target interval, so 1/32 chance to solve it, 31/32 chance that algorithm takes forever.

If you do 32 parallel P' kangaroo searches, so at least one fits in the target interval, you loose sqrt advantage. Instead of sqrt(32) slowdown of #120 compared to #115, you get 32 times slowdown.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: Jean_Luc on June 17, 2020, 09:56:18 AM

OK I see, I will try to implement this.
Thanks Wink

Ok.

Remember: first shift P to P - 2^119*G and then inv(32)*(P - 2^119**G) = inv(32)*P - 2^(119-5)*G

inv(32)*(original P) is not correct.

You could let all the old wild DPs as they are, and computing at the end the private key only for the collision, if you store the old P (point #114) too

Jean_Luc

sr. member

Activity: 462

Merit: 696

OK I see, I will try to implement this.
Thanks Wink

brainless

member

Activity: 330

Merit: 34

Quote from: brainless on June 17, 2020, 09:44:41 AM

Quote from: Jean_Luc on June 17, 2020, 09:36:41 AM

Quote from: arulbero on June 17, 2020, 08:26:46 AM

Jumps (the points) are the same, only their private keys are different;

So in practical, I let the old #115 DP as they are and for the new search #120 I use inv(32)*G instead of G ?

yes above is 1 point, and you need 2.5 points (25dp) in search
so if i generate 80 (2.5 per point) coresponding pubkeys, that could save more 80% time saving
those 80 keys only need to search in old 115bit save.work file
but i know u r hesitate to multipubkeys
so better use inv(32)*G instead of G with 1 pubeky

more over
for 25dp, you can go more downbit to 25bit down, final bit range would be 95bit, but with 2.5m corresponding pubkeys
can you imagine, where you can stand in finding solution ( time and resources )

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: Jean_Luc on June 17, 2020, 09:36:41 AM

Quote from: arulbero on June 17, 2020, 08:26:46 AM

Jumps (the points) are the same, only their private keys are different;

So in practical, I let the old #115 DP as they are and for the new search #120 I use inv(32)*G instead of G ?

Exactly.

You have to change P too, from P to P' = inv(32)*G.

The points are the same, not the distances, you have to multiply all the 32 distances of the jumps by 32.

And when you find a collision and you retrieve the private key, if the collision has happened with a old DP T = oldprivatekey*G:

P' + distance*G' = T (old DP point)

P' = T - distance*G'

P' = oldprivatekey*G - distance*G'

k*G' = oldprivatekey*32*G' - distance*G'

k = (oldprivatekey*32 - distance) mod n

I suggest do not check if a DP is 'old' or not, when you have a collision you can try both way:

k = privatekey of T - distance mod n

and

k = (privatekey of T)*32 - distance mod n

brainless

member

Activity: 330

Merit: 34

Quote from: Jean_Luc on June 17, 2020, 09:36:41 AM

Quote from: arulbero on June 17, 2020, 08:26:46 AM

Jumps (the points) are the same, only their private keys are different;

So in practical, I let the old #115 DP as they are and for the new search #120 I use inv(32)*G instead of G ?

yes above is 1 point, and you need 2.5 points (25dp) in search
so if i generate 80 (2.5 per point) coresponding pubkeys, that could save more 80% time saving
those 80 keys only need to search in old 115bit save.work file
but i know u r hesitate to multipubkeys
so better use inv(32)*G instead of G with 1 pubeky

Jean_Luc

sr. member

Activity: 462

Merit: 696

Quote from: arulbero on June 17, 2020, 08:26:46 AM

Jumps (the points) are the same, only their private keys are different;

So in practical, I let the old #115 DP as they are and for the new search #120 I use inv(32)*G instead of G ?

Topic: Pollard's kangaroo ECDLP solver - page 96. (Read 58608 times)