# Is there a Python or SageMath implementation for solving the ECDL problem for small secret multiplier?

I am looking for a Python script or SageMath code implementation for testing the `Baby Step - Giant Step`and `Pollard Rho`algorithms 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!

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.

• 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. 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. Jul 8, 2019 at 2:44
• Yes, that was the advice I was looking for. Thanks a lot. Much appreciated :) Jul 15, 2019 at 8:41