Вот и настало заключительно испытание. Сегодня нам было передано послание из будущего, к сожалению, нынешние панды-мастера не в силах разгадать его. Мы думаем, что новые ученики смогут решить данную проблему. Я уверен, ты с этим легко справишься. Желаю удачи!
Входные данные
Answer: 7235950 8653973 22582420 46400007 30942811 18377826 9090748 1809330 24157907 26947293 26463809 19620468 27720117 24249324 18761476 private Key: https://gist.github.com/Dragonprod/a3b2c7bfc75d442048b9c1e148751271 solver.py: https://gist.github.com/Dragonprod/4f0b5bac11d52efeb706b8465f41aa96Нам дан ответ, скрипт для решения и секретный ключ. После запуска на трёх символах скрипт зависает и не подаёт никаких признаков жизни, кроме потребления 100% мощностей одного ядра. Прервав скрипт, видим, что выполнение скрипта падает на строке
x = (a ** b) ** (c ** d)
На Python ** означает возведение в степень. Давайте посмотрим, что же возводится, и в какую степень. Видим, что дешифрование производится блоками по три символа. a — как раз очередной элемент из потока зашифрованных данных.
Остальные переменные берутся из private.key — это файл с данными, закодированными в base64, внутри которого лежит JSON. В private_key лежат пары (c, d), а в common_key — пары (b, n). Число n используется чуть позже: для получения символов используется не само число x, а его остаток от деления на n.
Первое число вычисляется быстро: в ключе b = c = d = 1, и мы получаем первые три символа флага: nin. Все же остальные числа имеют длину 20–30 бит (7–9 десятичных знаков), и даже одно возведение в степень уже вряд ли вычислится на среднем современном процессоре.
Дальше будут использованы несколько математических терминов. Под вычислением по модулю n мы будем понимать вычисление остатка от деления на n. Два числа называются сравнимыми или равными по модулю n, если их остатки от деления на n равны. Разумеется, везде, где не сказано иное, подразумеваются целые неотрицательные числа. Взаимно простыми числами называются два таких числа, у которых нет общего делителя, кроме единицы.
Давайте придумаем, как соптимизировать вычисление. Во-первых, довольно логично, что раз мы результат берём по модулю, можно брать по модулю результат на каждой итерации. В Python это проще всего записать так: pow(a ** b, c ** d, n). Функция pow в Python с тремя аргументами эффективно вычисляет степень числа по нужному модулю.
Эта оптимизация уже сильно упрощает процесс, но этого мало. Рассмотрим выражение ab mod n, где a > n. a представимо в виде a = kn + x, где x = a mod n. Тогда (kn + x)b = knb + b(kn)b − 1x + … + xb. И, поскольку все элементы, кроме последнего, делятся на n, то выражение сравнимо с xb по модулю n.
Таким образом, от выражения ab нас интересует только остаток от деления на n, и наше выражение превращается в pow(pow(a, b, n), c ** d, n). Соптимизировать cd таким же образом не выйдет — к сожалению, мы получим другой результат.
Назовём наше число pow(a, b, n) буквой q. Мы хотим посчитать остаток от деления e в некоторой степени на n. Рассмотрим последовательность: q mod n, q2 mod n, q3 mod n …. Все эти числа лежат в диапазоне от 1 до n − 1.
Здесь мы используем тот факт, что q и n взаимно просты. Это было верно для наших сообщений (и в целом, подобные условия нередко являются обязательными для различных криптографических систем), но в общем случае такие вещи стоит проверять, чтобы не ошибиться.
Очевидно, что рано или поздно остатки начнут повторяться — хотя бы на n-той операции. При этом если мы какой-то повторяющийся остаток снова умножим на q, то получим то же самое число — таким образом, последовательность зацикливается. Если мы найдём длину этого цикла, возводить в нужную степень и не придётся — все итерации цикла можно просто пропустить, вычислив вместо нужной степени остаток от её деления на длину цикла.
Поскольку наш модуль был небольшим, можно было просто перебрать все степени q, пока мы не встретим этот самый цикл. Но, на самом деле, за нас уже всё сделал Леонард Эйлер — его теорема гласит о том, что длина такого цикла для взаимнопростых q и n равна функции Эйлера числа n. Функция Эйлера φ(n) — это количество натуральных чисел, меньших n и взаимно простых с ним.
Опять же, её можно посчитать и наивно, но с помощью несложных математических преобразований можно вычислить функцию Эйлера, зная делители n.
Таким образом, итоговая формула приобретает такой вид:
pow(pow(a, b, n), pow(c, d, phi(n)), n)Используя её, мы мгновенно получаем ответ - solution.py
ninja{1t_wa5_hard3r_than_0th3r5_48007afpf6c5}