# Crypto 9 класс

## Решение

Оракул возвращает по переданному числу x:

$$
y = (flag \cdot x) \mod p
$$

Значение flag и p неизвестны.

При двух запросах:

$$
y_1 = oracle(2) = (2 \cdot flag) \mod p
$$
$$
y_2 = oracle(3) = (3 \cdot flag) \mod p
$$

Существует $k_1$, $k_2$ такие, что:

$$
y_1 = 2 \cdot flag - k_1 \cdot p
$$
$$
y_2 = 3 \cdot flag - k_2 \cdot p
$$

Тогда:

$$
3 \cdot y_1 - 2 \cdot y_2 = (2k_2 - 3k_1) \cdot p
$$

Правая часть кратна p, значит p можно восстановить через факторизацию числа $|3 \cdot y_1 - 2 \cdot y_2|$ (или через НОД нескольких комбинаций, если получилась кратность > p).

После этого:

$$
flag = y_1 \cdot 2^{-1} \mod p
$$

## Код

```python
from pwn import *

context.log_level = "info"

p = remote("localhost", 5055, timeout=5)
p.recvuntil(b"x> ")

p.sendline(b"2")
y1 = int(p.recvline().strip().removeprefix(b"x> "))

p.recvuntil(b"x> ")

p.sendline(b"3")
y2 = int(p.recvline().strip().removeprefix(b"x> "))

p = abs(3 * y1 - 2 * y2)
inv2 = pow(2, -1, p)
flag_int = (y1 * inv2) % p

print(flag_int)
```

## Флаг

vsosh{9223248580180220266}
