How to solve this ECDLP?

Question

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?

Answer 1

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[0] - 23796, P[1])
sage: Q_ = (Q[0] - 23796, Q[1])
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_[1] + t*P_[0])/(P_[1] - t*P_[0]) % p
sage: v = (Q_[1] + t*Q_[0])/(Q_[1] - t*Q_[0]) % 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.

Answer 2

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$$