Advanced Encryption Standard

AES, Rijndael-AES, Rijndael

Розробники	В.Реймен, Д.Даймон
Уперше оприлюднений	2001 р.
Раундів	10/12/14
Тип	Substitution permutation network

Advanced Encryption Standard (AES), також відомий під назвою Rijndael — симетричний алгоритм блочного шифрування (розмір блока 128 біт, ключ 128/192/256 біт), фіналіст конкурсу AES і прийнятий в якості американского стандарту шифрування урядом США. Вибір припав на AES з розрахуванням на широке використання і активний аналіз алгоритму, як це було із його попередником, DES. Державний інститут стандартів і технологій (англ. National Institute of Standards and Technology, NIST) США опублікував попередню специфікацію AES 26 жовтня 2001 року, після п'ятилітньої підготовки. 26 травня 2002 року AES оголошено стандартом шифрування. Станом на 2009 рік AES є одним із найпоширеніших алгоритмів симетричного шифрування.

Історія

Потреба у новому стандарті шифрування постала у середині 90-х років. Наявний тоді стандарт DES, довжиною ключа 56 біт, дозволяв застосувати метод грубої сили для дешифрування даних. Успішні злами даних відбулись уже в кінці 90-х. Крім того архітектура DES орієнтувалась на апаратну реалізацію, а програмна реалізація на платформах із обмеженими ресурсами не давала необхідної швидкості застосування. Модифікація DES 3-DES мала достатню довжину ключа, але при цьому була ще повільнішою.

12 жовтня 1997 р. NIST оголосила конкурс на обрання спадкоємця для DES, що був американським стандартом ще з 1977 року. Перед претендентами поставили такі основні вимоги

• блочний шифр
• довжина блоку 128 біт
• ключі довжиною 128, 192 і 256 біт.

Вибір алгоритму проходив у три етапи. 20 серпня 1998 року на 1-й конференції AES було оголошено список з 15 кандидатів. В серпні 1999 року на 2-й конференції AES список скоротився до п'яти фіналістів: MARS, RC6, Rijndael, Serpent и Twofish. За результатами доповідей 3-ї конференції, що проходила у Нью Йорку 13-14 квітня 2000 року, 2 жовтня 2000 алгоритм, запропонований бельгійськими криптографами Д. Деймоном та В. Ріджменом, був оголошений переможцем конкурсу і почалась процедура стандартизації. 26 травня 2002 року AES був прийнятий як стандарт.

Опис алгоритму

В принципі, алгоритм, запропонований Рейменом і Дейцменом, і AES не одне і те ж. Алгоритм Рейндол підтримує широкий діапазон розміру блоку та ключа. AES має фіксовану довжину у 128 біт, а розмір ключа може приймати значення 128, 192 або 256 біт. В той час як Рейндол підтримує розмірність блоку та ключа із кроком 32 біт у діапазоні від 128 до 256. Через фіксований розмір блоку AES оперує із масивом 4×4 байт, що називається станом (версії алгоритму із більшим розміром блоку мають додаткові колонки).

Для ключа 128 біт алгоритм має 10 раундів у яких послідовно виконуються операції

• subBytes()
• shiftRows()
• mixcolumns() (у 10-му раунді пропускається)
• xorRoundKey()

SubBytes()

У процедурі SubBytes , кожен байт в state замінюється відповідним елементом у фіксованій 8-бітній таблиці пошуку, S; b _ij = S (a _ij ).

Процедура SubBytes() обробляє кожен байт стану незалежно, проводячи нелінійну заміну байтів використовуючи таблицю замін (S-box). Така операція забезпечує нелінійність алгоритму шифрування. Побудова S-box складається з двох кроків. По-перше, проводиться отримання зворотного числа в полі Галуа $GF\left({2^{8}}\right)$. По-друге, до кожного байту b з яких складається S-box застосовується така операція:

$B'_{i}=b_{i}\oplus b_{\left({i+4}\right){\bmod {8}}}\oplus b_{\left({i+5}\right){\bmod {8}}}\oplus b_{\left({i+6}\right){\bmod {8}}}\oplus b_{\left({i+7}\right){\bmod {8}}}\oplus c_{i}$

де $0\leq i<8$, і де $b_{i}$ є i-ий біт b, а $c_{i}$ - i-ий біт константи $c=63_{16}=99_{10}=01100011_{2}$. Таким чином, забезпечується захист від атак, заснованих на простих алгебраїчних властивостях.

S-box можна відобразити таблицею простої підстановки:

S-box

\	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	63	7c	77	7b	f2	6b	6f	c5	30	01	67	2b	fe	d7	ab	76
1	ca	82	c9	7d	fa	59	47	f0	ad	d4	a2	af	9c	a4	72	c0
2	b7	fd	93	26	36	3f	f7	cc	34	a5	e5	f1	71	d8	31	15
3	04	c7	23	c3	18	96	05	9a	07	12	80	e2	eb	27	b2	75
4	09	83	2c	1a	1b	6e	5a	a0	52	3b	d6	b3	29	e3	2f	84
5	53	d1	00	ed	20	fc	b1	5b	6a	cb	be	39	4a	4c	58	cf
6	d0	ef	aa	fb	43	4d	33	85	45	f9	02	7f	50	3c	9f	a8
7	51	a3	40	8f	92	9d	38	f5	bc	b6	da	21	10	ff	f3	d2
8	cd	0c	13	ec	5f	97	44	17	c4	a7	7e	3d	64	5d	19	73
9	60	81	4f	dc	22	2a	90	88	46	ee	b8	14	de	5e	0b	db
a	e0	32	3a	0a	49	06	24	5c	c2	d3	ac	62	91	95	e4	79
b	e7	c8	37	6d	8d	d5	4e	a9	6c	56	f4	ea	65	7a	ae	08
c	ba	78	25	2e	1c	a6	b4	c6	e8	dd	74	1f	4b	bd	8b	8a
d	70	3e	b5	66	48	03	f6	0e	61	35	57	b9	86	c1	1d	9e
e	e1	f8	98	11	69	d9	8e	94	9b	1e	87	e9	ce	55	28	df
f	8c	a1	89	0d	bf	e6	42	68	41	99	2d	0f	b0	54	bb	16

Наприклад, на вході 19 на виході отримаємо d4.

Фактично це звичайний шифр простої підстановки.

ShiftRows()

У процедурі ShiftRows , байти в кожному рядку state циклічно зсуваються вліво. Розмір зміщення байтів кожного рядка залежить від її номера

ShiftRows працює з рядками таблиці State. При цій трансформації рядка стану циклічно зсуваються на r байт по горизонталі, залежно від номера рядка. Для нульового рядка r = 0, для першого рядка r = 1 і т. д. Таким чином кожна колонка вихідного стану після застосування процедури ShiftRows складається з байтів з кожної колонки початкового стану. Для алгоритму Rijndael патерн зсуву рядків для 128 - і 192-бітних рядків однаковий. Однак для блоку розміром 256 біт відрізняється від попередніх тим, що 2, 3, і 4-і рядки зміщуються на 1, 3, і 4 байта, відповідно.

Фактично це проста перестановка байт таблиці 4х4 State.

MixColumns()

У процедурі MixColumns , кожна колонка стану перемножується з фіксованим многочленом c (x).

У процедурі MixColumns , чотири байти кожної колонки State змішуються, використовуючи для цього зворотну лінійну трансформацію. MixColumns опрацьовує стан по колонках, трактуючи кожну з них як поліном четвертого степеня. Над цими поліномами виконується множення в $GF(2^{8})$ по модулю $x^{4}+1$ на фіксований многочлен $c(x)=3x^{3}+x^{2}+x+2$. Разом з ShiftRows , MixColumns вносить дифузію в шифр.

Під час цієї операції, кожен стовпчик множиться на матрицю, яка для 128-бітного ключа має вигляд

${\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix}}.$

AddRoundKey()

У процедурі AddRoundKey , кожен байт стану об'єднується з RoundKey використовуючи операцію XOR.

У процедурі AddRoundKey , RoundKey кожного раунду об'єднується зі State. Для кожного раунду Roundkey виходить з CipherKey використовуючи процедуру KeyExpansion ; кожен RoundKey такого ж розміру, що і State. Процедура виробляє побітовий XOR кожного байта State з кожним байтом RoundKey .

Фактично це звичайний побайтовий XOR байт ключа з байтами таблиці State.