Современная прикладная криптография (стр. 6 )

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

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

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

Всего к конкурсу AES были допущены 15 алгоритмов, разработанных криптографами из 12 стран - Австралии, Бельгии, Великобритании, Германии, Израиля, Канады, Коста-Рики, Норвегии, США, Франции, Южной Кореи и Японии.

В финал конкурса вышли следующие алгоритмы:

·  MARS (США),

·  RC6 (США),

·  RIJNDAEL (Бельгия),

·  SERPENT (Великобритания, Израиль, Норвегия),

·  TWOFISH (США).

Победителем конкурса стал криптоалгоритм RIJNDAEL.

Материалы конкурса AES, в том числе документацию по алгоритмам – финалистам конкурса, можно найти на странице http://www. nist. gov/aes/ .

Важно заметить, что алгоритм RIJNDAEL допускает различные размеры пар блока-ключа в битах, но в стандарте FIPS PUB 197 приняты только следующие: 128-128, 192-128, 256-128. Далее будет в основном излагаться описание в терминах RIJNDAEL.

Для понимания работы алгоритма RIJNDAEL напомним некоторые математические основы. В RIJNDAEL операции выполняются над байтами, которые рассматриваются как элементы поля Элементами являются двоичные многочлены степени N < 8, которые могут быть заданы строкой своих коэффициентов. Так, например, байту 01010111 (‘57h’ в шестнадцатеричной форме) соответствует многочлен

Умножение в поле может быть реализовано как операция умножения соответствующих многочленов с последующим приведением результата по модулю некоторого неприводимого двоичного многочлена восьмой степени. В RIJNDAEL для построения поля используют неприводимый многочлен показа.

В алгоритме RIJNDAEL авторы вводят операцию . - это операция умножения элемента поля на x. Тогда умножение на можно осуществить путем n-кратного повторения операции , а умножение на произвольный элемент поля можно осуществить, складывая результаты операций .

Структура шифра

Общие сведения

RIJNDAEL - это итерационный блочный шифр, имеющий следующие варьируемые параметры: длина блоков, длина ключа. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192 или 256 битам.(В AES не так).

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

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

рис. Пример представления состояния () и ключа шифрования ()

Входные данные для шифра обозначаются как байты состояния в порядке a00, a10, a20, a30, a01, a11, a21, a31, a41 ... После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке.

Число циклов зависит от значений и – числа 32-битных слов в информационном блоке и, соответственно, основном ключе алгоритма:

Зависимость числа циклов от числа столбцов в таблице состояний и длины ключа шифрования
	10	12	14
	12	12	14
	14	14	14

Цикловое преобразование

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

Round (State, RoundKey)

{

ByteSub(State); // замена байтов

ShiftRow(State); // сдвиг строк

MixColumn(State); // перемешивание столбцов

AddRoundKey(State, RoundKey); // добавление циклового ключа

}

Последний цикл шифрования немного отличается от остальных[1]. Вот как он выглядит:

FinalRound(State, RoundKey)

{

ByteSub(State); // замена байтов

ShiftRow(State); // сдвиг строк

AddRoundKey(State, RoundKey); // добавление циклового ключа

}

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

Замена байтов (ByteSub).

Заметим, что в AES употребляются несколько видоизмененные названия для этого и других преобразований, что можно рассматривать как еще одно различие в описании (Именно, SubBytes, ShiftRows, MixColumns, …). Излагать будем как в описании Rijndael.

Преобразование ByteSub является S-блоком и представляет собой нелинейную замену байтов, выполняемую независимо для каждого байта состояния. Таблицы замены S-блока являются инвертируемыми и построены как композиция двух преобразований:

переход к обратному элементу относительно умножения в поле GF(28), при этом нулевой элемент '00h' переходит сам в себя;

применение аффинного преобразования над 8-ми мерным двоичным вектором:

Применение описанного выше S-блока ко всем байтам состояния обозначено как ByteSub(State).

Операция обратная к ByteSub – это замена байтов с использованием инвертированной таблицы. Обратимость операции ByteSub следует из обратимости аффинного преобразования и наличия у каждого элемента поля обратного элемента.

Преобразование сдвига строк (ShiftRow)

Строки матрицы состояния (кроме нулевой строки) циклически сдвигаются на различное число байт. Строка 1 сдвигается на С1 байт, строка 2 - на С2 байт и строка 3 - на С3 байт. Значения сдвигов С1, С2 и С3 зависят от длины блока. Их величины приведены ниже в таблице.

Величина сдвига для разной длины блоков
	C1	C2	C3
4	1	2	3
6	1	2	3
8	1	3	4

Операция сдвига последних 3 строк состояния на определенную величину обозначена как ShiftRow (State).

Преобразование перемешивания столбцов (MixColumn)

В этом преобразовании столбцы состояния рассматриваются как многочлены над GF(28) и умножаются по модулю на многочлен

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