featherduster icon indicating copy to clipboard operation
featherduster copied to clipboard

Add Pollard's Rho method for solving EC Discrete Logarithms

Open sonOfRa opened this issue 8 years ago • 0 comments

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:

  1. The local version that uses Floyd's cycle finding algorithm to find collisions
  2. 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.

sonOfRa avatar Jun 29 '17 22:06 sonOfRa