0CTF2025 • Misay's blog

期末周看了看题把签到的分辨器和ntt给梭出来本文主要基于rec师傅的博客 ↗ 来进行对zkpuzzle的一个复现

zkpuzzle1#

from sage.all import EllipticCurve, Zmod, is_prime, randint, inverse_mod
from ast import literal_eval
from secret import flag

class proofSystem:
    def __init__(self, p1, p2):
        assert is_prime(p1) and is_prime(p2)
        assert p1.bit_length() == p2.bit_length() == 256
        self.E1 = EllipticCurve(Zmod(p1), [0, 137])
        self.E2 = EllipticCurve(Zmod(p2), [0, 137])

    def myrand(self, E1, E2):
        F = Zmod(E1.order())
        r = F.random_element()
        P = r * E2.gens()[0]
        x = P.x()
        return int(r * x) & (2**128 - 1)

    def verify(self, E, r, k, w):
        G = E.gens()[0]
        P = (r*k) * G
        Q = (w[0]**3 + w[1]**3 + w[2]**3 + w[3]**3) * inverse_mod(k**2, G.order()) * G
        return P.x() == Q.x()


def task():
    ROUND = 1000
    threshold = 999
    print("hello hello")
    p1, p2 = map(int, input("Enter two primes: ").split())

    proofsystem = proofSystem(p1, p2)
    print(f"You need to succese {threshold} times in {ROUND} rounds.")
    r = proofsystem.myrand(proofsystem.E1, proofsystem.E2)
    success = 0
    for _ in range(ROUND):
        k = proofsystem.myrand(proofsystem.E2, proofsystem.E1)
        w = literal_eval(input(f"Prove for {r}, this is your mask: {k}, now give me your witness: "))
        assert len(w) == 4
        assert max(wi.bit_length() for wi in w) < 200
        print("pass the bit check")
        if proofsystem.verify(proofsystem.E1, r, k, w) and proofsystem.verify(proofsystem.E2, r, k, w):
            print(f"Good!")
            success += 1
        r += 1


    if success > threshold:
        print("You are master of math!")
        print(flag)


if __name__ == "__main__":
    try
        task()
    except Exception:
        exit()

分为两个部分首先需要选择两个256bits的素数 $p_1\;p_2$ 构建一个曲线系统随后给出两个128bits的随机素数 $r\;\;k$ 需要我们找到四个小于200bits的数 $w_i$ ,能够

\sum_{i=1}^{4}w_i^{3}=r\times k^3 \mod p_1 \cdot p_2

我们首先看这里构造系统的过程中存在

def myrand(self, E1, E2):
    F = Zmod(E1.order())    
    r = F.random_element()	# r 属于标量域 (Scalar Field)，大小为 E1 的阶
    P = r * E2.gens()[0]    # P 是 E2 上的点
    x = P.x()               # x 属于基域 (Base Field)，大小为 p2
    return int(r * x) & (2**128 - 1)  # 类型错误

$r$ 是 $E_1$ 环上的元素但是 $x$ 是 $GF(p_2)$ 上的域内元素运行不报错的唯一方法是找出 $p_1\;\;p_2$ 满足

E_1.p=E_2.order()

E_2.p=E_1.order()

当然我们也可以令 $p_1==p_2$ 那么只需要满足

E.p==E.order()

所以我们第一步的操作是

寻找一个素数 $p$ 使得曲线 $E:y^2\equiv x^3+137\mod p$ 满足 $E.order()==p$

rec师傅使用了一个 Complex Multiplication的方法

随机选取一个大奇数 $y$ 在本题的曲线结构中可以通过寻找验证特殊的代数结构来找出 $p$ 代码如下

def find_prime_for_anomalous_curve(target_b): 
    y = randrange(2**127,2**128) | 1
    while True:
        # p = (3y^2 + 1) / 4
        numerator = 3 * y**2 + 1
        if numerator % 4 == 0:
            p = numerator // 4
            if is_prime(p): 
                try:
                    E = EllipticCurve(GF(p), [0, target_b])
                    if E.order() == p:
                        return p
                except Exception as e: 
                    pass
        y += 2

在找到这个 $p$ 之后我们进入到下一步

此时我们的验证

proofsystem.verify(proofsystem.E1, r, k, w) and proofsystem.verify(proofsystem.E2, r, k, w)

本质等于一个对 $E$ 的验证而 $E$ 又是奇异的转移到阶的算法上那么得到

\sum_{i=1}^{4}w_i^{3}=r\times k^3 \mod p

而我们有一个恒等式

(u+w)^3+(u-v)^3+(-u+w)^3+(-u-w)^3=6u(v-w)(v+w)

那么我们要找到

\sum_{i=1}^{4}w_i^{3}=r\times k^3 + t\times p

$t$ 是我们随便取的 $r\;k\;p$ 也已知我们接下来尝试把等式右边联系起来用上恒等式去解题我们这里的核心思路是去寻找特定的 $t$ 使得我们的

S = r\times k^3 + t\times p

能形如

6u(v-w)(v+w)

我们算一下 $r\times k^3$ 是512bits 而 $p$ 是256bits左右那么在我们穷举的过程中我们的 $S$ 最好满足以下特征

$6 \;|\; S$
在此之上我们有 $s=\frac{S}{6}=u(v^2-w^2)$
- 我们人为再令 $v-w=1$ $v - w = 1$ ,问题进一步简化成 $s=u(2\times w+1)$ $s = u (2 \times w + 1)$ ,也就是 $s=u\times x$ $s = u \times x$ ； $x$ $x$ 视为某个奇数
  - 故而我们对 $s$ $s$ 去用 $2$ $2$ 试除肯定能除掉那么能除掉的部分我们给 $u$ $u$ 我们的期望是
    - $u\in(1,2^{60})$ ; $x\in(1,2^{61})$ 一旦能进入这个范围的分解我们就直接得到 $u\;v\;w$ 完成分解发送通过此轮

然后就是分解的思路了还是从rec师傅的分解手法这里学到很多特别是factor的一种高效好用的写法

def _factor_worker(n, q):
    try:
        q.put(sum([[p]*i for p, i in factor(n)], []))
    except Exception as e:
        q.put(e)

def factor_with_timeout(n, timeout):
    """Run Sage factor in a child process to enforce wall-clock timeout."""
    ctx = mp.get_context("fork") if "fork" in mp.get_all_start_methods() else mp.get_context()
    q = ctx.Queue()
    proc = ctx.Process(target=_factor_worker, args=(n, q))
    proc.start()
    proc.join(timeout)
    if proc.is_alive():
        proc.terminate()
        proc.join()
        raise TimeoutError("factor timeout")
    if q.empty():
        raise RuntimeError("factor failed without result")
    res = q.get()
    if isinstance(res, Exception):
        raise res
    return res

思路就很简单每次都找我们的target 直接分解取光滑的情况然后找到一组合适的解就行

from Crypto.Util.number import *
from pwn import *
import ast, tqdm, multiprocessing as mp

def find_prime_for_anomalous_curve(target_b):
    # 让 y 至少是 128 位，增大 p 达到 256 位的概率
    y = randrange(2**128, 2**129) | 1
    while True:
        numerator = 3 * y**2 + 1
        if numerator % 4 == 0:
            p = numerator // 4
            if is_prime(p) and p.bit_length() == 256:
                try:
                    E = EllipticCurve(GF(p), [0, target_b])
                    if E.order() == p:
                        return p
                except Exception:
                    pass
        y = randrange(2**128, 2**129) | 1

def _factor_worker(n, q):
    try:
        q.put(sum([[p]*i for p, i in factor(n)], []))
    except Exception as e:
        q.put(e)

def factor_with_timeout(n, timeout):
    """Run Sage factor in a child process to enforce wall-clock timeout."""
    ctx = mp.get_context("fork") if "fork" in mp.get_all_start_methods() else mp.get_context()
    q = ctx.Queue()
    proc = ctx.Process(target=_factor_worker, args=(n, q))
    proc.start()
    proc.join(timeout)
    if proc.is_alive():
        proc.terminate()
        proc.join()
        raise TimeoutError("factor timeout")
    if q.empty():
        raise RuntimeError("factor failed without result")
    res = q.get()
    if isinstance(res, Exception):
        raise res
    return res  

def attack(r, k, p):
    t = ZZ(r*pow(k, 3, p) % p)
    for _ in tqdm.trange(10000):
        if t % 6 == 0:
            try:
                facs = factor_with_timeout(t // 6, 1)

                xs = [facs[-1], facs[-2], facs[-3]]
                ind = 0
                for i in range(len(facs)-3):
                    if ZZ(xs[ind]).nbits() >= 200:
                        ind += 1
                    if ind == 3:
                        raise Exception("try again")
                    xs[ind] *= facs[i]
                u = xs[0]
                v = (xs[1] + xs[2]) // 2
                w = (xs[2] - xs[1]) // 2

                ws = [u+v, u-v, -u+w, -u-w]
                assert max(wi.bit_length() for wi in ws) < 200, "too big"
                assert sum(wi**3 for wi in ws)*inverse_mod(k**2, p) % p == (r*k) % p, "not match"
                return ws
            except TimeoutError as e:
                print(e)
            except Exception as e:
                print(e)
        t += p



p = find_prime_for_anomalous_curve(137)

io = process(["/usr/sbin/sage", "-c", 'load("task.sage"); task()'])
io.recvuntil(b"Enter two primes:")

io.sendline(f"{p} {p}".encode())
print(p.bit_length())
for i in tqdm.tqdm(range(21)):
    print(f"Round {i}")
    io.recvuntil(b"Prove for ")
    r = int(io.recvuntil(b",", drop=True))
    io.recvuntil(b"mask: ")
    k = int(io.recvuntil(b",", drop=True))
    w = attack(r, k, p)
    io.sendlineafter(b"witness: ", str(w).encode())
    print(io.recvline().decode().strip())
    line = io.recvline().decode().strip()
    print(line)
print(io.recvall(timeout=2).decode())

zkpuzzle2#

from sage.all import EllipticCurve, Zmod, is_prime, randint, inverse_mod
from ast import literal_eval
from secret import flag


class proofSystem:
    def __init__(self, p1, p2):
        assert is_prime(p1) and is_prime(p2)
        assert p1.bit_length() == p2.bit_length() == 256 and p1 != p2
        self.E1 = EllipticCurve(Zmod(p1), [0, 137])
        self.E2 = EllipticCurve(Zmod(p2), [0, 137])

    def myrand(self, E1, E2):
        F = Zmod(E1.order())
        r = F.random_element()
        P = r * E2.gens()[0]
        x = P.x()
        return int(r * x) & (2**128 - 1)

    def verify(self, E, r, k, w):
        assert len(w) == 4 and type(w) == list
        assert max(wi.bit_length() for wi in w) < 400
        G = E.gens()[0]
        P = (r*k) * G
        Q = (w[0]**3 + w[1]**3 + w[2]**3 + w[3]**3) * inverse_mod(k**2, G.order()) * G
        return P.x() == Q.x()


def task():
    ROUND = 1000
    threshold = 940
    print("hello hello")
    p1, p2 = map(int, input("Enter two primes: ").split())

    proofsystem = proofSystem(p1, p2)
    print("N0n3 passes by and decides to steal some rounds. :D")
    ROUND = ROUND - bin(p1).count("1") - bin(p2).count("1")
    print(f"You need to succese {threshold} times in {ROUND} rounds.")
    r = proofsystem.myrand(proofsystem.E1, proofsystem.E2)
    success = 0
    for _ in range(ROUND):
        k = proofsystem.myrand(proofsystem.E2, proofsystem.E1)
        w = literal_eval(input(f"Prove for {r}, this is your mask: {k}, now give me your witness: "))
        if proofsystem.verify(proofsystem.E1, r, k, w) and proofsystem.verify(proofsystem.E2, r, k, w):
            print(f"Good!")
            success += 1
        r += 1


    if success > threshold:
        print("You are master of math!")
        print(flag)


if __name__ == "__main__":
    try:
        task()
    except Exception:
        exit()

等式没变但是做出了如下限制

$p_1\ne p_2$
ROUND = ROUND - bin(p1).count("1") - bin(p2).count("1")

同时要考虑p和order之间的限制关系依旧需要构造类似的2-cycle的椭圆曲线

对于 $j=0$ 的CM曲线它的阶满足

\#E=p+1-t

trace满足

4p=t^2+3y^2

我们有如下方程

\begin{cases}p_1+1-t_1 = p_2\\p_2+1- t_2 = p_1\end{cases}

低汉明权重和2-Cycle曲线处理中的对数据的要求让我们联想到NTT友好的素数形如

p=c\times 2^k + 1

当 $c$ 足够小汉明重量就会比较小这里找到是一组

p   = 0b1100000000110000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000110000000000010000100000010000000000000000000000100000100000000000000000001000001000010000000000001100000000001000000000000000000000000001
q   = 0b1100000000110000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000110000000110010000101100010000000000000000000000100000100000000000000000000100000100010000000000001100000000000100000110000000000000000001

接下来我们要求解zkp

\begin{cases}\sum_{i=1}^{4}w_i^{3}=r\times k^3 \mod p\\\sum_{i=1}^{4}w_i^{3}=r\times k^3 \mod q\end{cases}

考虑等式

\begin{cases}(u+tp)^3+(-u)^3\equiv0\mod p\\(u+tp)^3+(-u)^3\equiv tp\cdot(3u^2+3up+(tp)^2)\mod q\end{cases}

\begin{cases}(v+tq)^3+(-v)^3\equiv0\mod q\\(v+tq)^3+(-v)^3\equiv tq\cdot(3v^2+3vq+(tq)^2)\mod p\end{cases}

取 $t=1$

因为我们的检查是分别在 $\mod p$ $\mod q$ 下进行的而我们期望的四个数就是

(u+p)\;\;(-u)\;\;(v+q)\;\;(-v)

这样只用解二次同余方程组求出 $v\;u$ 实现zkp 非常快

from Crypto.Util.number import *
from pwn import *
import ast, tqdm, multiprocessing as mp
from sage.all import inverse_mod, Mod


def _solve_quadratic_mod_prime(a, b, c, p):
    a %= p
    b %= p
    c %= p
    if a == 0:
        return None
    D = (b*b - 4*a*c) % p
    try:
        s = int(Mod(D, p).sqrt())
    except (ValueError, ArithmeticError):
        return None
    inv2a = inverse_mod((2*a) % p, p)
    x = ((-b + s) * inv2a) % p
    return int(x)

def _solve_u(q, p, r, k, t):
    tp = (t * p) % q
    if tp == 0:
        return None
    rhs = (r * pow(k, 3, q)) % q
    inv_tp = inverse_mod(tp, q)
    a = 3 % q
    b = (3 * t * p) % q
    c = (pow(t * p, 2, q) - rhs * inv_tp) % q
    return _solve_quadratic_mod_prime(a, b, c, q)

def _solve_v(p, q, r, k, t):
    tq = (t * q) % p
    if tq == 0:
        return None
    rhs = (r * pow(k, 3, p)) % p
    inv_tq = inverse_mod(tq, p)
    a = 3 % p
    b = (3 * t * q) % p
    c = (pow(t * q, 2, p) - rhs * inv_tq) % p
    return _solve_quadratic_mod_prime(a, b, c, p)

def attack(r, k, p, q, tmax=32):
    # independently search t_p, t_q to make discriminants quadratic residues
    u = None
    t_p = None
    for t in range(1, tmax + 1):
        u = _solve_u(q, p, r, k, t)
        if u is not None:
            t_p = t
            break
    if u is None:
        raise ValueError("no u found")

    v = None
    t_q = None
    for t in range(1, tmax + 1):
        v = _solve_v(p, q, r, k, t)
        if v is not None:
            t_q = t
            break
    if v is None:
        raise ValueError("no v found")

    w = [u + t_p * p, -u, v + t_q * q, -v]
    return w
    


io = process(["/usr/sbin/sage", "-c", 'load("task.sage"); task()'])

p  = int("0b1100000000110000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000110000000000010000100000010000000000000000000000100000100000000000000000001000001000010000000000001100000000001000000000000000000000000001", 2)
q  = int("0b1100000000110000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000110000000110010000101100010000000000000000000000100000100000000000000000000100000100010000000000001100000000000100000110000000000000000001", 2)

io.recvuntil(b"Enter two primes:")

io.sendline(f"{p} {q}".encode())


for i in range(1000):
    try:
        io.recvuntil(b"Prove for ")
    except EOFError:
        break
    r = int(io.recvuntil(b",", drop=True))
    io.recvuntil(b"mask: ")
    k = int(io.recvuntil(b",", drop=True))
    w = attack(r, k, p, q)
    io.sendlineafter(b"witness: ", str(w).encode())
    line = io.recvline(timeout=1)
    if line:
        print(line.decode().strip())
    print(f"Round {i + 1} completed")

rest = io.recvall(timeout=2)
if rest:
    print(rest.decode())

zkpuzzle3#

from sage.all import EllipticCurve, Zmod, is_prime, randint, inverse_mod
from ast import literal_eval
from secret import flag
import signal, sys

def handler(signum, frame):
    sys.exit(1)


class proofSystem:
    def __init__(self, p1, p2):
        assert is_prime(p1) and is_prime(p2)
        assert p1.bit_length() == p2.bit_length() == 256 and p1 != p2
        self.E1 = EllipticCurve(Zmod(p1), [0, 137])
        self.E2 = EllipticCurve(Zmod(p2), [0, 137])

    def myrand(self, E1, E2):
        F = Zmod(E1.order())
        r = F.random_element()
        P = r * E2.gens()[0]
        x = P.x()
        return int(r * x) & (2**128 - 1)

    def verify(self, E, r, k, w):
        assert len(w) == 4 and type(w) == list
        assert max(wi.bit_length() for wi in w) < 260
        G = E.gens()[0]
        P = (r*k) * G
        Q = (w[0]**3 + w[1]**3 + w[2]**3 + w[3]**3) * inverse_mod(k**2, G.order()) * G
        return P.x() == Q.x() and (int(w[0])**3 + int(w[1])**3 + int(w[2])**3 + int(w[3])**3) == int(k)**3*int(r)


def task():
    ROUND = 1000
    threshold = 940
    print("hello hello")
    p1, p2 = map(int, input("Enter two primes: ").split())

    proofsystem = proofSystem(p1, p2)
    print("N0n3 passes by and decides to steal some rounds. :D")
    ROUND = ROUND - bin(p1).count("1") - bin(p2).count("1")
    print(f"You need to succese {threshold} times in {ROUND} rounds.")
    r = min(proofsystem.myrand(proofsystem.E1, proofsystem.E2), proofsystem.myrand(proofsystem.E2, proofsystem.E1))
    success = 0
    for _ in range(ROUND):
        # k = proofsystem.myrand(proofsystem.E2, proofsystem.E1)
        k = 1 # let's make situation simple! :P
        w = literal_eval(input(f"Prove for {r}, this is your mask: {k}, now give me your witness: "))
        if proofsystem.verify(proofsystem.E1, r, k, w) and proofsystem.verify(proofsystem.E2, r, k, w):
            print(f"Good!")
            success += 1
        r += 1

    if success > threshold:
        print("You are master of math!")
        print(flag)


if __name__ == "__main__":
    signal.signal(signal.SIGALRM, handler)
    signal.alarm(90)
    try:
        task()
    except Exception:
        exit()

限制和zkpuzzle2一样关键在于

90s限时基本0.1s不到就需跑完一轮
我们的zkp改为 $\sum_{i=1}^{4}w^3_i=r$ ，因为明显 $r<p\;\;r<q$ 而且 $r$ 是不变量

我们借用zkp2的思路

[(u+x)^3+(-x)^3]+[(v+y)^3+(-y)^3]=r

(3ux^2+3u^2x+x^3)+(3vy^2+3v^2y+y^3)=r

3u(x^2+ux)+3v(y^2+vy)=r-u^3-u^3

往完全平方转化

3u(4x^2+4ux)+3v(4y^2+4vy)=4(r-u^3-v^3)

那么

3u((2x+u)^2-u^2)+3v((2y+v)^2-v^2)=4(r-u^3-v^3)

移项

3u(2x+u)^2+3v(2y+v)^2=4r-u^3-v^3

我们可以取 $u\;\;v$ 是很简单的小数取尝试求解 $x\;\;y$ 本质是求

uA^2+vB^2=\frac{S}{3}

可以使用sagemath的BinaryQF(u, 0, v).solve_integer(t) 方法