N1CTF 2023 Writeups

發表於 2023-10-23

分類於 CTF

這次和 Balsn 參加這場，解了些 Crypto 方面的題目，把其中學到的東西紀錄下來。

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!")

首先生成一個質數 $p$ ，還有一個長度 20 的 ascii_letters 字串作為 guess，然後取它 sqrt 之後的小數部分當作一個整數 $j$ 。接下來在 $\mathbb{F}_p$ 上生成一條 j-invariant 為 $j$ 的 curve $E$ ，之後在它 3-isogeny 的鄰居中找出 $E_2$ ，並且輸出 $E_2$ 的 j-invariant 必須是 $x+yi$ 的形式，其中 $y \neq 0$ 。

之後告訴你 $p$ ，然後給你一個 oracle 可以輸入一個數 $t$ ，然後 server 計算 $x=t^r-1 \mod{p^2}$ 之後給你 $j(E_2)^x$ 的常數項，目標是要得到 guess。

要解這題很重要的關鍵是要知道有個叫做 modular polynomial 的東西，對於任兩個存在 n-degree isogeny 的兩條橢圓曲縣 $E_1$ , $E_2$ 來說都有 $\Phi_n(j(E_1), j(E_2))=0$ 。而 $\Phi_n(x,y)$ 的公式是可以在這邊找到的。

modular polynomial 在這邊有個很大的意義，因為在 $\mathbb{F}_{p^2}$ 下的 j-invariant 都是 $x+yi$ 形式的，也就是說 $j(E_1)=a+bi, j(E_2)=c+di$ ，其中 $a,b,c,d \in \mathbb{F}_p$ 。把它們代入 $\Phi_n(x,y)=0$ 中後按照 $\operatorname{Re}(\Phi_n(j_(E_1),j_(E_2)))=0$ 和 $\operatorname{Im}(\Phi_n(j_(E_1),j_(E_2)))=0$ 可列出兩個等式。這告訴我們一個很重要的事實，就是只要 $a,b,c,d$ 中有任兩個是已知的話那就能透過解聯立方程式的方式得到另外兩個。這個方法正是解決 Isogeny Hidden Number Problem 的方法之一 (參考這篇的 Chapter 8)。

回到題目本身，可知 $j(E)=a+bi$ 的 $b=0$ ，而 $j(E_2)=c+di$ 中我們什麼都不知道，所以很明顯是要透過 leak oracle 想辦法求出一些關係來。我一開始的想法是直接 leak $c$ ，也就是要 $x=1$ ，也就是 $t^r \equiv 2 \pmod{p^2}$ ，但我想不到一個可以在 $r$ 是隨機的狀況下做到這件事。後來我用的作法是設 $t=-1$ ，那麼在 $r$ 為奇數的情況下 $x=p^2-2$ ，在 $\mathbb{F}_{p^2}$ 下對某個數開 $p^2-2$ 次方正好就是算它的 inverse。

因此我如果設 $j(E_2)^{-1}=e+fi$ ，其中 leak 回傳的值會是 $e$ ，那麼就有 $(c+di)(e+fi)=1$ ，這邊一樣能透過把實部和虛部分開得到 $\mathbb{F}_p$ 上的兩條等式。所以在一共有六個未知數 $a,b,c,d,e,f$ ，其中透過 modular polynomial 和 inverse 的部分列出兩條等式，透過分離係數得到四條，而我們知道 $b=0,e=\text{leak}$ 所以代表這個系統有唯一解的。跑 groebner basis 好像有點慢，所以我是自己手動做 resultant 最後得到一個 $f(a)=0$ ，所以求根就能得到 $a$ ，也就是一開始的 $j$ 。

得到 $j$ ，也就是 $\sqrt{n}-\lfloor \sqrt{n} \rfloor$ 的小數部分之後要想辦法求 $n$ 。這邊我是先對 $j$ 做些轉換得到 $r=\sqrt{n}-\lfloor \sqrt{n} \rfloor$ ，然後設 $k=\lfloor \sqrt{n} \rfloor$ 後移項平方得:

(r+k)^2=r^2+2kr+k^2=n

注意到 $m=n-k^2$ 會是個小於 $2k+1$ 的正整數，所以有 $m-2kr-r^2=0$ ，然後給 $k,m$ 估個大小後用 LLL 就能找出 $m,k$ ，然後就有 $n=m+k^2$ 了。

證明 $0 \leq m<2k+1$ : $k=\lfloor \sqrt{n} \rfloor$ 代表的是 $k^2 \leq n < (k+1)^2$ ，所以 $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}')

簡單來說有個未知的 $p$ ，然後設 $f$ 為 $k$ bits 的 flag，然後生成 $n$ 個 $k$ bits 的 $m_i$ 計算 $c_i \equiv e^{m_i \oplus f} \pmod{p}$ ，其中 $f$ 是 flag 還有 $e=\text{0x10001}$ 。

看到這個題目我第一個想起的是 TetCTF 2022 - Fault (by @hellman)，因為前半恢復 modulus 的部分幾乎是一樣的。把那篇的方法改寫成這篇所用的符號會是這樣的:

\begin{aligned} c_i &\equiv e^{m_i \oplus f} \pmod{p} \\ &\equiv e^f \prod_j e^{(-1)^{f_j} 2^j m_{i,j}} \pmod{p} \end{aligned}

要求 $p$ ，需要找到一些夠小的 $a_i$ 使得:

\begin{aligned} \prod_i c_i^{a_i} \equiv 1 \pmod{p} \end{aligned}

那麼把 $a_i$ 分成正負的部分相乘得 $x,y$ ，那麼 $x-y \equiv 0 \pmod{p}$ ，所以 gcd 即可求 p，所以問題就是要怎麼找到 $a_i$ 。為了要做 gcd，還需要有多組 $a_i$ 。

把前面展開得到:

\prod_i c_i^{a_i} = \prod_i \left( e^{a_i f} \prod_j e^{(-1)^{f_j} 2^j a_i m_{i,j}} \right)

取 log 看指數部分:

\begin{aligned} \sum_i a_i \log{c_i} &= \log{e} \sum_i \left( a_i f + \sum_j (-1)^{f_j} 2^j a_i m_{i,j} \right) \\ &= \log{e} \left( f \sum_i a_i + \sum_j (-1)^{f_j} 2^j \left( \sum_i a_i m_{i,j} \right) \right) = 0 \end{aligned}

也就是說只要使 $\sum_i a_i m_{i,j} = 0$ 和 $\sum_i a_i = 0$ 即可，為了解決這個問題，@hellman 構造了一個矩陣:

A= \begin{bmatrix} m_{0,0} & m_{0,1} & \cdots & m_{0,k-1} & 1 \\ m_{1,0} & m_{1,1} & \cdots & m_{1,k-1} & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ m_{n-1,0} & m_{n-1,1} & \cdots & m_{n-1,k-1} & 1 \\ \end{bmatrix}

每個 row 塞了 $m_i$ 的 bits，然後後面多的一個 $1$ 是為了讓 $\sum_i a_i = 0$ 成立。

可知我們要找的 $a_i$ 是 $\ker{A^T}$ (left kernel) 中的短向量，這部分用 LLL 就能求了。

這部分的概念其實和我之前出的 No modulus 以及去年 N1CTF 的 ezdlp 還有 HITCON CTF 2022 - Secret 很像

求得 $p$ 之後還要想辦法拿 flag，參考 @hellman 的 writeup 知道有辦法求 $e^f$ ，可是 $p-1=2q$ ，明顯沒辦法做 DLP，所以這樣做是沒用的。我這邊的方法是透過觀察:

c_i \equiv e^f \prod_j e^{(-1)^{f_j} 2^j m_{i,j}} \pmod{p}

中的指數部分有出現一個 $(-1)^{f_i}$ ，所以想說能不能 bit by bit 求 $f$ 。在這題中我發現嘗試解 $sA=(0,0,\cdots,0,0,0,1)$ 會找不到解，也就是不存在一個 $s$ 符合 $\prod_i c_i^{s_i} = e^f$ ，不過 $sA=(0,0,\cdots,0,0,1,1)$ 則是有解的，即:

\prod_i c_i^{s_i} = e^f e^{(-1)^{f_{k-1}} 2^{k-1}} = y

這邊 $f_{k-1}$ 的意思是 $f$ 的 lsb，因為 $f$ 是 k bits 的緣故所以 $f_{k-1}=1$ 是已知的。之後如果我想知道 flag 的第 $k-2$ bits 是多少，就求 $s'A=(0,0,\cdots,0,1,1,1)$ ，這樣就能得到:

\prod_i c_i^{s'_i} = y e^{(-1)^{f_{k-2}} 2^{k-2}} = y z^{(-1)^{f_{k-2}}} = x

因此 $x=yz$ 代表 $f_{k-2}=0$ ， $x=y/z$ 代表 $f_{k-2}=1$ ，然後把 $k-2$ 換成其他的 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!")

這題有個神奇的 PRNG 和一個我不知道是那個 protocol 的 ZKP。

首先是 PRNG 的部分會先生成 $n=pqr=pq(2q-1)$ ，然後你需要決定某個參數固定的橢圓曲縣 $E: y^2=x^3+3x+7$ 上面的點 $P$ 。用 sage 檢查可知 $E$ 上沒有 rational point，所以要求 $P$ 需要有辦法分解 $n$ 才行。

這部分我是先注意到 $r+1=2q$ ，而 $2n$ 是 $pqr$ 的一個倍數的這個事實，所以想到用 $\mathbb{F}_{r^2}$ 做 algebraic-group factorisation。不清楚這個的話可以參考我之前出的 Imaginary CTF 2023 - Sus。

分解之後要選 $P$ 就是透過選 $P_p \in E(\mathbb{F}_p), P_q \in E(\mathbb{F}_q), P_r \in E(\mathbb{F}_r)$ 之後 CRT 就能搞定。

再來是後面 ZKP 的部分，它有參數 $N,q,m$ (這邊的 $q$ 不要和前面搞混)，總之它會在 $R=\mathbb{Z}_q[x]/(x^N+1)$ 做一些運算。一開始有一個 vector $A \in R^m$ ，還有一個 secret vector $s \in R^m$ ，其中 $s$ 中的任何一個 component 都是 $0,1$ ，且只有 30% 是 1 (from Sample)。之後求向量內積 $t=As$ 當 public key。

之後 protocol 的部分比較複雜，不過真正和解題有關的只有 $c$ 和 $y$ , $z$ 。首先 $c \in R$ ，一樣用 Sample 出來的，所以 component 都是 $0,1$ ，其中只有 30% 是 1。 $y \in R^m$ 也是個 vector，其中每個 component 也都是來自 Sample，不過這邊它有設定 signal=1，也就是在 sample 前會 call random.seed(prng.next())。最後的 proof $z \in R^m$ 符合 $z=cs+y$ 而已。

此處的 $c \in R$ , $s \in R^m$ ，所以 $cs$ 應該要理解為 scalar-vector multiplication

在 $y$ 未知的情況下要透過 $A,t$ 和 $z,c$ 解 $s$ 我能想到的方法只有 lattice reduction，不過這題的 $N=256$ 讓它很難透過 lattice reduction 解這題。另一個方向就是想辦法去干涉 $y$ ，因為只有 $y$ 在 sample 的時候會透過 PRNG 去 seed，而 prng 我們在某種程度上是可控的。

PRNG 的更新式很簡單，就是 $P_{i+1}=4P$ ，然後輸出 $o_i=(P_i)_x+b$ ，其中 $b$ 是某個隨機生成的 bias 值，這我們不知道。在不知道 $b$ 的情況下不管怎麼控 $P$ 都沒辦法預測 $o_i$ 。我這邊想說讓 $P_{i+1}=P_i$ 的話至少能讓 $o_{i+1}=o_i$ 一樣，而這個的條件就是 $4P=P \rightarrow 3P=0$ ，也就是 $P$ 是 3-torsion subgroup 的 generator。因此只要在 $p \equiv q \equiv r \equiv 0 \pmod{3}$ 的時候就能找到這樣的 $P$ 。

而當 PRNG 的輸出 $o_i$ 都相同的後果就是 $y$ vector 中的每個 $y_i \in R$ 都是相同的值。然後拿出原本的 $z=cs+y$ 來看，分開討論各 component 會得到 $z_i-cs_i=y_i$ ，但因為 $y_i$ 為定值，所以可得:

z_i-z_j-c(s_i-s_j)=0

因此可得 $s_i - s_j$ ，不過這樣要解 $s_i$ 還沒那麼容易。這邊的關鍵是注意到 $s_i$ 這些多項式的係數都是 $0,1$ ，而它們的減法表為:

-	0	1
0	0	1
1	-1	0

這代表的是 $1$ 只有可能是由 $1-0$ 產生的， $-1$ 也只有可能是由 $0-1$ 產生的。因此這代表 $s_i - s_j$ 中係數為 $1$ 的項代表的是 $s_i$ 在同一個位置也是 $1$ ， $-1$ 也是同理。所以就想辦法求多組 $s_i - s_j$ 就能求出 $s_i$ 了。去年 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!!}

從 flag 可以知道這原來是基於 ring-SIS 的，

賽後從 @Neobeo 那邊知道還有兩個改進的策略，一個是利用 $-P$ 和 $P$ 擁有相同 x 座標的性質，也可以允許 5-torsion subgroup。再來是題目其實還有給一個 $w=Ay$ ，所以在 $y_i$ 都相同的情況下可求 $y_i=w/\sum_{i}{A_i}$ 。

e2Is0#

e2D1p#

e20k#

e2Is0

e2D1p

e20k