Rijndael S-box

Подстановочное поле, используемое в шифре Rijndael

S-box Rijndael — это блок подстановки ( таблица поиска ), используемый в шифре Rijndael, на котором основан криптографический алгоритм Advanced Encryption Standard (AES) . ^[1]

S-образный ящик вперед

S-box отображает 8-битный вход, c , в 8-битный выход, s = S ( c ) . Как вход, так и выход интерпретируются как полиномы над GF(2) . Сначала вход отображается в его мультипликативную обратную ячейку в GF(2 ⁸ ) = GF(2) [ x ]/( x ⁸ + x ⁴ + x ³ + x + 1) , конечном поле Рейндала . Ноль, как тождество, отображается в себя. Это преобразование известно как S-box Ниберга в честь его изобретателя Кайсы Ниберг . ^[2] Затем мультипликативная обратная ячейка преобразуется с помощью следующего аффинного преобразования :

${\displaystyle {\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\\s_{4}\\s_{5}\\s_{6}\\s_{7}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&1&1&1&1\\1&1&0&0&0&1&1&1\\1&1&1&0&0&0&1&1\\1&1&1&1&0&0&0&1\\1&1&1&1&1&0&0&0\\0&1&1&1&1&1&0&0\\0&0&1&1&1&1&1&0\\0&0&0&1&1&1&1&1\end{bmatrix}}{\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{bmatrix}}+{\begin{bmatrix}1\\1\\0\\0\\0\\1\\1\\0\end{bmatrix}}}$

где [ s ₇ , ..., s ₀ ] — выход S-box, а [ b ₇ , ..., b ₀ ] — мультипликативная инверсия в виде вектора.

Это аффинное преобразование представляет собой сумму множественных поворотов байта как вектора, где сложение представляет собой операцию XOR:

${\displaystyle s=b\oplus (b\lll 1)\oplus (b\lll 2)\oplus (b\lll 3)\oplus (b\lll 4)\oplus 63_{16}}$

где b представляет собой мультипликативную инверсию, — побитовый оператор XOR , — левый побитовый циклический сдвиг , а константа 63 ₁₆ = 01100011 ₂ задана в шестнадцатеричном формате . ${\displaystyle \oplus }$ ${\displaystyle \lll }$

Эквивалентная формулировка аффинного преобразования имеет вид

${\displaystyle s_{i}=b_{i}\oplus b_{(i+4)\operatorname {mod} 8}\oplus b_{(i+5)\operatorname {mod} 8}\oplus b_{(i+6)\operatorname {mod} 8}\oplus b_{(i+7)\operatorname {mod} 8}\oplus c_{i}}$

где s , b и c — 8-битные массивы, c — 01100011 ₂ , а нижние индексы указывают ссылку на индексированный бит. ^[3]

Другой эквивалент:

${\displaystyle s=\left(b\times 31_{10}\mod {257_{10}}\right)\oplus 99_{10}}$^{[4] [5]}

где — полиномиальное умножение и , взятых как битовые массивы. ${\displaystyle \times }$ ${\displaystyle b}$ ${\displaystyle 31_{10}}$

Обратный S-бокс

Обратный S-box — это просто S-box, запущенный в обратном порядке. Например, обратный S-box для b8 ₁₆ — это 9a ₁₆ . Он вычисляется путем вычисления сначала обратного аффинного преобразования входного значения, а затем мультипликативного обратного. Обратное аффинное преобразование выглядит следующим образом:

${\displaystyle {\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7}\end{bmatrix}}={\begin{bmatrix}0&0&1&0&0&1&0&1\\1&0&0&1&0&0&1&0\\0&1&0&0&1&0&0&1\\1&0&1&0&0&1&0&0\\0&1&0&1&0&0&1&0\\0&0&1&0&1&0&0&1\\1&0&0&1&0&1&0&0\\0&1&0&0&1&0&1&0\end{bmatrix}}{\begin{bmatrix}s_{0}\\s_{1}\\s_{2}\\s_{3}\\s_{4}\\s_{5}\\s_{6}\\s_{7}\end{bmatrix}}+{\begin{bmatrix}1\\0\\1\\0\\0\\0\\0\\0\end{bmatrix}}}$

Обратное аффинное преобразование также представляет собой сумму множественных поворотов байта как вектора, где сложение представляет собой операцию XOR:

${\displaystyle b=(s\lll 1)\oplus (s\lll 3)\oplus (s\lll 6)\oplus 5_{16}}$

где — побитовый оператор XOR , — левый побитовый циклический сдвиг , а константа 5 ₁₆ = 00000101 ₂ задана в шестнадцатеричном формате . ${\displaystyle \oplus }$ ${\displaystyle \lll }$

Критерии проектирования

Rijndael S-box был специально разработан для устойчивости к линейному и дифференциальному криптоанализу. Это было достигнуто путем минимизации корреляции между линейными преобразованиями входных/выходных битов и одновременной минимизации вероятности распространения разницы.

S-box Rijndael может быть заменен в шифре Rijndael, ^[1] , что развеивает подозрение о бэкдоре, встроенном в шифр, который эксплуатирует статический S-box. Авторы утверждают, что структура шифра Rijndael, вероятно, обеспечит достаточную устойчивость к дифференциальному и линейному криптоанализу, даже если используется S-box со «средними» свойствами распространения корреляции/разности (ср. «оптимальные» свойства S-box Rijndael).

Пример реализации на языке C

Следующий код на языке C вычисляет S-box:

#include <stdint.h> #define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))void initialize_aes_sbox ( uint8_t sbox [ 256 ]) { uint8_t p = 1 , q = 1 ; /* инвариант цикла: p * q == 1 в поле Галуа */ do { /* умножаем p на 3 */ p = p ^ ( p << 1 ) ^ ( p & 0x80 ? 0x1B : 0 );                        /* разделить q на 3 (равнозначно умножению на 0xf6) */ q ^= q << 1 ; q ^= q << 2 ; q ^= q << 4 ; q ^= q & 0x80 ? 0x09 : 0 ;                    /* вычислить аффинное преобразование */ uint8_t xformed = q ^ ROTL8 ( q , 1 ) ^ ROTL8 ( q , 2 ) ^ ROTL8 ( q , 3 ) ^ ROTL8 ( q , 4 );               sbox [ p ] = xformed ^ 0x63 ; } while ( p != 1 );        /* 0 — особый случай, поскольку он не имеет обратного */ sbox [ 0 ] = 0x63 ; }  

Ссылки

1. "Блочный шифр Rijndael" (PDF) . Получено 11 ноября 2013 г.
2. Nyberg K. (1991) Perfect indirect S-boxes. В: Davies DW (ред.) Advances in Cryptology – EUROCRYPT '91. EUROCRYPT 1991. Lecture Notes in Computer Science, т. 547. Springer, Берлин, Гейдельберг
3. "Расширенный стандарт шифрования" (PDF) . FIPS PUB 197: официальный стандарт AES . Федеральный стандарт обработки информации . 2001-11-26 . Получено 2010-04-29 .
4. Йорг Дж. Бухгольц (19 декабря 2001 г.). «Реализация расширенного стандарта шифрования в Matlab» (PDF) .
5. Цзе Цуй; Люшен Хуан; Хун Чжун; Чинчен Чан; Вэй Ян (май 2011 г.). "Улучшенный S-box AES и анализ его производительности" (PDF) . Архивировано из оригинала (PDF) 2016-03-04.