# How to solve this ECDLP?

The Problem is as follows:

$E: y^2=x^3+17230x+22699 \pmod{23981}$

$p=23981$ is prime number

point $G$

$G$'s order $109$ : prime number

Alice creates a public key by selecting a private key $d$ ($d<q$)

public key $Q= dG= (3141,12767)$

therefore public information : $a,b,p,G,q,Q$

private key : $d$

However this curve has the following characteristic:

$$\Delta =-16(4a^3+27b^2)\bmod{p} = 0$$ That is, the discrimant is $0$. and embedding degree is 2

Q. How do I determine if a curve is a CUSPS or a Node?

Q. How to find private key $d$ in this case?

• It would be a lot simpler to answer this if you gave concrete values of $a$, $b$, and $p$. – Samuel Neves Aug 7 '18 at 9:57

We begin with the singular curve $$y^2 = x^3 + 17230x + 22699\,.$$ This curve is singular, as can be immediately determined by its $0$ discriminant. Furthermore, it has a singular point $(23796, 0)$, where both partial derivatives vanish. We translate the curve to have this singular point at $(0, 0)$ by changing variables $(x, y) \mapsto (x - 23796, y - 0)$, after which we obtain the corresponding curve $$y^2 = x^3 + 23426x^2\,,$$ which can be rewritten as $$y^2 = x^2(x + 23426)\,.$$ This curve is a node, not a cusp. A cusp would have, after translation, the form $y^2 = x^3$, because it would have a triple root.

Having the curve in the above form, it becomes easy to solve the logarithm. Because it is a node, we know it maps to a multiplicative group. And because $23426=7020^2$ is a square modulo $23981$, we know it maps to the multiplicative group $\mathbb{F}_{23981}^\ast$, i.e., the integers modulo $23981$. The map is

$$(x, y) \mapsto \frac{y + 7020x}{y - 7020x}\,,$$

after which we can simply solve the discrete logarithm over the integers modulo $23981$.

Here's a short Sagemath script that does the transformation and finds the discrete logarithm:

sage: p = 23981
sage: P.<x> = GF(p)[]
sage: f = x^3 + 17230*x + 22699
sage: P = (1451, 1362)
sage: Q = (3141, 12767)
sage: # change variables to have the singularity at (0, 0)
sage: f_ = f.subs(x=x + 23796)
sage: P_ = (P - 23796, P)
sage: Q_ = (Q - 23796, Q)
sage: # show that the curve is of the form y^2 = x^3 + x^2
sage: print f_.factor()
(x + 23426) * x^2
sage: t = GF(p)(23426).square_root()
sage: # map both points to F_p
sage: u = (P_ + t*P_)/(P_ - t*P_) % p
sage: v = (Q_ + t*Q_)/(Q_ - t*Q_) % p
sage: # use Sage to solve the logarithm
sage: print discrete_log(v, u)
53


This method, and others, are best described in Section 2.10 of Washington's Elliptic Curves: Number Theory and Cryptography.

If $$E$$ be the curve $$y^2 = x^3$$ and $$E_{ns}(K)$$ be the nonsingular points on this curve with coordinates in $$K$$, including the point $$\infty = (0:1:0)$$. Then the map

$$E_{ns}(K) \rightarrow K, \quad (x, y) \rightarrow \frac{x}{y}, \quad \infty \rightarrow 0$$

is a group of isomorphism between $$E_{ns}(K)$$ and $$K$$, regarded as an additive group.

By using this theorem if $$G$$ is base point on cusp curve and $$P = d \times G$$, then we can $$d$$ easily as follows:

$$g = G.x \times G.y^{-1} \pmod p, \quad y = P.x \times P.y^{-1} \pmod p$$ and $$d = g^{-1} \times y \pmod p$$