Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 97. (Read 59490 times)

member
Activity: 348
Merit: 34
June 17, 2020, 11:18:35 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, HuhHuh
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 11:16:35 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.
sr. member
Activity: 462
Merit: 701
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
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 10:46:40 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    
full member
Activity: 206
Merit: 447
June 17, 2020, 10:26:50 AM
If you change the jumps old DPs are useless.
And I moved the point P in this new interval.

How?
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 10:23:34 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.
full member
Activity: 206
Merit: 447
June 17, 2020, 10:20:20 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.
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 10:17:21 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.


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.
full member
Activity: 206
Merit: 447
June 17, 2020, 10:10:48 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.

legendary
Activity: 1932
Merit: 2077
June 17, 2020, 10:01:31 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
sr. member
Activity: 462
Merit: 701
June 17, 2020, 09:56:18 AM
OK I see, I will try to implement this.
Thanks Wink
member
Activity: 348
Merit: 34
June 17, 2020, 09:50:58 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 )
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 09:45:59 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
member
Activity: 348
Merit: 34
June 17, 2020, 09:44:41 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
sr. member
Activity: 462
Merit: 701
June 17, 2020, 09:36:41 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 ?
member
Activity: 348
Merit: 34
June 17, 2020, 09:23:10 AM
Hi,
I don't understand well how this can work ?
If you change G, the path will also differ as jumps are a function of the X value.

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

in this way the points are the same and the paths are the same. The same interval

A = [1G, 2G...., (2^114 - 1)*G]

can be viewed as

B = [32*G', 2*32*G'...., 32*(2^114 - 1)*G']

and this interval is a subset of the interval

C = [1*G', 2*G', 3*G',...., (2^119 - 1)*G']

Note that C has the same number of elements of

D = [1*G, 2*G, ...., (2^119 - 1)*G]

but C != D.

To recap:  

A = B, A subset C
A subset D

What is the difference? Why using C instead of D?

The advantage is that the old DPs, that lie in A = B, lie in C too, but now they are uniformly spread out in C, while the same points are not uniformly spread out in D.

Now, P lies in the interval D, not in C, but P' = inv(32)*P does, and the private key of P' respect to G' is the same as the private key of P respect to G.

-----------------------------------------------------
Note:

C is not the original interval D = [0*G, 2*G, ...., (2^119 - 1)*G], C is a 'contraction' of D, on other hand the very original interval (where the real public key P lies) is E = [2^119 *G, ..., (2^120 - 1)*G].

Usually you shift E to D and P to P' = P - 2^119*G; note that it is like you changed G to G' = G - 2^119G.

Now I suggest to add another move:

move D to C and P' to P'' = inv(32)*P' ; I call this move a 'contraction', because I divide G by 32.

Actually you r saying upword in multiple mode
And i said long time ago downside multiple mode.

Upside *32 mean u still stand 1 part of 32 part
And down side u r stand for 32/1
So i know this stage of multiple pub keys you have 90% work n time savings.
Hope u will not understand. Other jean luc will leave everything and rush to develop multipub key search ver .
Bc after long junps in thinking he will come to this stage in last
Example i said
2 x 100 = 200
But he listening
2+2+2 till 200
2+3 till 200
2x2 x2 till 200

Hope u all moving slowly to multiple keys or multiple bits
But dont try to understand my words. As its from brainless
sr. member
Activity: 661
Merit: 250
June 17, 2020, 09:06:16 AM
Yes thanks for this tip Smiley
I'm building a map to compute with accuracy the DP overhead as I didn't yet managed to get the correct analytical expression but only the 2 asymptote (0 and infinity)
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.

Can you please let the #64 for normal guys not owning/renting tons of gpu ?
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 08:26:46 AM
Hi,
I don't understand well how this can work ?
If you change G, the path will also differ as jumps are a function of the X value.

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

in this way the DP points are the same, the jumps are the same and all the old paths are the same too.

The same interval

A = [1G, 2G...., (2^114 - 1)*G]

can be viewed as

B = [32*G', 2*32*G'...., 32*(2^114 - 1)*G']

and this interval is a subset of the interval

C = [1*G', 2*G', 3*G',...., (2^119 - 1)*G']

Note that C has the same number of elements of

D = [1*G, 2*G, ...., (2^119 - 1)*G]

but C != D.

To recap:  

A = B, A subset C
A subset D

What is the difference? Why to work in C instead of D, since the old points in A are already in D?

The advantage is that the old DPs, that lie in A, are uniformly spread out in C, while the same points are not uniformly spread out in D.

Now, P lies in the interval D, not in C, but P' = inv(32)*P does, and the private key of P' respect to G' is the same as the private key of P respect to G.

-----------------------------------------------------
Note:

C is not the original interval D = [0*G, 2*G, ...., (2^119 - 1)*G], C is a 'contraction' of D, on other hand the very original interval (where the real public key P lies) is E = [2^119 *G, ..., (2^120 - 1)*G].

Usually you shift E to D and P to P' = P - 2^119*G.

Now I suggest to add another move:

move D to C and P' to P'' = inv(32)*P' ; I call this move a 'contraction', because I divide G by 32.
legendary
Activity: 1932
Merit: 2077
June 17, 2020, 08:23:58 AM
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.

In the search of #64 you will find several points with x-coordinate with the leading 60 bits = 0. You could use them here as jumps to save space (or to use more jumps in the same space).  But in this way you can't reuse the old DPs.


There was an interesting question in a previous message of this topic:
Why paths are important and why not adding DP without computing paths ?

Using only DP:
It is like drawing a random number in a reduced space N/2^dpbit so time to solve will be O( sqrt(N/2^dpbit) )
However, it is true, that you can reach a DP faster in this way by computing consecutive points.

Using paths:
It is like drawing a bunch of 2^dpbit random points at each DP, so time to solve is O( sqrt(N)/2^dpbit )
The "gain" using path is 2^dpbit while without paths, the "gain" is only sqrt(2^dpbit)

So even if reaching a DP without path is faster, the gain is not enough to beat path.

I think that a DP worth is equal to the length of the path you computed to find it.
 
If you find a DP with 25 bits = 0 after 2^27 steps, that point should be worth like 4 points, each with 25 bits = 0 and found after 2^25 steps. It is like a DP with 25 bits = 0 is equal to a DP with 27 bits = 0.

If you reuse only the DPs you found after 2^27 steps, you will have a better ratio "space occupied / chance to find a collision"
sr. member
Activity: 462
Merit: 701
June 17, 2020, 08:19:58 AM
Hi,
I don't understand well how this can work ?
If you change G, the path will also differ as jumps are a function of the X value.
Pages:
Jump to: