63 lines
5.8 KiB
Markdown
63 lines
5.8 KiB
Markdown
# Crypto-RSA
|
||
|
||
Слухи в Таверне гласят: кто найдёт Грааль, тот получит бесконечный запас маны и золота.
|
||
|
||
Некромант Сандро путешествует по Эрафии в поисках Грааля. Координаты сокровища надёжно зашифрованы могущественным заклинанием RSA. Чтобы снять защиту, нужно знать точное расположение всех Обелисков, которые формируют секретный магический фокус. Сандро успел посетить 6 из 8 Обелисков. Теперь он знает старшие биты магической координаты, но правый нижний угол карты всё ещё скрыт "Туманом войны". Не сумев полностью открыть карту, некромант в ярости бросил зашифрованный свиток и обрывок карты с открытыми Обелисками.
|
||
|
||
Разведчики передали эти данные вам. Сможете ли вы рассеять Туман войны, полностью восстановить координату и забрать Грааль до того, как Сандро вернётся с армией скелетов?
|
||
|
||
`
|
||
N = 10478327092484087119158811738002527881601133392230605359728636777609815579869678283867331428873702230467781035800930319302134425662634483320132982489385831425841142683276245240139807770094242769842712285436324254272792640567220605759816440095519657990655930770697233495280191856795686977028814794477226478424022094334917595550943153970859743416443075466307652568512202801367425261698533904718831085305741122872685782348491901469147144819542733684143982118060593950861934225209591938661726842353411448979388331957984491039941720316208753034352185033359022438790970437880769652134820269624136545195696512412902086547737
|
||
`
|
||
`
|
||
e = 65537
|
||
`
|
||
`
|
||
c = 2371908478747310630059898986871876272895367385836679471620653994043895929391935759268461102073140210469448513517093388784915155590867680910861238126882230573331605292181787234136901129322001225804993239553253815115175454153650336400717451897405778509283155936103207023688258230128247475695422393595702338795973073870189334970154365471517517328052432202583617568778188997290909337026276528139911107673782208700833801910261741350704957213863331988920136397794697512939924729956005535011011328130093021943779761037406840279182736278184729352019628495185205816545145747722511667416937357754661788964429902091376671458313
|
||
`
|
||
`
|
||
p_revealed = 103537519170277717476703855704210234988984256477016725267975201195283786500355490562158033894185780133509016924890164868577876427195910662513213720292660530388165461591925825231155280679347647383014480743406031945282107222824466834575211761120068458069640414044465161781503967875409303695137308078472563785728
|
||
`
|
||
|
||
|
||
|
||
## Идея атаки
|
||
|
||
Нам даны стандартные параметры RSA: $N$, $e$ и шифротекст $c$. Однако ключевая особенность кроется в значении `p_revealed`.
|
||
|
||
Разрядность $N$ - около 2048 бит (617 десятичных знаков). Нам дана часть одного из множителей ($p$). Если известна значительная часть бит одного из множителей (обычно более половины бит фактора), можно восстановить весь фактор методами поиска малых корней многочленов.
|
||
|
||
`f(x) = p_revealed + x (mod N)`.
|
||
|
||
Поскольку нам известны старшие биты $p$, мы имеем дело с задачей Partial Key Exposure. Согласно теореме Копперсмита, если мы знаем около $1/2$ бит фактора $p$ (для $p \approx \sqrt{N}$ это составляет $1/4$ бит от всего $N$), то можем найти недостающую часть за полиномиальное время.
|
||
|
||
### Математическая модель
|
||
|
||
Пусть $p = p_{revealed} + x$, где $x$ - неизвестная младшая часть (тот самый "Туман войны"). Ищем корень $x_0$ для полинома:
|
||
|
||
$$f(x) = p_{revealed} + x$$
|
||
|
||
по модулю некоторого неизвестного делителя $N$. В среде SageMath метод `small_roots()` позволяет находить такие корни, если выполняется условие $x < N^{0.25}$. В нашем случае $N \approx 2^{2048}$, следовательно, можно восстановить до 512 бит. У нас скрыто 448 бит, что идеально вписывается в границы применимости метода.
|
||
|
||
### Алгоритм действий в скрипте
|
||
|
||
Определяем кольцо многочленов над $\mathbb{Z}_N$. Задаём полином $f(x) = x + p_{revealed}$. Находим корень $x_0$ через LLL-редукцию (инкапсулировано в `small_roots`). Вычисляем $p = p_{revealed} + x_0$, находим $q = N / p$ и восстанавливаем секретную экспоненту $d$.
|
||
|
||
## Готовый solver
|
||
|
||
Готовый файл с скриптом решения: `solve.sage`. Он:
|
||
- парсит `task.txt`;
|
||
- запускает `small_roots` для `f(x)`;
|
||
- восстанавливает `p`, `q`, `d`;
|
||
- печатает флаг.
|
||
|
||
Запустить его можно следующим образом:
|
||
```bash
|
||
sage writeup/solve.sage public/task.txt
|
||
```
|
||
|
||
Таким образом получим флаг:
|
||
```
|
||
caplag{N3cr0m4nc3rs_us3_Fr4nkl1n_R31t3r_4tt4ck}
|
||
```
|