Tags: math factor pwntools

Rating:

Points: 90

Solve: 51

Difficulty: Medium ?

### 题面

The Bada equation contains an undetermined function. By closely examining how this equation behaves, you may be able to discover the concealed flag.

nc 00.cr.yp.toc.tf 17113

### 尝试交互

shell
> nc 00.cr.yp.toc.tf 17113
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Hey! It's time to solve the equation of a function f: N x N -> Z. ┃
┃ Function f has given certain conditions. In each step, solve the ┃
┃ equation f(x, y) = z with the given value of z. We know f(a+1, b) = ┃
┃ f(a, b) + a, and f(a, b+1) = f(a, b) - b, for every a' and b'. ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┃ We know: f(1, 1) = -444045537086 and f(x, y) = 202500187503
┃ Please send x, y separated by comma:



### 概述

### 方法详解

1. **设置**:
$$2n = (x - y)(x + y - 1)$$

2. **求解 $x$ 和 $y$**:
$$x = \frac{a + b + 1}{2}, \quad y = \frac{b - a + 1}{2}$$

3. **条件检查**:
- $a + b + 1$ 应为偶数，以确保 $x$ 是整数。
- $b - a + 1$ 也应为偶数，以确保 $y$ 是整数。
- $x \geq 1$ 和 $y \geq 1$ 确保值在定义域内。

### 单次询问/求解

python
def find_xy(n):
solutions = []
# 遍历可能的因子 a, b，其中 2n = a * b
for a in range(1, int(2*n**0.5) + 1):
if (2*n) % a == 0:
b = (2*n) // a
# 检查是否满足 a + b + 1 和 b - a + 1 都是偶数
if (a + b + 1) % 2 == 0 and (b - a + 1) % 2 == 0:
x = (a + b + 1) // 2
y = (b - a + 1) // 2
if x >= 1 and y >= 1:
solutions.append((x, y))
return solutions

# 设置 f(1, 1) 和目标 f(x, y)
f_1_1 = -793336362005
target_f_xy = 157252801734

# 计算 n
n = target_f_xy - f_1_1

# 查找符合条件的 x, y 对
result = find_xy(n)
if result:
print(f"Found solutions: {result}")
else:
print("No solution found.")


### Exploit

python
from pwn import *
from z3 import *

# 连接到挑战服务器
context.log_level = "DEBUG"
host, port = "01.cr.yp.toc.tf", 17113
conn = remote(host, port)

while True:

# 读取数据直到 'f(1, 1) ='
response = conn.recvuntil(b'f(1, 1) = ').decode()
print(response)

# 接着读取f(1, 1)的值直到' and f(x, y) = '
response += conn.recvuntil(b' and f(x, y) = ').decode()
# 从响应中提取f(1, 1)的值
initial_value = int(response.split('f(1, 1) = ')[1].split(' ')[0])
print(f"[+] f(1, 1) = {initial_value}")

# 继续接收数据获取f(x, y)的值
remaining_data = conn.recvline().strip().decode()
target_value = int(remaining_data)
print(f"[+] f(x, y) = {target_value}")

def find_xy(n):
solutions = []
# 遍历可能的因子 a, b，其中 2n = a * b
for a in range(1, int(2*n**0.5) + 1):
if (2*n) % a == 0:
b = (2*n) // a
# 检查是否满足 a + b + 1 和 b - a + 1 都是偶数
if (a + b + 1) % 2 == 0 and (b - a + 1) % 2 == 0:
x = (a + b + 1) // 2
y = (b - a + 1) // 2
if x >= 1 and y >= 1:
solutions.append((x, y))
break
return solutions

# 设置 f(1, 1) 和目标 f(x, y)
# f_1_1 = -793336362005
# target_f_xy = 157252801734
f_1_1 = initial_value
target_f_xy = target_value

# 计算 n
n = target_f_xy - f_1_1

# 查找符合条件的 x, y 对
result = find_xy(n)
if result:
print(f"[Y] Found solutions: {result}")
else:
print("[N] No solution found.")

for x, y in result:
conn.sendline(f"{x},{y}")
break
print(f"[+] Sent: {x},{y}")

"""