Рассылка

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

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

Цель: Широковещательную атаку Хастада и китайскую теорему об остатках.

Одно и то же сообщение без набивки отправили трём получателям с e = 3 и разными модулями. Каждый модуль по отдельности меньше m³, поэтому простой кубический корень не сработает.

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

Одно сообщение с e = 3 зашифровано под тремя разными модулями: ci = m³ mod ni.

Китайская теорема об остатках (КТО) собирает из трёх остатков m³ mod (n1·n2·n3). Поскольку m < ni, то m³ < n1·n2·n3, и найденное число — это ровно m³. Остаётся извлечь целый кубический корень.

Инструменты

Python: pow(x, -1, n), бинарный поиск для корня
sympy.ntheory.modular.crt (если доступен)

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

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

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

n1 = 10916846464868530277133185012288694679354431841852505102288114898639841064071207617361047728006662622187375190344972542721965422674074921410316737178402311
c1 = 4448163147571855143875202629101288461895885774444203895578264369058969922147259608659425196129312725055896867549042096792358515101777141332825936663799575
n2 = 7362010214856095677702599353012467848066837089271431555345049056234675371698095501427594346624967371523964800574825535704014467764816124328058041548839589
c2 = 897642828189342048051864047529969797077348980290677124352529572435710431971303837730899607602782063241201678174725265488606836336927295676827396271129873
n3 = 5201976475732044636704397917322197983830436686529940790125364513803690357390780565831389180375025377312504369389374302471883707452204078214527650334002097
c3 = 4431106355631054641134918749443593698353580557794732680648934830432469583914452084023415011764170319080570552173173111446827232719085536421798949957706490

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

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

1
Вычислите N = n1·n2·n3.
2
По КТО: x = Σ ci · Ni · (Ni⁻¹ mod ni) mod N, где Ni = N / ni.
3
Извлеките целый кубический корень из x.
4
Переведите в байты.

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

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

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

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

Набивка OAEP делает каждое шифрование случайным, и атака не работает. Без набивки RSA применять нельзя.

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

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