Prelim

#

Подготовлено: rasti

Автор задания: blupper

Уровень сложности: легко

Описание

#

• Седрик теперь нашёл ещё одно секретное сообщение, но уронил его на пол, и оно полностью перепуталось! Думаешь, сможешь найти способ восстановить его?

В таске дано два файла:

• chall.py: основной скрипт, который шифрует в out.txt
• out.txt / tales.txt: содержит ключ после перестановки и зашифрованный флаг поксоренный с хешем ключа

Анализ исходного кода

#

Основные функции скрипта: scramble берет два списка чисел, которые будут перестановлены от list(range(4919)) и применяет перестановки по порядку. И super_scramble реализует алгоритм быстрого возведения в степень, где операция умножения заменена на функцию scramble как закон группы.

def scramble(a, b):
    return [b[a[i]] for i in range(n)]

def super_scramble(a, e):
    b = list(range(n))
    while e:
        if e & 1:
            b = scramble(b, a)
        a = scramble(a, a)
        e >>= 1
    return b

Закон группы реализует применение перестановок по порядку, это точно тот же закон группы, что и в симметрической группе $S_{4919}$, обычно определяемой как группа всех перестановок множества из 3000 элементов.

Генерируется случайная перестановка исходника message (в дальнейшем обозначаемая как $m$), затем вычисляется scrambled_message (в дальнейшем обозначаемая как $c$) по формуле $c = m^e$, и $e$ = 0x10001. Результат хешируется и затем ксорится с флагом, полученное записывается в output.txt вместе с $c$.

Наша цель это восстановить флаг $m$ по шифротексту $c$ (scrambled_message), затем хешировать $m$ и через XOR с зашифрованным флагом отменить предыдущий XOR (в enc_flag), восстановив флаг.

Решение

#

Сложность дешифрования в контексте RSA очень похожа, нужно вычислить порядок группы. Но в этом случае мы работаем в симметрической группе $S_{4919}$, и ее порядок можно легко вычислить как $\varphi = 4919!$ (факториал 0x1337) .

$4919!$ достаточно большое число, но вычислимо. И мы можем ускорить скрипт если использовать $\varphi = \text{lcm}(1, 2, 3, …, 4919)$ , это делитель от $4919!$ и так ни один элемент не имеет порядка больше этого значения.

Зная порядок группы $\varphi$ мы можем вычислить мультипликативную обратную к публичной экспоненте по модулю порядка группы. Тогда закрытая экспонента $d$ такая, что $e d \equiv 1 \pmod{\varphi}$ , что позволяет вычислить $c^d = m^{e d} = m$ и восстановить $m$. То есть возведение шифротекста $c$ в степень закрытой экспоненты $d$ отменяет действие степени открытой экспоненты e и возвращает исходную перестановку сообщения $m$, а $d$ можно получить через обратную к $e$ по модулю $\varphi$ через lcm (наименьшее общее кратное).

Для решения мы оставим реализацию scramble и super_scramble, но переименуем их в mul и exp для лучшей читаемости

from random import shuffle

def mul(a, b):
    return [b[a[i]] for i in range(n)]

def exp(a, e):
    b = one
    while e:
        if e & 1:
            b = mul(b, a)
        a = mul(a, a)
        e >>= 1
    return b

Загрузка в переменные через парсинг почти как питоновский код

from ast import literal_eval

with open('tales.txt') as f:
    c = literal_eval(f.readline().split('=')[1])
    enc_flag = bytes.fromhex(literal_eval(f.readline().split('=')[1]))

Используя теорию выше для вычисления $m$

n = 0x1337
e = 0x10001
one = list(range(n))
m = exp(c, pow(e, -1, lcm(*range(1, n+1))))

Хешируем ее и ксорим с зашифрованным флагом

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

key = sha256(str(m).encode()).digest()
flag = AES.new(key, AES.MODE_ECB).decrypt(enc_flag)
print(unpad(flag, 16).decode())