Шифрование содержимого базы данных

⇐ ПредыдущаяСтр 3 из 4Следующая ⇒

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

В качестве алгоритма шифрования выбран алгоритм AES. На текущий момент этот алгоритм считается достаточно надежным, имеет приемлемую длину ключа и отсутствие метода простого взлома [14].

AES является стандартом, основанным на алгоритме Rijndael. Для AES длина блока входных данных (input) и длина блока с промежуточным результатом шифрования (State) постоянна и равна 128 бит, а длина шифроключа K составляет 128, 192, или 256 бит. При этом, исходный алгоритм Rijndael допускает длину ключа и размер блока от 128 до 256 бит
с шагом в 32 бита. Для обозначения выбранных длин input, State и K
в 32-битных словах используются обозначения: для input и State, для K соответствующих длин [15].

В начале шифрования input копируется в массив State по правилу:

, (5)

для и {\displaystyle 0\leq c< Nb}.

После этого к State применяется процедура AddRoundKey() и затем State проходит через процедуру трансформации (раунд) 10, 12, или 14 раз
(в зависимости от длины ключа), при этом надо учесть, что последний раунд несколько отличается от предыдущих. В итоге, после завершения последнего раунда трансформации, State копируется в блок выходных данных (output)
по правилу:

, (6)

для и {\displaystyle 0\leq c< Nb}.

Отдельные трансформации SubBytes(), ShiftRows(), MixColumns() и AddRoundKey() обрабатывают State. Массив w [ ] содержит key schedule.

В рассматриваемой версии алгоритма AES-128 ключ шифра состоит из 128 битов, поделенных на 16 байтов: k₀, k₁, k₂, … k₁₅ и записывается
в столбцы матрицы InputKey. Каждый столбец матрицы InputKey образует слово, то есть фактически ключ шифра – это четыре слова w₀, w₁, w₂, w₃,
где w₀= k₀, k₁, k₂, k₃, w₁= k₄, k₅, k₆, k₇ и так далее (рисунок 9).

k₀	k₄	k₈	k₁₂
k₁	k₅	k₉	k₁₃
k₂	k₆	k₁₀	k₁₄
k₃	k₇	k₁₁	k₁₅

w₀

w₁

w₂

w₃

w₄

w₅

w₆

w₇

…

w₄₂

w₄₃

ключ первого раунда

ключ второго раунда

Рисунок 10 – Формирование ключей раунда

Из этих слов с помощью специального алгоритма (о нем позже) образуется последовательность из 44 слов: w₀, w₁, w₂, …, w₄₃ (каждое слово по 32 бита).

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

Рисунок 11 – Схема шифрования и дешифрования AES

Перед первым раундом выполняется операция AddRoundKey (суммирование по модулю 2 с начальным ключом шифра). Преобразования, выполненные в одном раунде, обозначают Round (State, RoundKey)
где переменная State является матрицей, описывающей данные на входе раунда и на его выходе после шифрования; переменная RoundKey – матрица, содержащая раундовый ключ.

Раунд состоит из 4 различных преобразований (рисунок 11).

В данные преобразования входят:

1) побайтовая подстановка в S–боксе с фиксированной таблицей замен (SubBytes);

2) побайтовый сдвиг строк матрицы State на различное количество байт (ShiftRows);

3) перемешивание байт в столбцах (MixColumns);

4) сложение по модулю 2 с раундовым ключом (AddRoundKey).

Последний раунд несколько отличается от предыдущих тем, что не задействует функцию MixColumns [16, 17].

Рисунок 12 – Схема раундов шифрования и дешифрования AES

При дешифровании в каждом раунде выполняются обратные операции: InvShiftRows, InvSubBytes, AddRoundKey и InvMixColumns. Порядок выполнения операций при шифровании и дешифровании различен, причины чего будут ясны после детального рассмотрения каждого преобразования.

Поскольку алгоритм использует конечное поле Галуа GF(2⁸), рассмот-рим математические основы шифра AES.

Для описания алгоритма используется конечное поле Галуа GF(2⁸), построенное как расширение поля GF(2⁸) = {0, 1} по модулю неприводимого многочлена. Элементами поля GF(2⁸) являются многочлены вида:

. (7)

Степень многочленов меньше 8, а коэффициенты b₇, b₆, …, b₀Î {0, 1}. Операции в поле выполняются по модулю . Всего в поле GF(2⁸) насчитывается 256 многочленов.

Представление двоичного числа b₇b₆b₅b₄b₃b₂b₁b₀ в виде многочлена
с коэффициентами b₇, b₆, …, b₀ позволяет интерпретировать байт как битовый многочлен в конечном поле GF(2⁸):

. (8)

Например, байт 63 задает последовательность битов 01100011
и определяет конкретный элемент поля 01100011 « .

Рассмотрим основные математические операции в поле GF(2⁸):

1) сложение байт можно выполнить любым из трех способов:

1.1) представить байты битовыми многочленами и сложить
их по обычному правилу суммирования многочленов с последующим приведением коэффициентов суммы по модулю 2 (операция XOR над коэффициентами);

1.2) суммировать по модулю 2 соответствующие биты в байтах;

1.3) сложить байты в шестнадцатеричной системе исчисления;

Например, следующие три записи эквивалентны:

– представление в виде многочленов:

; (9)

– битовое представление:

; (10)

– шестнадцатеричное представление:

{57} Å {83}= {D4}; (11)

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

Перемножение многочленов в поле можно упростить, введя операцию умножения битового многочлена на :

. (12)

Для любого ненулевого битового многочлена в поле GF(2⁸) существует многочлен обратный к нему по умножению, то есть

). (13)

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

2.7.1 Многочлены с коэффициентами,
принадлежащими полю GF(2⁸)

Многочлены третьей степени с коэффициентами Î GF(2⁸) из конеч-ного поля имеют вид:

(14)

Таким образом, в этих многочленах в роли коэффициентов при неизвестных задействованы байты вместо бит. Далее такие многочлены будем представлять в форме слова [a₀, a₁, a₂, a₃].

В стандарте AES при умножении многочленов используется приведение по модулю другого многочлена .

Для изучения арифметики рассматриваемых многочленов введем дополнительно многочлен:

, (15)

где Î GF(2⁸).

Тогда сумма многочленов и имеет вид:

. (16)

Умножение является более сложной операцией. Пусть, мы перемножаем
два многочлена:

. (18)

Результатом умножения будет многочлен

, (19)

где ;

;

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

. (20)

Поэтому в произведении коэффициенты при степенях , 0, 1, 2, 3 равны сумме произведений по индексам, для которых ,

, = 0, 1, 2, 3. Таким образом, после приведения по модулю получим:

, (21)

где ;

;

Рассмотрим подробнее преобразования раунда шифрования:

1) операция SubBytes. Операция выполняет нелинейную замену байтов, выполняемую независимо с каждым байтом матрицы State. Замена обратима и построена путем комбинации двух преобразований над входным байтом (рисунок 12);

2) нахождение обратного (инвертированного) элемента относительно умножения в поле GF(2⁸) (считается, что нулевой байт {00} переходит сам в себя);

3) выполнение некого аффинного преобразования: умножение инвертированного байта на многочлен

(22)

и суммирование с многочленом

(23)

в поле F₂.

В матричной форме процедура SubBytes записывается как

, (24)

где через обозначены входные биты, а через – выходные.

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

Рисунок 13 – Операция SubBytes

Созданную на основе операции SubBytes специальную таблицу замен байтов в шестнадцатеричной системе называют S–боксом или таблицей преобразований SubBytes (таблица 13).

Таблица 13 – Таблица преобразований SubBytes

Например, если _{1, 1} = , то результат замены этого байта следует искать на пересечении строки с индексом и столбца с индексом .

Операция ShiftRows применяется к строкам матрицы State – ее первая строка неподвижна, а элементы нижних трех строк циклически сдвигаются вправо на 1, 2 и 3 байта соответственно (рисунок 14).

По сути это перестановка элементов матрицы, в которой участвуют только элементы строк, поэтому преобразование обратимо.

Рисунок 14 – Операция ShiftRows

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

(25)

по модулю многочлена (рисунок 15).

Как показано выше, такую операцию можно записать в матричном виде как

(26)

Рисунок 15 – Операция MixColumns

Функция AddRoundKey(State, RoundKey) побитово складывает элементы переменной RoundKey и элементы переменной State по принципу: i–й столбец данных ( 0, 1, 2, 3) складывается с определенным 4–байтовым фрагментом расширенного ключа , где – номер поточного раунда алгоритма (рисунок 16).

При шифровании первое сложение ключа раунда происходит
до первого выполнения операции SubBytes.

Рисунок 16 – Операция AddRoundKey

Рисунок 17 демонстрирует свойства рассеивания и перемешивания информации в ходе шифрование алгоритмом AES. Видно, что два раунда обеспечивают полное рассеивание и перемешивание информации. Достигается это за счет использования функций ShiftRows и MixColumns. Операция SubBytes придает шифрованию стойкость против дифферен-циального криптоанализа, а операция AddRoundKey обеспечивает необходимую секретную случайность.

Рисунок 17 – Перемешивание информации

Для трех вариантов ключей AES полный перебор требует 2¹²⁷, 2¹⁹¹
или 2²⁵⁵ операций соответственно.

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

1) дифференциальный криптоанализ;

2) линейныйкриптоанализ;

3)криптоанализ на основе связанных ключей (слабых ключей
в алгоритме нет)

⇐ Предыдущая 1 234 Следующая ⇒