This time I participated in this event with Balsn and solved some Crypto-related problems. Here are the things I learned.

e2Is0#

from string import ascii_letters
from sympy import sqrt
import random
import signal
import os
FLAG = os.environ.get('FLAG', 'n1ctf{XXXXFAKE_FLAGXXXX}')    
    
def banner():
    print("""
░░░░░░░ ░░░░░░  ░░ ░░░░░░░  ░░░░░░  
▒▒           ▒▒ ▒▒ ▒▒      ▒▒    ▒▒ 
▒▒▒▒▒    ▒▒▒▒▒  ▒▒ ▒▒▒▒▒▒▒ ▒▒    ▒▒ 
▓▓      ▓▓      ▓▓      ▓▓ ▓▓    ▓▓ 
███████ ███████ ██ ███████  ██████  
    """)

def curve_init():
    p = random_prime(2^256)
    F.<i> = GF(p^2, modulus = x**2 + 1)
    R.<t> = PolynomialRing(GF(p))
    guess = ''.join(random.choices(ascii_letters, k=20))
    RR = RealField(256)
    num = RR(int(guess.encode().hex(),16))
    j = F(str(sqrt(num)).split('.')[1])
    E = EllipticCurve(j=j)
    P = E(0).division_points(3)
    P.remove(E(0))
    phi = E.isogeny(random.choice(P))
    E2 = phi.codomain()
    j2 = E2.j_invariant()
    assert list(R(j2))[1] != 0
    return E2, p, guess

def leak(E, p):
    F = Zmod(p^2)
    R.<t> = PolynomialRing(GF(p))
    r = random.getrandbits(20)
    x = F(input("your magic number?\n$ "))^r - 1
    j_ = E.j_invariant()^x
    print(list(R(j_))[0])

def main():
    signal.alarm(120)
    banner()
    para = None
    print("Curve Initialization...")
    while not para:
        try:
            para = curve_init()
        except:
            continue
    E, p, guess = para
    print(f"einfo: {E.base_ring()}")
    leak(E, p)
    if input("guess > ").strip('\n') == guess:
        print(f"Congratz, your flag: {FLAG}")
    else:
        print("Game over!")
        

if __name__ == "__main__":
    try:
        main()
    except:
        print("error!")

First, generate a prime number $p$, and a string of length 20 from ascii_letters as guess, then take the fractional part of its sqrt as an integer $j$. Next, generate a curve $E$ with j-invariant $j$ over $\mathbb{F}_p$, then find $E_2$ among its 3-isogeny neighbors, and output the j-invariant of $E_2$ which must be in the form $x+yi$ where $y \neq 0$.

Then you are given $p$, and an oracle where you can input a number $t$, and the server calculates $x=t^r-1 \mod{p^2}$ and gives you the constant term of $j(E_2)^x$. The goal is to obtain guess.

A crucial point to solve this problem is to know about modular polynomials. For any two elliptic curves $E_1$ and $E_2$ that have an n-degree isogeny, $\Phi_n(j(E_1), j(E_2))=0$. The formula for $\Phi_n(x,y)$ can be found here.

Modular polynomials are significant here because j-invariants over $\mathbb{F}_{p^2}$ are in the form $x+yi$, meaning $j(E_1)=a+bi$ and $j(E_2)=c+di$, where $a,b,c,d \in \mathbb{F}_p$. Substituting them into $\Phi_n(x,y)=0$ and separating the real and imaginary parts, $\operatorname{Re}(\Phi_n(j_(E_1),j_(E_2)))=0$ and $\operatorname{Im}(\Phi_n(j_(E_1),j_(E_2)))=0$, gives two equations. This tells us that if any two of $a,b,c,d$ are known, the other two can be obtained by solving the simultaneous equations. This method is one way to solve the Isogeny Hidden Number Problem (refer to Chapter 8 of this paper).

Back to the problem, we know $j(E)=a+bi$ with $b=0$, and we know nothing about $j(E_2)=c+di$. So, it is clear that we need to use the leak oracle to find some relationships. My initial thought was to directly leak $c$, which requires $x=1$, meaning $t^r \equiv 2 \pmod{p^2}$, but I couldn't figure out how to achieve this with a random $r$. Later, I set $t=-1$, so when $r$ is odd, $x=p^2-2$, and in $\mathbb{F}_{p^2}$, taking the $p^2-2$ power of a number is equivalent to finding its inverse.

Thus, if I set $j(E_2)^{-1}=e+fi$, where the leak returns $e$, then $(c+di)(e+fi)=1$, and separating the real and imaginary parts gives two equations over $\mathbb{F}_p$. So, there are six unknowns $a,b,c,d,e,f$, and we can form two equations from the modular polynomial and the inverse part, and four equations by separating coefficients. Knowing $b=0$ and $e=\text{leak}$ means this system has a unique solution. Running Groebner basis might be slow, so I manually used resultant to get $f(a)=0$, and solving for $a$ gives the initial $j$.

After obtaining $j$, which is the fractional part of $\sqrt{n}-\lfloor \sqrt{n} \rfloor$, we need to find $n$. I transformed $j$ to get $r=\sqrt{n}-\lfloor \sqrt{n} \rfloor$, then set $k=\lfloor \sqrt{n} \rfloor$ and squared both sides:

Noting that $m=n-k^2$ is a positive integer less than $2k+1$, we have $m-2kr-r^2=0$. Estimating the size of $k,m$ and using LLL, we can find $m,k$, and then $n=m+k^2$.

Proof that $0 \leq m<2k+1$: $k=\lfloor \sqrt{n} \rfloor$ means $k^2 \leq n < (k+1)^2$, so $0 \leq n-k^2 < 2k+1$.

import ast

# https://math.mit.edu/~drew/ClassicalModPolys.html
mp3_def_str = """[1,0] 1855425871872000000000
[1,1] -770845966336000000
[2,0] 452984832000000
[2,1] 8900222976000
[2,2] 2587918086
[3,0] 36864000
[3,1] -1069956
[3,2] 2232
[3,3] -1
[4,0] 1"""
mp3_def = [
    [ast.literal_eval(x) for x in line.split(" ")] for line in mp3_def_str.split("\n")
]
mp_term = (
    lambda e, coef: lambda x, y: coef * x ** e[0] * y ** e[1]
    + coef * x ** e[1] * y ** e[0]
    if e[0] != e[1]
    else coef * x ** e[0] * y ** e[1]
)
mp = lambda mp_def: lambda x, y: sum([mp_term(*term)(x, y) for term in mp_def])
mp3 = mp(mp3_def)


from pwn import process, remote
import subprocess


def connect():
    # io = process(["sage", "task.sage"])
    # return io

    io = remote("121.41.9.20", int(6668))
    io.recvuntil(b") solve ")
    pow_token = io.recvlineS().strip()
    input(f"continue run pow with {pow_token}?")
    ret = subprocess.check_output(
        "python3 <(curl -sSL https://goo.gle/kctf-pow) solve " + pow_token,
        shell=True,
        timeout=20,
    )
    print(ret)
    io.sendline(ret)
    return io


io = connect()
io.recvuntil(b"of size ")
p = ZZ(io.recvuntil(b"^2", drop=True).decode())
io.sendlineafter(b"$ ", b"-1")  # (-1)^r-1=p^2-2 (mod p^2) if r is odd
leak = ZZ(io.recvline().decode())
print(leak)

"""
j1=A+0i  # two unk
j2=C+Di  # two unk
phi(j1,j2)=0  # two eq
B=0  # one eq
(C+Di)*(leak+Fi)=1  # one unk, two eq
"""

x = var("x")
Fp = GF(p)
Fp2 = GF(p ^ 2, "i", modulus=x**2 + 1)
i = Fp2.gen()
aa, cc, dd, ff = Fp2["aa,cc,dd,ff"].gens()
PR_Fp = Fp["aa,cc,dd,ff"]
f = mp3(aa + 0 * i, cc + dd * i)
f_real = PR_Fp(f.map_coefficients(lambda c: c.polynomial()[0]))
f_imag = PR_Fp(f.map_coefficients(lambda c: c.polynomial()[1]))
g = (cc + dd * i) * (leak + ff * i) - 1
g_real = PR_Fp(g.map_coefficients(lambda c: c.polynomial()[0]))
g_imag = PR_Fp(g.map_coefficients(lambda c: c.polynomial()[1]))
aa, cc, dd, ff = PR_Fp.gens()
f1 = f_real.sylvester_matrix(f_imag, dd).det()  # function of a, c
f2 = f_real.sylvester_matrix(g_real, dd).det()  # function of a, c, f
f3 = g_real.sylvester_matrix(g_imag, dd).det()  # function of c, f
f4 = f2.sylvester_matrix(f3, ff).det()  # function of a, c
g = f1.sylvester_matrix(f4, cc).det().univariate_polynomial()  # function of a
for r, _ in g.roots():
    print(r, ZZ(r).bit_length())
    if r > 0 and ZZ(r).bit_length() < 200:
        target_j = ZZ(r)
print("j", target_j)


def recover(r):
    # r = sqrt(n) - floor(sqrt(n))
    # set k = floor(sqrt(n)) is integer
    # (r+k)^2 = r^2 + 2rk + k^2 = n
    # n - 2rk - k^2 - r^2 = 0
    # set m = n - k^2, which is approximately equal to k
    error = -4.22494828768973e-29  # the error by experimenting
    k_ap = 2 ** (20 * 8 // 2)  # approximate k

    B = matrix(
        QQ, [[1, 1, 0, 0], [-2 * QQ(r), 0, 1, 0], [-QQ(r) ** 2, 0, 0, 1]]  # m  # k  # 1
    )
    bounds = [QQ(abs(error)), k_ap, k_ap, 1]
    Q = diagonal_matrix([2**512 // b for b in bounds])
    B *= Q
    T, mul = B._clear_denom()
    T = T.LLL()
    B = T.change_ring(QQ) / mul
    B /= Q
    for row in B:
        if row[-1] < 0:
            row = -row
        if row[-1] == 1:
            n_sub_k2 = row[1]
            k = row[-2]
            return k**2 + n_sub_k2


R = RealField(256)
r = R(target_j) / 10 ** len(str(target_j))  # take the fractional part of sqrt(n)
print(r)
n = recover(r)
print(n)
guess = int(n).to_bytes(20, "big").decode()
print(guess)
io.sendline(guess.encode())
io.interactive()
# n1ctf{0h_you_c4n_get_j_fr0m_th3_h4lf@#$%}

e2D1p#

from Crypto.Util.number import *
import os
FLAG = os.environ.get('FLAG', b'n1ctf{XXXXFAKE_FLAGXXXX}')
assert FLAG[:6] == b'n1ctf{' and FLAG[-1:] == b'}'
FLAG = FLAG[6:-1]


def keygen(nbits):
    while True:
        q = getPrime(nbits)
        if isPrime(2*q+1):
            if pow(0x10001, q, 2*q+1) == 1:
                return 2*q+1

def encrypt(key, message, mask):
    return pow(0x10001, message^mask, key)


p = keygen(512)
flag = bytes_to_long(FLAG)
messages = [getRandomNBitInteger(flag.bit_length()) for i in range(200)]
enc = [encrypt(p, message, flag) for message in messages]

print(f'message = {messages}')
print(f'enc = {enc}')

In short, there is an unknown $p$, and let $f$ be the $k$ bits flag, then generate $n$ $k$ bits $m_i$ and calculate $c_i \equiv e^{m_i \oplus f} \pmod{p}$, where $f$ is the flag and $e=\text{0x10001}$.

The first thing that came to my mind was TetCTF 2022 - Fault (by @hellman), because the part about recovering the modulus is almost the same. Rewriting that method using the notation in this problem:

To find $p$, we need to find some small enough $a_i$ such that:

Then, separating the positive and negative parts of $a_i$ and multiplying them gives $x,y$, so $x-y \equiv 0 \pmod{p}$, and gcd gives $p$. The problem is how to find $a_i$. To do gcd, we need multiple sets of $a_i$.

Expanding the above:

Taking the log of the exponent part:

So, we need $\sum_i a_i m_{i,j} = 0$ and $\sum_i a_i = 0$. To solve this, @hellman constructed a matrix:

Each row contains the bits of $m_i$, and the extra $1$ at the end ensures $\sum_i a_i = 0$.

We need to find $a_i$ in $\ker{A^T}$ (left kernel) as short vectors, which can be done using LLL.

This concept is similar to my previous challenge No modulus and last year's N1CTF ezdlp and HITCON CTF 2022 - Secret.

After finding $p$, we need to find the flag. Referring to @hellman's writeup, we know there is a way to find $e^f$, but $p-1=2q$, making DLP infeasible. My method is to observe:

The exponent part has $(-1)^{f_i}$, so we can find $f$ bit by bit. In this problem, I found that solving $sA=(0,0,\cdots,0,0,0,1)$ has no solution, meaning there is no $s$ such that $\prod_i c_i^{s_i} = e^f$. However, $sA=(0,0,\cdots,0,0,1,1)$ has a solution:

Here, $f_{k-1}$ is the lsb of $f$, known to be $1$ since $f$ is $k$ bits. To find the $(k-2)$th bit of the flag, solve $s'A=(0,0,\cdots,0,1,1,1)$ to get:

So, $x=yz$ means $f_{k-2}=0$, and $x=y/z$ means $f_{k-2}=1$. Repeating this for other bits, we can find $f$ bit by bit.

from sage.all import *
from Crypto.Util.number import *
from subprocess import check_output
from re import findall
from output import message, enc  # ln -s output.txt output.py
from binteger import Bin


def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))


def clean(n):
    for p in sieve_base:
        while n % p == 0:
            n //= p
    return n


"""
c[i]=e^(flag xor msg[i]) % p
    =e^flag*prod((-1^flag[j])*(2^j)*msg[i][j])
    =a*prod(k[i][j]^e[i][j])
"""

# ref: https://affine.group/writeup/2022-01-TetCTF#fault
bl = 159
mat = matrix(
    ZZ,
    [
        Bin(e, bl).tuple[::-1] + (1,) for e, c in zip(message, enc)
    ],  # 1 for the base b = 0x10001^flag
)
L = mat.augment(identity_matrix(mat.nrows()))
L[:, : bl + 1] *= 2**32
L = flatter(L)
assert L[0][bl] == L[1][bl] == 0
xx = product([QQ(y) ** x for x, y in zip(L[0][bl + 1 :], enc)])
yy = product([QQ(y) ** x for x, y in zip(L[1][bl + 1 :], enc)])
p = clean(gcd(xx.numer() - xx.denom(), yy.numer() - yy.denom()))
print(p)
# p = 25070940894294854944213724808057610995878580501834029791436842569011975159898869595617649716256078890953233822913946718277574163417715224718477846001735447


def field_exp(el, e):
    a, b = e.numerator(), e.denominator()
    el **= a
    q = el.parent().characteristic() // 2
    d = inverse_mod(b, q)
    return el**d


F = GF(p)
sol = mat.solve_left(vector([0] * (bl - 1) + [1, 1]))  # pick a base that works
y = product([field_exp(F(y), z) for y, z in zip(enc, sol)])
# y = F(0x10001) ** flag * F(0x10001) ** ((-1) ** flagbits[bl - 1] * 2 ** (bl - 1))
# also, flagbits[bl - 1] = 1 is known
# so we can recover bits using `c[i]=e^flag*prod((-1^flag[j])*(2^j)*msg[i][j])`

recovered_bits = [0] * bl
recovered_bits[bl - 1] = 1
for i in reversed(range(bl - 1)):
    base = vector([0] * (bl - 1) + [1, 1])
    base[i] = 1
    sol = mat.solve_left(base)
    x = product([field_exp(F(y), z) for y, z in zip(enc, sol)])
    z = F(0x10001) ** (2**i)
    if x == y * z:
        recovered_bits[i] = 0
    else:
        recovered_bits[i] = 1
    flag = Bin(recovered_bits[::-1]).bytes
    print(flag)
# n1ctf{s0o0_ezzz_dLLLp%$#@!}

e20k#

#!/usr/bin/sage
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
import signal
import random
import os
FLAG = os.environ.get('FLAG', 'n1ctf{XXXXFAKE_FLAGXXXX}')

class ECPrng:
    def __init__(self):
        self.N = self.keygen()
        self.E = EllipticCurve(Zmod(self.N), [3, 7])
        self.bias = random.randint(1, 2^128)
        self.state = None
        print(f"N = {self.N}")
        
    def keygen(self):
        P = getPrime(256)
        while True:
            q = getPrime(256)
            if is_prime(2*q-1):
                Q = 2*q^2-q
                return P*Q
    
    def setState(self, x0, y0):
        self.state = self.E(x0, y0)
    
    def next(self):
        self.state = 4*self.state
        return int(self.state.xy()[0])+self.bias

def v2l(v):
    tp = []
    for item in v:
        tp.append(item.list())
    return tp

def Sample(eta, num, signal=0):
    if signal:
        random.seed(prng.next())
    s = []
    for _ in range(num):
        if random.random() < eta:
            s.append(1)
        else:
            s.append(0)
    return Rq(s)

class P:
    def __init__(self, A, s, t):
        self.A = A
        self.s = s
        self.t = t
        self.y = None
    
    def generateCommit(self, Verifier):
        self.y = vector(Rq, [Sample(0.3, N, 1) for _ in range(m)])
        w = self.A * self.y
        Verifier.w = w
        print(f"w = {w.list()}")
        
    def generateProof(self, Verifier, c):
        z = self.s*c + self.y
        print(f"z = {v2l(z)}")
        Verifier.verifyProof(z)

class V:
    def __init__(self, A, t):
        self.A = A
        self.t = t
        self.w = None
        self.c = None
        
    def challenge(self, Prover):
        self.c = Sample(0.3, N)
        print(f"c = {self.c.list()}")
        Prover.generateProof(self, self.c)
        
    def verifyProof(self, z):
        if self.A*z == self.t*self.c + self.w:
            return True
        return False

def Protocol(A, secret, t):
    prover = P(A, secret, t)
    verifier = V(A, t)
    prover.generateCommit(verifier)
    verifier.challenge(prover)

if __name__ == "__main__":
    try:
        signal.alarm(120)
        print("ECPRNG init ...")
        prng = ECPrng()
        x0, y0 = input("PLZ SET PRNG SEED > ").split(',')
        prng.setState(int(x0), int(y0))
        N, q, m = (256, 4197821, 15)
        PRq.<a> = PolynomialRing(Zmod(q))
        Rq = PRq.quotient(a^N + 1, 'x')
        A = vector(Rq, [Rq.random_element() for _ in range(m)])
        secret = vector(Rq, [Sample(0.3, N) for _ in range(m)])
        t = A*secret
        print(f"A = {v2l(A)}")
        print(f"t = {t.list()}")
        Protocol(A, secret, t)
        cipher = AES.new(md5(str(secret).encode()).digest(), mode=AES.MODE_ECB)
        print(f"ct = {cipher.encrypt(pad(FLAG.encode(), 16)).hex()}")
    except:
        print("error!")

This problem involves a magical PRNG and a ZKP protocol I am unfamiliar with.

First, the PRNG generates $n=pqr=pq(2q-1)$, and you need to decide a point $P$ on an elliptic curve $E: y^2=x^3+3x+7$ with fixed parameters. Checking with sage, $E$ has no rational points, so finding $P$ requires factoring $n$.

I noticed that $r+1=2q$, and $2n$ is a multiple of $pqr$, so I thought of using algebraic-group factorization in $\mathbb{F}_{r^2}$. For more details, refer to my previous challenge Imaginary CTF 2023 - Sus.

After factoring, choose $P$ by selecting $P_p \in E(\mathbb{F}_p), P_q \in E(\mathbb{F}_q), P_r \in E(\mathbb{F}_r)$ and using CRT.

Next is the ZKP part with parameters $N,q,m$ (don't confuse this $q$ with the previous one). It involves operations in $R=\mathbb{Z}_q[x]/(x^N+1)$. Initially, there is a vector $A \in R^m$ and a secret vector $s \in R^m$, where each component of $s$ is $0$ or $1$, with 30% being 1 (from Sample). Then, compute the inner product $t=As$ as the public key.

The protocol part is complex, but only $c$, $y$, and $z$ are relevant. First, $c \in R$, also from Sample, with 30% 1s. $y \in R^m$ is a vector, each component from Sample, but with signal=1, meaning random.seed(prng.next()) is called before sampling. Finally, the proof $z \in R^m$ satisfies $z=cs+y$.

Here, $c \in R$, $s \in R^m$, so $cs$ should be understood as scalar-vector multiplication.

Without knowing $y$, solving $s$ from $A,t$ and $z,c$ seems only possible with lattice reduction, but $N=256$ makes it hard. Another approach is to interfere with $y`, as only$y` is seeded by the PRNG, which we can control to some extent.

The PRNG update is simple: $P_{i+1}=4P$, outputting $o_i=(P_i)_x+b$, where $b$ is a random bias we don't know. Without knowing $b$, controlling $P$ doesn't help predict $o_i$. I thought setting $P_{i+1}=P_i$ would make $o_{i+1}=o_i$, requiring $4P=P \rightarrow 3P=0$, meaning $P$ is a 3-torsion subgroup generator. So, if $p \equiv q \equiv r \equiv 0 \pmod{3}$, we can find such $P`.

When PRNG outputs $o_i$ are the same, each $y_i \in R$ is the same. Then, from $z=cs+y$, separating components gives $z_i-cs_i=y_i$, and since $y_i$ is constant:

Thus, $s_i - s_j$ can be found, but solving $s_i$ is still tricky. The key is that $s_i$ coefficients are $0,1$, with subtraction table:

This means $1$ can only come from $1-0$, and $-1$ from $0-1$. So, $s_i - s_j$ coefficients of $1$ mean $s_i$ has $1$ in the same position, and $-1$ similarly. Finding multiple $s_i - s_j$ gives $s_i$. This technique was also used in HITCON CTF 2022 - Easy NTRU.

from pwn import process, remote, context
import ast
from Crypto.Cipher import AES
from hashlib import md5
from Crypto.Util.Padding import unpad
import subprocess

N, q, m = (256, 4197821, 15)
PRq = PolynomialRing(Zmod(q), "a")
a = PRq.gen()
Rq = PRq.quotient(a ^ N + 1, "x")
mod = a ^ N + 1


def connect():
    # io = process(["sage", "task.sage"])
    # return io

    io = remote("121.41.9.20", int(6666))
    io.recvuntil(b") solve ")
    pow_token = io.recvlineS().strip()
    input(f"continue run pow with {pow_token}?")
    ret = subprocess.check_output(
        "python3 <(curl -sSL https://goo.gle/kctf-pow) solve " + pow_token,
        shell=True,
        timeout=20,
    )
    print(ret)
    io.sendline(ret)
    return io


io = connect()
io.recvuntil(b"N = ")
n = int(io.recvline().strip())


def do_factor(n):
    # n=p*q*r=p*q*(2*q-1)
    # |GF(r^2)|=r^2-1=(r+1)*(r-1)
    # r+1=2*q -> 2*n is a multiple of r+1
    # so we can apply algebraic group factorization
    R = Zmod(n)["x"]
    while True:
        Q = R.quo(R.random_element(2))
        rr = gcd(ZZ(list(Q.random_element() ^ (2 * n))[1]), n)
        if rr != 1:
            qq = (rr + 1) // 2
            pp = n // qq // rr
            assert pp * qq * rr == n
            return pp, qq, rr


def pick_xy(primes):
    xs = []
    ys = []
    for i, p in enumerate(primes):
        # we want 4P=P, that is, 3P=0
        # so we want to find a generator to the 3-torsion subgroup
        # we can't use P=0 as .xy() will throw at point at infinity
        # success rate is 1/27 :)
        E = EllipticCurve(GF(p), [3, 7])
        assert E.order() % 3 == 0, f"unlucky at {i}-th prime"
        G = E.gen(0)
        P = G * (E.order() // 3)
        x, y = map(ZZ, P.xy())
        xs.append(x)
        ys.append(y)
    x = crt(xs, primes)
    y = crt(ys, primes)
    return x, y


p, q, r = do_factor(n)
print(p, q, r)

x, y = pick_xy([p, q, r])
print(x, y)

io.sendline(f"{x},{y}".encode())

io.recvuntil(b"A = ")
a_list = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"t = ")
t_list = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"c = ")
c_list = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"z = ")
z_list = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"ct = ")
ct = bytes.fromhex(io.recvlineS().strip())

A = vector([PRq(a) for a in a_list])
t = PRq(t_list)
c = PRq(c_list)
z = vector([PRq(z) for z in z_list])

# pz[i]-pc*secret[i]=y[i]
# so pz[i]-pz[j]-pc*(secret[i]-secret[j])=y[i]-y[j]=0 (we controlled the prng to make y[i]-y[j]=0)
# and we can solve for secret[i]-secret[j]
# note that secret[i] are binary polynomials (i.e. 0, 1)
# so a `1` in secret[i]-secret[j] is only possible if secret[i]=1 and secret[j]=0
# so we can recover secret[i] by checking which bits are `1` in secret[i]-secret[j]

# another way to solve for the inverse using linear algebra
# x = PRq.gen()
# mat = matrix([vector((c * x**i % mod).padded_list(N)) for i in range(N)])

# this can be optimized by accounting for `-1` in secret[i]-secret[j]
# from n*(n-1) to C(n, 2)=n*(n-1)/2
def get_secret(i):
    result = [0] * N
    for j in range(m):
        if j == i:
            continue
		# another way to solve for the inverse using linear algebra
        # sol = mat.solve_left(vector(((z[i] - z[j]) % mod).padded_list(N)))
        sol = ((Rq(z[i]) - Rq(z[j])) / c).lift().padded_list(N)
        oneidxs = [i for i, v in enumerate(sol) if v == 1]
        for idx in oneidxs:
            result[idx] = 1
    return PRq(result)


secret_prq = vector([get_secret(i) for i in range(m)])
assert (A * secret_prq - t) % mod == 0
secret = vector([Rq(x) for x in secret_prq])
cipher = AES.new(md5(str(secret).encode()).digest(), mode=AES.MODE_ECB)
flag = unpad(cipher.decrypt(ct), 16)
print(flag)
# n1ctf{A_Weak_RSIS_pr0bl3m_H373!!}

From the flag, it is clear this is based on ring-SIS.

After the competition, @Neobeo mentioned two improved strategies: using $-P$ and $P$ having the same x-coordinate allows 5-torsion subgroup, and the problem also gives $w=Ay$, so with constant $y_i$, $y_i=w/\sum_{i}{A_i}$ can be found.