大家在开赛后临时创号玩的，二进制哥们很忙，于是我们就做了一些别的题，但也遗憾在这里，只靠密码，前 24h 便来到第九名，后续没题可做了

最终 22 名，还不错

质量不错，也许值 65+ 权重

另外，本场比赛遇到不少 Golang 可能遇到的问题，并解决了

博客还在调试，图片显示可能存在问题，在寻找一个好用的对象存储

idekCTF 2025 Write-ups / Challenge List

题目名称前带 * 的为赛后做出的

sanity

check

签到

survey

问卷

rev

constructor

静态分析

$\text{decrypted}[i] = \text{encrypted}[i] \bigoplus (i * \text{0x1f}) \bigoplus (i >> 1) \bigoplus \text{0x5a}$

i * 0x1f 的计算结果会发生溢出，我们只需取其低8位即可，这和寄存器 cl 的行为一致

随后导出加密数据

使用 dd 导出 42 byte

dd if=./chall bs=1 skip=$((0x3040)) count=42 2>/dev/null | xxd -i

Exploit

def solve_flag():
    """
    Applies the decryption algorithm found in the binary's constructor
    function to the extracted data.
    """
    # The 42 encrypted bytes from address 0x403040
    encrypted_flag = [
      0x33, 0x21, 0x00, 0x6d, 0x5f, 0xab, 0x86, 0xb4, 0xd4, 0x2d, 0x36, 0x3a,
      0x4e, 0x90, 0x8c, 0xe3, 0xcc, 0x2e, 0x09, 0x6c, 0x49, 0xb8, 0x8f, 0xf7,
      0xcc, 0x22, 0x4e, 0x4d, 0x5e, 0xb8, 0x80, 0xcb, 0xd3, 0xda, 0x20, 0x29,
      0x70, 0x02, 0xb7, 0xd1, 0xb7, 0xc4
    ]

    decrypted_flag = ""
    mask32 = 0xFFFFFFFF  # Used to simulate 32-bit register behavior
    key1_register = 0    # Simulates the %ecx register

    for i in range(42):
        # The encrypted byte is loaded into the low part of a 32-bit register
        encrypted_word = encrypted_flag[i]
        
        # Key 1: The full 32-bit value of the %ecx register
        key1 = key1_register
        
        # Key 2: The loop counter right-shifted by 1
        key2 = i >> 1
        
        # constant
        key3 = 0x5a
        
        # The decryption emulates the 32-bit 'xorl' operations
        decrypted_word = encrypted_word ^ key1 ^ key2 ^ key3
        
        # The final character is the lowest byte of the result
        decrypted_byte = decrypted_word & 0xFF
        decrypted_flag += chr(decrypted_byte)
        
        # The %ecx register is incremented for the next loop
        key1_register = (key1_register + 0x1f) & mask32

    return decrypted_flag

final_flag = solve_flag()
print(f"Decrypted Flag: {final_flag}")

ski

又出现和 CryptoCTF 类似的情况，正规子群 CN 分群看了好几次都没做出来，越南老哥薄纱了

Given a SKI combinator program (program.txt) and an interpreter, the challenge encodes the flag as bits, mapping each bit to a variable (_F0, _F1, …). Each _F{i} is set to K if the bit is 1, or (K I) if 0.

The SKI expression is a sequence of similar blocks, each containing several _F… variables. The number of _F… variables in each block corresponds to a specific bit pattern.

focus on the final part of txt file from here: (((S ((S I) (K (K I)))) (K K)) _F0)) _F1)) _F2))...

Each check block has the form (((S ((S I) (K (K I)))) (K K)) … ) and inside, the number of _F… variables determines the bit pattern to check:

• 1 variable: checks for bit pattern 0
• 2 variables: checks for 01
• 3 variables: checks for 011
• 4 variables: checks for 0111 etc.

script:

Exploit

import re

data = open("program.txt").read()
segments = re.split(r"\(\(\(S", data)
pattern_map = {1: "0", 2: "01", 3: "011", 4: "0111", 5: "01111", 6: "011111"}

bits = "".join(pattern_map[len(re.findall(r"_F\d+", seg))] for seg in segments if re.findall(r"_F\d+", seg))
flag = "".join(chr(int(bits[i:i+8], 2)) for i in range(0, len(bits), 8) if len(bits[i:i+8]) == 8)
print(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()

其核心任务是将服务器生成的 中缀表达式（Infix Expression） 转换为 逆波兰表达式（Reverse Polish Notation, RPN）。服务器使用Z3求解器来验证玩家的转换是否正确，这意味着需要严格遵守逻辑等价性。

中缀表达式与逆波兰表达式

• 中缀表达式：我们日常使用的数学表达式，如 $A + B$ 或 $(A \land B) \lor C$。运算符位于其操作数之间。
• 逆波兰表达式（RPN）：又称后缀表达式，如 $A B +$ 或 $A B \land C \lor$。运算符位于其操作数之后。

中缀表达式存在优先级和结合性的问题，需要括号来消除歧义。例如，$A \lor B \land C$ 究竟是 $(A \lor B) \land C$ 还是 $A \lor (B \land C)$？这取决于运算符的优先级。RPN 表达式则天然地消除了这种歧义，因为运算符的顺序严格定义了计算顺序。

本题中的表达式使用了位运算符：| (或), ^ (异或), & (与), ~ (非)。它们的优先级关系为：~ > & > ^ > |。

核心算法：调度场算法 (Shunting-yard Algorithm)

下面 Exploit 的核心是 shunting_yard_fix 函数，它实现了调度场算法。这个算法就像一个火车站的调度场：

• 输入（轨道）: 中缀表达式的符号流（token）。
• 输出（出库）: RPN 表达式的符号流。
• 中转站（栈）: 一个用于临时存放运算符的栈。

调度场算法的数学逻辑严格基于运算符的 优先级（precedence） 和 结合性（associativity）。

算法流程

1. 分词（Tokenization）: 首先，将中缀表达式字符串分解成一个个独立的符号（tokens），包括数字、变量、运算符和括号。

   • 例如，表达式 ((A & B) | C) 被分解为 (, (, A, &, B, ), |, C, )。

2. 符号流处理: 算法逐一处理每个 token，并根据其类型采取不同的行动。

   • 操作数 (Operand): 如果 token 是一个操作数（数字或变量），直接将其发送到输出队列（output 列表）。

     • 这遵循 RPN 的基本规则：操作数先于其运算符出现。

   • 左括号 (: 将左括号压入运算符栈（op_stack）。

     • 括号在表达式中起着改变运算顺序的作用。将它压栈，意味着它是一个“屏障”，阻止在它内部的运算被提前执行。

   • 右括号 ): 从运算符栈中不断弹出运算符并发送到输出队列，直到遇到一个左括号为止。然后弹出这个左括号，但不会发送到输出队列。

     • 这保证了括号内的所有运算都在括号外部的运算之前完成。当遇到右括号时，表示一个子表达式已经结束，可以将其所有运算符结算。

   • 运算符 (Operator): 这是算法中最复杂的部分，它依赖于优先级规则。

     • 优先级比较: 算法会比较当前运算符和栈顶运算符的优先级。
     • 如果栈顶是运算符，且其优先级 ≥ 当前运算符的优先级，则将栈顶运算符弹出并发送到输出队列。
     • 这个过程会一直重复，直到栈为空，或者栈顶是左括号，或者栈顶运算符的优先级低于当前运算符。
     • 这个逻辑保证了高优先级的运算符（例如 &）在低优先级的运算符（例如 |）之前被处理。
     • 处理完高优先级运算符后，将当前运算符压入栈。

3. 清栈: 当所有 token 都处理完毕后，运算符栈中可能还有剩余的运算符。将栈中所有剩余的运算符依次弹出并发送到输出队列。

   • 这确保了所有未被括号限定的运算符（即优先级最低的那些）在最后被结算。

示例：((A & B) | C) 的转换过程

最终得到的 RPN 表达式为 A B & C |，与中缀表达式的逻辑等价。

通过这种方式，shunting_yard_fix 函数将中缀表达式的结构和优先级信息，精确地映射到了 RPN 表达式的顺序中。这是一种严谨的数学转换，确保了表达式的逻辑等价性，从而满足了服务器Z3求解器的验证要求。

#!/usr/bin/env python3

from pwn import *
import re

# remote connection
HOST = 'gacha-gate.chal.idek.team'
PORT = 1337

# Operator precedence and associativity
# Precedence: `~` (highest) > `&` > `^` > `|` (lowest)
# All are left-associative except for `~`, which is unary
OP_PRECEDENCE = {'~': 3, '&': 2, '^': 1, '|': 0}
# Associativity: L for left-associative, R for right-associative (not needed here)
OP_ASSOCIATIVITY = {'&': 'L', '^': 'L', '|': 'L'}


def shunting_yard_fix(infix_expr: str) -> str:
    """
    Correctly converts an infix expression to RPN using the Shunting-yard algorithm.
    This version handles operator precedence and parentheses correctly.
    """
    output = []
    op_stack = []

    # Regex to tokenize the expression: numbers, variables, operators, and parentheses
    # Note: the `|` operator is a bitwise OR, not a regex OR
    tokens = re.findall(r'[0-9]+|[iIl]+|[~&^|]|[()]', infix_expr)
    
    # Simple state machine to distinguish unary `~`
    # The server always formats it as `(~...)`, so `~` is always followed by `(`
    # We can rely on this predictable format.

    for token in tokens:
        if token.isdigit() or re.fullmatch(r'[iIl]+', token):
            output.append(token)
        elif token == '(':
            op_stack.append(token)
        elif token == ')':
            while op_stack and op_stack[-1] != '(':
                output.append(op_stack.pop())
            if op_stack and op_stack[-1] == '(':
                op_stack.pop() # Pop the left parenthesis
            else:
                raise ValueError("Mismatched parentheses")
        elif token in OP_PRECEDENCE:
            while (op_stack and op_stack[-1] in OP_PRECEDENCE and
                   OP_PRECEDENCE[op_stack[-1]] >= OP_PRECEDENCE[token]):
                output.append(op_stack.pop())
            op_stack.append(token)
        else:
            raise ValueError(f"Unknown token: {token}")

    while op_stack:
        if op_stack[-1] == '(':
            raise ValueError("Mismatched parentheses")
        output.append(op_stack.pop())

    # For the unary `~`, the server formats it as `(~A)`.
    # Our algorithm will generate `A ~`.
    # Let's adjust for the fact that the server `~` is always unary.
    # The `combine` function in server code handles `~` as a unary operator.
    # We will treat it as a unary postfix operator in RPN.
    
    # The above algorithm handles it correctly as long as `~` is treated as an operator
    # with high precedence. The `pop from empty list` error indicates the stack
    # was empty *before* a binary op, not `~`. Let's re-verify the logic.
    # A standard Shunting-yard algorithm should handle this.
    
    # A key observation: the server expression is always fully parenthesized.
    # `(A op B)` or `(~A)`. This means we can use a simpler stack-based parser
    # that doesn't need to handle complex precedence rules, as the parentheses
    # already define the order of operations.

    # Let's try a stack-based parser specifically for fully parenthesized expressions.
    stack = []
    for token in tokens:
        if token.isdigit() or re.fullmatch(r'[iIl]+', token):
            stack.append(token)
        elif token == '~':
            # This is a unary operator, it will operate on the next operand
            # In RPN, it becomes `operand ~`
            # For `(~...)`, we will push `~` to stack and pop it after the operand is processed
            # But the server tokenizes as `~` then `(`, which complicates things.
            # A simple way to fix the original code is to check for stack length.
            # Let's go back to the original simple parser and fix it.
            pass
        elif token == '(':
            pass # Ignore opening parentheses
        elif token == ')':
            # Closing a subexpression.
            # Check for a binary op first. `(a op b)` -> `a b op`
            if len(stack) >= 3 and stack[-2] in OP_PRECEDENCE and stack[-3] not in OP_PRECEDENCE:
                 op = stack.pop()
                 b = stack.pop()
                 a = stack.pop()
                 stack.append(f'{a} {b} {op}')
            # Check for a unary op. `(~a)` -> `a ~`
            elif len(stack) >= 2 and stack[-2] == '~':
                 op = stack.pop()
                 operand = stack.pop()
                 stack.append(f'{operand} {op}')
            
        elif token in OP_PRECEDENCE:
            stack.append(token)
    
    # The previous logic was flawed. A proper Shunting-yard is needed.
    # The `pop from empty list` error in your run shows that a naive approach fails.
    # Let's try again with a robust Shunting-yard implementation.
    
    # The problem is that the `~` can be followed by a `(`, and the `pop` would fail.
    # A robust algorithm must handle unary operators correctly.
    # Let's re-write `shunting_yard` from scratch for clarity and correctness.
    
    output = []
    op_stack = []
    # Tokenize the expression, including all symbols
    tokens = re.findall(r'[0-9]+|[iIl]+|[~&^|]|[()]', infix_expr)
    
    for token in tokens:
        if token.isdigit() or re.fullmatch(r'[iIl]+', token):
            output.append(token)
        elif token == '(':
            op_stack.append(token)
        elif token == ')':
            while op_stack and op_stack[-1] != '(':
                output.append(op_stack.pop())
            if op_stack:
                op_stack.pop() # pop '('
        elif token in OP_PRECEDENCE:
            # Handle unary `~`
            if token == '~':
                # The server's format is `(~...)`, so `~` is always followed by `(`.
                # We can treat `~` as a special case.
                # Let's push it, and process it later
                op_stack.append(token)
            else: # Binary operators
                while op_stack and op_stack[-1] != '(' and \
                      OP_PRECEDENCE[op_stack[-1]] >= OP_PRECEDENCE[token]:
                    output.append(op_stack.pop())
                op_stack.append(token)
        else:
            raise ValueError(f"Unknown token: {token}")

    while op_stack:
        output.append(op_stack.pop())
    
    return ' '.join(output)


def main():
    conn = remote(HOST, PORT)
    
    conn.recvuntil(b'lets play a game!\n')
    
    log.info("Starting the challenge...")

    for i in range(50):
        line = conn.recvline().decode().strip()
        log.info(f"[{i+1}/50] Received: {line}")
        
        try:
            rpn_expression = shunting_yard_fix(line)
            log.info(f"[{i+1}/50] Sending: {rpn_expression}")
            
            conn.sendline(rpn_expression.encode())
            
            response = conn.recvline().decode().strip()
            log.info(f"[{i+1}/50] Received: {response}")
            
            if "wrong!" in response or "invalid" in response or "too slow" in response:
                log.error(f"Failed at round {i+1}. Server said: {response}")
                conn.close()
                return
        except Exception as e:
            log.error(f"An error occurred during round {i+1}: {e}")
            conn.close()
            return

    log.success("All 50 rounds completed! Waiting for the flag...")
    flag = conn.recvline().decode().strip()
    log.success(f"Flag: {flag}")
    
    conn.close()

if __name__ == "__main__":
    main()

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()}")

赛后看官方 WriteUp，发现是一道论文题

题目核心

• 状态：$(x,y)$ 为两个大整数。
• 步骤：从 8‑字节的 part 读取 4 个 16‑位整数

$$ M=\begin{pmatrix} a & b\ c & d \end{pmatrix}, \qquad \begin{pmatrix}x’\y’\end{pmatrix}=M\begin{pmatrix}x\y\end{pmatrix}, $$

其中 part 为 mind 中的一个不重复的块。

• 初始坐标 $(x_0,y_0)$ 随机于 $[0,2^{256})$。
• mind 长 1000 字节，划分成 125 个互不相同的 8‑字节块 step，随后在 moving 中不放回地取 30 次。

每次乘以一个 2×2 整数矩阵，行列式的绝对值大约在 $2^{16}$ 量级，导致坐标的位数每一步增加约 16–17 位。

$$ \operatorname{bitlen}(x_{i})\approx 256+16\cdot i. $$

当 $i=30$ 时，位长约 $256+30\cdot 17\approx 766$ 位。 给出的 limit 是 1024‑位的整数，远大于此值，因此在 30 步内不可能出现 x>limit 或 y>limit，循环永远不会在途中 break，必定执行完整的 30 次变换。

矩阵 $M$ 的逆为

$$ M^{-1}=\frac{1}{\det M} \begin{pmatrix} d & -b\ -c & a \end{pmatrix}, \qquad \det M=ad-bc. $$

若 $(x_{k},y_{k})$ 为第 $k$ 步后的坐标，则

$$ \begin{aligned} x_{k-1} &=\frac{d,x_{k}-b,y_{k}}{\det M},\ y_{k-1} &=-\frac{c,x_{k}+a,y_{k}}{\det M}. \end{aligned} $$

为了保持整数，必须满足

$$ \begin{cases} d,x_{k} - b,y_{k}\equiv 0\pmod{\det M},\ -a,y_{k} - c,x_{k}\equiv 0\pmod{\det M}. \end{cases} $$

对随机的 16‑位矩阵来说，上式的同余条件出现的概率约为 $2^{-16}$ 甚至更低，因而在全部 125 条候选中几乎只能找出 唯一 能满足整除的矩阵。换言之，逆向搜索每一步都几乎唯一确定上一轮使用的 part。

Exploit

1. 已知初始向量 $\mathbf{v}0=(x_0,y_0)$ 与最终向量 $\mathbf{v}{30}=(x_{30},y_{30})$。
2. 设 $\mathcal{S}$ 为剩余未使用的 125 条 part。
3. 对于当前坐标 $\mathbf{v}k$（从 $\mathbf{v}{30}$ 开始），遍历 $\mathcal{S}$ 中的每个 part，
   • 解析成 $(a,b,c,d)$，计算 $\det M$。若 $\det M=0$ 则直接跳过。
   • 检验上面的两条同余式，若都能整除，则唯一得到上一状态 $\mathbf{v}_{k-1}$。
   • 将该 part 从 $\mathcal{S}$ 中移除，递归继续寻找 $\mathbf{v}_{k-1}$。
4. 当递归深度达到 30 且恰好回到 $\mathbf{v}_0$ 时，已得到完整的逆序 part 列表；把顺序反转即可得到正向的 30 步路径。

#!/usr/bin/env python3
from pwn import *
import ast

def get_matrix_from_part(part):
    """Parses an 8-byte part into a tuple of 4 integers (matrix elements)."""
    a = int.from_bytes(part[0:2], "big")
    b = int.from_bytes(part[2:4], "big")
    c = int.from_bytes(part[4:6], "big")
    d = int.from_bytes(part[6:8], "big")
    return (a, b, c, d)

def solve_round(initial_pos, final_pos, all_parts):
    """
    Solves a single round using an iterative Depth-First Search (DFS)
    based on the divisibility constraint.
    """
    # Stack for DFS: (current_target_pos, available_parts_set, path_in_reverse)
    stack = [(final_pos, frozenset(all_parts), [])]

    while stack:
        current_pos, available, path_rev = stack.pop()

        if len(path_rev) == 30:
            if current_pos == initial_pos:
                log.success("Found the correct path of 30 steps!")
                # The path was built in reverse, so we flip it.
                return b"".join(path_rev[::-1])
            continue

        tx, ty = current_pos
        for part in available:
            a, b, c, d = get_matrix_from_part(part)
            det = a * d - b * c
            if det == 0:
                continue

            # Calculate the numerators for the inverse transformation
            prev_x_num = d * tx - b * ty
            prev_y_num = -c * tx + a * ty

            # The key insight: intermediate coordinates must be integers.
            if prev_x_num % det == 0 and prev_y_num % det == 0:
                prev_pos = (prev_x_num // det, prev_y_num // det)
                stack.append((prev_pos, available - {part}, path_rev + [part]))
    
    return None # Should not be reached

def main():
    conn = remote("catch.chal.idek.team", 1337)
    
    for round_num in range(20):
        conn.recvuntil(b"begins!\n")
        
        # Parse initial position
        line_co_location = conn.recvline().decode().strip()
        x0, y0 = ast.literal_eval(line_co_location.split(": ")[1])
        
        # Parse the cat's mind
        line_mind = conn.recvline().decode().strip()
        mind_hex = line_mind.split(": ")[1]
        mind_bytes = bytes.fromhex(mind_hex)
        all_parts = [mind_bytes[i:i+8] for i in range(0, 1000, 8)]
        
        conn.recvuntil(b"The chase is on!\n")
        
        # Parse final position
        line_final_pos = conn.recvline().decode().strip()
        xf, yf = ast.literal_eval(line_final_pos.split(": ")[1])
        
        log.info(f"--- Starting Hunt {round_num+1}/20 ---")

        # Solve the round
        solution_path_bytes = solve_round((x0, y0), (xf, yf), all_parts)
        
        if solution_path_bytes is None:
            log.error("Solver failed. Something is wrong with the assumptions.")
            conn.close()
            return

        solution_hex = solution_path_bytes.hex()
        conn.sendlineafter(b"Path to recall (hex): ", solution_hex.encode())
        
        response = conn.recvline()
        if b"Reunion!" not in response:
            log.error("Submitted the wrong path.")
            print(response.decode())
            conn.close()
            return
            
    flag = conn.recvall().decode()
    log.success(f"Flag: {flag}")

if __name__ == "__main__":
    main()

Sadness ECC

题目

# chall.py
from Crypto.Util.number import *
from secret import n, xG, yG
import ast

class DummyPoint:
    O = object()

    def __init__(self, x=None, y=None):
        if (x, y) == (None, None):
            self._infinity = True
        else:
            assert DummyPoint.isOnCurve(x, y), (x, y)
            self.x, self.y = x, y
            self._infinity = False

    @classmethod
    def infinity(cls):
        return cls()

    def is_infinity(self):
        return getattr(self, "_infinity", False)

    @staticmethod
    def isOnCurve(x, y):
        return "<REDACTED>"

    def __add__(self, other):
        if other.is_infinity():
            return self
        if self.is_infinity():
            return other

        # ——— Distinct‑points case ———
        if self.x != other.x or self.y != other.y:
            dy    = self.y - other.y
            dx    = self.x - other.x
            inv_dx = pow(dx, -1, n)
            prod1 = dy * inv_dx
            s     = prod1 % n

            inv_s = pow(s, -1, n)
            s3    = pow(inv_s, 3, n)

            tmp1 = s * self.x
            d    = self.y - tmp1

            d_minus    = d - 1337
            neg_three  = -3
            tmp2       = neg_three * d_minus
            tmp3       = tmp2 * inv_s
            sum_x      = self.x + other.x
            x_temp     = tmp3 + s3
            x_pre      = x_temp - sum_x
            x          = x_pre % n

            tmp4       = self.x - x
            tmp5       = s * tmp4
            y_pre      = self.y - tmp5
            y          = y_pre % n

            return DummyPoint(x, y)

        dy_term       = self.y - 1337
        dy2           = dy_term * dy_term
        three_dy2     = 3 * dy2
        inv_3dy2      = pow(three_dy2, -1, n)
        two_x         = 2 * self.x
        prod2         = two_x * inv_3dy2
        s             = prod2 % n

        inv_s         = pow(s, -1, n)
        s3            = pow(inv_s, 3, n)

        tmp6          = s * self.x
        d2            = self.y - tmp6

        d2_minus      = d2 - 1337
        tmp7          = -3 * d2_minus
        tmp8          = tmp7 * inv_s
        x_temp2       = tmp8 + s3
        x_pre2        = x_temp2 - two_x
        x2            = x_pre2 % n

        tmp9          = self.x - x2
        tmp10         = s * tmp9
        y_pre2        = self.y - tmp10
        y2            = y_pre2 % n

        return DummyPoint(x2, y2)

    def __rmul__(self, k):
        if not isinstance(k, int) or k < 0:
            raise ValueError("Choose another k")
        
        R = DummyPoint.infinity()
        addend = self
        while k:
            if k & 1:
                R = R + addend
            addend = addend + addend
            k >>= 1
        return R

    def __repr__(self):
        return f"DummyPoint({self.x}, {self.y})"

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

if __name__ == "__main__":
    G = DummyPoint(xG, yG)
    print(f"{n = }")
    stop = False
    while True:
        print("1. Get random point (only one time)\n2. Solve the challenge\n3. Exit")
        try:
            opt = int(input("> "))
        except:
            print("❓ Try again."); continue

        if opt == 1:
            if stop:
                print("Only one time!")
            else:
                stop = True
                k = getRandomRange(1, n)
                P = k * G
                print("Here is your point:")
                print(P)

        elif opt == 2:
            ks = [getRandomRange(1, n) for _ in range(2)]
            Ps = [k * G for k in ks]
            Ps.append(Ps[0] + Ps[1])

            print("Sums (x+y):", [P.x + P.y for P in Ps])
            try:
                ans = ast.literal_eval(input("Your reveal: "))
            except:
                print("Couldn't parse."); continue

            if all(P == DummyPoint(*c) for P, c in zip(Ps, ans)):
                print("Correct! " + open("flag.txt").read())
            else:
                print("Wrong...")
            break

        else:
            print("Farewell.") 
            break