I have C++ code for this at hand, I'd have to work on porting it to Python.
There's two versions of this algorithm:
- The local version that uses Floyd's cycle finding algorithm to find collisions
- The distributed version that uses Distinguished Points to find collisions
The code I have uses the latter (it can just be used on a single computer, using multiple cores).
The algorithm can be used when given a Point Q, and its generator P, to find k such that k*P = Q. For small curves (40 bit) the algorithm finishes in below 5 seconds on my machine. For a larger (70 bit) curve, it took about 12 hours to find a collision. For large curves (>128 bit) it is unlikely to finish in a reasonable time frame.
The algorithm is also portable to "regular" Discrete Logarithms (used in DHKE): Given a group element x and its generator g, find k such that g^k = x
This issue is mostly a reminder for myself so I can find this again and port and contribute my code when I find the time.
I have C++ code for this at hand, I'd have to work on porting it to Python.
There's two versions of this algorithm:
The code I have uses the latter (it can just be used on a single computer, using multiple cores).
The algorithm can be used when given a Point Q, and its generator P, to find k such that k*P = Q. For small curves (40 bit) the algorithm finishes in below 5 seconds on my machine. For a larger (70 bit) curve, it took about 12 hours to find a collision. For large curves (>128 bit) it is unlikely to finish in a reasonable time frame.
The algorithm is also portable to "regular" Discrete Logarithms (used in DHKE): Given a group element x and its generator g, find k such that g^k = x
This issue is mostly a reminder for myself so I can find this again and port and contribute my code when I find the time.