Стандарт шифрования США нового поколения

В 80-х годах в США был принят стандарт симметричного криптоалгоритма для внутреннего применения DES, который получил достаточно широкое распространение в свое время. Однако на текущий момент этот стандарт полностью неприемлем для использования по двум причинам:

1) основной – длина его ключа составляет 56 бит, что чрезвычайно мало на современном этапе развития ЭВМ;

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

Все это привело к тому, что в 1997 году Американский институт стандартизации (NIST) объявил конкурс на новый стандарт симметричного криптоалгоритма (AES – Advanced Encryption Standard).

На первом этапе в оргкомитет соревнования поступило 15 заявок из разных стран мира. В течение 2 лет специалисты комитета, исследуя самостоятельно, и изучая публикации других исследователей, выбрали 5 лучших представителей, прошедших в финал соревнования: MARS, RC3, Rijndael, Serpent и TwoFish. Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа.

2 октября 2000 года NIST объявил о своем выборе: победителем конкурса стал бельгийский алгоритм Rijndael, разработанный Йоаном Даменом (Joan Daemen) и Винсентом Райменом (Vincent Rijnmen). Название алгоритма составлено из первых букв фамилий авторов.

Шифр Rijndael выполнен в архитектуре "Квадрат" (Square) и имеет следующие параметры:

· размер блока – 128, 192 или 256 бит;

· размер ключа – 128, 192 или 256 бит;

· число раундов – 10, 12 или 14.

В алгоритме Rijndael блоки открытых и зашифрованных данных, соответственно T и T', представляются в виде массивов из N = 16, 24 или 32 байтов. В ходе криптографических преобразований исходный и зашифрованный блоки данных, а также все промежуточные результаты процесса шифрования (состояния) интерпретируются как матрицы байтов, содержащие по 4 строки. Таким образом, в зависимости от размера блока, размер матрицы составляет байта. Количество столбцов , где . Матрицы заполняются байтами входного блока (открытого текста при шифровании и шифртекста при расшифровании) по столбцам – сверху вниз и слева направо, и

точно в таком же порядке извлекаются байты из матрицы-результата:

 

. (3.3)

 

Схема преобразования данных при шифровании показана на рис. 3.3. На рисунке использованы следующие обозначения: T, T' – открытый и зашифрованный блоки данных соответственно; i-тый ключевой элемент; F, F' – регулярное нелинейное преобразование и преобразование последнего раунда соответственно; – промежуточное состояние шифруемого блока после прибавления i-того ключевого элемента; R – количество раундов шифрования.

 

Рис. 3.3. Схема преобразования информации в алгоритме шифрования блока Rijndael.

 

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

.

Число раундов шифрования определяется в зависимости от размера блока и ключа: из двух размеров выбирается максимальный, и если он равен 128 бит, то используется 10 раундов, если 192 бита, то 12, и если 256 – то 14 раундов. Эту зависимость можно представить таблицей 3.2.

 

Таблица 3.2

Зависимость количества раундов от размеров блока и ключа
в алгоритме Rijndael

Размер блока (бит) Размер ключа (бит)

 

Прибавление ключевых элементов, которым начинается и заканчивается процесс шифрования, а также некоторые другие операции раундового преобразования выполняется побайтно в конечном поле Галуа GF(28). Операцией сложения в нем является побитовое сложение по модулю 2. Соответственно, каждый ключевой элемент является байтовой матрицей того же самого размера, что и блок данных.

За один раунд шифрования преобразуется полный блок данных, а не его часть, как в сетях Фейстеля. На последнем раунде функция нелинейного преобразования отличается от аналогичной функции, используемой в остальных раундах – это сделано для обеспечения алгоритмической эквивалентности прямого и обратного преобразований шифрования.

Нелинейное преобразование F матрицы данных состоит из трех шагов: ByteSub – замены байтов матрицы на новые значения (S[]), ShiftRows – циклического сдвига строк матрицы влево ( ) и MixColumns – умножения матрицы данных слева на постоянную матрицу-циркулянт M:

.

Все входные (X), выходные (X') и промежуточные значения преобразования являются матрицами байтов одинакового размера .

Функция преобразования последнего раунда F' отличается от регулярной функции преобразования F отсутствием шага MixColumns:

.

В преобразовании ByteSub каждый байт исходной матрицы данных заменяется новым значением в соответствии с единственной таблицей замены (S-Box). В этой таблице замен (табл. 3.3) заменяющее значение выбирается на пересечении строки, определяемой старшей 16-ричной цифрой заменяемого значения, и столбца, определяемого его младшей цифрой.

 

Таблица 3.3

Таблица замен преобразования ByteSub

  x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF
0x 7c 7b f2 6b 6f c5 2b fe d7 ab
1x ca c9 7d fa f0 ad d4 a2 af 9c a4 c0
2x b7 fd 3f f7 cc A5 e5 f1 d8
3x c7 c3 9a e2 eb b2
4x 2c 1a 1b 6e 5a a0 3b d6 b3 e3 2f
5x d1 ed fc b1 5b 6a cb be 4a 4c cf
6x d0 ef aa fb 4d f9 7f 3c 9f a8
7x a3 8f 9d f5 bc b6 da ff f3 d2
8x cd 0c ec 5f c4 a7 7e 3d 5d
9x 4f dc 2a ee b8 de 5e 0b db
Ax e0 3a 0a 5c c2 d3 ac e4
Bx e7 c8 6d 8d d5 4e a9 6c f4 ea 7a ae
Cx ba 2e 1c a6 b4 c6 e8 dd 1f 4b bd 8b 8a
Dx 3e b5 f6 0e b9 c1 1d 9e
Ex e1 f8 d9 8e 9b 1e e9 ce df
Fx 8c a1 0d bf e6 2d 0f b0 bb

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

Таблица 3.4

Зависимость количества сдвигов строки
в преобразовании ShiftRows

№ строки Количество столбцов (n)

 

На шаге MixColumns каждый столбец исходной матрицы слева умножается на постоянную матрицу-циркулянт M:

,

.

При выполнении матричного умножения операции сложения и умножения выполняются в конечном поле GF(28). Матрица M является циркулянтом: каждая ее строка получается циклическим сдвигом предыдущей строки вправо на один элемент. Элементы матрицы выбраны таким образом, чтобы свести к минимуму трудоемкость операции умножения: в ней присутствуют лишь небольшие по значению числа 01, 02 и 03, половина элементов – единичные, т.е. реального умножения выполнять для них не требуется. Этим самым обеспечивается высокая эффективность возможных реализаций этой операции.

Следует добавить, что операция умножения в конечном поле GF(28) является достаточно трудоемкой в программной реализации и никаким образом не сводится к обычному арифметическому умножению. Если умножение двоичных чисел реализуется сдвигами и обычным арифметическим суммированием, то умножение полиномов над полем GF(28) – теми же сдвигами и побитовым суммированием по модулю 2. Однако в шифре Rijndael одним из множителей всегда является константа и размер операндов невелик – один байт. Это позволяет реализовать умножение на константу в поле GF(28) как замену, что существенно повышает эффективность программной реализации. Для каждого множителя-константы при этом требуется свой отдельный узел замен. Напротив, наиболее эффективной аппаратной реализацией этой операции является реализация в виде серии сдвигов и побитовых сложений по модулю два в соответствие с ее непосредственным определением.

Рис. 3.4 иллюстрирует операции ByteSub, ShiftRows и MixColumns.

Размер ключа в шифре Rijndael равен 128, 192 или 256 бит. Размер ключевого элемента, используемого на раунде, совпадает с размером блока и также равен 128, 192 или 256 бит независимо от размера ключа. Число раундов шифрования находится в пределах от 10 до 14. Массив ключевых элементов вырабатывается из ключа шифрования с использованием KeyExpansion – процедуры "развертывания" ключа.

Алгоритм KeyExpansion (развертывания ключа) оперирует 32-битовыми ключевыми словами Wi, интерпретируя их как четырехбайтовые массивы: .

Первые (здесь – количество байтов ключа) ключевых слов получаются простым разделением ключа K на 4-байтовые фрагменты аналогично тому, как байтами шифруемого блока заполняются столбцы матрицы данных:

Необходимое число ключевых элементов на 1 больше числа раундов R, каждый ключевой элемент по размеру равен блоку данных ( байт) и содержит ключевых слов. Таким образом, всего необходимо ключевых слов.

 

 

Рис. 3.4. Иллюстрация основных операций шифра Rijndael.

 

 

Первые q ключевых слов составлены из байтов ключа как показано выше, остальные Q – q вырабатываются по следующему алгоритму.

При размере ключа 16 или 24 байта ( ) используется следующая итерационная формула:

а при размере ключа 32 байта (q = 8) – следующая:

В приведенных выше формулах использованы следующие обозначения: S(W) – побайтовая замена с использованием штатного узла замен S, – циклический сдвиг 4-байтового вектора на один элемент влево, – раундовая константа, представляющая собой 4-байтовый вектор , где возведение в степень выполняется в поле GF(28).

Таким образом, все усложняющее преобразование может быть представлено в следующей форме:

Как видно из приведенных выше соотношений, ключевые слова вырабатываются порциями, по размеру равными ключу, причем первое слово каждой порции вырабатывается по усложненной схеме с использованием приведенного выше нелинейного преобразования, а остальные – простым побитовым суммированием непосредственно предшествующего элемента с элементом, имеющим тот же порядковый номер в предыдущей порции ключевых слов. При размере ключа 256 бит (32 байта) усложнение используется также и при выработке каждого пятого элемента порции – при нумерации с нуля он имеет индекс 4 в группе из q слов.

Каждые последовательно выработанные ключевых слов (включая и те, что получены непосредственно из ключа) объединяются в раундовые ключевые элементы:

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

В этом случае столбцы матрицы ключевого элемента образуются ключевыми словами:

Процесс расшифрования блока данных алгоритмически идентичен процессу его шифрования (рис. 3.3), если через T обозначить блок зашифрованных данных, а через T' – открытых. Расшифрование отличается от шифрования по следующим четырем пунктам:

1. Ключевые элементы используются в порядке, обратном тому, в котором они используются при шифровании. Кроме того, все ключевые элементы, кроме первого и последнего, должны быть умножены слева на матрицу, обратную матрице M. Таким образом, если при шифровании используется следующая последовательность ключевых элементов , то при расшифровании должна быть использована следующая последовательность элементов: .

2. На шаге побайтовой замены используется узел замен обратный тому, что применяется в процедуре шифрования S. Это означает, что каково бы ни было байтовое значение b, всегда справедливо следующее соотношение: . Указанный узел замен представлен в табл. 3.5.

Таблица 3.5

Таблица замен обратного преобразования ByteSub

  x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF
0x 6a d5 a5 bf a3 9e f3 d7 fb
1x 7c e3 9b 2f ff 8e c4 de e9 cb
2x 7b a6 c2 3d ee 4c 0b fa c3 4e
3x 2e a1 d9 b2 5b a2 6d 8b d1
4x f8 f6 d4 a4 5c cc 5d b6
5x 6c fd ed b9 da 5e a7 8d 9d
6x d8 ab 8c bc d3 0a f7 e4 b8 b3
7x d0 2c 1e 8f ca 3f 0f c1 af bd 8a 6b
8x 3a 4f dc ea f2 cf ce f0 b4 e6
9x ac e7 ad e2 f9 e8 1c df 6e
Ax f1 1a 1d c5 6f b7 0e aa be 1b
Bx fc 3e 4b c6 d2 9a db c0 fe cd 5a f4
Cx 1f dd a8 c7 b1 ec 5f
Dx 7f a9 b5 4a 0d 2d e5 7a 9f c9 9c ef
Ex a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c
Fx 2b 7e ba d6 e1 0c 7d

 

3. На шаге построчного вращения матрицы данных осуществляется циклический сдвиг строк на то же самое количество элементов, что и при шифровании, но в обратную сторону – вправо.

4. На шаге умножения слева на постоянную матрицу используется матрица , обратная используемой при шифровании матрице M: