Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Pollard's Rho method for solving EC Discrete Logarithms #74

Open
sonOfRa opened this issue Jun 29, 2017 · 0 comments
Open

Add Pollard's Rho method for solving EC Discrete Logarithms #74

sonOfRa opened this issue Jun 29, 2017 · 0 comments

Comments

@sonOfRa
Copy link

sonOfRa commented Jun 29, 2017

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant