Недавно я опубликовал статью о шифровании в состоянии покоя, в которой обсуждал работу Rijndael Cipher. Конкретный алгоритм шифрования, более известный как Advanced Encryption Standard (AES).

В этой статье предлагается альтернативный метод выполнения ByteSubstitution, но без необходимости читать предыдущую статью. Это можно осуществить одним из двух способов:

  • Используя справочную таблицу для выполнения замены
  • Математически вычисляя замену

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

Прежде всего, мне нужно охватить одну из моих новых любимых областей интересов: Поле Галуа.

Поле Галуа

Я обнаружил, что это очень интересный раздел математики. Поле Галуа создает конечное поле для работы. Это сильно ограничивает диапазон чисел, которые можно использовать для расчета. Я думал, что знаком с этой концепцией (от модульной арифметики), но не ожидал, насколько она может изменить вычисления, которые вы должны выполнять.

Классически математика оперирует бесконечной областью. Мы можем смотреть на действительно большие отрицательные числа на действительно большие положительные числа. Но конечное поле сильно ограничивает это. Чтобы понять, что такое конечное поле, рассмотрим аналоговые часы. Руки двигаются по лицу; 1, 2, 3,…, 11, 12, а затем обратно к 1.

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

К сожалению, поле Галуа не так однозначно. В Поле Галуа число, которое вы смотрите, представлено многочленом (например, x³ + x² + 1). Таким образом, чтобы вернуть ваше Поле Галуа в цикл, вам необходимо выполнить модульную арифметику с «неприводимым многочленом». Фактическая структура неприводимого многочлена определяется конкретным полем Галуа, которое вы используете. Например, в AES это: x⁸ + x⁴ + x³ + x + 1.

Я должен упомянуть еще две границы Поля Галуа: основание числа и количество значащих цифр.

Значимые цифры достаточно просты, это просто количество символов в числе. «1234» состоит из 4 значащих цифр, «111» - из 3-х. Просто вот сколько это число!

Основание числа - это диапазон используемых символов. Мы больше всего привыкли к десятичной системе счисления, состоящей из десяти чисел; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Это дает нам базу «10». Двоичная - это еще одна система счисления, которая часто упоминается в компьютерах, и состоит из двух чисел; 0, 1. Это дает нам базу «2». Наконец, шестнадцатеричная система счисления - это еще одна распространенная система счисления, используемая в вычислениях, которая состоит из шестнадцати «чисел»; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. Это дает нам базу «16». Таким образом, базой становится количество символов, к которым у нас есть доступ.

Все границы могут быть сокращены, чтобы рассказать вам о размере и диапазоне Поля Галуа. Например, в AES мы имеем: GF (2⁸). "GF" сообщает нам, что это Поле Галуа. «2» указывает нам основание (двоичное). Наконец, "" указывает количество значащих цифр. Итак, у нас есть поле Галуа в двоичной системе с 8 значащими цифрами.

Нахождение мультипликативного обратного

Если исходить из десятичной точки зрения, это чрезвычайно простая задача. Мультипликативный обратный просто задает вопрос:

«Если у меня x, на что я могу его умножить, чтобы получить« 1 »?»

Используя десятичную систему, вы получите x * 1/x = 1. Но это тоже над бесконечным полем. В случае с ByteSubstitution дело обстоит иначе.

Для начала мы используем двоичный код, который на самом деле упрощает некоторые арифметические операции. Однако в сочетании с конечным полем это приводит к тому, что число оказывается менее связанным со своим обратным. Например, эти два числа являются двоичными, мультипликативными обратными друг другу; 111 и 100. Это определенно в GF (2³) с неприводимым многочленом x³ + x + 1 (1x³ + 0x² + 1x + 1 переходит в 1011 в двоичном формате). Я буду использовать эти числа и это поле в качестве примера, чтобы показать, как находится обратное, и доказать, что они являются обратными друг другу.

Начнем с преобразования 111 в полином. Это становится x² + x + 1. Далее нам понадобится многочлен от неизвестных переменных. Мы берем наивысший порядок неприводимого многочлена (x³), уменьшаем его на единицу и используем его как наивысший порядок неизвестного многочлена. Затем умножьте каждый заказ на неизвестную переменную («a», «b», «c» и т. Д.). В результате получается: ax² + bx + c.

Затем мы умножаем известное число на неизвестный многочлен и упрощаем:

(x^2 + x + 1) * (ax^2 + bx + c)
= ax^4 + bx^3 + cx^2 + ax^3 + bx^2 + cx + ax^2 + bx + c
= (a)x^4 + (a+b)x^3 + (a+b+c)x^2 + (b+c)x + c

После того, как у нас есть этот длинный многочлен, нам нужно уменьшить его до неприводимого многочлена. Это делается путем деления в столбик, когда в качестве ответа принимается остаток (опять же, как в модульной арифметике).

Чтобы не мешать, вам может быть интересно, почему нет отрицательных значений, когда это деление в столбик. Это одно из основных преимуществ выполнения этих вычислений над двоичными числами. Поскольку двоичный код равен модулю 2, «+1» эквивалентен «-1», и поэтому мы можем рассматривать любые отрицательные значения как положительные.

Второй положительный момент (который не выделяется в этом примере) заключается в том, что число, кратное 2, можно не принимать во внимание. То есть, если бы у нас было, например, «2ax²», это эквивалентно «0». Это снова возвращается к модульной арифметике: 2 mod 2 = 0.

Теперь, когда мы сделали наше деление, мы просто позволяем результату равняться «1» (или подробно: 0x² + 0x + 1), объединяем в пары каждый полиномиальный член и вычисляем значение каждого неизвестного:

Используя то, что мы вычислили выше, чтобы заполнить неизвестный многочлен, мы получаем 1x² + 0x + 0. Преобразуя это из полинома в двоичный, мы получаем 100. Это как и ожидалось.

Чтобы доказать, что они противоположны друг другу, мы умножаем 111 на 100, а затем получаем результат по модулю 1011. Упрощенный способ вычисления этого заключается в выполнении повторяющихся операций XOR между неприводимым многочленом (1011) и произведением умножения (111 * 100) с выстраиванием наиболее значимой «1» каждого из них. Пример такого построения можно увидеть слева. Как только результат операции XOR (без учета ведущих нулей) короче, чем неприводимый многочлен, у нас есть ответ.

Как видно из примера слева, после умножения и уменьшения обоих чисел результатом будет «1». Это доказывает, что оба числа противоположны друг другу. (Несмотря на то, что это Поле Галуа, обратные числа все же умножаются, чтобы дать "1")

Обратные значения в нашем поле GF (2⁸) находятся тем же методом, но для их поиска требуется гораздо больше работы. Этот фактор побудил меня написать скрипт на Python, который может выполнять такое действие.

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

БайтЗамещение

Теперь, когда мы можем найти мультипликативную инверсию двоичного числа, мы можем выполнить последний шаг ByteSubstitution. Сначала мы генерируем матрицу 8 * 8 из двоичного представления 1F со сдвигом позиции (в шестнадцатеричном формате). В двоичном виде это 00011111. Верхняя строка сдвигается на 1, вторая строка на 2, третья на 3 и т. Д. Результат этого показан в виде первой матрицы ниже.

Затем эта матрица умножается на вычисленную обратную матрицу, при этом обратная матрица размещается с наименьшим значащим битом (крайним правым символом в числе) в верхней строке матрицы 1 * 8 и старшим значащим битом в нижней строке. В качестве примера возьмем 01010011, который является обратным 11001010.

Наконец, матрица продукта подвергается операции XOR с матрицей столбцов, содержащей число 01100011. Младший бит находится в верхнем ряду, как и обратное число.

Теперь, когда у нас есть ответ, давайте перейдем от матрицы к одной строке с номером: 01110100. Затем мы хотим преобразовать и это, и 11001010 из двоичного в шестнадцатеричный, чтобы мы могли сравнить наши входные и выходные данные с таблицей поиска в начале этой статьи. Если они там совпадают, значит, это математическая альтернатива использованию справочной таблицы.

11001010:
(1100 = 'C', 1010 = 'A')
01110100:
(0111 = '7', 0100 = '4')

Оглядываясь назад на нашу таблицу, принимая «C» как X и «A» как Y, мы обнаруживаем, что наша ByteSubstitution - «74». Точно так, как мы рассчитали выше!

Все это становится длительным, затяжным процессом, который нужно повторять неоднократно. Итак, вот сценарий python, который я написал для выполнения шага ByteSubstitution. Он ожидает значений в том же формате, что и мой мультипликативный обратный сценарий, и использует выходные данные этапа инверсии.

Надеюсь, вы нашли это информативным и полезным. Если у вас есть какие-либо вопросы или комментарии (или критика), вы можете найти меня в LinkedIn по адресу https://www.linkedin.com/in/hugh-gallagher/

* Все представления принадлежат мне, а не Oracle *