Topic: Pollard's kangaroo ECDLP solver - page 142. (Read 55599 times)
Hello everybodey. Big thanks for your work. My GPU is ready for tests !!!!
Thanks for the readings 
I will try to see if this can be implemented on ECDLP.
I will try to see if this can be implemented on ECDLP.
OK i will try this.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.
I think there's a paper about this already:
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf
You probably need to detect frutiless cycles with this method (stuck kangaroos in a loop without distinguished points).
Many thanks!!! I didn't know it !
EDIT:
from the article:
Quote
Average number of group operations performed by our algorithm: 1.46 * sqrt(2^n)
The cost of searching the list of previous group elements is not included in our experimental results, but our count of group operations does include the “wasted” steps from being in a cycle.
The cost of searching the list of previous group elements is not included in our experimental results, but our count of group operations does include the “wasted” steps from being in a cycle.
OK i will try this.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.
I think there's a paper about this already:
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf
You probably need to detect frutiless cycles with this method (stuck kangaroos in a loop without distinguished points).
OK i will try this.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.
Now:
tamei = rand(0..(k2-k1)) # Scalar operation
wildi = rand(0..(k2-k1)) - (k2-k1)/2 # Scalar operation
wildPosi = P + wildi.G # Group operation
My proposal (assuming that private key of P is for sure in [-(k2-k1)/2, (k2-k1)/2])
tamei = rand(0,..(k2-k1)/2) # Scalar operation (you can avoid negative numbers for tame)
wildi = rand(-(k2-k1)/4,...(k2-k1)/4) # Scalar operation
wildPosi = P + wildi.G # Group operation
OK i will try this.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.
It is enough to modify slightly the way we generate the next jump:
+ jP[tamePosi.x % n]*G if y > p/2, - jP[tamePosi.x % n]*G is y
(then I will indicate 'y' if y > p/2, '-y' if y < p/2)
in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision
The tame and the wild will go on with 2 specular paths:
Q -> Q + k*G -> Q + k*G -r*G -> ... -> DP
(x,y) (x1,-y1) (x2,y2) (x0, y0)
-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y) (x1,y1) (x2, -y2) (x0, -y0)
until they reach 2 symetric DP, for both of which we know the private key.
I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.
+ jP[tamePosi.x % n]*G if y > p/2, - jP[tamePosi.x % n]*G is y
(then I will indicate 'y' if y > p/2, '-y' if y < p/2)
in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision
The tame and the wild will go on with 2 specular paths:
Q -> Q + k*G -> Q + k*G -r*G -> ... -> DP
(x,y) (x1,-y1) (x2,y2) (x0, y0)
-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y) (x1,y1) (x2, -y2) (x0, -y0)
until they reach 2 symetric DP, for both of which we know the private key.
May be a brownian motion can be interesting (having positive and negative jump).
I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.
I'm not sure to fully understand your idea.
You want to add a condition on the y parity to determine the jump ?
You let the starting positions as they are or you translate them ?
The start interval must be: [-(b-a)/2, +(b-a)/2]
and yes, I want to add a condition on the y parity to determine the jump's direction.
In this way a wild and a tame collide if they reach:
1) the same point
2) two symetric points
In the interval [-(b-a)/2, +(b-a)/2], the x-coordinates of [1, +(b-a)/2] are equal to the x-coordinates of [-(b-a)/2, -1]; we should get more collisions, because we work in a space of 2^(n-1) points instead of 2^n.
We introduce a equivalence class [P], where P ~ Q if Q = -P and the jump function goes from [P] to [P1], i.e. it is defined between 2 equivalence classes instead of between 2 points.
A problem could be that many paths could enter in a loop before they reach a DP, because each kangaroo jumps back and forth and then a single kangaroo can collide with itself.
It is enough to modify slightly the way we generate the next jump:
+ jP[tamePosi.x % n]*G if y > p/2, - jP[tamePosi.x % n]*G is y
(then I will indicate 'y' if y > p/2, '-y' if y < p/2)
in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision
The tame and the wild will go on with 2 specular paths:
Q -> Q + k*G -> Q + k*G -r*G -> ... -> DP
(x,y) (x1,-y1) (x2,y2) (x0, y0)
-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y) (x1,y1) (x2, -y2) (x0, -y0)
until they reach 2 symetric DP, for both of which we know the private key.
I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.
+ jP[tamePosi.x % n]*G if y > p/2, - jP[tamePosi.x % n]*G is y
(then I will indicate 'y' if y > p/2, '-y' if y < p/2)
in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision
The tame and the wild will go on with 2 specular paths:
Q -> Q + k*G -> Q + k*G -r*G -> ... -> DP
(x,y) (x1,-y1) (x2,y2) (x0, y0)
-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y) (x1,y1) (x2, -y2) (x0, -y0)
until they reach 2 symetric DP, for both of which we know the private key.
May be a brownian motion can be interesting (having positive and negative jump).
I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.
I'm not sure to fully understand your idea.
You want to add a condition on the y parity to determine the jump ?
You let the starting positions as they are or you translate them ?
Hello,
I would like to present an interval ECDLP solver based on the Pollard's kangaroo method.
This program is fully open source and available on GitHub: https://github.com/JeanLucPons/Kangaroo
It has GPU support (CUDA Only) and works on both Linux and Windows.
This program is currently under development.
Thanks to test it and to share ideas of improvements here
I would like to present an interval ECDLP solver based on the Pollard's kangaroo method.
This program is fully open source and available on GitHub: https://github.com/JeanLucPons/Kangaroo
It has GPU support (CUDA Only) and works on both Linux and Windows.
This program is currently under development.
Thanks to test it and to share ideas of improvements here
Jump to: