5.8 KiB
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; - печатает флаг.
Запустить его можно следующим образом:
sage writeup/solve.sage public/task.txt
Таким образом получим флаг:
caplag{N3cr0m4nc3rs_us3_Fr4nkl1n_R31t3r_4tt4ck}