P. Упрощенный AES (S-AES)

P.1. Структура S-AES

Упрощенный AES (S-AES), разработан профессором Эдвардом Шаефером (Edward Schaefer) в Университете Санта-Клары, является образовательным инструментом и предназначен помочь студентам изучать структуру AES с использованием меньших блоков и ключей.

На стороне шифрования S-AES получают исходный текст на 16 битов и создают зашифрованный текст на 16 битов; на стороне дешифрации S-AES получают зашифрованный текст на 16 битов и создают исходный текст на 16 битов. Ключ шифра на 6 битов используется и для шифрования, и для дешифрования.

Раунды

S-AES -шифр не-Файстеля, который зашифровывает и расшифровывает блок данных в 16 битов. Он использует предварительный раунд преобразования и два раунда. Ключ шифра - также 16 битов. Рисунок P.2 показывает общий вид для алгоритма шифрования (называемого "шифр") и алгоритма дешифрования (называемого "обратный шифр"). Они совпадают, но ключи раунда применяются в обратном порядке.

На рисунке P.2 ключи раунда, которые созданы алгоритмом расширения ключей, всегда содержат 16 бит, - они такого же размера, как и блок зашифрованного текста или исходный текст. В S-AES есть три ключа раунда - K0, K1 и K2.

Модули данных

Для представления данных S-AES, как показано на рис. P.3, используют пять модулей измерения: биты, полубайты, слова, блоки и состояния.

Бит

В S-AES бит -.двоичная цифра, которая принимает значение либо 0, либо 1. Для обозначения бита мы будем использовать латинскую букву b.

Полубайт

Полубайт - группа из 4 битов, которая может быть обработана как один объект, матрица-строка на 4 бита или матрица-столбец на 4 бита. Когда полубайт обрабатывается как матрица-строка, биты располагаются в матрице слева направо; когда полубайт обрабатывается как матрица-столбец, биты располагаются в матрице сверху вниз. Чтобы обозначить полубайт, мы используем строчную полужирную букву n. Обратите внимание, что полубайт - фактически одна шестнадцатеричная цифра.

Слово

Слово - группа 8 битов, которая может быть обработана как один объект: матриц-строка из двух полубайт или матрица-столбец из двух полубайт. Когда слово обрабатывается как матрица-строка, полубайты располагаются в матрице слева направо; когда слово рассматривается как матрица-столбец, полубайты располагаются в матрице сверху вниз. Чтобы обозначить слово, мы используем строчную полужирную букву w.

Блок

S-AES шифрует и расшифровывает блоки данных. Блок в S-AES - группа из 16 битов. Однако блок может быть представлен как матрица-строка из 4 полубайтов.

Состояние

В S-AES блок данных называется также состоянием. Мы используем полужирную заглавную букву S, чтобы обозначить состояние. Состояния, подобно блокам, состоят из 16 битов, но обычно они обрабатываются как матрицы по 4 полубайта. В этом случае каждый элемент состояния обозначается как sr,c, где. r ( 0 или 1 ) определяет строку и. c ( 0 или 1 ) определяет столбец. В начале шифра полубайты в блоке данных состояния располагаются столбец за столбцом и в каждом столбце сверху вниз. В конце шифра полубайты состояния извлекаются тем же способом, как показано на рис. P.4.

Пример P.1

Давайте посмотрим, как можно блок в 16 битов представить как матрицу 2 x 2. Пусть текстовый блок имеет вид 1011 0111 1001 0110. Сначала мы представим блок как 4 полубайта. Затем заполняем матрицу состояний, "столбец за столбцом", как это показано на рис. P.5.

Структура каждого раунда

Рисунок P.6 показывает, что каждое преобразование получает состояние и создает другое состояние, которое используется для следующего преобразования или следующего раунда. Секция предварительного преобразования (перед раундом) применяет одно преобразование ( AddRoundKey ); последний раунд использует только три преобразования (преобразование MixColumns отсутствует).

На стороне дешифрования используются: обратные преобразования InvSubNibbles, InvShiftRows, InvMixColumns и AddRoundKey (этот процесс является самообратимым).

P.2. Преобразования

Чтобы обеспечить безопасность, S-AES используют четыре типа преобразований: подстановка, перестановка, смешивание и сложение ключа. Ниже мы обсудим каждое из них.

Подстановка

Подстановка сделана для каждого полубайта (модуль данных на 4 бита). Для преобразований каждого полубайта используется только одна таблица, что означает, что если два полубайта одинаковые, то и результат преобразования одинаковый. В этом приложении преобразование определено процессом поиска таблицы.

Подполубайты

Первое преобразование, SubNibbles, используется на стороне шифрования. Для того чтобы заменять полубайты, мы интерпретируем каждый полубайт как 4 бита. Левые 2 бита определяют строку, а правые 2 бита определяют столбец таблицы подстановки. Шестнадцатеричная цифра в пересечении строки и столбца - новый полубайт. Рисунок P.7 показывает идею.

В преобразовании SubNibbles состояния обрабатываются как матрицы полубайтов 2 x 2. Преобразование осуществляется с одним полубайтом одновременно. Содержание каждого полубайта изменяется, но порядок полубайтов в матрице остается тем же самым. В процессе обработки каждый полубайт преобразуется независимо: есть четыре различных преобразования от полубайта к полубайту.

Рисунок P.7 также показывает таблицы подстановки (S-блоки) для преобразования SubNibbles. Преобразование SubNibbles обеспечивает эффект перемешивания. Например, два полубайта, A16 и B16, которые отличаются только одним битом (самый правый бит), преобразованы к 016 и 316, которые отличаются двумя битами.

InvSubNibbles

InvSubNibbles - инверсия преобразования SubNibbles. На рис. P.7 также показано обратное преобразование. Мы можем легко проверить, что эти два преобразования инверсны друг другу.

Пример P.2

Рисунок P.8 показывает, как преобразовано состояние, применяющее преобразование SubNibbles. На рисунке также показано преобразование InvSubNibbles, которое создает первоначальное состояние. Обратите внимание, что если два полубайта имеют одинаковые значения, в результате их преобразования получается одинаковое значение - поскольку каждый полубайт использует одну и ту же таблицу.

Перестановка

Другое преобразование, которое проводится в раунде, - сдвиг, переставляющий полубайты. Преобразование сдвига в S-AES делается на уровне полубайта; порядок следования битов в полубайте не изменяется.

ShiftRows

Преобразование при шифровании, называемое ShiftRows, сдвигает биты строки влево. Число сдвигов зависит от номера строки (0, 1) в матрице состояний. Это означает, что строка 0 не сдвигается вообще, а строка 1 сдвигается на 1 полубайт. Рисунок P.9 показывает преобразование сдвига. Обратите внимание, что ShiftRows -преобразование работает одновременно только с одной строкой.

InvShiftRows

При дешифровании преобразование называется InvShiftRows и производит сдвиг вправо. Число сдвигов равно номеру строки в матрице состояний (0, 1).

Пример P.3

Рисунок P.10 показывает, как преобразуется состояние с использованием ShiftRows. Рисунок также показывает как преобразование InvShiftRow создает первоначальное состояние.

Смешивание

Подстановка обеспечивает преобразование SubNibbles и изменяет значение полубайта исходя только из первоначального значения полубайта и входа в таблицу; процесс не включает соседние полубайты. Мы можем сказать, что преобразование SubNibbles происходит внутри полубайта. Перестановка, обеспеченная ShiftRows -преобразованием, обменивает полубайты, не переставляя биты в байтах. Мы можем сказать, что ShiftRows -.преобразование обмена полубайтами. Нам нужно также преобразование между полубайтами, которое изменяет биты в полубайте, учитывая биты в соседних полубайтах. Мы должны смешать полубайты, чтобы обеспечить рассеивание на побитовом уровне.

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

MixColumns

Преобразование MixColumns работает на уровне столбца; оно преобразовывает каждый столбец состояния в новый столбец. Преобразование - фактически матричное умножение столбца состояния на квадратную матрицу констант. Полубайты в столбце состояний и в матрице констант интерпретируются как слова по 4 бита (или полиномы) с коэффициентами в GF(2).

Умножение байтов делается в GF(24) по модулю. (x4 + x + 1) или ( 10011 ). Сложение - это операция ИСКЛЮЧАЮЩЕЕ ИЛИ на 4 бита. Рисунок P.11 показывает преобразование MixColumns.

InvMixColumns

InvMixColumns -преобразование - в основном такое же, как преобразование MixColumns. Если две матрицы констант инверсны друг другу, то несложно доказать, что эти два преобразования инверсны друг другу.

Рисунок P.12 показывает, как преобразуется состояние, используя преобразование MixColumns. Мы также видим здесь, что преобразование InvMixColumns создает первоначальный текст.

Обратите внимание, что равные байты в старом состоянии неравны в новом состоянии. Например, два байта F во второй строке изменены на 4 и A.

Ключевое сложение

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

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

S-AES использует процесс, называемый расширением ключа (он будет рассмотрен позже в этом приложении), который из ключа шифра создает три ключа раунда. Каждые ключ раунда имеет длину 16 битов - он применяется как два слова по 8 битов. При сложении ключа и состояниякаждое слово рассматривают как матрицу-столбец.

AddRoundKey

AddRoimdKey обрабатывает один столбец одновременно. Это преобразование похоже на MixColumns. MixColumns умножает квадратную матрицу констант на каждый столбец состояний.

AddRoundKey складывает слово ключа раунда с каждой матрицей-столбцом состояний. Операции в MixColumns - матричное умножение; операции в AddRoundKey - матричное сложение. Сложение выполнено в поле GF(24). Поскольку сложение и вычитание в этом поле одинаковы, преобразование AddRoundKey самоинверсно. Рисунок P.13 показывает преобразование AddRoundKey.

P.3. Расширение ключа

Процедура расширения ключа создает три ключа раунда по 16 битов из единственного ключа шифра на 16 битов. Первые ключи раунда используются для предварительного преобразования ( AddRoundKey ); оставшиеся ключи применяются для последнего преобразования ( AddRoundKey ) в конце раунда 1 и раунда 2.

Процедура расширения ключей создает слово ключа раунда последовательно - слово за словом, где слово - массив 2 полубайта. Процедура создает 6 слов, которые обозначаются

w0, w1, w2, .....,w5.

Создание слов в S-AES

P.14 показывает, как создаются 6 слов из первоначального ключа.

Процесс создания слов в S-AES следующий:

RotWord

RotWord (вращение слова) - процедура, подобная преобразованию ShiftRows, но она применяется только к одной строке. Процедура получает слово как массив 2 полубайтов и сдвигает каждый полубайт влево с полным вращением (полный оборот) слова. В S-AES это заполнение 2 полубайтов в слове.

SubWord

SubWord (слово-заменитель) - процедура является подобной преобразованию SubNibbels, но она применяется только к 2 полубайтам. Процедура берет каждый полубайт в слове и заменяет его другим полубайтом. Она использует таблицы SubNibbels, показанные на рис. P.7.

Константы раунда

Каждая константа раунда, RC, является значением, содержащим 2 полубайта, в котором самый правый полубайт всегда нуль. Рисунок P.14 также показывает значение RC

Пример P.4

Таблица P.1 показывает, как вычисляется ключ для каждого раунда. При этом предполагается, что Алиса и Боб согласовали ключ 247516.

В каждом раунде второе слово вычисляется очень просто. Для вычисления первого слова мы должны сначала вычислить значение временного слова ( ti ), как это показано ниже:

P.4. Шифры

Теперь давайте посмотрим, как S-AES используют четыре типа преобразований для шифрования и дешифрования. Алгоритм шифрования будем называть шифратор, а алгоритм дешифрования - обратный шифратор.

S-AES - шифр не-Файстеля, и это означает, что каждое преобразование или группа преобразований должны быть обратимыми. Кроме того, шифратор и обратный шифратор должны использовать эти операции таким способом, при котором они отменяют друг друга. Ключи раунда должны использоваться в обратном порядке. Чтобы выполнить эти требования, преобразования применяются в установленном порядке в шифраторе и обратном шифраторе, как это показано на рис. P.15.

Первое: порядок использования SubNibbles и ShiftRows изменяется в обратном шифраторе. Второе: порядок MixColumns и AddRoundKey в обратном шифраторе также изменяется. Это отличие в порядке необходимо, чтобы сделать каждое преобразование в шифре соответствующим по порядку его инверсии в обратном шифраторе. Следовательно, алгоритм дешифрования в целом - инверсия алгоритма шифрования. Обратите внимание, что ключи раунда используются в обратном порядке.

Пример P.5

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

Исходный текст: 1A2316    Ключ: 247516        Зашифрованный текст: 3AD216

Рисунок P.16 показывает значение состояний в каждом раунде. Мы используем ключи раунда, сгенерированные в примере P.4.