RSA без набивки

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

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

Цель: Почему RSA без набивки с маленьким e небезопасен.

Сообщение зашифровано «учебным» RSA с открытой экспонентой e = 3 и без набивки (padding). Сообщение короткое.

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

RSA шифрует так: c = m^e mod n. Если e = 3, а сообщение короткое, то m³ может оказаться меньше n — тогда операция mod n ничего не меняет, и c = m³ как обычное число.

Значит, достаточно извлечь целочисленный кубический корень. Набивка (OAEP) делает сообщение большим и случайным и закрывает эту атаку.

Инструменты

Python: целые числа произвольной длины, бинарный поиск
gmpy2.iroot (если установлен)

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

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

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

n = 84071106697817416551752248351771259508213691658905784679540797730241633110509562120275905176097872528754182563536319467938784499311471318880200474822009175665042242354575540687667540583225238032639935897453747653561353251328908189792030681880733698875707266995483684428204321484849587201931422227017141647773
e = 3
c = 100343063041834765693525850620975348975497021304262967768471836578154972736873304132580709923258465286667209886450001241838446337473683200221715039204113789204466450207307815835014220626273402274038730345701679213157

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

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

1
Убедитесь, что e = 3.
2
Найдите целый кубический корень из c бинарным поиском (не через ** (1/3) — float теряет точность).
3
Проверьте: корень в кубе должен точно равняться c.
4
Переведите число в байты: m.to_bytes((m.bit_length() + 7) // 8, 'big').

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

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

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

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

Используйте RSA только с набивкой OAEP (для шифрования) или PSS (для подписи), e = 65537, и готовые библиотеки.

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

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