Rijndael S-box

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

Передний S-бокс

S-блок AES
	00	01	02	03	04	05	06	07	08	09	0а	0б	0с	0д	0е	0ф
00	63	7с	77	7б	f2	6б	6ф	с5	30	01	67	2б	фе	d7	аб	76
10	что	82	с9	7д	но	59	47	f0	объявление	d4	а2	из	9с	a4	72	с0
20	b7	ФД	93	26	36	3ф	f7	копия	34	а5	е5	ф1	71	d8	31	15
30	04	с7	23	с3	18	96	05	9а	07	12	80	е2	Эб	27	б2	75
40	09	83	2с	1а	1б	6е	5а	а0	52	3б	d6	б3	29	е3	2ф	84
50	53	d1	00	Эд	20	ФК	б1	5б	6а	CB	быть	39	4а	4с	58	см.
60	д0	если	аа	ФБ	43	4д	33	85	45	f9	02	7ф	50	3с	9ф	а8
70	51	а3	40	8 ф	92	9 дней	38	f5	до нашей эры	б6	и	21	10	фф	f3	d2
80	компакт-диск	0с	13	ЕС	5ф	97	44	17	с4	a7	7е	3d	64	5д	19	73
90	60	81	4ф	округ Колумбия	22	2а	90	88	46	да	б8	14	из	5е	0б	БД
а0	e0	32	3а	0а	49	06	24	5с	с2	д3	и	62	91	95	е4	79
б0	e7	с8	37	6д	8д	d5	4е	а9	6с	56	f4	из	65	7а	но	08
с0	нет	78	25	2е	1с	а6	б4	с6	е8	дд	74	1ф	4б	др.	8б	8а
д0	70	3е	б5	66	48	03	f6	0е	61	35	57	б9	86	с1	1д	9е
e0	е1	f8	98	11	69	d9	8е	94	9б	1е	87	е9	Этот	55	28	дф
f0	8с	а1	89	0д	парень	е6	42	68	41	99	2д	0ф	б0	54	бб	16
Столбец определяется младшим значащим полубайтом , а строка — самым значимым полубайтом. Например, значение 9a ₁₆ преобразуется в b8 ₁₆ .

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

{\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 7, ..., s 0]$ является выходом S-блока, а $[b 7, ..., b 0]$ является мультипликативным обратным вектором.

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

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

где $b$ представляет мультипликативную обратную величину, $\oplus$ это побитовый оператор XOR , $\lll$ представляет собой побитовый циклический сдвиг влево , а константа $6316 = 01100011 2$ задается в шестнадцатеричном формате .

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

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]

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

s=\left(b\times 31_{10}\mod {257_{10}}\right)\oplus 99_{10}

^[4]^[5]

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

Инверсный S-блок

Инверсный S-блок
	00	01	02	03	04	05	06	07	08	09	0а	0б	0с	0д	0е	0ф
00	52	09	6а	d5	30	36	а5	38	парень	40	а3	9е	81	f3	d7	ФБ
10	7с	е3	39	82	9б	2ф	фф	87	34	8е	43	44	с4	из	е9	CB
20	54	7б	94	32	а6	с2	23	3d	да	4с	95	0б	42	но	с3	4е
30	08	2е	а1	66	28	d9	24	б2	76	5б	а2	49	6д	8б	d1	25
40	72	f8	f6	64	86	68	98	16	d4	a4	5с	копия	5д	65	б6	92
50	6с	70	48	50	ФД	Эд	б9	и	5е	15	46	57	a7	8д	9 дней	84
60	90	d8	аб	00	8с	до нашей эры	д3	0а	f7	е4	58	05	б8	б3	45	06
70	д0	2с	1е	8 ф	что	3ф	0ф	02	с1	из	др.	03	01	13	8а	6б
80	3а	91	11	41	4ф	67	округ Колумбия	из	97	f2	см.	Этот	f0	б4	е6	73
90	96	и	74	22	e7	объявление	35	85	е2	f9	37	е8	1с	75	дф	6е
а0	47	ф1	1а	71	1д	29	с5	89	6ф	b7	62	0е	аа	18	быть	1б
б0	ФК	56	3е	4б	с6	d2	79	20	9а	БД	с0	фе	78	компакт-диск	5а	f4
с0	1ф	дд	а8	33	88	07	с7	31	б1	12	10	59	27	80	ЕС	5ф
д0	60	51	7ф	а9	19	б5	4а	0д	2д	е5	7а	9ф	93	с9	9с	если
e0	а0	e0	3б	4д	но	2а	f5	б0	с8	Эб	бб	3с	83	53	99	61
f0	17	2б	04	7е	нет	77	d6	26	е1	69	14	63	55	21	0с	7д

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

{\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:

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

где $\oplus$ это побитовый оператор XOR , $\lll$ представляет собой побитовый круговой сдвиг влево , а константа $516 = 00000101 2$ задается в шестнадцатеричном формате .

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

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

S-блок Rijndael можно заменить шифром Rijndael, ^[1] что устраняет подозрения о встроенном в шифр бэкдоре, использующем статический S-box. Авторы утверждают, что структура шифра Рейндала, вероятно, обеспечит достаточную устойчивость к дифференциальному и линейному криптоанализу, даже если используется S-блок со «средними» свойствами корреляции / распространения разности (ср. «оптимальные» свойства 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;
}

Ссылки

^ Перейти обратно: ^а ^б «Блочный шифр Рейндала» (PDF) . Проверено 11 ноября 2013 г.
^ Нюберг К. (1991) Совершенные нелинейные S-блоки . В: Дэвис Д.В. (ред.) Достижения в криптологии – EUROCRYPT '91. EUROCRYPT 1991. Конспекты лекций по информатике, том 547. Springer, Берлин, Гейдельберг.
^ «Расширенный стандарт шифрования» (PDF) . FIPS PUB 197: официальный стандарт AES . Федеральный стандарт обработки информации . 26 ноября 2001 г. Проверено 29 апреля 2010 г.
^ Йорг Й. Бухгольц (19 декабря 2001 г.). «Реализация Matlab Advanced Encryption Standard» (PDF) .
^ Цзе Цуй; Люшэн Хуан; Хун Чжун; Чинчен Чанг; Вэй Ян (май 2011 г.). «Улучшенный S-блок AES и анализ его производительности» (PDF) .

[rijndael_cipher-1] Перейти обратно: ^а ^б «Блочный шифр Рейндала» (PDF) . Проверено 11 ноября 2013 г.

[2] Нюберг К. (1991) Совершенные нелинейные S-блоки . В: Дэвис Д.В. (ред.) Достижения в криптологии – EUROCRYPT '91. EUROCRYPT 1991. Конспекты лекций по информатике, том 547. Springer, Берлин, Гейдельберг.

[fips197-3] «Расширенный стандарт шифрования» (PDF) . FIPS PUB 197: официальный стандарт AES . Федеральный стандарт обработки информации . 26 ноября 2001 г. Проверено 29 апреля 2010 г.

[4] Йорг Й. Бухгольц (19 декабря 2001 г.). «Реализация Matlab Advanced Encryption Standard» (PDF) .

[5] Цзе Цуй; Люшэн Хуан; Хун Чжун; Чинчен Чанг; Вэй Ян (май 2011 г.). «Улучшенный S-блок AES и анализ его производительности» (PDF) .

[1]

[2]

[3]

[4]

[5]