Rijndael S-box

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

Передний S-бокс [ править ]

S-блок отображает 8-битный вход c в 8-битный выход s = S ( c ) . И вход, и выход интерпретируются как полиномы над GF (2) . Сначала вход отображается в его мультипликативный обратный в GF (2 ⁸ ) = GF (2) [ x ] / ( x ⁸ + x ⁴ + x ³ + x + 1) , конечное поле Rijndael . Ноль, как тождество, отображается на себя. Это преобразование известно как S-box Nyberg в честь его изобретателя Кайсы Ниберг . ^[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-блока, а [ 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-образный блок - это просто S-образный блок, работающий в обратном направлении. Например, обратный S-блок для 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 }$

Критерии дизайна [ править ]

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

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

Пример реализации на языке C [ править ]

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

#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 ; д  ^ =  д  <<  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 [ р ]  =  xformed  ^  0x63 ; }  while  ( p  ! =  1 );/ * 0 - особый случай, так как у него нет обратного * / sbox [ 0 ]  =  0x63 ; }

Ссылки [ править ]