Rijndael S-box - Rijndael S-box

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

Передняя S-образная коробка

S-бокс AES

	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	7d	фа	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
Столбец определяется наименее значимым грызть, а строку - по старшему полубайту. Например, значение 9a16 конвертируется в b816.

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

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

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

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

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

${\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, б, и 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-образный блок

	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	7d

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

${\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}}$

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

Критерий дизайна

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

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

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

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

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

Рекомендации

1. "Блочный шифр Rijndael" (PDF). Получено 2013-11-11.
2. Ниберг К. (1991) Совершенные нелинейные S-блоки. В: Дэвис Д.В. (ред.) Достижения в криптологии - EUROCRYPT ’91. EUROCRYPT 1991. Lecture Notes in Computer Science, vol 547. Springer, Berlin, Heidelberg.
3. «Расширенный стандарт шифрования» (PDF). FIPS PUB 197: официальный стандарт AES. Федеральный стандарт обработки информации. 2001-11-26. Получено 2010-04-29.
4. Йорг Й. Бухгольц (19 декабря 2001 г.). «Реализация в Matlab стандарта Advanced Encryption Standard» (PDF).
5. Цзе Цуй; Люшэн Хуан; Хун Чжун; Чинчен Чанг; Вэй Ян (май 2011 г.). «Улучшенный S-box AES и анализ его производительности» (PDF).