Advanced Encryption Standard

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

Історія

Потреба у новому стандарті шифрування постала у середині 1990-х років. Наявний тоді стандарт DES, довжиною ключа 56 біт, давав змогу застосувати метод грубої сили для дешифрування даних. Успішні злами даних відбулися вже наприкінці 1990-х. Крім того, архітектура 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{\text{'}}_i=b_i\oplus b_{\left(i+4\right)mod8}\oplus b_{\left(i+5\right)mod8}\oplus b_{\left(i+6\right)mod8}\oplus b_{\left(i+7\right)mod8}\oplus c_i$

де $0\le 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-бітного ключа має вигляд

$\left[\begin{array}{cccc}2& 3& 1& 1\\ 1& 2& 3& 1\\ 1& 1& 2& 3\\ 3& 1& 1& 2\end{array}\right].$

AddRoundKey()

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

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

Примітки

Шаблон:Crypto-stub