Общий модуль

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

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

Цель: Атаку на общий модуль RSA через соотношение Безу.

Одно и то же сообщение зашифровали RSA для двух получателей. По ошибке у них общий модуль n, но разные экспоненты. Восстановите сообщение, не факторизуя n.

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

Одно сообщение m зашифровано с одинаковым n и разными e1, e2, причём gcd(e1, e2) = 1.

Расширенный алгоритм Евклида даёт числа a, b: a·e1 + b·e2 = 1. Тогда c1^a · c2^b = m^(a·e1 + b·e2) = m mod n. Одно из чисел a, b отрицательно — для него используйте обратный элемент по модулю n.

Инструменты

Python: рекурсивный extended gcd, pow(c, -k, n) (Python 3.8+ поддерживает отрицательную степень)

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

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

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

n  = 145916055284408221411248184562246616711725617364723188412800731351620447763193447697287978235297031807996789080070581733514908747146811739005401927333574781174612987636701125229699375614507908668295090956821431029355147890518943109035064006464481029020913095401724721579268599119990796253344742683422794914697
e1 = 17
c1 = 45924143767031389791218414209455602172224894673005206274617736719563500086873583334153633624382698072459938709694471676739480383214915510403704096889891005592506714879438624040723841913568475312617992680086119465162863061187133960819445651542229313622697135379727640989150875846808126939976703161537391968967
e2 = 65537
c2 = 56394587678360858263232312481000783040151300978961637621434930251153458169627498244605787172240521843614631254286645000554030939897702077422946002014723843413997441959594212762176365269086871940481748434760017656103470024860807067606259180336978601381183469646519159890253863349288381498545281189615165603674

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

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

1
Найдите a, b расширенным алгоритмом Евклида для e1 и e2.
2
Вычислите pow(c1, a, n) и pow(c2, b, n) (отрицательную степень Python обработает сам через обратный элемент).
3
Перемножьте по модулю n — получится m.
4
Переведите m в байты.

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

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

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

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

Каждому получателю — свой модуль n. Никогда не переиспользуйте n с разными экспонентами.

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

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