Tags: elliptic dlp crypto
Rating:
# 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](delta_force.tar.gz)
#### Given Curve is Singular
We are given a curve in the form of [Weierstrass form](https://crypto.stanford.edu/pbc/notes/elliptic/weier.html): $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.
```python
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](https://en.wikipedia.org/wiki/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](https://crypto.stackexchange.com/questions/72613/elliptic-curve-discrete-log-in-a-composite-ring) 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$.
```python
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](https://en.wikipedia.org/wiki/Singular_point_of_a_curve). Compute partial derivatives of $EC(p)$ and find values where they vanish and also on a curve.
```python
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)$.
```python
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$.
```python
# 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.
```python
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](https://en.wikipedia.org/wiki/Singular_point_of_a_curve). 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)$.
```python
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](https://en.wikipedia.org/wiki/Field_norm) is $1$. Let $K/F$ be an extension field when $F = GF(q)$. Norm map $Norm_{K/F}$ is [surjective](https://math.stackexchange.com/questions/143711/show-the-norm-map-is-surjective); [(Proof)](https://math.stackexchange.com/questions/1717178/extension-of-finite-fields-under-norm-map). By the proof, $ord(S)$(cardinality of kernel) is equal to $q + 1$. Confirmation:
```python
# 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](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) algorithm for solving the DLP.
```python
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`](https://doc.sagemath.org/html/en/reference/groups/sage/groups/generic.html#sage.groups.generic.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`.
```python
# 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.
```python
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`.
```python
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](problem.sage) depending on [elliptic_curve.py](elliptic_curve.py)
Problem output: [output.txt](output.txt)
Exploit driver code: [solve.sage](solve.sage)
#### References
[^book]: Elliptic Curves: Number Theory and Cryptography 2nd Edition
