# Weird RSA | crypto, beginner

**Автор:** —

## Описание

> rsa is to slow, i came up with a speed up

## Деплой

Не требуется.

## Выдать участникам

Только [public/weird-rsa.tar.gz](public/weird-rsa.tar.gz).

Внутри:

- `chall.sage` — скрипт шифрования;
- `output.txt` — открытые параметры `p`, `e`, `N`, `c`.

## Идея

Это обычный учебный RSA, но вместо кольца целых чисел $\mathbb{Z}$ он построен
над кольцом многочленов $R = \mathbb{F}_{257}[x]$.

- «Простые» — это неприводимые многочлены $P$ и $Q$ степеней 58 и 59;
- модуль $N = P \cdot Q$ (степень 117);
- шифрование: $c = m^e \bmod N$, где $e = 65537$;
- флаг закодирован как коэффициенты многочлена-сообщения $m$ (свободный член — первый байт).

Весь секрет — в разложении $N$ на множители. В обычном RSA это тяжёлая задача
факторизации целого числа. Но над конечным полем факторизация многочлена —
**полиномиальная** по времени (алгоритм Кантора — Цассенхауса, он же встроен в
`.factor()` в sage). Поэтому «RSA» здесь ломается мгновенно.

Пересборка раздатки: [build_public.sh](build_public.sh) (упаковывает `src/chall.sage`
и `src/output.txt` в `public/weird-rsa.tar.gz`).

## Решение

1. Факторизуем модуль: $N = P \cdot Q$.
2. Считаем аналог функции Эйлера — количество обратимых элементов кольца
   $R / (N) \cong \mathbb{F}_{257^{58}} \times \mathbb{F}_{257^{59}}$:

   $$\varphi(N) = (257^{58} - 1)\,(257^{59} - 1).$$

3. Находим приватную экспоненту $d = e^{-1} \bmod \varphi(N)$.
4. Расшифровываем $m = c^d \bmod N$ и читаем коэффициенты $m$ как байты флага.

Код решения — [solve/solve.sage](solve/solve.sage).

```text
> cd solve && cp ../src/output.txt . && sage solve.sage
factor degrees: [58, 59]
ctfcup{862b7b348272087bd9cc0613646db566}
```

## Флаг

```
ctfcup{862b7b348272087bd9cc0613646db566}
```