These Walls::Codegate CTF Qual 2025

(Updated: )

Time: 2025.03.29 (online)

Time to learn more about elliptic curve :D

These Walls (5 solves)

https://github.com/soon-haari/my-ctf-challenges/tree/main/2025-codegate/crypto-thesewalls

Our target is to solve DDH/DLP on ECC to get the key.

Curves Recovery

First we need to recover the elliptic curve from the given points. This can be easily done by groebner_basis on ZZ.

1
2
3
4
5
6
7
8
Ps = [ast.literal_eval(P) for P in open("output.txt", "r").readlines()[2:]]

R, (a, b) = PolynomialRing(ZZ, 'a,b').objgens()
Fs = [x**3 + a*x + b - y**2 for x, y in dat]
B = Ideal(Fs).groebner_basis()
n = B[-1]
a = ZZ(n-B[0].univariate_polynomial()(0))
b = ZZ(n-B[1].univariate_polynomial()(0))
1
2
3
n = 102426836944425277819174256940128868455066517869185115488781035394164877927042198980921397582250905694209313963017944880679709788694772632564808279062807699845761214703586660326307989151472431126842544189892251409194318824261554131269698538462346988910692541060196190265045309883144365795763912362099350625483
a = 59988839927984767712262022881015186528306823080680093817066551387449092966635391654583736371714324230765899668876056205191762535690049456590296016977519955444196107647233071737264095096436949854658419817766417617008402215963718256820349403830936535830427821814691174887502426870436662513573210000832221322398
b = 101967710743792389969422216712450509569034697830818344524896876130478391402643388132308880397086156977788425616725940825720775848656512466204212492162471675713660761367404158291366066068856768564375952666036454337938403204290723496566781748665353311583138442143621327486984669015180894834194757115816809502955

But this is not enough, since we have a composite $n$ here.

For a curve $E_p$ with order $o_p$, we have $o_p \cdot P = (0, 0)$. When it comes to $E_n$ where $p | n$, we have $o_p \cdot P = (k_x \cdot p, k_y \cdot p)$. Multiplication based on this may fail since there’s no inverse element for $k \cdot p$, and we can extract $p$ through the error message.

In short, I just kept run this and get new prime factors with gcd.

1
2
3
4
5
6
7
8
9
10
11
12
13
o = 118549579796788515994414649236369265269780996946642393375504713268996543836492572997532134962413661837052222678148616587175464294656866212083879163757595198637277720148049394221272652120067946542481202345536577647854319626518830885330021003068475187962796231844540355486949322214342559093662111580693859480
ps = [(2, 3), (3, 2), (5, 1), (11, 1), (19, 1), (31, 1), (53, 1), (349, 1), (3517, 1), (673063, 1), (2745521, 1), (55050007, 1), (377214161, 1), (30174718114417, 1), (139792886025540383, 1), (388450213394528490535805887, 1), (2717597692908121319788497985451, 2), (3692983360407686094702508373879, 1), (1405747484361299393418580978953630281779614293727193, 1), (324094280281900209908870811008292068290746348301400744740589987, 1)]
assert o == prod(pi**i for pi, i in ps)

E = EllipticCurve(Zmod(n), [a, b])
P = E(Ps[0])
for pi, _ in ps:
    oi = o // pi
    try:
        Q = oi*P
    except Exception as e:
        print(pi, e)

1
2
3
4
5
6

p0 = 3562548874780288796769030192977
p1 = 3692983360407686094702508373879
p2 = 324094280281900209908870811008292068290746348301400744740589987
p3 = 2717597692908121319788497985451
assert n == p0 * p1**2 * p2**2 * p3**3

Now we need to solve DDH on each curve $E_{p_i}$.

Part1: Singular Curve

Why are singular “elliptic” curve bad for crypto

For an elliptic curve $E: y^2 = x^3 + a \cdot x + b \pmod{p}$, the curve is singular if $\Delta = 4 a^3 + 27 b^2 = 0 \pmod{p}$, which implies that $f(x) = x^3 + a \cdot x + b \pmod{p}$ has a double/triple root.

It turns out that we have a singular curve $E_{p_0}$. At this point we can transfrom the original DLP into a much easier one.

  1. $f(x) = (x - \alpha)^3$: There are exacly $p$ non-singular points, and we can map them to the addictive group of $GF_p$ through $(x, y) \rightarrow \frac{x - \alpha}{y}$.
  2. $f(x) = (x - \alpha)^2 \cdot (x - \beta)$: There are $p-1$ or $p+1$ points, and we can map them to the multiplicative group of $GF_{p^2}$ (with $p^2-1 = (p-1)\cdot(p+1)$ elements) through $(x, y) \rightarrow \frac{y+\sqrt{\alpha - \beta} \cdot (x - \alpha)}{y-\sqrt{\alpha - \beta} \cdot (x - \alpha)}$.
  3. $f(x) = (x - \alpha) \cdot (x - \beta) \cdot (x - \gamma)$: Nah this is impossible.

In case 2, it’s quite clear that we extend the group with $x^2 = (\alpha - \beta) \pmod{p}$. If there exist the corresponding square roots, we just map the original group to $GF_p$.

We have $ p_0+1 = 2 \cdot 7841 \cdot 240017 \cdot 1190977577 \cdot 79471936121$, and it takes less than 10s to solve one DLP on $GF_{p^2}$. Actually we can just solve one or two of them, and check DDH with the rest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def singular_attack(p, a, b, P, Q):
    Px, Py = P
    Qx, Qy = Q

    x = GF(p)["x"].gen()
    f = x**3 + a*x + b
    roots = f.roots()

    if len(roots) == 1:
        alpha = roots[0][0]
        u = (Px - alpha) / Py
        v = (Qx - alpha) / Qy
        s = v / u
        return int(s)

    if len(roots) == 2:
        if roots[0][1] == 2:
            alpha = roots[0][0]
            beta = roots[1][0]
        elif roots[1][1] == 2:
            alpha = roots[1][0]
            beta = roots[0][0]
        
        t = (alpha - beta).sqrt()
        u = (Py + t * (Px - alpha)) / (Py - t * (Px - alpha))
        v = (Qy + t * (Qx - alpha)) / (Qy - t * (Qx - alpha))
        s = v.log(u)
        return int(s)
ans0 = [singular_attack(p0, a, b, Ps[i], Ps[i+1]) for i in tqdm.trange(len(Ps)-1)]
1
2
s0 = 1688818121111580066310934554129
ans0 = [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Part2: p-adic Field

Sth old but cool.

For $(p_1, p_2, p_3)$, we need to solve DLP/DDH on $E_{p^k}$. It turns out that the order is $o_p \cdot p^{k-1}$ where $o_p$ is the order of $E_p$. With p-adic field, we can just solve DLP $\pmod{p^{k-1}}$. This is similar to solve DLP $y = g^x \pmod{p^k}$.

Really fast.

1
2
3
4
5
6
7
8
9
10
11
def padic_attack(p, k, a, b, P, Q):
    E = EllipticCurve(Zmod(p**k), [a, b])
    ordp = E.change_ring(GF(p)).order()

    P = ordp*E.change_ring(Qp(p, k))(P)
    Q = ordp*E.change_ring(Qp(p, k))(Q)
    s = Zmod(p**(k-1))((P[0] / P[1]) / (Q[0] / Q[1]))
    return int(s)
ans1 = [padic_attack(p1, 2, a, b, Ps[i], Ps[i+1]) for i in tqdm.trange(len(Ps)-1)]
ans2 = [padic_attack(p2, 2, a, b, Ps[i], Ps[i+1]) for i in tqdm.trange(len(Ps)-1)]
ans3 = [padic_attack(p3, 3, a, b, Ps[i], Ps[i+1]) for i in tqdm.trange(len(Ps)-1)]
1
2
3
4
5
6
7
8
s1 = 161442084316875579136566655050
ans1 = [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

s2 = 124693667754253363360592289430893581474062041013016987009502208
ans2 = [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

s3 = 5975425618449852857611277904948728242283739833255577381465035
ans3 = [0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Part3: MOV

Now we just need to solve DLP/DDH on $E_p$ for $(p_1, p_2, p_3)$. These curves all satisfy $o_p = p+1$, so the embedding degree $k = 2$. This time we can try MOV attack which maps curve points to elements on $GF_{p^k}$ with pairing tech, solving an easier DLP.

It is worth to notice that we can solve DLP more easily only because $GF_{p^k}$ has better structure than $E_p$. The order of the elements on $GF_{p^k}$ is $o_p$ and it’s still hard to solve DLP if $o_p$ has large factors. In this challenge, we can solve completely DLP on $p_1$ since $p_1 + 1 = 2^3 \cdot 3^2 \cdot 5 \cdot 31 \cdot 3517 \cdot 673063 \cdot 139792886025540383$.

It’s said to be possible to solve such DLP on $GF_p^2$ with cado-nfs.

It takes about 20min to solve one, so this time we have to solve one or two answers and then check DDH on the rest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def mov_attack(p, a, b, P, Q):
    E = EllipticCurve(GF(p), [a, b])
    ord = E.order()
    k = 1
    while pow(p, k, ord) != 1:
        k += 1
    
    Ek = E.base_extend(GF(p**k))
    G = Ek.gens()[0]
    P = Ek(P).weil_pairing(G, ord)
    Q = Ek(Q).weil_pairing(G, ord)
    s = Q.log(P)
    return int(s)
ans1 = [mov_attack(p1, a, b, Ps[i], Ps[i+1]) for i in tqdm.trange(len(Ps)-1)]
1
2
s1 = 860437940168965817900625942259
ans1 = [1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0]

Part4: Distortion Map

Check this.

Since it’s hard to completely solve DLP for $(p_2, p_3)$, we need to find some luck on DDH itself. An apparent idea is to solve DDH with pairing. For instance, we can check whether $e(P_i, P_{j+1}) = e(P_j, P_{i+1})$ holds.

But this doesn’t work, cuz you will find $e(P_i, P_{i+1}) = 1$ for all $i$. For weil_pairing, we shall take two points from different subgroups to compute bilinear pairing, otherwise it will just degenerate to 1. I’m not familiar with both weil_pairing and tate_pairing but neither of them worked.

Here, both curves on $(p_2, p_3)$ are supersingular since $o_p = p+1$. There exist several special supersingular curves on which we can do something cool. For this challenge, here is what we need:

  • Type A Curve: $y^2 = x^3 + a \cdot x$
  • Type B Curve: $y^2 = x^3 + b$

One can find a distrotion map $\Phi: E_p \rightarrow E_{p^2}$ on these curves, and construct a nondegenerate bilinear map $e(P, Q) = f(P, \Phi(Q))$ (where $f$ is the original weil_pairing). You can check for more details in the materials above.

Here we can use both of them to solve DDH on $(p_2, p_3)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def type_a_ddh_attack(p, a, b, P0, Q0, Pi, Qi):
    def distortion_map(P):
        Px, Py = P.xy()
        z = Fp2.gens()[0]
        return E(-Px, z*Py)

    x = var('x')
    Fp2 = GF(p2**2, 'z', modulus=x**2+1)
    E = EllipticCurve(Fp2, [a, b])
    e0 = E(P0).weil_pairing(distortion_map(E(Qi)), p+1)
    e1 = E(Pi).weil_pairing(distortion_map(E(Q0)), p+1)
    return int(e0 == e1)

def type_b_ddh_attack(p, a, b, P0, Q0, Pi, Qi):
    def distortion_map(P):
        Px, Py = P.xy()
        z = Fp2(1).nth_root(3)
        return E(z*Px, Py)

    Fp2 = GF(p**2)
    E = EllipticCurve(Fp2, [a, b])
    e0 = E(P0).weil_pairing(distortion_map(E(Qi)), p+1)
    e1 = E(Pi).weil_pairing(distortion_map(E(Q0)), p+1)
    return int(e0 == e1)

ans2 = [type_a_ddh_attack(p2, a, b, Ps[0], Ps[1], Ps[i], Ps[i+1]) for i in tqdm.trange(len(Ps) - 1)]
ans3 = [type_b_ddh_attack(p3, a, b, Ps[0], Ps[1], Ps[i], Ps[i+1]) for i in tqdm.trange(len(Ps) - 1)]
1
2
ans2 = [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1]
ans3 = [1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1]

Get Flag

Finally.

We need to combine the DDH answers from all subgroups. For any position i, if one 0 appears then the answer is 0. We may mischeck some 0s to 1s in certain subgroups, but the opposite condition will never occur. For the first position, just guess it out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ans = [
    [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1],
]
ans = [prod([ans[j][i] for j in range(len(ans))]) for i in range(255)]

from Crypto.Cipher import AES
from Crypto.Util.number import *

key = int(''.join(map(str, [1] + ans))[::-1], 2)
key = long_to_bytes(key, 32)
enc = '5ade26f7b0461ec24e2f6a328be00be8e49e7707b5533c8da3b42bbb41a2aeb4ec8a63c2d625f891b6cce1c6842bda77a31957351aa90525385df3d80431db3c9c73183207267adccf016cbda326cf872c365903d63e20fab0f31bb2ef19b31ea151db097514b49f3fdbc05b8a26ae02'
flag = AES.new(key, AES.MODE_CTR, nonce=bytes(12)).decrypt(bytes.fromhex(enc))
print(flag)
# codegate2025{If_these_weils_could_talk_(I_can_feel_your_reign_when_it_cries_supersingular_curves_inside_of_you)}

Special thanks to @糖醋小鸡块, who helped untangle many of the mathematical knots for me.