ShiftRows

ShiftRows — это один из этапов преобразования данных в алгоритме симметричного блочного шифрования AES (Advanced Encryption Standard), реализующий циклический сдвиг строк в матрице состояний. Относится к классу операций перемешивания (diffusion), обеспечивающих рассеивание битов исходного текста по всему блоку данных.

Описание и роль в алгоритме AES

AES обрабатывает данные блоками фиксированного размера 128 бит, которые представляются в виде двумерного массива байтов размером 4×4, называемого состоянием (state). Каждый байт состояния имеет координаты (строка, столбец). Преобразование ShiftRows применяется на каждом раунде шифрования (кроме последнего, где может отсутствовать операция MixColumns) после замены байтов в операции SubBytes и перед смешиванием столбцов в MixColumns.

Операция ShiftRows заключается в циклическом сдвиге влево байтов каждой строки состояния на различное количество позиций:

• Строка 0 (первая строка) не сдвигается.
• Строка 1 сдвигается на 1 байт влево.
• Строка 2 сдвигается на 2 байта влево.
• Строка 3 сдвигается на 3 байта влево.

Для вариантов AES с размером блока 128 бит (AES-128, AES-192, AES-256) схема сдвига одинакова. Для других вариантов Rijndael, поддерживающих блоки 192 и 256 бит, сдвиги могут отличаться (например, для блока 256 бит сдвиг строки 3 составляет 4 байта).

Математическое представление

Пусть состояние представлено как матрица байтов S размером 4×4, где элемент S[r][c] — байт, находящийся в строке r и столбце c. После преобразования ShiftRows элемент S'[r][c] определяется как:

S'[r][c] = S[r][(c + shift(r)) mod Nb]

где:

• Nb — количество столбцов в состоянии (для AES — 4);
• shift(r) — величина сдвига для строки r: shift(0)=0, shift(1)=1, shift(2)=2, shift(3)=3.

Обратное преобразование (InvShiftRows)

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

• Строка 0 не сдвигается;
• Строка 1 сдвигается на 1 байт вправо;
• Строка 2 сдвигается на 2 байта вправо;
• Строка 3 сдвигается на 3 байта вправо.

Пример выполнения ShiftRows

Исходное состояние (в шестнадцатеричном представлении):

После ShiftRows:

Как видно, строка 0 осталась без изменений, строка 1 сдвинута на 1 позицию влево (3d переместился в конец), строка 2 — на 2 позиции, строка 3 — на 3 позиции.

Криптографическое значение

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

Без ShiftRows каждый столбец состояния обрабатывался бы только в рамках операций SubBytes и MixColumns, что позволило бы атакующему анализировать столбцы по отдельности. Сдвиг строк гарантирует, что каждый байт шифротекста зависит от всех байтов исходного текста.

Реализация

В программных реализациях AES ShiftRows часто выполняется не как отдельная операция, а встраивается в табличные методы (T-tables), где комбинируются SubBytes, ShiftRows и MixColumns. В аппаратных реализациях сдвиг реализуется простой перекоммутацией проводников без задержек.

Критика и альтернативы

ShiftRows является частью семейства преобразований, используемых в AES, и не подвергался существенной критике. Альтернативные схемы сдвига предлагались в других алгоритмах, например, в Serpent используется битовое перемешивание, а в Twofish — псевдо-перестановки на основе MDS-матриц. Однако для AES схема ShiftRows была выбрана как оптимальная по соотношению безопасности и производительности.

Источники

• Joan Daemen, Vincent Rijmen. «The Design of Rijndael: AES — The Advanced Encryption Standard». Springer, 2002.
• National Institute of Standards and Technology (NIST). «FIPS PUB 197: Advanced Encryption Standard (AES)». 2001.
• William Stallings. «Криптография и защита сетей: принципы и практика». 6-е издание, 2014.
• Bruce Schneier. «Прикладная криптография». 2-е издание, 1996.