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

Question

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!

Answer 1

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.