К середине 1990-х годов стало очевидно, что 56 бит ключа при шифровании DES стало недостаточно, шифр весьма медленно работает в программных реализациях и был рассчитан на 4-х битные процессоры 1970-х годов. Поэтому в 1997 году NIST объявил о запуске программы по принятию нового криптостандарта AES (Advanced Encryption Standard). Основные требования к алгоритму AES: размер блока в 128 бит и возможность использования ключей размером 128, 192 и 256 бит.
В августе 1998 года прошла первая конференция кандидатов на AES, где были объявлены 15 принятых на конкурс алгоритмов. Одна из самых больших проблем при сравнении разнообразных алгоритмов – это два конфликтующих между собой требования к конструкции шифра: стойкость и скорость. В течение 2-х лет специалисты комитета, исследуя самостоятельно и изучая публикации других исследователей, выбрали пять лучших представителей, прошедших во второй тур соревнования. Ими стали MARS, RC6, Rijndael, Serpent, TwoFish. Комплексный анализ всех достоинств и недостатков привёл к тому, что 2 октября 2000 года новым стандартом блочного шифрования в США был объявлен алгоритм Rijndael.
Алгоритм Rijndael создавался таким образом, чтобы с помощью него можно было шифровать блоки размером 128, 192 и 256 бит с использованием ключа размером 128, 192 и 256 бит. Ниже рассмотрен алгоритм, шифрующий данные блоками размером 128 бит с использованием ключа, соответственно, размером 128 бит. В целом алгоритм состоит из одного раунда инициализации и 10 раундов шифрования (количество раундов также зависит от размеров блока и ключа).
Раунд инициализации состоит из одной операции сложения входного текста с подключом (AddRoundKey). Первые 9 раундов шифрования включают в себя четыре операции каждый, которые выполняются в следующем порядке:
побайтовая замена с помощью S-таблицы (ByteSub);
сдвиг строк (ShiftRow);
умножение столбцов на матрицу M (MixColumn);
сложение с подключом (AddRoundKey).
И, наконец, последний, десятый раунд, состоит из трёх операций:
побайтовая замена;
сдвиг строк;
сложение с подключом.
Входной текст представляется в виде матрицы 4х4, в которой каждый элемент составляет один байт (т.е. всего 16 байт по 8 бит, итого 128 бит). Если входной текст B=B00B01B02B03B10B11B12B13B20B21B22B23B30B31B32B33, то коэффициенты при 8-ми битовых элементах обозначают позицию элемента в матрице. Все операции выполняются с этой матрицей. Аналогичным образом представляется и 128-ми битовый ключ.
Операция сложения текста с подключом представляет собой операцию XOR соответствующих элементов обеих матриц (AddRoundKey).
Операция побайтовой замены состоит в замене каждого элемента матрицы элементом из S-таблицы размером 16х16 (по аналогии с алгоритмом DES). Строка, в которой стоит элемент S-таблицы, определяется по первым четырём битам байта, а столбец – по последним (ByteSub).
Сдвиг строк выполняется следующим образом: первая строка матрицы остаётся неизменной, во второй строке производится циклический сдвиг влево на один элемент, в третьей – на два элемента, в четвёртой – на три. Затем каждый столбец умножается на фиксированную матрицу М.
Подключи для каждого раунда, представляемые в виде матриц размером 4х4, считаются из подключа предыдущего раунда. Подключ первого раунда генерируется из ключа шифрования.
Первый столбец подключа вычисляется в три этапа:
1. Последний столбец подключа предыдущего раунда циклически сдвигается влево на один элемент.
2. Побайтовая замена элементов столбца по S-таблице происходит аналогичным образом, как и в тексте.
3. Результат суммируется с первым столбцом и столбцом фиксированной матрицы Rcon (номер столбца определяется по порядковому номеру раунда) с помощью операции исключающего или.
Остальные столбцы получаются применением операции XOR к предыдущему столбцу и столбцу предыдущего раунда с тем же номером, что и у вычисляемого.
Расшифрование по алгоритму Rijndael отличается от шифрования по четырём пунктам:
1. Побайтовая замена при расшифровании является инверсной к побайтовой замене при шифровании.
2. Сдвиг строк происходит в обратном направлении (вправо) на то же самое число элементов, что и при шифровании.
3. Подключи используются в обратном порядке, причём все за исключением первого и последнего умножаются справа на матрицу транспонированную матрице M.
4. При умножении текста на матрицу вместо матрицы M используется транспонированная к ней.
Основным преимуществом Rijndael является то, что алгоритм реализует нетрадиционную схему, отличную от схемы Фейстеля, используемой в большинстве симметричных блочных алгоритмов (см. табл. 9.1). Он обладает хорошим быстродействием на всех платформах от 8-битных до 64-битных, очень высоким потенциальным параллелизмом, минимальными требованиями к оперативной памяти. Процедуры шифрования и расшифрования отличаются достаточно сильно по сравнению с простым изменением порядка ключей. В дополнении к этому в алгоритме можно использовать разнообразные размеры ключа и блоков открытого текста, что также затрудняет процесс взлома.
