Разбор: Weird RSA с отбора X Кубка CTF

Условие: crypto с меткой beginner. Участникам дают скрипт шифрования и открытые параметры. По таблице организаторов задание решили 646 раз.

Идея

Это учебный RSA над кольцом многочленов над конечным полем из 257 элементов. «Простые» здесь — неприводимые многочлены степеней 58 и 59, а секрет лежит в разложении модуля на множители.

Ход решения

• Разложить модуль на множители: над конечным полем это быстро, метод Кантора — Цассенхауса встроен в factor() в Sage
• Посчитать аналог функции Эйлера: число обратимых элементов кольца
• Найти приватную экспоненту как обратную к e = 65537
• Расшифровать и прочитать коэффициенты многочлена как байты флага

Что вынести

Стойкость RSA держится на трудности факторизации целых чисел. Переносите конструкцию в другую структуру: сначала спросите, остаётся ли там задача трудной.

Пример

Пример условный. В команде заводят правило: перед атакой на самодельный шифр выписать, на какой трудной задаче он держится, и проверить её в новой структуре.

Чек-лист

• ☐ Определён тип структуры
• ☐ Понятно, на чём держится стойкость
• ☐ Разложение проверено
• ☐ Приём записан в разбор команды

Документ уже составлен

Открыть «Разбор задачи для команды CTF» →

Основание: условие и решение авторов задачи, репозиторий acisoru/ctfcup2026-quals, crypto/weird-rsa. Канал не принадлежит организаторам; официальный сайт — ctfcup.ru.