babyrsa-2022
В 2022 году заданием на RSA никого не удивишь.
nc BEBRABEBRA 17171
Участникам нужно выдать файлы:
docker-compose up --build -d
В таске реализовано шифрование RSA, также выдаётся hint = p - flag. По факту для решения таска нужно только это, остальные возможности таска не требуются.
Известно, что p — простое число (как один из множителей RSA). Возьмём какое-то маленькое простое число prime, меньшее p. Заметим свойство:
p != 0 (mod prime), по определению простого числа
Затем рассмотрим тождество:
hint == p - flag (mod prime)
Можно заметить, что случай hint == -flag (mod prime) невозможен (по свойству выше).
Соответственно, поскольку flag зафиксирован, число hint (mod prime) при разных p может принимать любые значения из диапазона [0, prime), кроме числа -flag (mod prime).
Мы можем использовать эту информацию для решения таска:
- для каждого простого числа
primeподдерживаем множество остатков от деления из диапазона[0, prime) - постоянно генерируем RSA ключи и берём
hint - для каждого
primeубираем из множества остатков число-hint (mod prime) - рано или поздно в множестве останется один элемент — искомое "невозможное" число
flag (mod prime)
В конце нужно использовать китайскую теорему об остатках, чтобы найти flag.
Чтобы ускорить выкачивание данных из таска, можно распараллелить запросы по нескольким потокам.
Пример решения: solution/solver.py
Cup{sorry_I_did_not_understand_what_RSA_CRT_means}