InvShiftRows

InvShiftRows — это операция обратного преобразования, используемая в алгоритме симметричного шифрования AES (Advanced Encryption Standard) при расшифровании данных. Она является частью цикла обратного раунда и представляет собой обратную операцию к ShiftRows, выполняемой при зашифровании. InvShiftRows применяется к состоянию (state) — двумерному массиву байтов размером 4×4, где каждый столбец соответствует 32-битному слову, а каждая строка — байтам, сдвинутым в определённом порядке.

Место в алгоритме AES

AES (Rijndael) — блочный шифр, принятый в 2001 году Национальным институтом стандартов и технологий США (NIST) в качестве стандарта шифрования. Он работает с блоками данных фиксированной длины 128 бит (16 байт) и использует ключи длиной 128, 192 или 256 бит. Процесс шифрования включает несколько раундов (10, 12 или 14 в зависимости от длины ключа), каждый из которых состоит из четырёх преобразований: SubBytes, ShiftRows, MixColumns и AddRoundKey. При расшифровании применяются обратные операции: InvSubBytes, InvShiftRows, InvMixColumns и AddRoundKey (та же операция, но с обратным порядком ключей).

InvShiftRows выполняется на этапе расшифрования после InvSubBytes и перед InvMixColumns. В каждом раунде расшифрования (кроме последнего, где InvMixColumns не применяется) InvShiftRows изменяет порядок байтов в строках состояния, восстанавливая исходное расположение, нарушенное при шифровании.

Описание операции

Состояние в AES представляется как матрица 4×4, где строки нумеруются от 0 до 3, а столбцы — от 0 до 3. При шифровании операция ShiftRows выполняет циклический сдвиг каждой строки влево на определённое количество байтов: строка 0 не сдвигается, строка 1 сдвигается на 1 байт, строка 2 — на 2 байта, строка 3 — на 3 байта. InvShiftRows, соответственно, выполняет циклический сдвиг вправо на то же количество байтов:

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

Таким образом, InvShiftRows восстанавливает исходное расположение байтов, которое было до применения ShiftRows. Например, если после ShiftRows байт из позиции (1, 0) переместился в позицию (1, 1), то при InvShiftRows он возвращается обратно.

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

Для состояния S размером 4×4, где S[r][c] — байт в строке r и столбце c, операция InvShiftRows определяется как:

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

где shift[r] — величина сдвига для строки r:

• shift[0] = 0
• shift[1] = 1
• shift[2] = 2
• shift[3] = 3

Для расшифрования сдвиг выполняется вправо, что эквивалентно добавлению shift[r] к индексу столбца по модулю 4. В отличие от шифрования, где сдвиг влево соответствует вычитанию shift[r].

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

Рассмотрим состояние размером 4×4, где каждая ячейка содержит байт, обозначенный как a[r][c]. Исходное состояние после InvSubBytes (перед InvShiftRows):

`` a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23 a30 a31 a32 a33 ``

После применения InvShiftRows:

• Строка 0: без изменений — a00 a01 a02 a03
• Строка 1: сдвиг вправо на 1 — a13 a10 a11 a12
• Строка 2: сдвиг вправо на 2 — a22 a23 a20 a21
• Строка 3: сдвиг вправо на 3 — a31 a32 a33 a30

Результирующее состояние:

`` a00 a01 a02 a03 a13 a10 a11 a12 a22 a23 a20 a21 a31 a32 a33 a30 ``

Этот порядок соответствует обратному преобразованию по отношению к ShiftRows, который при шифровании сдвигает строки влево.

Значение в криптографии

InvShiftRows, как и ShiftRows, обеспечивает диффузию — перемешивание байтов внутри блока данных. В сочетании с другими операциями AES (SubBytes, MixColumns, AddRoundKey) она предотвращает статистические атаки, такие как линейный и дифференциальный криптоанализ. Без циклических сдвигов байты в одной строке не взаимодействовали бы с байтами из других строк, что сделало бы шифр уязвимым к атакам, основанным на разделении блока на независимые части.

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

Реализация

В программных реализациях AES InvShiftRows часто выполняется путём перестановки индексов байтов в массиве состояния. Для повышения производительности может использоваться табличная реализация (lookup table), где заранее вычисленные комбинации InvShiftRows и InvSubBytes объединяются в одну операцию. В аппаратных реализациях (например, на FPGA или ASIC) InvShiftRows реализуется через переключение проводников, что обеспечивает нулевую задержку.

В стандарте FIPS 197 (Federal Information Processing Standards Publication 197), опубликованном NIST, приведены точные спецификации как для ShiftRows, так и для InvShiftRows. Для AES-128, AES-192 и AES-256 операция InvShiftRows идентична, так как размер состояния и количество строк не зависят от длины ключа.

Связь с другими операциями

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

Источники

• FIPS PUB 197, Advanced Encryption Standard (AES), National Institute of Standards and Technology, 2001.
• Daemen, J., Rijmen, V. The Design of Rijndael: AES — The Advanced Encryption Standard. Springer, 2002.
• Stallings, W. Cryptography and Network Security: Principles and Practice. 6th ed., Pearson, 2014.