前言

此前四处搜刮题目做的时候想找Decidophobia的题解，找到了Maple师傅的writeups，于是对idekCTF有了点印象。没过多久，自己也是参与上了，不过也做不出几道题，凑个热闹。

正文

第一天一道题都不会，颇有些破防——然后每睡一觉就解出一道，只恨比赛只有两天。

Crypto

Catch

题目如下。

from Crypto.Random.random import randint, choice
import os

# In a realm where curiosity roams free, our fearless cat sets out on an epic journey.
# Even the cleverest feline must respect the boundaries of its world—this magical limit holds all wonders within.
limit = 0xe5db6a6d765b1ba6e727aa7a87a792c49bb9ddeb2bad999f5ea04f047255d5a72e193a7d58aa8ef619b0262de6d25651085842fd9c385fa4f1032c305f44b8a4f92b16c8115d0595cebfccc1c655ca20db597ff1f01e0db70b9073fbaa1ae5e489484c7a45c215ea02db3c77f1865e1e8597cb0b0af3241cd8214bd5b5c1491f

# Through cryptic patterns, our cat deciphers its next move.
def walking(x, y, part):
    # Each step is guided by a fragment of the cat's own secret mind.
    epart = [int.from_bytes(part[i:i+2], "big") for i in range(0, len(part), 2)]
    xx = epart[0] * x + epart[1] * y
    yy = epart[2] * x + epart[3] * y
    return xx, yy

# Enter the Cat: curious wanderer and keeper of hidden paths.
class Cat:
    def __init__(self):
        # The cat's starting position is born of pure randomness.
        self.x = randint(0, 2**256)
        self.y = randint(0, 2**256)
        # Deep within, its mind holds a thousand mysterious fragments.
        while True:
            self.mind = os.urandom(1000)
            self.step = [self.mind[i:i+8] for i in range(0, 1000, 8)]
            if len(set(self.step)) == len(self.step):
                break

    # The epic chase begins: the cat ponders and strides toward the horizon.
    def moving(self):
        for _ in range(30):
            # A moment of reflection: choose a thought from the cat's endless mind.
            part = choice(self.step)
            self.step.remove(part)
            # With each heartbeat, the cat takes a cryptic step.
            xx, yy = walking(self.x, self.y, part)
            self.x, self.y = xx, yy
            # When the wild spirit reaches the edge, it respects the boundary and pauses.
            if self.x > limit or self.y > limit:
                self.x %= limit
                self.y %= limit
                break

    # When the cosmos beckons, the cat reveals its secret coordinates.
    def position(self):
        return (self.x, self.y)

# Adventurer, your quest: find and connect with 20 elusive cats.
for round in range(20):
    try:
        print(f"👉 Hunt {round+1}/20 begins!")
        cat = Cat()

        # At the start, you and the cat share the same starlit square.
        human_pos = cat.position()
        print(f"🐱✨ Co-location: {human_pos}")
        print(f"🔮 Cat's hidden mind: {cat.mind.hex()}")

        # But the cat, ever playful, dashes into the unknown...
        cat.moving()
        print("😸 The chase is on!")

        print(f"🗺️ Cat now at: {cat.position()}")

        # Your turn: recall the cat's secret path fragments to catch up.
        mind = bytes.fromhex(input("🤔 Path to recall (hex): "))

        # Step by step, follow the trail the cat has laid.
        for i in range(0, len(mind), 8):
            part = mind[i:i+8]
            if part not in cat.mind:
                print("❌ Lost in the labyrinth of thoughts.")
                exit()
            human_pos = walking(human_pos[0], human_pos[1], part)

        # At last, if destiny aligns...
        if human_pos == cat.position():
            print("🎉 Reunion! You have found your feline friend! 🐾")
        else:
            print("😿 The path eludes you... Your heart aches.")
            exit()
    except Exception:
        print("🙀 A puzzle too tangled for tonight. Rest well.")
        exit()

# Triumph at last: the final cat yields the secret prize.
print(f"🏆 Victory! The treasure lies within: {open('flag.txt').read()}")

题目很有诗意hh但是有点像没开thinking的ChatGPT写的，搞了半天是GPT对抗GPT（×）
题目生成一只猫，给定它的初始坐标和所有“思考”块，经过一些移动后给出最终坐标，我们需要从最终坐标中得到移动时使用的思考块，重复20次就能抓到猫，获得flag。
受到好多阴间题目的“启发”，我第一想到的已经不是如何破解这个问题，而是代码中有没有漏洞。虽然题目的要求很清晰，但是从第71行的if part not in cat.mind: 我看出了两点——
1.mind没有变过，始终是最初的1000个byte，其中每个8bytes都不重复，因此，虽然猫的移动使用的step不允许重复，但是用户不影响，用户的输入是可以重复的。
2.mind是一连串bytes，因此，即使输入的mind分割成part后，某个part不是step的一员，只要它是mind的连续8bytes，就可以通过。所以，我们其实有1000-8+1=993个part可用，而非猫移动时的125个。
虽然其实这两点都没用到，但是我觉得抓漏洞也是我们需要做的……说不定哪次就有用呢，AI不太会做这种“违规”的事，只能靠人自己来。
题目还给出了一个limit，它是一个1024位的大质数。考虑每一次walking，part是8个byte，分成4个2*8=16bit的数，这样，新的xx和yy长度最多是原来的x和y加16位，30次就是480位。这样的话，猫最终的坐标也只有256+480=736位，还是远小于limit，而猫的moving过程一定会走满30轮。这个如此大的limit有什么用呢？
将起点和终点作为向量，则epart中的四个数可以组成一个2*2矩阵 $[\begin{matrix} e_{0} & e_{1} \\ e_{2} & e_{3} \end{matrix}]$ 。对于1000个随机byte，划分为2byte一组，一共500组。其中出现数字0的期望为 $\frac{500}{2^{16}}$ ，因此epart矩阵中出现0是不太可能的，出现连续两个0使得xx或yy = 0 * x + 0 * y = 0就更不可能了，在20次挑战中几乎可以排除，因此我们认为每一次walking后，xx大于x，yy大于y。
正着找过去，不管选哪个矩阵都满足 $[\begin{matrix} x_{i} & y_{i} \end{matrix}] [\begin{matrix} e_{0} & e_{1} \\ e_{2} & e_{3} \end{matrix}] = [\begin{matrix} x_{i + 1} & y_{i + 1} \end{matrix}]$ 中的 $x_{i + 1} > x_{i}, y_{i + 1} > y_{i}$ 。对于筛选需要的矩阵没有帮助，逆着找过来， $[\begin{matrix} e_{0} & e_{1} \\ e_{2} & e_{3} \end{matrix}]$ 的逆矩阵多半含有分数，存储还是计算都不方便，无论哪个方向都不行。
……真的吗？我们可以在 $F_{p}$ 中找逆矩阵。对于随机选取的 $[0, 2^{16}]$ 中的数，第一行全0概率约为 $\frac{1}{2^{32}}$ ，第二行与第一行成比例在 $F_{p} \times F_{p}$ 中共有 $p$ 种可能，而在 $[0, 2^{16}) \times [0, 2^{16})$ 的概率为 $\frac{2^{32}}{p^{2}} * p = \frac{2^{32}}{p}$ ，由于这里的 $p = limit$ 约有1024bit，两种情况的概率均远小于1，在20次内可认为都不会发生，即所有矩阵都可逆。
由于 $p$ 是一个很大的质数，对于小于 $p$ 的任何正整数 $a$ ，都有 $gcd (a, p) = 1$ ，因此一定有逆元 $a^{- 1}$ 存在。且因为这里矩阵的每个数都是1~65535（0不考虑），所以除了1以外，其他数的逆元可以表示为 $\frac{k p + 1}{a}$ ，它大于1024-16=1008位，1的逆元当然是1。在同样不考虑1出现在epart中后，原始矩阵的逆矩阵中每个数都很大。
这样，因为我们知道 $x_{30} > x_{29} ， y_{30} > y_{29}$ ，我们只需找出合适的矩阵，模乘逆矩阵后得到的 $(x_{29}, y_{29})$ 满足上式即可。由于最初cat选择的第30个矩阵一定满足，所以至少有一个解。最后我们分析出现多个解的概率。
由上可知，逆矩阵中每个元素都很大，因此它们之间间隔也很大，可以看作是随机选择的矩阵。由于最终结果约736位，故期望的倒数第二步结果小于736位。给定最终的 $(x_{30}, y_{30})$ ， $(x_{29}, y_{29})$ 满足条件的概率为 $(\frac{2^{736}}{2^{1024}})^{2}$ ，因此，除了内定的一个解，在125个矩阵中出现其他解的概率同样极小。这样，只要遍历125个矩阵的逆矩阵，每次都寻找一个，使得倒推的向量中，每一个分量都小于前一步向量的分量，找到30次回到原点，就得到了part的逆序，倒序发送即可。

from ast import literal_eval
from typing import List, Tuple

from Crypto.Util.number import getPrime


def find_candidate_prev_points(
        mind: bytes,
        endpoint: Tuple[int, int],
        limit: int
) -> List[Tuple[int, int, int]]:
    """
    For each 8-byte part in 'mind', treat it as a 2x2 matrix over F_p (p=limit),
    compute its inverse, apply it to 'endpoint', and collect those previous points
    whose coordinates are both strictly less than the corresponding coordinates of endpoint.

    Returns a list of tuples: (index, prev_x, prev_y).
    """
    x_n, y_n = endpoint
    candidates = []

    for i in range(125):
        part = mind[i * 8:(i + 1) * 8]
        e0 = int.from_bytes(part[0:2], "big") % limit
        e1 = int.from_bytes(part[2:4], "big") % limit
        e2 = int.from_bytes(part[4:6], "big") % limit
        e3 = int.from_bytes(part[6:8], "big") % limit

        det = (e0 * e3 - e1 * e2) % limit
        if det == 0:
            continue

        det_inv = pow(det, -1, limit)
        inv_a = (e3 * det_inv) % limit
        inv_b = (-e1 * det_inv) % limit
        inv_c = (-e2 * det_inv) % limit
        inv_d = (e0 * det_inv) % limit

        prev_x = (inv_a * x_n + inv_b * y_n) % limit
        prev_y = (inv_c * x_n + inv_d * y_n) % limit

        if prev_x < x_n and prev_y < y_n:
            candidates.append((i, prev_x, prev_y))

    return candidates


def recover_mind_sequence(
        mind: bytes,
        start: Tuple[int, int],
        end: Tuple[int, int],
        limit: int,
        steps: int = 30
) -> List[bytes]:
    """
    Reverse-engineer the sequence of 'parts' used by the cat to move from 'start' to 'end'.
    Returns the list of 8-byte parts in forward order.
    """
    current = end
    seq_indices = []
    seq_coords = []

    for step in range(steps):
        candidates = find_candidate_prev_points(mind, current, limit)
        if len(candidates) != 1:
            raise ValueError(f"Step {step + 1}: expected 1 candidate, found {len(candidates)}")
        idx, prev_x, prev_y = candidates[0]
        seq_indices.append(idx)
        seq_coords.append((prev_x, prev_y))
        current = (prev_x, prev_y)

    # Verify we reached the start coordinate
    if current != start:
        raise ValueError(f"After reverse ({steps} steps), reached {current}, expected start {start}")

    # Reverse indices to forward order and extract parts
    seq_indices.reverse()
    recovered_parts = [mind[i * 8:(i + 1) * 8] for i in seq_indices]
    return recovered_parts


def simulate_walking_sequence(
        start: Tuple[int, int],
        parts: List[bytes]
) -> Tuple[int, int]:
    """
    Simulate the cat's walking forward using the recovered parts to verify correctness.
    """
    x, y = start
    for part in parts:
        # parse matrix
        e0 = int.from_bytes(part[0:2], "big")
        e1 = int.from_bytes(part[2:4], "big")
        e2 = int.from_bytes(part[4:6], "big")
        e3 = int.from_bytes(part[6:8], "big")
        xx = e0 * x + e1 * y
        yy = e2 * x + e3 * y
        x, y = xx, yy
    return (x, y)


if __name__ == "__main__":
    import os
    from pwn import *

    conn = remote('catch.chal.idek.team', 1337)

    for iter in range(20):
        conn.recvuntil(b'Co-location: ')
        x0, y0 = literal_eval(conn.recvline().decode())
        #print(x0, y0)
        conn.recvuntil(b'Cat\'s hidden mind: ')
        mind_hex = conn.recvline().decode()
        mind = bytes.fromhex(mind_hex)
        conn.recvuntil(b'Cat now at: ')
        xn, yn = literal_eval(conn.recvline().decode())
        limit = 0xe5db6a6d765b1ba6e727aa7a87a792c49bb9ddeb2bad999f5ea04f047255d5a72e193a7d58aa8ef619b0262de6d25651085842fd9c385fa4f1032c305f44b8a4f92b16c8115d0595cebfccc1c655ca20db597ff1f01e0db70b9073fbaa1ae5e489484c7a45c215ea02db3c77f1865e1e8597cb0b0af3241cd8214bd5b5c1491f

        conn.recvuntil(b'Path to recall (hex):')
        parts = recover_mind_sequence(mind, (x0, y0), (xn, yn), limit)
        print("Recovered sequence of indices and parts:")
        sendpart = ''.join(part.hex() for part in parts)
        print(sendpart)

        # Verify forward simulation
        simulated_end = simulate_walking_sequence((x0, y0), parts)
        #print("Simulated end:", simulated_end)
        #print("Original end: ", (xn, yn))
        if simulated_end == (xn, yn):
            print("Verification passed!")
        else:
            print("Verification failed.")

        conn.sendline(sendpart.encode())

    conn.interactive()

#idek{Catch_and_cat_sound_really_similar_haha}
#By the way, 这个limit换成其他的大质数也可以过关，只要比x_30和y_30大就可以了。

diamond ticket

题目如下。

from Crypto.Util.number import *

#Some magic from Willy Wonka
p = 170829625398370252501980763763988409583
a = 164164878498114882034745803752027154293
b = 125172356708896457197207880391835698381

def chocolate_generator(m:int) -> int:
    return (pow(a, m, p) + pow(b, m, p)) % p

#The diamond ticket is hiding inside chocolate
diamond_ticket = open("flag.txt", "rb").read()
assert len(diamond_ticket) == 26
assert diamond_ticket[:5] == b"idek{"
assert diamond_ticket[-1:] == b"}"
diamond_ticket = bytes_to_long(diamond_ticket[5:-1])

flag_chocolate = chocolate_generator(diamond_ticket)
chocolate_bag = []

#Willy Wonka are making chocolates
for i in range(1337):
    chocolate_bag.append(getRandomRange(1, p))

#And he put the golden ticket at the end
chocolate_bag.append(flag_chocolate)

#Augustus ate lots of chocolates, but he can't eat all cuz he is full now :D
remain = chocolate_bag[-5:]

#Compress all remain chocolates into one
remain_bytes = b"".join([c.to_bytes(p.bit_length()//8, "big") for c in remain])

#The last chocolate is too important, so Willy Wonka did magic again
P = getPrime(512)
Q = getPrime(512)
N = P * Q
e = bytes_to_long(b"idek{this_is_a_fake_flag_lolol}")
d = pow(e, -1, (P - 1) * (Q - 1))
c1 = pow(bytes_to_long(remain_bytes), e, N)
c2 = pow(bytes_to_long(remain_bytes), 2, N) # A small gift

#How can you get it ?
print(f"{N = }")
print(f"{c1 = }")
print(f"{c2 = }") 

"""
N = 85494791395295332945307239533692379607357839212287019473638934253301452108522067416218735796494842928689545564411909493378925446256067741352255455231566967041733698260315140928382934156213563527493360928094724419798812564716724034316384416100417243844799045176599197680353109658153148874265234750977838548867
c1 = 27062074196834458670191422120857456217979308440332928563784961101978948466368298802765973020349433121726736536899260504828388992133435359919764627760887966221328744451867771955587357887373143789000307996739905387064272569624412963289163997701702446706106089751532607059085577031825157942847678226256408018301
c2 = 30493926769307279620402715377825804330944677680927170388776891152831425786788516825687413453427866619728035923364764078434617853754697076732657422609080720944160407383110441379382589644898380399280520469116924641442283645426172683945640914810778133226061767682464112690072473051344933447823488551784450844649
"""

一道充满着“特别”的题目，每一个数据都是精心给出的。
拿到题目，先读一下巧克力工厂的故事，flag开头和结尾共6 bytes已给出，中间20 bytes未知。列表chocolate_bag加入了1337个1~p的随机数，又加入了 $(a^{flag} + b^{flag}) mod p$ 的值——看起来又是一个离散对数，而且不是普通的离散对数。
生成结束后，remain仅包含最后5个数，所幸包含flag信息的项是最后一项，它保留了下来。将这5项转化为16*5=80 bytes的字节串并拼接，最后是一个RSA加密。
因此，如果没有意外，我们的大致逻辑应该是解密RSA -> 提取flag_chocolate -> 还原diamond_ticket 。这样做也确实能够得到答案。

第1步：解密RSA
已知 $m^{e} mod N$ 和 $m^{2} mod N$ ，且 $m$ 是一个80*8=640bit的数， $m^{2}$ 也有1280位，爆破高256位不现实。由于e是一个247位的奇数， $gcd (e, 2) = 1$ ，我们用 $m^{2}$ 和 $m^{e}$ 凑出 $m^{1}$ 。可以构造 $m^{1} = m^{1 * e - \frac{e - 1}{2} * 2} = m^{e} * (m^{2})^{- \frac{e - 1}{2}}$ ，模 $N$ 下运算得到 $m$ 。

第2步：提取flag_chocolate
我们只要最后一项，故提取最后16个byte，咱图省事就全部一起提取了，并输出chunks的最后一个元素。

第3步：还原diamond_ticket
此时我们拥有等式 $(a^{flag} + b^{flag}) mod p = c$ ，已知a, b, c, p，求flag。在咨询了Deepseek等AI并通过代码验证后，我们发现了给定的a, b, p有一些有趣的性质——
$p$ 是一个质数，但 $p - 1 = 2 \times 40841 \times 50119 \times 51193 \times 55823 \times 57809 \times 61991 \times 63097 \times 64577$ ，是很多小素数之积（ $p - 1$ 是光滑数）。
$a$ 和 $b$ 的阶均为 $\frac{p - 1}{2}$ ，且 $b = a^{73331} mod p$
因此，对于问题 $(a^{flag} + b^{flag}) mod p = c$ ，将其转化为 $((a^{flag} + (a^{flag})^{73331}) - c) mod p = 0$ ，即寻找 $f (x) = x^{73331} + x - c$ 的一个根 $x_{0}$ 。一旦找到这个根，它就是 $a^{flag}$ ，转化为普通的离散对数，再利用Pohlig-Hellman算法，求得阶为光滑数的离散对数。
使用cypari库对该函数进行求根，相比sage的roots()函数，它快得多，只需要十多秒就能得到答案。再利用sage自带的discrete_log()函数求解即可得到flag。

……真的吗？
将求出的 x = 4807895356063327854843653048517090061 转换成bytes后不都是可打印字符，说明我们还有路没走完，但是 assert chocolate_generator(x) == c 也通过了，说明我们确实找到了正确的一个x。
求一下x的位数，它有122位，而diamond_ticket有20*8=160位。由于 $a$ , $b$ 的阶相等，故 $a^{\frac{p - 1}{2}} mod p = b^{\frac{p - 1}{2}} mod p = 1$ ，因此除了 $x$ 以外，所有 $x + k * \frac{p - 1}{2}$ 也都是可能的diamond_ticket， $k$ 为正整数。
对于该取什么 $k$ 没有好的办法，一共20 bytes（160位），最高位的byte最多是0x7E(01111110)，故diamond_ticket最多有159位；最少是0x20(00100000)，diamond_ticket最少也有158位。根据 $diamond_ticket = x + k * \frac{p - 1}{2}$ 可知 $k$ 至少为31位，最多为32位，我们遍历k in range(2**31, 2**33)即可。由于数据过大，采用多线程并行加速，实测本机32线程约20分钟。
以及，我的多线程写得一团糟，把起点修改为 $2^{31}$ 就给不出结果，所以代码是从 $0$ 遍历到 $2^{33}$ ，多花了约 $\frac{1}{4}$ 的时间。

#####################################################
#python

from Crypto.Util.number import *

N = 85494791395295332945307239533692379607357839212287019473638934253301452108522067416218735796494842928689545564411909493378925446256067741352255455231566967041733698260315140928382934156213563527493360928094724419798812564716724034316384416100417243844799045176599197680353109658153148874265234750977838548867
c1 = 27062074196834458670191422120857456217979308440332928563784961101978948466368298802765973020349433121726736536899260504828388992133435359919764627760887966221328744451867771955587357887373143789000307996739905387064272569624412963289163997701702446706106089751532607059085577031825157942847678226256408018301
c2 = 30493926769307279620402715377825804330944677680927170388776891152831425786788516825687413453427866619728035923364764078434617853754697076732657422609080720944160407383110441379382589644898380399280520469116924641442283645426172683945640914810778133226061767682464112690072473051344933447823488551784450844649
e = 186211850710224327090212578283834164039515361235211653610924153794366237821
# 已知量：N, e, c1, c2

# 计算 temp = (e-1)//2
temp = (e - 1) // 2

# 先算 t = c2^temp mod N
t = pow(c2, temp, N)

# 再算 t 的模反元素 inv_t = t^{-1} mod N
inv_t = inverse(t, N)

# 最后 m = c1 * inv_t mod N
m = (c1 * inv_t) % N

assert pow(m,e,N) == c1
assert pow(m,2,N) == c2

# 将整数 m 转成字节串
remain_bytes = long_to_bytes(m)

print(remain_bytes)
#b'{\xd1\xdf\xeb|F\xce\xbc\x11\xd8nZ\x8b\xfc\xaebN\xf4\x8a{0,\x01\xb7\xf9\xe7\xb5q\xc93%\xba\x0b\x15\x94g\x0b|\xd8 \xf38\xf2\xe2#\t\x0ci^\x10\x86\x94\x12\xcb\xe7b/\xefj\xb5\x05\xfb\xc8\xf9J\xebU|z\x10\xd3|\xa7\xec\xd1\x9d\x17\\P\xb3'
#其中\\表示一个反斜杠，算一个byte

#Some magic from Willy Wonka
p = 170829625398370252501980763763988409583
a = 164164878498114882034745803752027154293
b = 125172356708896457197207880391835698381

L = p.bit_length() // 8   # =128//8 =16
chunks = [remain_bytes[i*L:(i+1)*L] for i in range(5)]
print(bytes_to_long(chunks[-1]))
#99584795316725433978492646071734128819

#####################################################
#sage

def chocolate_generator(m:int) -> int:
    return (pow(a, m, p) + pow(b, m, p)) % p

c = 99584795316725433978492646071734128819

import cypari2
pari = cypari2.Pari()

def roots_mod_p_via_pari(k, c, p):

    y = pari('y')
    f = y**k + y - c
    return list(map(int, pari(f).polrootsmod(p)))

k = 73331
roots = roots_mod_p_via_pari(k, c, p)
print("roots:", roots)
#[126961729658296101306560858021273501485]

a = 164164878498114882034745803752027154293
for y in roots:
    # 把 a, y 视为 GF(p) 中的元素
    F = GF(p)
    A = F(a)
    Y = F(y)
    # 调用 discrete_log
    x = discrete_log(Y, A)
    assert chocolate_generator(x) == c
    print("解得 x =", x)
#4807895356063327854843653048517090061

#####################################################
#python

def is_all_printable(bs: bytes) -> bool:
    return all(0x20 <= b <= 0x7E for b in bs)

import multiprocessing
# 上一部分结果
BASE = 4807895356063327854843653048517090061
from tqdm import tqdm
import os

# 子任务：在给定区间内查找满足条件的 j
def worker(start: int, end: int, queue):
    results = []
    for j in range(start, end):
        val = BASE + (p-1)//2 * j
        text = long_to_bytes(val)
        if is_all_printable(text):
            results.append((j, text))
        if j % 10000 == 0:
            queue.put(10000)
    return results

if __name__ == '__main__':
    multiprocessing.set_start_method('spawn')  # For compatibility, especially on Windows
    cpu_count = multiprocessing.cpu_count()
    total = 2**33
    chunk = total // cpu_count

    # 使用 Manager 和 Queue 跟踪进度
    with multiprocessing.Manager() as manager:
        queue = manager.Queue()
        pool = multiprocessing.Pool(processes=cpu_count)

        # 用 tqdm 显示总进度
        with tqdm(total=total, desc="Brute-forcing", unit="j") as pbar:
            results = []
            tasks = []
            for i in range(cpu_count):
                start = i * chunk
                end = start + chunk if i < cpu_count - 1 else total
                tasks.append(pool.apply_async(worker, (start, end, queue)))

            # 实时更新进度条
            finished = 0
            while finished < total:
                inc = queue.get()
                pbar.update(inc)
                finished += inc

            # 等待所有任务完成并收集结果
            pool.close()
            pool.join()

            for task in tasks:
                for j, text in task.get():
                    print(f"Found j={j}: {text}")
                    #Found j=7781310273: b'tks_f0r_ur_t1ck3t_xD'
#idek{tks_f0r_ur_t1ck3t_xD}

RE

construction

附件是一个elf程序，试验得知，当没有参数时，输出👀，有参数时，输出Wrong! ，搜索字符串发现：

1 2	.rodata:0000000000403013 aCorrect db 'Correct!',0 ; DATA XREF: sub_401050:loc_401159↑o .rodata:000000000040301C aWrong db 'Wrong!',0 ; DATA XREF: sub_401050+CE↑o

推测主函数是sub_401050，找到该函数：

unsigned __int64 __fastcall sub_401050(__int64 a1, __int64 a2, __int64 a3, __int64 a4, __int64 a5, __int64 a6)
{
  __int64 v6; // rcx
  unsigned __int64 i; // rax
  int v8; // edx
  __int64 v9; // rdx
  int v10; // eax
  unsigned int v11; // ebp
  signed __int64 v12; // r12
  unsigned __int8 *v13; // rax
  unsigned __int64 result; // rax
  char v15[24]; // [rsp+0h] [rbp-1038h] BYREF
  unsigned __int64 v16; // [rsp+1008h] [rbp-30h]

  LODWORD(v6) = 0;
  v16 = __readfsqword(0x28u);
  for ( i = 0; i != 42; ++i )
  {
    v8 = v6 ^ (unsigned __int8)::a3[i];
    v6 += 31;
    v9 = (i >> 1) ^ v8 ^ 0x5A;
    byte_405140[i] = v9;
  }
  byte_40516A = 0;
  v10 = sub_401670((__int64)"/proc/self/cmdline", 0, v9, v6, a5, a6, v15[0]);
  v11 = v10;
  if ( v10 >= 0 )
  {
    v12 = sub_401A10((unsigned int)v10, v15, 4095);
    sub_4019C0(v11);
    if ( v12 > 0 )
    {
      v15[v12] = 0;
      v13 = sub_401830(v15, 0, v12);
      if ( v13 )
      {
        if ( v13 + 1 < (unsigned __int8 *)&v15[v12] )
        {
          if ( (unsigned int)sub_401910(v13 + 1, byte_405140) )
            sub_401770("Wrong!");
          else
            sub_401770("Correct!");
          sub_401010(0);
        }
      }
    }
  }
  result = v16 - __readfsqword(0x28u);
  if ( result )
    sub_401610();
  return result;
}

因此，正确答案的生成过程是

LODWORD(v6) = 0;
for ( i = 0; i != 42; ++i )
{
  v8 = v6 ^ (unsigned __int8)::a3[i];
  v6 += 31;
  v9 = (i >> 1) ^ v8 ^ 0x5A;
  byte_405140[i] = v9;
}

分析它太麻烦了，直接动态调试到这个位置，提取byte_405140如下。

.bss:0000000000405140 ; _BYTE byte_405140[42]
.bss:0000000000405140 byte_405140 db 69h, 64h, 65h, 6Bh, 7Bh, 68h, 65h, 34h, 72h, 64h, 5Fh, 30h, 66h, 5Fh
.bss:0000000000405140                                         ; DATA XREF: sub_401050+1C↑o
.bss:000000000040514E db 63h, 6Fh, 6Eh, 73h, 74h, 72h, 75h, 63h, 74h, 6Fh, 72h, 73h, 3Fh, 5Fh
.bss:000000000040515C db 6Eh, 6Fh, 77h, 5Fh, 79h, 6Fh, 75h, 5Fh, 64h, 31h, 64h, 21h, 21h, 7Dh
.bss:000000000040516A byte_40516A db 0                        ; DATA XREF: sub_401050+6C↑w

续上后面的byte_40516A = 0;，直接可以在IDA中整合成字符串：

1 2	.bss:0000000000405140 aIdekHe4rd0fCon db 'idek{he4rd_0f_constructors?_now_you_d1d!!}',0 .bss:0000000000405140 ; DATA XREF: sub_401050+1C↑o

于是我们已经找到了——idek{he4rd_0f_constructors?_now_you_d1d!!}

但是这太快了，于是水一下wp（×）

对输入的判定过程是

if ( (unsigned int)sub_401910(v13 + 1, byte_405140) )
  sub_401770("Wrong!");
else
  sub_401770("Correct!");

中间就是截取输入的过程

v10 = sub_401670((__int64)"/proc/self/cmdline", 0, v9, v6, a5, a6, v15[0]);
v11 = v10;
if ( v10 >= 0 )
{
  v12 = sub_401A10((unsigned int)v10, v15, 4095);
  sub_4019C0(v11);
  if ( v12 > 0 )
  {
    v15[v12] = 0;
    v13 = sub_401830(v15, 0, v12);
    ...

判定输入的函数 sub_401910 是

__int64 __fastcall sub_401910(unsigned __int8 *a1, unsigned __int8 *a2)
{
  unsigned __int8 v2; // dl
  int v3; // ecx
  __int64 v4; // rax

  v2 = *a1;
  v3 = *a2;
  v4 = 1;
  if ( *a1 != (_BYTE)v3 )
    return (unsigned int)v2 - v3;
  while ( v2 )
  {
    v2 = a1[v4++];
    v3 = a2[v4 - 1];
    if ( v2 != (_BYTE)v3 )
      return (unsigned int)v2 - v3;
  }
  return (unsigned int)-v3;
}

其要求 *a1 和 *a2 每一位都要相等，如果有不等的位，则返回他们的差值；如果v3更长，则返回v2结束后的第一个v3的位。由于我们已知作为字符串末尾的byte_40516A是0，因此唯一能让这个判定返回0的方法是，输入的长度与v13相等，且每一位都一样，这样返回的就是字符串末尾的0。

因此，根据前面的提取数据过程，最后应该输入idek{he4rd_0f_constructors?_now_you_d1d!!}，这就是flag。

Misc

Gacha gate

题目如下。

#!/usr/bin/env python3
import contextlib
import os
import random
import re
import signal
import sys

from z3 import ArithRef, BitVec, BitVecRef, BitVecVal, Solver, simplify, unsat

WIDTH = 32
OPS = ['~', '&', '^', '|']
MAX_DEPTH = 10
FLAG = os.getenv('FLAG', 'idek{fake_flag}')
VARS = set('iIl')


def rnd_const() -> tuple[str, BitVecRef]:
    v = random.getrandbits(WIDTH)
    return str(v), BitVecVal(v, WIDTH)


def rnd_var() -> tuple[str, BitVecRef]:
    name = ''.join(random.choices(tuple(VARS), k=10))
    return name, BitVec(name, WIDTH)


def combine(
    op: str,
    left: tuple[str, BitVecRef],
    right: tuple[str, BitVecRef] | None = None,
) -> tuple[str, ArithRef]:
    if op == '~':
        s_left, z_left = left
        return f'(~{s_left})', ~z_left
    s_l, z_l = left
    s_r, z_r = right
    return f'({s_l} {op} {s_r})', {
        '&': z_l & z_r,
        '^': z_l ^ z_r,
        '|': z_l | z_r,
    }[op]


def random_expr(depth: int = 0) -> tuple[str, ArithRef]:
    if depth >= MAX_DEPTH or random.random() < 0.1:
        return random.choice((rnd_var, rnd_const))()
    op = random.choice(OPS)
    if op == '~':
        return combine(op, random_expr(depth + 1))
    return combine(op, random_expr(depth + 1), random_expr(depth + 1))


TOKEN_RE = re.compile(r'[0-9]+|[iIl]+|[~&^|]')


def parse_rpn(s: str) -> ArithRef:
    tokens = TOKEN_RE.findall(s)
    if not tokens:
        raise ValueError('empty input')

    var_cache: dict[str, BitVecRef] = {}
    stack: list[BitVecRef] = []

    for t in tokens:
        if t.isdigit():
            stack.append(BitVecVal(int(t), WIDTH))
        elif re.fullmatch(r'[iIl]+', t):
            if t not in var_cache:
                var_cache[t] = BitVec(t, WIDTH)
            stack.append(var_cache[t])
        elif t in OPS:
            if t == '~':
                if len(stack) < 1:
                    raise ValueError('stack underflow')
                a = stack.pop()
                stack.append(~a)
            else:
                if len(stack) < 2:
                    raise ValueError('stack underflow')
                b = stack.pop()
                a = stack.pop()
                stack.append({'&': a & b, '^': a ^ b, '|': a | b}[t])
        else:
            raise ValueError(f'bad token {t}')

    if len(stack) != 1:
        raise ValueError('malformed expression')
    return stack[0]


def equivalent(e1: ArithRef, e2: ArithRef) -> tuple[bool, Solver]:
    s = Solver()
    s.set(timeout=5000)
    s.add(simplify(e1) != simplify(e2))
    return s.check() == unsat, s


def _timeout_handler(_: int, __) -> None:
    raise TimeoutError


def main() -> None:
    signal.signal(signal.SIGALRM, _timeout_handler)
    print('lets play a game!')

    for _ in range(50):
        random.seed()
        expr_str, expr_z3 = random_expr()
        print(expr_str, flush=True)

        signal.alarm(5)
        try:
            line = sys.stdin.readline()
            signal.alarm(0)
        except TimeoutError:
            print('too slow!')
            return

        try:
            rpn_z3 = parse_rpn(line.strip())
        except Exception as e:
            print('invalid input:', e)
            return

        print('let me see..')
        is_eq, s = equivalent(expr_z3, rpn_z3)
        if not is_eq:
            print('wrong!')
            with contextlib.suppress(BaseException):
                print('counter example:', s.model())
            return

    print(FLAG)


if __name__ == '__main__':
    main()

咱倒是没想到一个misc题居然这么好心，完成了任务就真的给你flag。

这题目像是给大学生准备的（笑）题目给出一个中缀表达式，要求给出它对应的后缀表达式，并检验是否等效，规定时间内通过50次检验就能得到flag。中缀转后缀，只要学过数据结构或者算法的都应该能写出来，再不济让ChatGPT写，它很擅长做这种大学课后习题
对于一个表达式 '((~((~1925064568) ^ (~(~(348138675 & IIiIlIillI))))) & (~(~(((iIllIIIIII & 648807684) | (4074926542 | iIilIIIiiI)) | (iiiiIIliIl ^ (203353170 ^ 3427631998))))))'，转成后缀表达式(RPN)需要先划词为'(', '~', '1925064568'等token，借助一个栈，将符号按照优先级移到操作数的后面，由于本题生成的表达式均有括号包裹，可以避免^&|~这四种符号的优先级问题。对于括号，每当遇到')'时，就从栈内弹出符号直到匹配'('，这两者中间的表达式就可以直接移动符号。
上述表达式转换后为 '1925064568 ~ 348138675 IIiIlIillI & ~ ~ ^ ~ iIllIIIIII 648807684 & 4074926542 iIilIIIiiI | | iiiiIIliIl 203353170 3427631998 ^ ^ | ~ ~ &' 。
signal.alarm(5)表示5秒后进入超时处理部分，本题只是简单抛出TimeoutError，经由main函数捕获后告知'too slow!'，手动计算并复制到命令行不易且容易出错，交由pwntool库自动交互完成。
使用recvline()接收一行，recvuntil()接收直到指定的字节串，sendline()发送一行字节串。注意所有发送和接收到的都是字节，可以使用decode()方法变为字符串。交互不难！使用合适的方法，获取关键信息，加以处理，再传回去~

from pwn import *
import re

# 用于将输入字符串切分成 token
TOKEN_RE = re.compile(r'([0-9]+|[iIl]+|[~&^|]|\(|\))')

def tokenize(expr: str) -> list[str]:
    """
    将中缀表达式字符串拆分成 token 列表。
    支持：
      - 十进制整数，如 1234
      - 由 i, I, l 构成的变量名，如 iiIIlI
      - 单字符运算符 ~ & ^ |
      - 括号 ( )
    """
    tokens = TOKEN_RE.findall(expr)
    if ''.join(tokens) != expr.strip().replace(' ', ''):
        raise ValueError("非法字符或格式错误")
    return tokens

def infix_to_rpn(expr: str) -> str:
    """
    将中缀表达式 expr 转成逆波兰表达式，
    返回一个以空格分隔的 RPN 字符串。
    """
    tokens = tokenize(expr)
    # 运算符优先级
    prec = {'~': 4, '&': 3, '^': 2, '|': 1}
    # 一元运算符 ~ 右结合，二元运算符左结合
    right_assoc = {'~'}

    output: list[str] = []
    ops: list[str] = []

    for t in tokens:
        if re.fullmatch(r'\d+|[iIl]+', t):
            # 数字或变量
            output.append(t)

        elif t in prec:
            # 运算符
            while ops and ops[-1] in prec:
                top = ops[-1]
                if (prec[top] > prec[t] or
                        (prec[top] == prec[t] and t not in right_assoc)):
                    output.append(ops.pop())
                else:
                    break
            ops.append(t)

        elif t == '(':
            ops.append(t)

        elif t == ')':
            # 弹出直到左括号
            while ops and ops[-1] != '(':
                output.append(ops.pop())
            if not ops or ops[-1] != '(':
                raise ValueError("括号不匹配")
            ops.pop()  # 丢弃 '('

        else:
            raise ValueError(f"未知 token: {t}")

    # 最后把剩余运算符都弹出
    while ops:
        if ops[-1] in ('(', ')'):
            raise ValueError("括号不匹配")
        output.append(ops.pop())

    return ' '.join(output)

conn = remote('gacha-gate.chal.idek.team', 1337)
context.log_level = 'debug'
conn.recvuntil(b'lets play a game!\n')
for i in range(50):
    expression = conn.recvline().decode()
    #print(f'expression: {expression}')
    ans = infix_to_rpn(expression)
    conn.sendline(ans.encode())
    conn.recvuntil(b'let me see..\n')
conn.interactive()

后记

太弱啦太弱啦！crypto和re双修的我根本做不出来几道呢，我很想看看那几道椭圆曲线的题目是如何解的，一点思路都没有，以及那个5美元外包的vm，虽然已经有一些进展了（指看到了输入 i 可以调出寄存器），但是后面的工程似乎还很大，猪脑过载了喵>_<

等大手子师傅的wp（躺