Sekur Julius

#

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

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

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

Описание

#

• В глубине леса был спрятан древний свиток, который, по слухам, даровал огромную силу любому, кто сможет прочесть его меняющиеся символы. На Хэллоуин любопытный нашёл свиток, буквы в котором были расположены в странном порядке. По мере того, как он расшифровывал послание, слова медленно перестраивались, открывая тёмное заклинание. Но на последнее измение, он почувствовал за спиной чьё-то холодное присутствие, шепчущее: «Тебе никогда не суждено было понять». Лес затих, но заклинание уже было наложено.

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

• source.py : шифрует секретное сообщение в шифротекст и сохраняет в output.txt
• output.txt : сам по себе файл с защифрованным сообщением

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

#

Основная часть скрипта

from random import choices

def julius_encrypt(msg, shift):
    ct = ''
    for p in msg:
        if p == ' ':
            ct += '0'
        elif not ord('A') <= ord(p) <= ord('Z'):
            ct += p
        else:
            o = ord(p) - 65
            ct += chr(65 + (o + shift) % 26)
    return ct

def encrypt(msg, key):
    for shift in key:
        msg = julius_encrypt(msg, shift)
    return msg

msg = open('secret.txt').read().upper()
secure_key = os.urandom(1337)

with open('output.txt', 'w') as f:
    f.write(encrypt(msg, secure_key))

Сообщение загружается из secret.txt и шифруется ключем. Ключ это случайная строка от байтов 1337.

Тогда сообщение шифруется с каждым из этих байтов ключа. Функция, которая шифрует настоящее сообщение это julius_encrypt и есть ее исходный код. Функция проходит по каждому символу в сообщении и шифрует его так:

1. Если символ это пробел, добавить ‘0’ в шифротекст
2. Если символ это любой другой не заглавный символ, записать как есть.
3. Если символ заглавный, подставить символ который на $\text{shift}$ позиций правее. Например для ‘A’ к ключем 4 в зашифрованном виде будет ‘E’.

Название функции это еще одна подсказка, конечно это шифр Цезаря.

Решение

#

Шифр Цезаря считается уязвимым из-за малого количества варинатов ключей, в этом таске это всего 26 символов; только заглавных английского алфавита. Хотя есть особенность в этом таске, сообщение защифрованно не одной перестановкой, а 1337 перестановок где каждый сдвиг может быть в диапозоне $[0, 255]$.

Стандартный выбор сдвига находится в диапозоне $[0, 25]$ и не в $[0, 255]$. Хотя методы шифрования добавляют сдвиги к исходному сообщению и затем уменьшает результат $\pmod {26}$.

(o + shift) % 26

Из за свойств модульной арифметики это эквивалентно:

(o % 26 + shift % 26) % 26

То есть независимо насколько большой сдвиг, итоговое число будет в диапозоне $[0, 25]$. Например шифрование с $\text{shift} = 250$ эквивалентно $250 \pmod {26} = 10$. В результате мы делаем вывод что эффективное пространство ключей не изменяется.

Теперь согласно нескольким раундам шифрования, давайте посмотрим что будет если зашифровать сообщение пару раз с двумя разными сдвигами. Для примера CRYPTOGRAPHY. Сначала шифруем исходный текст с значением сдвига $3$, и тогда шифруем результат с значением сдвига $5$.

Можно заметить, что результат шифрования исходного текста с сдвигом равен сумме всех сдвигов $3 + 5 = 8$.

И это важно, мы исключили один раунд сдвига и получили то же сообщение. В таске секретное сообщение защифровано в 1337 рауда. Схожем образом мы можем получить то же зашифрованное сообщение через сумму 1337 сдвигов, кроме $\pmod {26}$. В итоге эффективный диапозон ключей тоже $[0, 25]$.

Для решения можно просто перебрать все 26 возможных значений сдвига и смотреть где дешифруется английские слова. Могли бы использовать технику совпадений, чтобы найти правильный исходный текст сразу, но это не обязательно в этом случае.

Давайте напишем функцию которая перебирает все возможные ключи.

def decrypt():
	enc = open('output.txt').read()
    for i in range(1, 26):
    	print(f'{i = } | {julius_decrypt(enc, i)}')

Флаг : HTB{SECURITYOFATHOUSANDOR…}