THE GARDEN

Conic-Non-Elliptic Curve DLP Reduction (Fake ECC)

Updated 13 Sep 2026

• •

  What it is

  • •

    Elliptic-curve cryptography's security relies on a specific hard structure — the point group of a genuine elliptic curve (a smooth cubic) has no known efficient discrete-log algorithm in general. A conic — a degree-2 curve like $x^2 - Dy^2 = 1$ — can also be equipped with a group law that superficially looks like "elliptic curve" code, but conics are not elliptic curves, and their groups are secretly isomorphic to something much simpler: the substitution $u = x - \sqrt{D}\,y,\ v = x + \sqrt{D}\,y$ transforms the conic's equation into $uv = 1$ — literally the multiplicative group of the field (when $\sqrt D$ exists there, i.e. $D$ is a quadratic residue) — collapsing the "discrete log problem" on the conic into an ordinary discrete log in $\mathbb{F}_p^\times$, easy whenever $p-1$ is smooth (typical for a randomly chosen toy prime), via Pohlig-Hellman.

• •

  When to apply

  • •

    A challenge presents a hand-rolled "elliptic curve" whose point-addition formula doesn't look like the real Weierstrass group law (no cubic term, no slope/tangent-line computation) — especially a simple bilinear formula in the coordinates. Check what implicit curve equation the code's assertions define; if it's degree 2 (a conic), not degree 3, this reduction almost certainly applies.

• •

  Math

  • •

    Given the conic $x^2 - Dy^2 \equiv 1 \pmod p$ with $D$ a QR mod $p$ (write $s \equiv \sqrt D$), the map $\varphi(x,y) = x - sy \bmod p$ is a group isomorphism onto $\mathbb{F}_p^\times$. For base point $G$ and public point $A = n_a \cdot G$: $\varphi(A) = \varphi(G)^{n_a} \bmod p$, so $n_a = \log_{\varphi(G)} \varphi(A)$ — an ordinary multiplicative discrete log.

• •

  Worked example

  • •

    Toy 20-bit prime $p$ with $D$ a QR (via a known small square root $s$), a random base point $G$ satisfying $x^2 - Dy^2 \equiv 1$, and a random private scalar: computing $g = \varphi(G)$, $h = \varphi(A)$ and brute-force searching for $n_a$ with $g^{n_a} \equiv h \pmod p$ recovered the exact private scalar used to generate $A$ via the real scalar_multiplication, confirming the isomorphism holds and the discrete log transfers correctly.

• •

  Python

  • •

    # after finding integer square root s of D mod p (only possible if D is a QR mod p):
    def phi(P, s, p):
        return (P.x - s * P.y) % p
    
    g, h = phi(G, s, p), phi(A, s, p)
    # now solve g^na == h (mod p) -- an ordinary multiplicative-group DLP
    

• •

  SageMath

  • •

    This is exactly the case Sage helps most with — its discrete_log() runs Pohlig-Hellman/BSGS automatically once $p-1$ is factored:

  • •

    F = GF(p)
    n_a = discrete_log(F(h), F(g))   # trivial when p-1 is smooth, as it usually is for a toy modulus
    

• •

  Cards

  • •

    What's the giveaway that a "custom elliptic curve" is actually a conic in disguise?

    • •

      The point-addition formula is a simple bilinear expression with no cubic/Weierstrass structure, and the implicit curve equation is degree 2, not degree 3.

  • •

    What group is a conic x²-Dy²=1 secretly isomorphic to, and via what map?

    • •

      The multiplicative group of the field (F_p*, when D is a quadratic residue mod p), via u = x - √D·y.

◌ Explore connections in Graph view