Rijndael S-box - Rijndael S-box
Rijndael S-бокс представляет собой окно подстановки ( таблица поиска ) используется в шифре Rijndael, которую Advanced Encryption Standard криптографический (AES) , алгоритм основан на.
Передняя S-образная коробка
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0a | 0b | 0c | 0d | 0e | 0f | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
00 | 63 | 7c | 77 | 7b | f2 | 6b | 6f | c5 | 30 | 01 | 67 | 2b | fe | d7 | ab | 76 |
10 | ок | 82 | c9 | 7д | фа | 59 | 47 | f0 | объявление | d4 | а2 | аф | 9c | а4 | 72 | c0 |
20 | b7 | fd | 93 | 26 год | 36 | 3f | f7 | cc | 34 | а5 | e5 | f1 | 71 | d8 | 31 год | 15 |
30 | 04 | c7 | 23 | c3 | 18 | 96 | 05 | 9а | 07 | 12 | 80 | e2 | eb | 27 | Би 2 | 75 |
40 | 09 | 83 | 2c | 1а | 1b | 6e | 5а | а0 | 52 | 3b | d6 | b3 | 29 | e3 | 2f | 84 |
50 | 53 | d1 | 00 | ред | 20 | fc | b1 | 5b | 6а | cb | быть | 39 | 4а | 4c | 58 | ср |
60 | d0 | ef | аа | fb | 43 год | 4d | 33 | 85 | 45 | f9 | 02 | 7f | 50 | 3c | 9f | а8 |
70 | 51 | а3 | 40 | 8f | 92 | 9d | 38 | f5 | до н.э | b6 | да | 21 год | 10 | ff | f3 | d2 |
80 | CD | 0c | 13 | ec | 5f | 97 | 44 год | 17 | c4 | а7 | 7e | 3d | 64 | 5d | 19 | 73 |
90 | 60 | 81 год | 4f | Округ Колумбия | 22 | 2а | 90 | 88 | 46 | ее | b8 | 14 | де | 5e | 0b | db |
а0 | e0 | 32 | 3а | 0a | 49 | 06 | 24 | 5c | c2 | d3 | ac | 62 | 91 | 95 | e4 | 79 |
b0 | e7 | c8 | 37 | 6d | 8d | d5 | 4e | а9 | 6c | 56 | f4 | еа | 65 | 7а | ае | 08 |
c0 | ба | 78 | 25 | 2e | 1c | а6 | b4 | c6 | e8 | дд | 74 | 1f | 4b | bd | 8b | 8а |
d0 | 70 | 3e | b5 | 66 | 48 | 03 | f6 | 0e | 61 | 35 год | 57 год | b9 | 86 | c1 | 1д | 9e |
e0 | e1 | f8 | 98 | 11 | 69 | d9 | 8e | 94 | 9b | 1e | 87 | e9 | ce | 55 | 28 год | df |
f0 | 8c | а1 | 89 | 0d | парень | e6 | 42 | 68 | 41 год | 99 | 2d | 0f | b0 | 54 | BB | 16 |
Столбец определяется младшим полубайтом , а строка - старшим полубайтом. Например, значение 9a 16 преобразуется в b8 16 . |
S-блок отображает 8-битный вход c в 8-битный выход s = S ( c ) . И вход, и выход интерпретируются как полиномы над GF (2) . Сначала вход отображается в его мультипликативную инверсию в GF (2 8 ) = GF (2) [ x ] / ( x 8 + x 4 + x 3 + x + 1) , конечное поле Rijndael . Ноль, как тождество, отображается на себя. Это преобразование известно как S-box Nyberg в честь его изобретателя Кайсы Ниберг . Затем мультипликативное обратное преобразование преобразуется с помощью следующего аффинного преобразования :
где [ s 7 ,…, s 0 ] - это выход S-блока, а [ b 7 ,…, b 0 ] - мультипликативный обратный вектор.
Это аффинное преобразование представляет собой сумму нескольких поворотов байта как вектора, где сложение - это операция XOR:
где b представляет собой мультипликативную инверсию, является побитовым оператором XOR , является побитовым циклическим сдвигом влево , а константа 63 16 = 01100011 2 дается в шестнадцатеричном формате .
Эквивалентная формулировка аффинного преобразования:
где s , b и c - 8-битные массивы, c - 01100011 2 , а нижние индексы указывают ссылку на индексированный бит.
Другой эквивалент:
где полиномиальное умножение и принимать в виде битовых массивов.
Обратный S-образный блок
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0a | 0b | 0c | 0d | 0e | 0f | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
00 | 52 | 09 | 6а | d5 | 30 | 36 | а5 | 38 | парень | 40 | а3 | 9e | 81 год | f3 | d7 | fb |
10 | 7c | e3 | 39 | 82 | 9b | 2f | ff | 87 | 34 | 8e | 43 год | 44 год | c4 | де | e9 | cb |
20 | 54 | 7b | 94 | 32 | а6 | c2 | 23 | 3d | ее | 4c | 95 | 0b | 42 | фа | c3 | 4e |
30 | 08 | 2e | а1 | 66 | 28 год | d9 | 24 | Би 2 | 76 | 5b | а2 | 49 | 6d | 8b | d1 | 25 |
40 | 72 | f8 | f6 | 64 | 86 | 68 | 98 | 16 | d4 | а4 | 5c | cc | 5d | 65 | b6 | 92 |
50 | 6c | 70 | 48 | 50 | fd | ред | b9 | да | 5e | 15 | 46 | 57 год | а7 | 8d | 9d | 84 |
60 | 90 | d8 | ab | 00 | 8c | до н.э | d3 | 0a | f7 | e4 | 58 | 05 | b8 | b3 | 45 | 06 |
70 | d0 | 2c | 1e | 8f | ок | 3f | 0f | 02 | c1 | аф | bd | 03 | 01 | 13 | 8а | 6b |
80 | 3а | 91 | 11 | 41 год | 4f | 67 | Округ Колумбия | еа | 97 | f2 | ср | ce | f0 | b4 | e6 | 73 |
90 | 96 | ac | 74 | 22 | e7 | объявление | 35 год | 85 | e2 | f9 | 37 | e8 | 1c | 75 | df | 6e |
а0 | 47 | f1 | 1а | 71 | 1д | 29 | c5 | 89 | 6f | b7 | 62 | 0e | аа | 18 | быть | 1b |
b0 | fc | 56 | 3e | 4b | c6 | d2 | 79 | 20 | 9а | db | c0 | fe | 78 | CD | 5а | f4 |
c0 | 1f | дд | а8 | 33 | 88 | 07 | c7 | 31 год | b1 | 12 | 10 | 59 | 27 | 80 | ec | 5f |
d0 | 60 | 51 | 7f | а9 | 19 | b5 | 4а | 0d | 2d | e5 | 7а | 9f | 93 | c9 | 9c | ef |
e0 | а0 | e0 | 3b | 4d | ае | 2а | f5 | b0 | c8 | eb | BB | 3c | 83 | 53 | 99 | 61 |
f0 | 17 | 2b | 04 | 7e | ба | 77 | d6 | 26 год | e1 | 69 | 14 | 63 | 55 | 21 год | 0c | 7д |
Обратный S-образный блок - это просто S-образный блок, работающий в обратном направлении. Например, обратный S-блок для b8 16 равен 9a 16 . Он вычисляется путем вычисления сначала обратного аффинного преобразования входного значения, а затем обратного мультипликативного преобразования. Обратное аффинное преобразование выглядит следующим образом:
Обратное аффинное преобразование также представляет собой сумму нескольких поворотов байта как вектора, где сложение - это операция XOR:
где - побитовый оператор XOR , - побитовый круговой сдвиг влево , а константа 5 16 = 00000101 2 дается в шестнадцатеричном формате .
Критерий дизайна
S-box Rijndael был специально разработан для защиты от линейного и дифференциального криптоанализа. Это было сделано путем минимизации корреляции между линейными преобразованиями входных / выходных битов и в то же время минимизации вероятности распространения разности.
S-блок Rijndael может быть заменен шифром Rijndael, который устраняет подозрение на наличие бэкдора, встроенного в шифр, который использует статический 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;
/* loop invariant: p * q == 1 in the Galois field */
do {
/* multiply p by 3 */
p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0);
/* divide q by 3 (equals multiplication by 0xf6) */
q ^= q << 1;
q ^= q << 2;
q ^= q << 4;
q ^= q & 0x80 ? 0x09 : 0;
/* compute the affine transformation */
uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4);
sbox[p] = xformed ^ 0x63;
} while (p != 1);
/* 0 is a special case since it has no inverse */
sbox[0] = 0x63;
}