Elliptic Enigma
В руках два файла:
| Файл | Что внутри |
|---|---|
| `public/server.py` | Код сервера подписи |
| `public/signatures.json` | Параметры кривой, публичный ключ, 30 подписей, шифротекст флага |
ECDSA на кастомной эллиптической кривой — смотрим генерацию nonce `k`, обычно вся соль в нём.
## Решение
В коде сервера:
```python
k = random.getrandbits(120)
```
Порядок группы `n` — 128 бит. У каждого `k` старшие 8 бит тупо равны нулю. Даже небольшая утечка нескольких бит nonce, размазанная по десяткам подписей, приводит прямиком к [Hidden Number Problem](https://link.springer.com/chapter/10.1007/3-540-68697-5_11), а HNP классически решается решёточной редукцией ([LLL](https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm)).
Стандартная ECDSA-подпись: для сообщения с хешем $z$ считается
$$s = k^{-1}(z + r \cdot d) \pmod{n}$$
Откуда чистой алгеброй:
$$k = s^{-1} z + s^{-1} r d \pmod{n}$$
Обозначим $t_i = s_i^{-1} r_i \pmod{n}$ и $u_i = s_i^{-1} z_i \pmod{n}$, и для каждой подписи получаем уравнение вида
$$k_i = u_i + t_i \cdot d \pmod{n}, \qquad k_i < 2^{120}$$
Получили классическую постановку HNP: много сравнений по модулю $n$, а сами скрытые числа маленькие.
Дальше — стандартный пайплайн:
1. Загружаем подписи из `signatures.json`.
2. Для каждого сообщения считаем `z_i` так же, как сервер: `SHA-256`, первые 16 байт.
3. Вычисляем `t_i` и `u_i`.
4. Собираем из них решётку для LLL и запускаем редукцию.
5. Из редуцированного базиса вытаскиваем кандидатов на приватный ключ `d`.
6. С `d` на руках расшифровываем флаг: `AES-256-CBC(SHA256(d), iv=0, ciphertext)`.
## Флаг
`caplag{b14s3d_n0nc3_l4tt1c3_r3duc710n}`