InvMixColumns

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

Математическая основа

InvMixColumns, как и MixColumns, оперирует с байтами как с элементами конечного поля Галуа GF(2⁸). В AES используется поле, порождённое неприводимым многочленом \(x^8 + x^4 + x^3 + x + 1\) (0x11B). Все операции сложения и умножения выполняются по модулю этого многочлена. Сложение в GF(2⁸) эквивалентно побитовой операции XOR.

Прямое преобразование MixColumns выполняет умножение каждого столбца матрицы состояния (4 байта) на фиксированную матрицу \(M\):

\[ \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix} \]

InvMixColumns использует обратную матрицу \(M^{-1}\), которая в GF(2⁸) имеет вид:

\[ \begin{bmatrix} 0E & 0B & 0D & 09 \\ 09 & 0E & 0B & 0D \\ 0D & 09 & 0E & 0B \\ 0B & 0D & 09 & 0E \end{bmatrix} \]

Здесь числа 0E, 0B, 0D, 09 — это шестнадцатеричные представления байтов, которые интерпретируются как элементы GF(2⁸). Умножение на эти константы выполняется в поле Галуа.

Применение в AES

В стандарте AES (FIPS PUB 197) используется сеть подстановочно-перестановочного типа (SP-сеть). Процесс шифрования включает в себя следующие раундовые преобразования:

• SubBytes (нелинейная замена байтов через S-блок);
• ShiftRows (циклический сдвиг строк);
• MixColumns (смешивание столбцов);
• AddRoundKey (наложение раундового ключа).

Расшифрование в AES может быть реализовано двумя способами:

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

Вычислительная реализация

Умножение в GF(2⁸) на константы 0x0E, 0x0B, 0x0D, 0x09 может быть реализовано через последовательность операций умножения на 0x02 (xtime) и сложения (XOR). Например, умножение байта \(a\) на 0x0E (0b1110) можно представить как:

\[ a \cdot 0E = (a \cdot 02) \oplus (a \cdot 04) \oplus (a \cdot 08) \]

где \(a \cdot 02\) — это операция xtime (сдвиг влево на 1 бит с последующим условным XOR с 0x1B), а \(a \cdot 04\) и \(a \cdot 08\) — это последовательные применения xtime.

Для повышения производительности в программных реализациях часто используют таблицы предвычислений (T-tables). В случае расшифрования применяются обратные T-tables (InvT-tables), которые объединяют в себе InvSubBytes, InvShiftRows и InvMixColumns. Это позволяет выполнить расшифрование за то же количество операций, что и шифрование.

Свойства

• Линейность: InvMixColumns является линейным преобразованием, то есть для любых двух столбцов \(A\) и \(B\) и константы \(c\) выполняется: InvMixColumns(\(A \oplus B\)) = InvMixColumns(\(A\)) \(\oplus\) InvMixColumns(\(B\)).
• Обратимость: InvMixColumns является точной обратной операцией к MixColumns: MixColumns(InvMixColumns(\(S\))) = \(S\) и InvMixColumns(MixColumns(\(S\))) = \(S\) для любого состояния \(S\).
• Диффузия: InvMixColumns, как и MixColumns, обеспечивает распространение изменений по всем байтам столбца. Изменение одного байта на входе InvMixColumns влияет на все четыре байта на выходе.

Ошибки реализации

Распространённой ошибкой при реализации расшифрования AES является пропуск InvMixColumns в последнем раунде. В стандарте AES указано, что InvMixColumns не применяется в последнем раунде расшифрования, так же как MixColumns не применяется в последнем раунде шифрования. Если это правило нарушается, расшифрование даёт неверный результат.

Другая ошибка — использование неправильных констант (например, 0x01, 0x02, 0x03 вместо 0x09, 0x0B, 0x0D, 0x0E). Это приводит к необратимости преобразования.

Сравнение с MixColumns

Источники

• 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 edition, Pearson, 2014.