Расшифровка однобайтового шифротекста XOR

Автор оригинала: Arpit Bhayani.

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

Сила алгоритма шифрования определяется тем, насколько трудно будет извлечь исходное сообщение, не зная ключа шифрования. Обычно это зависит от количества битов в ключе – чем больше ключ, тем больше времени требуется для расшифровки зашифрованных данных.

В этом эссе мы будем работать с очень простым шифром (алгоритмом шифрования), который использует ключ шифрования размером в один байт, и попытаемся расшифровать зашифрованный текст и получить исходное сообщение, не зная ключа шифрования. Постановка задачи, определенная выше, основана на Наборе криптопалов 1 Вызов 3 .

Однобайтовый алгоритм шифрования XOR работает с ключом шифрования размером 1 байт, что означает, что ключ шифрования может быть одним из возможных 256 значений байта. Теперь мы подробно рассмотрим, как выглядят процессы шифрования и дешифрования для этого шифра.

Шифрование

В рамках процесса шифрования исходное сообщение повторяется последовательно, и каждый отдельный байт b фиксируется ключом шифрования key , а результирующий поток байтов снова переводится обратно в виде символов и отправляется другой стороне. Эти зашифрованные байты не обязательно должны быть среди обычных печатаемых символов и в идеале должны интерпретироваться как поток байтов. Ниже приведена реализация процесса шифрования на основе python.

def single_byte_xor(text: bytes, key: int) -> bytes:
    """Given a plain text `text` as bytes and an encryption key `key` as a byte
    in range [0, 256) the function encrypts the text by performing
    XOR of all the bytes and the `key` and returns the resultant.
    """
    return bytes([b ^ key for b in text])

В качестве примера мы можем попытаться зашифровать обычный текст – abcd – с помощью ключа шифрования 69 и в соответствии с алгоритмом мы выполняем XOR по заданному простому тексту. Для символа a байт , т. е. значение ASCII, равно 97 который, когда XORed с 69 результаты в 36 чей символьный эквивалент равен $ , аналогично для b зашифрованный байт равен ' , для c это & и для d это ! . Следовательно, когда abcd шифруется с использованием однобайтового шифра XOR и ключа шифрования 69 , результирующий зашифрованный текст, т. е. зашифрованное сообщение, является $'&! .

Расшифровка

Расшифровка-это процесс извлечения исходного сообщения из зашифрованного зашифрованного текста с учетом ключа шифрования. XOR имеет свойство | – если a ^ c , то b ^ c , следовательно, процесс расшифровки точно такой же, как и шифрование, т. е. мы перебираем зашифрованное сообщение по порядку и XOR каждый байт с ключом шифрования - результатом будет исходное сообщение.

Поскольку шифрование и дешифрование имеют одну и ту же реализацию , мы передаем зашифрованный текст функции single_byte_xor , определенной выше, чтобы вернуть исходное сообщение.

>>> single_byte_xor(b"$'&!", 69)
b'abcd'

Вещи становятся действительно интересными, когда мы должны восстановить исходное сообщение, учитывая зашифрованный текст и не зная ключа шифрования; хотя мы знаем алгоритм шифрования.

В качестве примера простого текста мы возьмем последние два сообщения, отправленные по их немецкой военной радиосети во время Второй мировой войны. Эти сообщения были перехвачены и расшифрованы британскими войсками. Во время войны сообщения шифровались с помощью Enigma Machine и Алан Тьюринг лихо взломал код Enigma (похожий на ключ шифрования), который использовался для шифрования немецких сообщений.

В этом эссе вместо шифрования сообщения с помощью кода Enigma мы будем использовать однобайтовый шифр XOR и попытаемся восстановить исходное сообщение без какого-либо знания ключа шифрования.

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

>>> key = 82
>>> plain_text = b'british troops entered cuxhaven at 1400 on 6 may - from now on all radio traffic will cease - wishing you all the best. lt kunkel.'
>>> single_byte_xor(plain_text, key)
b'0 ;&;!:r& =="!r7<&7 76r1\'*:3$7>r 36;=r& 344;1r%;>>r173!7r\x7fr%;!:;<5r+=\'r3>>r&:7r07!&|r>&r9\'<97>|'

Грубая сила

Существует очень ограниченное количество возможных ключей шифрования – 256, если быть точным, – мы можем, очень удобно, использовать подход Брутфорса и попытаться расшифровать зашифрованный текст с помощью каждого из них. Поэтому мы начинаем перебирать все ключи в диапазоне [0, 256) , расшифровываем зашифрованный текст и смотрим, какой из них больше всего похож на исходное сообщение.

На рисунке выше мы видим, что сообщение расшифровано с помощью ключа 82 это, по сути, наше исходное сообщение, в то время как другие извлеченные простые тексты выглядят скремблированными и мусорными. Сделать это визуально очень легко; мы, как люди, способны понять знакомство, но как компьютер распознает это?

Нам нужен способ количественной оценки близости текста к подлинному английскому предложению. Чем ближе расшифрованный текст к подлинному английскому предложению, тем ближе он будет к нашему исходному простому тексту.

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

ЭТАОИН ШРДЛУ

Частота букв-это количество раз, когда буквы алфавита появляются в среднем в письменном языке. В английском языке частота букв буквы a составляет 8,239% , для b это 1,505% , что означает, что из 100 букв, написанных на английском языке, буква a в среднем будет отображаться 8,239% раз, в то время как b отображается 1,505% раз. Частота букв (в процентах) для других букв, как показано ниже.

occurance_english = {
    'a': 8.2389258,    'b': 1.5051398,    'c': 2.8065007,    'd': 4.2904556,
    'e': 12.813865,    'f': 2.2476217,    'g': 2.0327458,    'h': 6.1476691,
    'i': 6.1476691,    'j': 0.1543474,    'k': 0.7787989,    'l': 4.0604477,
    'm': 2.4271893,    'n': 6.8084376,    'o': 7.5731132,    'p': 1.9459884,
    'q': 0.0958366,    'r': 6.0397268,    's': 6.3827211,    't': 9.1357551,
    'u': 2.7822893,    'v': 0.9866131,    'w': 2.3807842,    'x': 0.1513210,
    'y': 1.9913847,    'z': 0.0746517
}

Этот анализ частоты букв является рудиментарным способом идентификации языка, с помощью которого мы видим, соответствует ли текущее распределение частоты букв в тексте среднему распределению частоты букв в английском языке. ETAOIN SHRDLU – это приблизительный порядок частоты 12 наиболее часто используемых букв в английском языке.

На следующей диаграмме показан анализ частоты букв для расшифрованных открытых текстов с ключами шифрования из 79 чтобы 84 .

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

Коэффициент подгонки

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

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

dist_english = list(occurance_english.values())

def compute_fitting_quotient(text: bytes) -> float:
    """Given the stream of bytes `text` the function computes the fitting
    quotient of the letter frequency distribution for `text` with the
    letter frequency distribution of the English language.

    The function returns the average of the absolute difference between the
    frequencies (in percentage) of letters in `text` and the corresponding
    letter in the English Language.
    """
    counter = Counter(text)
    dist_text = [
        (counter.get(ord(ch), 0) * 100) / len(text)
        for ch in occurance_english
    ]
    return sum([abs(a - b) for a, b in zip(dist_english, dist_text)]) / len(dist_text)

Расшифровка

Теперь, когда у нас есть все необходимое для непосредственного извлечения обычного текста из данного зашифрованного текста, мы заключаем его в функцию, которая перебирает все возможные ключи шифрования в диапазоне [0, 256) , расшифровывает зашифрованный текст, вычисляет коэффициент соответствия для обычного текста и возвращает тот, который минимизирует коэффициент в качестве исходного сообщения. Реализация этой логики расшифровки на основе Python показана ниже.

def decipher(text: bytes) -> Tuple[bytes, int]:
    """The function deciphers an encrypted text using Single Byte XOR and returns
    the original plain text message and the encryption key.
    """
    original_text, encryption_key, min_fq = None, None, None
    for k in range(256):
        # we generate the plain text using encryption key `k`
        _text = single_byte_xor(text, k)
        
        # we compute the fitting quotient for this decrypted plain text
        _fq = compute_fitting_quotient(_text)
        
        # if the fitting quotient of this generated plain text is lesser
        # than the minimum seen till now `min_fq` we update.
        if min_fq is None or _fq < min_fq:
            encryption_key, original_text, min_fq = k, _text, _fq

    # return the text and key that has the minimum fitting quotient
    return original_text, encryption_key

Этот подход также был протестирован на 100 случайных английских предложениях со случайными ключами шифрования, и было обнаружено, что этот метод расшифровки хорошо работает для всех образцов. Этот подход потерпит неудачу, если предложение очень короткое или содержит много символов. Исходный код для всего этого процесса расшифровки доступен в записной книжке Jupyter по адресу arpitbhayani.me/decipher-single-byte-xor .

Если вам понравилось то, что вы прочитали, подумайте о подписке на мою еженедельную рассылку по адресу arpitbhayani.me/newsletter где раз в неделю я пишу эссе о внутренних функциях языков программирования, или глубокое погружение в какой-нибудь суперумный алгоритм, или просто несколько советов по созданию масштабируемых распределенных систем.

Вы всегда можете найти меня в твиттере @arpit_bhayani .