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