Our team (Students Taking Flags United) won the champion in Teritary category in HKCERT CTF 2025. This is the required writeup.

**Crypto - Bivariate copper**
Challenge setup

from Crypto.Util.number import *
from secret import *

with open("message", "r") as f:
    message = f.read().strip().encode()

m = bytes_to_long(flag)
message = bytes_to_long(message)

p = getPrime(1024)
q = getPrime(25)
N = p * q
e = 65537

c = pow(message, e, N)
r1, r2 = getPrime(512), getPrime(512)
k = getPrime(64)

t1 = (k * inverse(m + r1, p)) % p
t2 = (k * inverse(m + r2, p)) % p

leak1 = t1 >> 244
leak2 = t2 >> 244

print(f'{e = }')
print(f'{N = }')
print(f'{c = }')

print(f'{k = }')
print(f'{r1 = }')
print(f'{r2 = }')
print(f'{leak1 = }')
print(f'{leak2 = }')

notice that q is only 25 bits!!!
Whats that mean? There is only 2^25 combinations of q, which is around 30millions. So, it is very easy to find the correct value of q and factor N and obtain p.

for i in range(1,2**25+1):
    if N % i == 0:
        print(i) # q = 23520857

once obtained q, we have

p = N/q = 141728564220215689105745310666761712438508810180329898864435481120368603802944433535439870033233448775648620641750653586896162186017744701345428383181658483867762748650405587002562099473480910200825070136353056453764908432415631471548522147066421239360596574292417840898610873956701534267841521331362184363411

Then we look for the second part of the challenge

t1 = (k * inverse(m + r1, p)) % p
t2 = (k * inverse(m + r2, p)) % p

Where k, r1, r2 are known values. But instead of giving us t1 and t2 directly, we only get:

leak1 = t1 >> 244
leak2 = t2 >> 244

The leaks give us the high-order bits of t1 and t2. This creates a system we can solve using lattice techniques.

`t1 = leak1 × 2^244 + δ1 where δ1 < 2^244 (unknown small error)`

rearranging the above formula will give
`k = t1 × (m + r1) + λ1 × p (for some integer λ1)`

`k = leak1 × 2^244 × m + leak1 × 2^244 × r1 + δ1 × (m + r1) + λ1 × p`

Since δ1 is small and m is relatively small compared to p:

`m × leak1 × 2^244 - λ1 × p + leak1 × 2^244 × r1 ≈ k (ignoring small terms)`

where t2 is similar.

Then it is the time for LLL, like most of the other challenges.

Full solve script:

from Crypto.Util.number import long_to_bytes, inverse, isPrime

def solve():
    e = 65537
    N = 3333577291839009732612693330613476891341287017491683764014849337158389717338712200133085615150269196268856288361865352673921704626130772582853528604556994221890454520933132803888321775335519781063447756692130742361931522856942232406992357982482263472763363458621836220024977864980600979194500121897419553619426163227
    k = 9352039867057736323
    r1 = 10421792656200324147964684790160875926436411483496860422433732508593789212449544620816674407170998779863336939494663076247759140488927744939619406024905901
    r2 = 8806088830734144089522276896226392806947836111998696180055727048752624989402057411311728398322297424598954586424896296000606209022432442660527640463521679
    leak1 = 4266222222502644630611545246271868348722888987303187402827005454059765428769160822475080050046035916876078546634293907218937483241284454918367519709206766322037148585465519188582916280829212776096606923824120883699251868362915920299645
    leak2 = 1176921186497191878459783787148403806360469809421921990427675048480656171919274113895695842508460760829511824635106692634456334400022597605585661597793889066395539405395254174368285751236344600489419240628821864912762242188289636510706

    q = 23520857
    p = N // q
    L1 = leak1 << 244
    L2 = leak2 << 244

    # Lattice to find m, lambda1, lambda2
    # m*L1 - lambda1*p + L1*r1 = delta1
    # m*L2 - lambda2*p + L2*r2 = delta2
    # Weights
    W_delta = 1
    W_m = 2^244
    W_lambda = 2^244
    X = 2^1024 # dummy for target

    M = Matrix(ZZ, [
        [L1 * W_delta, L2 * W_delta, W_m, 0, 0, 0],
        [-p * W_delta, 0, 0, W_lambda, 0, 0],
        [0, -p * W_delta, 0, 0, W_lambda, 0],
        [L1 * r1 * W_delta, L2 * r2 * W_delta, 0, 0, 0, X]
    ])

    M_lll = M.LLL()
    print("LLL done.")
    
    for row in M_lll:
        if row[-1] == X or row[-1] == -X:
            if row[-1] == -X:
                row = -row
            # delta1, delta2, m, -lambda1, -lambda2, X
            m = abs(row[2]) // W_m
            if m == 0: continue
            print(f"Candidate m: {m}")
            # Verify
            t1 = (k * inverse_mod(int(m + r1), int(p))) % p
            if (t1 >> 244) == leak1:
                print(f"Found flag: {long_to_bytes(int(m))}")
                return

solve()

flag:

Candidate m: 56006392793415003917986111046017601616434940439235635749695606734099817013403284743481843113162926205
Found flag: b'flag{H4hAHhhHh4_c0pP3r_N07_v1OI3n7_3n0uGh}'

**Crypto/ LWECC**

By looking at the title we can already tell it is a combination of LWE (Learning With Errors) + ECC (Elliptic-curve cryptography).

task.sage

from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import choice
from hashlib import md5
from secret import flag

p = 1096126227998177188652856107362412783873814431647
E = EllipticCurve(GF(p), [0, 5])

s = [E.random_element() for _ in range(73)]
e = [E.random_element() for _ in "01"]
A = random_matrix(GF(p), 137, 73)
b = [(sum(i*j for i,j in zip(_,s)) + choice(e)).xy() for _ in A]


print("A =", A.list())
print("b =", b)
print("enc =", AES.new(key=md5(str(s).encode()).digest(), nonce=b"LWECC", mode=AES.MODE_CTR).encrypt(flag))

a short code, but tedious to solve.

**Given:**
- Elliptic curve $E: y^2 = x^3 + 5$ over $\mathbb{F}_p$
- Public matrix $A \in \mathbb{F}_p^{137 \times 73}$
- Public vector $B = [B_1, \ldots, B_{137}]$ where $B_i \in E(\mathbb{F}_p)$
- Encrypted flag using AES with key derived from secret $s$

**Encryption relation:**
$$B_i = \sum_{j=1}^{73} A_{ij} \cdot s_j + e_i$$

where:
- $s = [s_1, \ldots, s_{73}]$ is a secret vector of random points on $E$
- $e_i \in \{e_0, e_1\}$ is an error term (one of two random curve points)
- Operations are in the elliptic curve group $E(\mathbb{F}_p)$

When we look at the Elliptic curve, we can see that it is anomalous (trace-one) curve. Whats that mean? This mean the order of the curve is exactly equal to the field size p. which could be confirmed by

E.order()==p

So what does that mean even though we know it is an anomalous curve?

When $\#E(\mathbb{F}_p) = p$, we can construct an **isomorphism** between:
- The elliptic curve group $E(\mathbb{F}_p)$ (additive group of order $p$)
- The field $\mathbb{F}_p$ (additive group of order $p$)

A non-canonical group homomorphism inducing an isomorphism after normalization.

This isomorphism transforms elliptic curve problems into **linear algebra problems** over $\mathbb{F}_p$.

The isomorphism is constructed using **p-adic logarithms**. The map $\phi: E(\mathbb{F}_p) \to \mathbb{F}_p$ satisfies:
$$\phi(P + Q) = \phi(P) + \phi(Q)$$

This is a **group homomorphism**, and for anomalous curves, it's an isomorphism (bijective).

The **p-adic numbers** $\mathbb{Q}_p$ are a completion of $\mathbb{Q}$ with respect to the p-adic metric rather than the usual absolute value metric.

**p-adic valuation:** For $x \in \mathbb{Q}_p \setminus \{0\}$, write $x = p^n \cdot u$ where $u$ is a p-adic unit. Then $v_p(x) = n$ is the p-adic valuation.

**Key property:** Elements close to 0 in the p-adic metric are those divisible by high powers of $p$.

We lift the curve $E/\mathbb{F}_p$ to a curve $\tilde{E}/\mathbb{Q}_p$ with the same coefficients:
- Original: $E: y^2 = x^3 + 5$ over $\mathbb{F}_p$
- Lifted: $\tilde{E}: y^2 = x^3 + 5$ over $\mathbb{Q}_p$

For a point $P = (x, y) \in E(\mathbb{F}_p)$, we can lift it to $\tilde{P} = (x, y) \in \tilde{E}(\mathbb{Q}_p)$ where we view $x, y$ as elements of $\mathbb{Z}_p$ (the p-adic integers).

For an anomalous curve, the map is:
$$\phi(P) = \frac{-x(pP)}{y(pP)} \bmod p$$

where $pP$ denotes the $p$-multiple of the lifted point $\tilde{P}$ on $\tilde{E}(\mathbb{Q}_p)$.

The formal group law near the identity can be written in coordinates $(t)$ where $t = -x/y$ for points near $O$. The group law becomes:
$$t(P + Q) = t(P) + t(Q) + O(t^2)$$

For $pP$, where $P$ is a point of exact order $p$, the higher-order terms vanish modulo $p$, giving us an exact homomorphism.

**Attack Strategy**

Apply the isomorphism $\phi: E(\mathbb{F}_p) \to \mathbb{F}_p$ to the encryption equation:

$$B_i = \sum_{j=1}^{73} a_{ij} s_j + \epsilon_i$$

Apply $\phi$ to both sides:
$$\phi(B_i) = \phi\left(\sum_{j=1}^{73} a_{ij} s_j + \epsilon_i\right)$$

Since $\phi$ is a group homomorphism:
$$\phi(B_i) = \sum_{j=1}^{73} a_{ij} \phi(s_j) + \phi(\epsilon_i)$$

**Define:**
- $y_i = \phi(B_i)$
- $x_j = \phi(s_j)$
- $\eta_i = \phi(\epsilon_i) \in \{\eta_0, \eta_1\}$ where $\eta_k = \phi(e_k)$

We now have a **linear system over $\mathbb{F}_p$**:
$$y = Ax + \eta$$

where $\eta$ is a noise vector with each component in $\{\eta_0, \eta_1\}$.

We have:
- Unknown: $x \in \mathbb{F}_p^{73}$ (the secret)
- Unknown: $\eta_0, \eta_1 \in \mathbb{F}_p$ (the error values)
- Unknown: The choice of which $\eta_k$ is used for each position

**Key insight:** Since $A$ is $137 \times 73$, the system is **overdetermined**. The kernel of $A$ is non-trivial.

Compute the **left kernel** of $A$:
$$V \in \mathbb{F}_p^{k \times 137} \quad \text{where } VA = 0$$

Multiply both sides by $V$:
$$Vy = V(Ax + \eta) = 0 + V\eta = V\eta$$

The unknown secret $x$ has been eliminated!

The error vector $\eta$ has a specific structure. Let $C \in \{0,1\}^{137}$ be the **error choice vector**:
$$C_i = \begin{cases} 0 & \text{if } \eta_i = \eta_0 \\ 1 & \text{if } \eta_i = \eta_1 \end{cases}$$

Then:
$$\eta = \eta_0 \mathbf{1} + (\eta_1 - \eta_0) C$$

where $\mathbf{1} = (1, 1, \ldots, 1)^T$.

Substituting:
$$V\eta = \eta_0 V\mathbf{1} + (\eta_1 - \eta_0) VC$$

**Define:**
- $\gamma = Vy$ (known)
- $u = V\mathbf{1}$ (known)
- $W = V$ (known matrix)

We get:
$$\gamma = \eta_0 u + (\eta_1 - \eta_0) WC$$

We still have two unknown scalars $\eta_0, \eta_1$. To eliminate them, we project orthogonally to both $u$ and $\gamma$.

Consider the $2 \times k$ matrix:
$$M = \begin{bmatrix} \gamma^T \\ u^T \end{bmatrix}$$

Find its left kernel (a subspace of dimension $k-2$):
$$P \in \mathbb{F}_p^{(k-2) \times k} \quad \text{where } PM = 0$$

This means $P\gamma = 0$ and $Pu = 0$.

Multiply our equation by $P$:
$$P\gamma = \eta_0 Pu + (\eta_1 - \eta_0) PWC$$
$$0 = 0 + (\eta_1 - \eta_0) PWC$$

Since generically $\eta_1 \neq \eta_0$, we have:
$$PWC = 0 \pmod{p}$$

We now have a system:
$$MC = 0 \pmod{p}$$

where:
- $M = PW$ is a known $(k-2) \times 137$ matrix over $\mathbb{F}_p$
- $C \in \{0,1\}^{137}$ is unknown
- The equation holds modulo $p$

This is a **hidden subset sum problem** or **modular knapsack**.

**Lattice formulation:**

Build a lattice basis:
$$L = \begin{bmatrix} I_{137} & M^T \cdot s \\ 0 & p \cdot s \cdot I_{k-2} \end{bmatrix}$$

where $s$ is a scaling factor (typically $s = p$ or $s = 1$).

A short vector in this lattice corresponds to a solution $C$:
- First 137 coordinates: the binary vector $C$
- Last $k-2$ coordinates: should be $\approx 0$ (due to the constraint $MC \equiv 0$)

**LLL reduction** finds short vectors. The shortest vector often has:
- Binary entries in the first 137 positions
- Small/zero entries in the last $k-2$ positions

(lol, so it is LLL again)

Once we have $C$:

1. **Recover $\eta_0, \eta_1$:** Use two linearly independent equations from $\gamma = \eta_0 u + (\eta_1 - \eta_0) WC$

2. **Reconstruct $\eta$:** Build the full error vector
$$\eta_i = \begin{cases} \eta_0 & \text{if } C_i = 0 \\ \eta_1 & \text{if } C_i = 1 \end{cases}$$

3. **Solve for $x$:** From $y = Ax + \eta$, we get
$$Ax = y - \eta$$
Solve this linear system (possible since we have more equations than unknowns)

4. **Invert the logarithm map:** We have $x_j = \phi(s_j)$. To recover $s_j$:
- Find a generator $G \in E(\mathbb{F}_p)$ with $\phi(G) \neq 0$
- Compute $k_j = x_j / \phi(G)$
- Then $s_j = k_j \cdot G$

5. **Decrypt:** Compute `key = md5(str(s))` and decrypt the flag

full solve script:

import ast
import re
from sage.all import *
from hashlib import md5
from Crypto.Cipher import AES

def parse_output(filename):
    with open(filename, 'r') as f:
        content = f.read()
    a_match = re.search(r'A = (\[.*?\])', content, re.DOTALL)
    A_list = ast.literal_eval(a_match.group(1))
    b_match = re.search(r'b = (\[.*?\])', content, re.DOTALL)
    b_list = ast.literal_eval(b_match.group(1))
    enc_match = re.search(r'enc = (b[\'"].*?[\'"])', content)
    if not enc_match:
         enc_match = re.search(r'enc = (.*)', content)
    enc_val = eval(enc_match.group(1))
    return A_list, b_list, enc_val

def find_smart_log_func(E):
    p = E.base_ring().order()
    Q = Qp(p, 20)
    base_invs = [ZZ(x) for x in E.a_invariants()]
    
    for diff in [p, 2*p, 3*p]:
        invs = list(base_invs)
        invs[3] += diff 
        print(f"Trying perturbation a4 += {diff}")
        try:
            Eq = EllipticCurve(Q, invs)
        except:
            continue
        def log_candidate(P):
            if P == E(0): return 0
            x_P = ZZ(P.xy()[0])
            y_P = ZZ(P.xy()[1])
            try:
                P_lift = Eq.lift_x(x_P, all=True)[0]
            except:
                return None
            if (P_lift.xy()[1] - y_P).valuation() < 1:
                P_lift = -P_lift
            R = p * P_lift
            if R == Eq(0):
                return None
            x_R, y_R = R.xy()
            val = -x_R / y_R
            v = val.valuation()
            if v < 1: return None
            if v >= 2:
                res = val / p**2
            else:
                res = val / p
            return GF(p)(res.residue())

        P1 = E.random_element()
        P2 = E.random_element()
        P3 = P1 + P2
        l1 = log_candidate(P1)
        l2 = log_candidate(P2)
        l3 = log_candidate(P3)
        if l1 is None or l2 is None or l3 is None: continue
        if l1 == 0 and l2 == 0: continue
        if (l1 + l2 - l3) == 0:
            print(f"Found working Smart Log with perturbation {diff}")
            return log_candidate
            
    raise Exception("Could not find working Smart Log map")

def solve():
    print("Parsing data...")
    A_flat, b_coords, enc = parse_output("output.txt")
    p = 1096126227998177188652856107362412783873814431647
    E = EllipticCurve(GF(p), [0, 5])
    rows = 137
    cols = 73
    A_matrix = Matrix(GF(p), rows, cols, A_flat)
    B_points = [E(x, y) for x, y in b_coords]
    
    print("Finding Smart Log function...")
    try:
        smart_log = find_smart_log_func(E)
    except Exception as e:
        print(e)
        return
    
    print("Computing logs...")
    y_vec_vals = []
    for i, P in enumerate(B_points):
        y_vec_vals.append(smart_log(P))
    y_vec = vector(GF(p), y_vec_vals)
    
    print("Computing kernel...")
    K = A_matrix.kernel()
    V = K.basis_matrix()
    
    gamma = V * y_vec
    u = V * vector(GF(p), [1]*rows)
    W = V
    
    M_proj = matrix([gamma, u]).transpose()
    P_mat = M_proj.kernel().basis_matrix()
    M_lat_base = P_mat * W 
    
    print("Building Lattice...")
    dim = 137 + M_lat_base.nrows()
    L = Matrix(ZZ, dim, dim)
    
    # Use scaling
    scale = p # Large scaling factor
    
    for i in range(137):
        L[i, i] = 1
        col = M_lat_base.column(i)
        for j in range(M_lat_base.nrows()):
            L[i, 137+j] = int(col[j]) * scale 
            
    # Modulus part
    for j in range(M_lat_base.nrows()):
        L[137+j, 137+j] = p * scale
        
    print("Running LLL...")
    L_red = L.LLL()
    
    C_found = None
    for row in L_red:
        # Check if last part is 0 (since scaled, it should be exactly 0)
        is_zero = True
        for k in range(137, dim):
            if row[k] != 0:
                is_zero = False
                break
        if is_zero:
            cand = row[:137]
            if all(x in [0, 1] for x in cand) and sum(cand) > 0:
                print("Found binary C!")
                C_found = vector(GF(p), cand)
                break
            elif all(x in [0, -1] for x in cand) and sum(cand) < 0:
                print("Found negative binary C!")
                C_found = vector(GF(p), [-x for x in cand])
                break

    if C_found is None:
        print("C not found via LLL.")
        # Debug output
        for i in range(5):
             print(f"Row {i} norm: {float(L_red[i].norm())}")
        return

    v1 = u
    v2 = W * C_found
    
    eta0 = 0
    delta_eta = 0
    solved = False
    for i in range(64):
        for j in range(i+1, 64):
            mat = matrix(GF(p), [[v1[i], v2[i]], [v1[j], v2[j]]])
            if mat.det() != 0:
                rhs = vector(GF(p), [gamma[i], gamma[j]])
                sol = mat.solve_right(rhs)
                eta0 = sol[0]
                delta_eta = sol[1]
                solved = True
                break
        if solved: break
        
    eta1 = eta0 + delta_eta
    print(f"eta0: {eta0}")
    print(f"eta1: {eta1}")
    
    E_vals = []
    for k in range(137):
        if C_found[k] == 0:
            E_vals.append(eta0)
        else:
            E_vals.append(eta1)
    E_vec = vector(GF(p), E_vals)
    
    rhs = y_vec - E_vec
    s_log = A_matrix.solve_right(rhs)
    
    print("Recovered s_log.")
    
    while True:
        G = E.random_element()
        lg = smart_log(G)
        if lg != 0:
            break
            
    inv_lg = 1/lg
    s_points = []
    for val in s_log:
        k = val * inv_lg
        k_int = int(k)
        s_points.append(k_int * G)
        
    key = md5(str(s_points).encode()).digest()
    cipher = AES.new(key=key, nonce=b"LWECC", mode=AES.MODE_CTR)
    try:
        flag = cipher.decrypt(enc)
        print("Flag:", flag)
    except:
        print("Decryption failed")

solve()

The script take around a few minutes to run

(base) sage solver.sage
Parsing data...
Finding Smart Log function...
Trying perturbation a4 += 1096126227998177188652856107362412783873814431647
Found working Smart Log with perturbation 1096126227998177188652856107362412783873814431647
Computing logs...
Computing kernel...
Building Lattice...
Running LLL...
Found negative binary C!
eta0: 909150034385859605294145899352651824206394192717
eta1: 1015467823800812299882714936635122995816109565601
Recovered s_log.
Flag: b'flag{deb0b9c915b92dea9db131becdf306}'