Предсказатель
Задание 1Введение
Цель: Предсказывать линейный конгруэнтный генератор по его выходам.
Казино генерирует «случайные» числа линейным конгруэнтным генератором x(n+1) = (a·x(n) + c) mod m, где m = 2³¹ − 1, а a и c — секрет. Вы подсмотрели четыре подряд идущих числа. Предскажите следующее. Флаг — CTF{число}.
Задание 2Теория и инструменты
LCG: x(n+1) = (a·x(n) + c) mod m. Если m известно, а a и c нет, трёх подряд выходов достаточно.
Вычитаем соседние уравнения: x3 − x2 = a·(x2 − x1) mod m. Так как m простое, у (x2 − x1) есть обратный элемент, и a находится однозначно. Потом c = x2 − a·x1 mod m.
Инструменты
- Python:
pow(v, -1, m)— обратный элемент по модулю
Больше теории — в разделе «Обучение: Криптография».
Задание 3Практика: найдите флаг
m = 2147483647 outputs = [12515102, 574440575, 1329049979, 1375144134]
Пошаговый план — открывайте по одному шагу
- 1Обозначьте выходы x1, x2, x3, x4.
- 2Вычислите
a = (x3 − x2) · (x2 − x1)⁻¹ mod m. - 3Вычислите
c = (x2 − a·x1) mod m. - 4Проверьте на x4:
(a·x3 + c) mod mдолжно дать x4. - 5Следующее число:
(a·x4 + c) mod m.
Подсказки — каждая до решения стоит −100 очков
Задание 4Как защититься
Для токенов, паролей и игр на деньги — только криптостойкие генераторы: secrets, crypto.randomBytes, /dev/urandom.
Разборы участников
Разборы открываются после того, как вы решите комнату, — чтобы не спойлерить ответ.