Маленькая тайна

Прогресс комнаты 0 / 4

Задание 1Введение

Цель: Атаку Винера на RSA с маленькой секретной экспонентой.

Чтобы ускорить расшифровку, разработчик выбрал очень маленькую секретную экспоненту d. Открытая экспонента e из-за этого огромная. Восстановите d и расшифруйте сообщение.

Задание 2Теория и инструменты

Если d < n^(1/4) / 3, то дробь k/d встречается среди подходящих дробей цепной дроби e/n (теорема Винера).

Для каждой подходящей дроби k/d проверяем: φ = (e·d − 1)/k должно быть целым, а уравнение x² − (n − φ + 1)·x + n = 0 — иметь целые корни p и q.

Инструменты

Python: цепные дроби вручную, math.isqrt
RsaCtfTool (для проверки)

Больше теории — в разделе «Обучение: Криптография».

Задание 3Практика: найдите флаг

Данные задания940 символов

n = 117338631220016385720115215843373131093596668124248996137584901579312194136048699435125376841671876247746579526179850332503901096938254008782444470407007011430984437455326564128821382547528812540479246029886565955328112330446972014121658893151177785980892633029814686483416951103742409078514758700805329051799
e = 116419597323907517078580805346581100184685845898568380892552300728650829299661827655519609774077879296091190562971728644332628599590241546805985225680099961290864257319871176065546235180457124487141971858781877304747605294786221410143451152417667597714090568321157281748578289413814870429527066516034522772667
c = 43637953196322611512499410439229026183646267987921381640506091813179857280084098865630241397951032666715250043370276401192358925114799169137322114369586907325165752421356738693727919084385626459446585883144962323287049624296604873504678247661270275872901241337268171973739423990772912154663446741440391590842

Вопрос: какой флаг спрятан в данных? Войдите, чтобы ответить

Пошаговый план — открывайте по одному шагу

1
Разложите e/n в цепную дробь: последовательные целые части при алгоритме Евклида.
2
Постройте подходящие дроби k/d по рекуррентным формулам.
3
Для каждой проверьте, что (e·d − 1) mod k == 0, и вычислите φ.
4
Проверьте дискриминант (n − φ + 1)² − 4n на полный квадрат. Если да — d найдено.
5
Расшифруйте: m = c^d mod n.

Подсказки — каждая до решения стоит −100 очков

Войдите, чтобы открыть подсказку 1

Войдите, чтобы открыть подсказку 2

Задание 4Как защититься

Не уменьшайте d ради скорости. Ускоряйте RSA через CRT (dp, dq) — это делают все стандартные библиотеки.

Разборы участников

Разборы открываются после того, как вы решите комнату, — чтобы не спойлерить ответ.