Delta Force Writeup

TSG CTF 2023 - crypto 341 - 6 solves

Commence Operation Delta!! Hint: Last part of this problem, discrete_log() function in sagemath is useful. Run ?discrete_log in sage CLI and read the document.

delta_force.tar.gz

Given Curve is Singular

We are given a curve in the form of Weierstrass form: $E: y^{2} + a_{1}xy + a_{3}y = x^{3} +a_{2}x^{2} + a_{4} x + a_{6}$ over integer modulo ring $N = p q$ , where $p$ and $q$ are hidden.

By checking the discriminant is zero, we find that the given curve is singular.

def is_singular():
    b2 = a1**2 + 4 * a2
    b4 = 2 * a4 + a1 * a3
    b6 = a3**2 + 4 * a6
    b8 = a1**2 * a6 + 4 * a2 * a6 - a1 * a3 * a4 + a2 * a3**2 - a4**2
    Di = -(b2**2) * b8 - 8 * b4**3 - 27 * b6**2 + 9 * b2 * b4 * b6
    return Di % N == 0

assert is_singular(), "Curve is not singular"

Goal: Solve DLP over Integer Modulo `N` over Singular Curve

We are given points $P = (Px, Py)$ and $Q = (Qx, Qy)$ . $Q = d P$ where $d$ is secret. Our goal is to recover $d$ which contains the flag.

Denote $EC(k)$ be the curve defined over modulo ring $k$ , and $ord(EC(k))$ be the order of $EC(k)$ . If we factor $N$ , we can solve each DLP over $EC(p)$ and $EC(q)$ and combine them using chinese remainder theorem.

Factorization of `N = pq`

We do not know the values of $p$ and $q$ yet. However, we know that elliptic curve operation is not well defined in composite ring( $N$ is composite). Also, if singular curve is the form of cusp( $y^2 = x^3$ ) over prime $r$ , its order is $r$ . $ord(EC(N)) = ord(EC(p)) \times ord(EC(q))$ .

Assuming that $EC(p)$ is a cusp( $ord(EC(p)) = p$ ), $N$ will be the multiple of $p = ord(EC(p))$ . If we calculate scalar multiplication $N * P$ over $EC(N)$ , operation will be not well defined. Let $t$ be the intermediate value which breaks down the operation, because $t$ 's inverse does not exist over composite $N$ . This means $gcd(t, N)$ will give a nontrivial factor, which results in factorization, obtaining $p$ .

def factor():
    try:
        ec.scalar(N, P)
    except Exception as e:
        t, _ = list(
            map(
                int,
                str(e).lstrip("inverse of Mod(").rstrip(") does not exist").split(", "),
            )
        )
    p = gcd(t, N)
    q = N // p
    return p, q

Solving DLP over `EC(p)`

Lets classify whether $EC(p)$ is a cusp(form $y^{2} = x^{3}$ ) or node(form $y^{2} = x^{3} + \alpha x^{2}$ ). To do this, we need to find a singular point. Compute partial derivatives of $EC(p)$ and find values where they vanish and also on a curve.

def calc_singular_point(f):
    FF = f.base_ring()
    p = FF.order()

    dfdx = lambda x, y: FF(a1 * y - 3 * x**2 - 2 * a2 * x - a4)
    dfdy = lambda x, y: FF(2 * y + a1 * x + a3)

    A = FF(6)
    B = FF(4 * a2 + a1**2)
    C = FF(2 * a4 + a1 * a3)
    roots = solve_quadratic(A, B, C)

    for xp in roots:
        yp = FF((-a1 * xp - a3) * pow(2, -1, p))
        assert dfdx(xp, yp) == 0 and dfdy(xp, yp) == 0
        if f.subs(x=xp, y=yp) == 0:
            return xp, yp

After that, we shift the curve to set the singular point as origin $(0, 0)$ .

    f = f.subs(x=x + xp, y=y + yp)
    assert f.subs(x=0, y=0) == 0
    xy_coeff = f.coefficient(x * y)
    f = f.subs(y=y + xy_coeff * twoinv * x)
    assert f == x ** 3 - y ** 2, "Given curve is not a cusp"

We confirmed $EC(p)$ is a cusp. We can solve DLP easily when a singular curve is a cusp form. $EC(p)$ has group isomorphism with $GF(p)$ , and can be regarded as an additive group (Theorem 2.30 [^book]).

$\varphi : EC(p) \rightarrow GF(p), \quad (x, y) \rightarrow \frac{x}{y}, \quad \inf \rightarrow 0$

We use this isomorphism $\varphi$ to map points from $EC(p)$ to elements of the group ( $GF(p), +$ ). We first also shift the points because curve has shifted and mapped to an additive group. Therefore $ord(EC(p)) = p$ .

    # shift points
    Pxp = Px - xp
    Pyp = Py - yp - xy_coeff * twoinv * Pxp
    assert f.subs(x=Pxp, y=Pyp) == 0

    Qxp = Qx - xp
    Qyp = Qy - yp - xy_coeff * twoinv * Qxp
    assert f.subs(x=Qxp, y=Qyp) == 0
    
    # map to additive group over FF
    Q_ = FF(FF(Qxp) // FF(Qyp)) 
    P_ = FF(FF(Pxp) // FF(Pyp))

Solving DLP over additive group is easy.

    dp = Q_ // P_

We recovered $d_{p}$ , which is the result of DLP over $EC(p)$ between $P$ and $Q$ . Every implementation for this step is done at method solve_dlp_over_p().

Solving DLP over `EC(q)`

Lets classify whether $EC(q)$ is a cusp(form $y^{2} = x^{3}$ ) or node(form $y^{2} = x^{3} + \alpha x^{2}$ ). Again, we need to find a singular point. Compute partial derivatives of $EC(p)$ and find values where they vanish, and also on a curve. We shift the curve to set the singular point as origin $(0, 0)$ .

    xq, yq = calc_singular_point(f)

    # change of variables to make (0, 0) as singular point
    f = f.subs(x=x + xq, y=y + yq)
    assert f.subs(x=0, y=0) == 0
    xy_coeff = f.coefficient(x * y)
    f = f.subs(y=y + xy_coeff * twoinv * x)
    
    assert alpha != 0
    assert f == x**3 + alpha * x**2 - y**2

We confirmed $EC(q)$ is a node of the form $y^{2} = x^{2} (x + \alpha)$ . We have an isomorphism(Theorem 2.31 [^book]):

$\phi: (x, y) \rightarrow \frac{y + \alpha x}{y - \alpha x}$

$\alpha$ is not a quadratic residue in this challenge, so $\phi$ gives an isomorphism:

$EC(q) \simeq S := { u + \alpha v | u, v \in GF(q), u^{2} - \alpha v^{2} = 1 }$

where the righthand side is a group under multiplication. This is called nonsplit multiplicative reduction. $S$ is a set of points which field norm is $1$ . Let $K/F$ be an extension field when $F = GF(q)$ . Norm map $Norm_{K/F}$ is surjective; (Proof). By the proof, $ord(S)$ (cardinality of kernel) is equal to $q + 1$ . Confirmation:

    # order of Elliptic curve over GF(q) = q + 1
    oq = q + 1
    ec = EC(FF, (a1, a2, a3, a4, a6))
    assert ec.iszeropoint(P) and ec.iszeropoint(Q)
    assert ec.scalar(oq, P) == ec.O and ec.scalar(oq, Q) == ec.O

We know $ord(EC(q)) = q + 1$ . Luckily, $q + 1$ is $B$ -smooth, so we can apply Pohlig Hellman algorithm for solving the DLP.

    factors = [2, 2148001447, ...]
    assert reduce(mul, factors) == oq
    # order is B-smooth where B = 2 ** 33
    B = 2**33
    assert all(fac << B for fac in factors)

Pohlig Hellman algorithm only cares about input elements form a finite abelian group whose order is a smooth integer, which is our case. Sagemath has discrete_log method implemented, which takes elements and operations to make every step of the algorithm well defined. Identity, inverse, addition must be defined over custom groups. Define class ECPoint which is a wrapper of a tuple, define operations, and plug in to discrete_log.

    # ECPoint class for discrete_log
    class ECPoint:
        def __init__(self, point):
            self.point = point

        def is_zero(self):
            return self.point == EC.O

        def __eq__(self, other):
            return self.point == other.point

        def __hash__(self):
            return hash(self.point)

    # factory method for discrete_log
    add = lambda x, y: ECPoint(ec.add(x.point, y.point))
    inv = lambda x: ECPoint(ec.negate(x.point))

    # wrapping points with ECPoint class
    identity = ECPoint(ec.O)
    P_, Q_ = ECPoint(P), ECPoint(Q)

    # discrete_log time
    dq = discrete_log(
        Q_, P_, ord=oq, operation="other", identity=identity, inverse=inv, op=add
    )

Recovering $d_{q}$ takes about 10 minutes in my laptop, which is the result of DLP over $EC(q)$ between $P$ and $Q$ . Every implementation for this step is done at method solve_dlp_over_q().

Solving DLP over `EC(N)`

We solved DLP over $EC(p)$ and $EC(q)$ . Combine the results using the Chinese remainder theorem.

def solve_dlp_over_N():
    p, q = factor()
    dp = solve_dlp_over_p(p)
    dq = solve_dlp_over_q(q)
    return crt([dp, dq], [p, q + 1])

We have recovered $d$ , which is the result of DLP over $EC(N)$ between $P$ and $Q$ .

Flag

Recover flag based on d.

from Crypto.Util.number import long_to_bytes as l2b

flag = l2b(int(d))
flag = flag[: flag.index(b"}") + 1]

We get flag.

TSGCTF{@l1_y0u_n3Ed_IS_ReaDiNG_5ilvErman_ThE_@r1thmetic_of_e11iPtiC_cURVe5}

Problem src: problem.sage depending on elliptic_curve.py

Problem output: output.txt

Exploit driver code: solve.sage

References

[^book]: Elliptic Curves: Number Theory and Cryptography 2nd Edition

Original writeup (https://github.com/pcw109550/write-up/tree/master/2023/TSG/Delta-Force).

Delta Force

Delta Force Writeup

TSG CTF 2023 - crypto 341 - 6 solves

Given Curve is Singular

Goal: Solve DLP over Integer Modulo N over Singular Curve

Factorization of N = pq

Solving DLP over EC(p)

Solving DLP over EC(q)

Solving DLP over EC(N)