1

I am looking for a Python script or SageMath code implementation for testing the Baby Step - Giant Stepand Pollard Rhoalgorithms on the secp256k1 curve.

I have read that these algorithms are well known for solving the ECDL problem for small numbers but I haven't found any code to test this.

edit:

I am looking for generating a small secret multiplier over the standard secp256k1 curve parameters.

Here is an example for E=EllipticCurve(GF(modi), [0,7]) using the standard NIST parameters for G. 

G=E(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)

We know that for

P=E(69335761065767984070318781108127416310968753866933119760392423089576366173459, 113425617697416972613102767146321902225172329004525144463444008550345431352693)

when calculating discrete_log we get the small x=24734216105351567 as a result of P = x * G

Is there any such implementation that will calculate the small x?

Thanks!

Improve this question

1 Answer 1

Reset to default
2

In Sage.

Let's first define a finite field of size 2^32 (over which exhaustively searching would be painful but doable, but Pollard-Rho should be pretty fast).

sage F = GF(2^32 - 5)

And a prime-ordered elliptic curve over it (y^2 = x^3 + x + 13 happens to be prime)

sage: E = EllipticCurve(F, [1, 13])

Let's call the order of the curve n:

sage: n = E.order()
sage: n
4295040499
sage: n.is_prime()
True

Let's pick an arbitrary generator on that curve:

sage: G = E.gen(0)
sage: G
(4022957561 : 1193765470 : 1)
sage: G.order() == n
True

Now let's pick a random multiple of that generator:

sage: import random
sage: x = random.randrange(n)
sage: x
1334636724
sage: P = x * G
sage: P
(2051230087 : 1391923842 : 1)

And to find the discrete logarithm, simply use:

sage: discrete_log(P, G, n, operation='+')
1334636724

The same as our random secret multiplier x.

Sage uses Pollard-Rho and other algorithms internally.

Improve this answer
3
  • Thank you but I am looking for generating a small secret multiplier over the standard secp256k1 curve parameters. Here is an example for E=EllipticCurve(GF(modi), [0,7]) using the standard NIST (G=E) parameters. We know that for P=E(69335761065767984070318781108127416310968753866933119760392423089576366173459, 113425617697416972613102767146321902225172329004525144463444008550345431352693) when calculating discrete_log(P, G, n, operation='+') we get the small x=24734216105351567 as a result of P = x * G - how do I update your code to calculate this example? I clarified the Question.
    – Robert
    Jul 4, 2019 at 19:34
  • If you're going to use Pollard's Rho over secp256k1, it'd need ~2^128 steps to complete. If you know the DL is very small perhaps the algorithm can be optimized using that information, but I'm not sure about the gains.
    – Pieter Wuille
    Jul 8, 2019 at 2:44
  • Yes, that was the advice I was looking for. Thanks a lot. Much appreciated :)
    – Robert
    Jul 15, 2019 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.