53 lines
2.9 KiB
Markdown
53 lines
2.9 KiB
Markdown
<h1 align="center">ShardSlope</h1>
|
||
|
||
<p align="center">
|
||
<img src="https://img.shields.io/badge/category-Crypto-blueviolet" alt="Crypto"/>
|
||
<img src="https://img.shields.io/badge/difficulty-easy-brightgreen" alt="easy"/>
|
||
</p>
|
||
|
||
В `escrow_export.json` лежат две группы долей секрета по схеме Шамира с порогом `threshold = 2`. У калибровочной группы есть две доли, у карантинной — только одна. Для карантинного секрета одной доли обычно недостаточно. Но в экспорте обе группы имеют одинаковый `rng_cache_id` — проверяем, не переиспользован ли случайный коэффициент.
|
||
|
||
## Решение
|
||
|
||
При пороге два доли — точки на прямой над конечным полем:
|
||
|
||
$$y = s + ax \pmod p,$$
|
||
|
||
где $s$ — секрет, а $a$ — случайный коэффициент наклона. Для каждого секрета коэффициент должен выбираться заново. Общий `rng_cache_id` позволяет предположить, что worker мог переиспользовать его между `calibration_batch` и `quarantine_batch`. Вычисляем коэффициент по калибровочной группе и проверяем, даст ли он осмысленный второй секрет.
|
||
|
||
В раздатке есть `recover.py`, который восстанавливает калибровочный секрет из двух точек. По этим же точкам вычисляем наклон.
|
||
|
||
$$a = (y_2-y_1)(x_2-x_1)^{-1} \pmod p.$$
|
||
|
||
Когда $a$ известен, одной карантинной доли $(x,y)$ уже хватает для расчёта $s = y-ax \pmod p$. Повторяем расчёт на Python:
|
||
|
||
```python
|
||
from pathlib import Path
|
||
import json
|
||
|
||
data = json.loads(Path("public/escrow_export.json").read_text())
|
||
p = int(data["field_prime"])
|
||
first, second = data["calibration_batch"]["shares"][:2]
|
||
x1, y1 = int(first["x"]), int(first["y"])
|
||
x2, y2 = int(second["x"]), int(second["y"])
|
||
slope = (y2 - y1) * pow(x2 - x1, -1, p) % p
|
||
|
||
share = data["quarantine_batch"]["shares"][0]
|
||
secret = (int(share["y"]) - slope * int(share["x"])) % p
|
||
```
|
||
|
||
Остаётся перевести число в байты в big-endian:
|
||
|
||
```python
|
||
raw = secret.to_bytes(max(1, (secret.bit_length() + 7) // 8), "big")
|
||
print(raw.decode())
|
||
```
|
||
|
||
Получаем строку флага. Коэффициент, вычисленный по калибровочной группе, позволил восстановить карантинный секрет по одной доле.
|
||
|
||
[Солвер](solve/solve.py).
|
||
|
||
## Флаг
|
||
|
||
`caplag{slope_reuse_breaks_2of3_escrow}`
|