Misay's blog

0CTF2025

发表于 分类于
本文字数： 14k
0CTF2025Crypto复现

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

zkpuzzle1

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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的素数 构建一个曲线系统 随后给出两个128bits的随机素数 需要我们找到四个小于200bits的数,能够 我们首先看这里构造系统的过程中 存在

1
2
3
4
5
6
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)  # 类型错误

是环上的元素 但是是上的域内元素 运行不报错的唯一方法是找出 满足

当然我们也可以令那么只需要满足 所以我们第一步的操作是

寻找一个素数 使得曲线满足

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

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

此时我们的验证

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

本质等于一个对的验证 而又是奇异的 转移到阶的算法上 那么得到 而我们有一个恒等式 那么我们要找到 是我们随便取的 也已知 我们接下来尝试把等式右边联系起来 用上恒等式去解题 我们这里的核心思路是去寻找特定的 使得我们的 能形如 我们算一下是512bits 而是256bits左右 那么在我们穷举的过程中 我们的最好满足以下特征

  • 在此之上 我们有

    • 我们人为再令,问题进一步简化成,也就是 ；视为某个奇数
      • 故而 我们对去用试除 肯定能除掉 那么能除掉的部分我们给 我们的期望是
        • ; 一旦能进入这个范围的分解 我们就直接得到 完成分解 发送通过此轮

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 直接分解 取光滑的情况 然后找到一组合适的解就行

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
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

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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()

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

  • ROUND = ROUND - bin(p1).count("1") - bin(p2).count("1")

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

对于的CM曲线 它的阶满足 trace满足 我们有如下方程 低汉明权重和2-Cycle曲线处理中的对数据的要求 让我们联想到NTT友好的素数 形如 当足够小 汉明重量就会比较小 这里找到是一组

1
2
p   = 0b1100000000110000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000110000000000010000100000010000000000000000000000100000100000000000000000001000001000010000000000001100000000001000000000000000000000000001
q   = 0b1100000000110000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000110000000110010000101100010000000000000000000000100000100000000000000000000100000100010000000000001100000000000100000110000000000000000001

接下来我们要求解zkp 考虑等式

取

因为我们的检查是分别在 下进行的 而我们期望的四个数就是 这样只用解二次同余方程组求出 实现zkp 非常快

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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改为，因为明显而且是不变量

我们借用zkp2的思路

往完全平方转化 那么 移项 我们可以取是很简单的小数 取尝试求解 本质是求 可以使用sagemath的BinaryQF(u, 0, v).solve_integer(t) 方法