Просмотр кода страницы AES (стандарт шифрования)

{{Значения|AES}}
{{Карточка блочного шифра
|название = AES, Rijndael-AES, Rijndael
|изображение = AES-SubBytes.svg
|ширина = 275px
|создатель     = [[Рэймен, Винсент|Винсент Рэймен]]<br>[[Даймен, Йоан|Йоан Даймен]]
|создан = [[1998]] г.
|размер ключа = 128/192/256 бит
|размер блока = 128 бит
|число раундов = 10/12/14 (зависит от размера ключа)
|тип = [[SP-сеть|Подстановочно-перестановочная сеть]]
<!-- не поддерживаются и не поддерживались
|опубликован = [[2001]] г.
|произошёл от = square
|переемники = Anubis, Grand Cru
|сертифицирован= AES winner, CRYPTREC, NESSIE-->
}}
'''AES''' ({{lang-en|Advanced Encryption Standard}}; также ''Rijndael'', {{МФА|[rɛindaːl]}} — ''рейндал'') — [[Симметричные криптосистемы|симметричный алгоритм]] [[блочный шифр|блочного шифрования]] (размер блока 128 бит, ключ 128/192/256 бит), принятый в качестве стандарта [[шифрование|шифрования]] [[Правительство США|правительством США]] по результатам [[AES (конкурс)|конкурса AES]]. Этот алгоритм хорошо проанализирован и сейчас широко используется, как это было с его предшественником [[DES]]. Национальный институт стандартов и технологий США ({{lang-en|[[National Institute of Standards and Technology]]}}, NIST) опубликовал спецификацию AES [[26 ноября]] [[2001 год]]а после пятилетнего периода, в ходе которого были созданы и оценены 15 кандидатур. [[26 мая]] [[2002 год]]а AES был объявлен стандартом шифрования. По состоянию на [[2009 год]] AES является одним из самых распространённых алгоритмов симметричного шифрования<ref>{{cite web|url=http://www.thg.ru/cpu/aes_clarkdale/index.html|title=Intel Core i5 (Clarkdale): анализ аппаратного ускорения шифрования AES|author=Лаборатория Чеканова|quote=наиболее популярный стандарт симметричного шифрования в мире ИТ|date=2010-01-19|publisher=[[THG]]|lang=ru|accessdate=2010-11-14|archiveurl=https://web.archive.org/web/20120226205745/http://www.thg.ru/cpu/aes_clarkdale/index.html|archivedate=2012-02-26|deadlink=no}}</ref><ref>{{статья|автор=Biryukov, Alex and Khovratovich, Dmitry|заглавие=Related-key Cryptanalysis of the Full AES-192 and AES-256|ссылка=http://www.impic.org/papers/Aes-192-256.pdf|язык=en|издание=Advances in Cryptology – ASIACRYPT 2009|издательство=Springer Berlin / Heidelberg|год=2009|том=5912|страницы=1—18|doi=10.1007/978-3-642-10366-7_1|archivedate=2010-12-18|archiveurl=https://web.archive.org/web/20101218042639/http://www.impic.org/papers/Aes-192-256.pdf}}</ref>. Поддержка [[Расширение системы команд AES|ускорения AES]] была введена фирмой [[Intel]] в семейство процессоров [[x86]] начиная с {{iw|Arrandale}} в 2010 году, а затем на процессорах [[Sandy Bridge]]; фирмой AMD — в [[Bulldozer (микроархитектура)|Bulldozer]] с 2011 года.

== История AES ==
{{main|AES (конкурс)}}
[[2 января]] [[1997 год]]а [[NIST]] объявляет<ref>{{cite web |url=http://csrc.nist.gov/CryptoToolkit/aes/pre-round1/aes_9701.txt |title=Архивированная копия |accessdate=2006-12-07 |deadlink=да |archiveurl=https://web.archive.org/web/20061106004319/http://csrc.nist.gov/CryptoToolkit/aes/pre-round1/aes_9701.txt |archivedate=2006-11-06 }}</ref> о намерении выбрать преемника для [[DES]], являвшегося американским стандартом с [[1977 год]]а. [[2 октября]] [[2000 год]]а было объявлено, что победителем конкурса стал алгоритм Rijndael<ref>[http://www.nist.gov/public_affairs/releases/g00-176.htm NIST Error Page<!-- Заголовок добавлен ботом -->] {{webarchive|url=https://web.archive.org/web/20100928154133/http://www.nist.gov/public_affairs/releases/g00-176.htm |date=2010-09-28 }}</ref>, и началась процедура стандартизации. [[28 февраля]] [[2001 год]]а был опубликован проект, а [[26 ноября]] [[2001 год]]а AES был принят как [[FIPS]] 197. Историческую ретроспективу конкурса можно проследить на веб-сайте [[NIST]]<ref>[http://csrc.nist.gov/CryptoToolkit/aes/ Bounce to index.html<!-- Заголовок добавлен ботом -->] {{webarchive|url=https://web.archive.org/web/20140717094809/http://csrc.nist.gov/CryptoToolkit/aes/ |date=2014-07-17 }}</ref>.

== Описание AES ==

=== Определения и вспомогательные процедуры ===
{| class="wikitable" style="text-align:left"
|+ Определения
|-
!'''Block'''
| последовательность бит, из которых состоит input, output, State и Round Key. Также под Block можно понимать последовательность байтов
|-
!'''Cipher Key'''
|секретный криптографический ключ, который используется Key Expansion процедурой, чтобы произвести набор ключей для раундов (Round Keys); может быть представлен как прямоугольный массив байтов, имеющий четыре строки и ''N<sub>k</sub>'' столбцов
|-
!'''Ciphertext'''
|выходные данные алгоритма шифрования
|-
!'''Key Expansion'''
|процедура генерации Round Keys из Cipher Key
|-
!'''Round Key'''
|Round Keys получаются из Cipher Key использованием процедуры Key Expansion. Они применяются к State при шифровании и расшифровании
|-
!'''State'''
|промежуточный результат шифрования, который может быть представлен как прямоугольный массив байтов, имеющий 4 строки и ''N<sub>b</sub>'' столбцов
|-
!'''S-box'''
|нелинейная таблица замен, использующаяся в нескольких трансформациях замены байтов и в процедуре Key Expansion для взаимнооднозначной замены значения байта. Предварительно рассчитанный S-box можно увидеть ниже
|-
!'''N<sub>b</sub>'''
|число столбцов (32-битных слов), составляющих ''State''. Для AES ''N<sub>b</sub>'' = 4
|-
!'''N<sub>k</sub>'''
|число 32-битных слов, составляющих шифроключ. Для AES ''N<sub>k</sub>'' = 4, 6, или 8
|-
!'''N<sub>r</sub>'''
|число раундов, которое является функцией ''N<sub>k</sub>'' и ''N<sub>b</sub>''. Для AES ''N<sub>r</sub>'' = 10, 12, 14
|-
!'''Rcon[]'''
|массив, который состоит из битов 32-разрядного слова и является постоянным для данного раунда. Предварительно рассчитанный Rcon[] можно увидеть ниже
|}
<blockquote style="background: white; border: 1px solid black; padding: 1em; margin: 0 1em 1em 0;"> S-box <pre><nowiki>

Sbox = array{
        0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 
        0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, 
        0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, 
        0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, 
        0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, 
        0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, 
        0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 
        0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 
        0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 
        0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 
        0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 
        0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 
        0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 
        0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 
        0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, 
        0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
    };

</nowiki></pre></blockquote>
<blockquote style="background: white; border: 1px solid black; padding: 1em; margin: 0 1em 1em 0;">Обратный S-box для процедуры InvSubBytes <pre><nowiki>
InvSbox = array{
        0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
        0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
        0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
        0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
        0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
        0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
        0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
        0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
        0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
        0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
        0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
        0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
        0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
        0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
        0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
        0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d
        };

</nowiki></pre></blockquote>
<blockquote style="background: white; border: 1px solid black; padding: 1em; margin: 0 1em 1em 0;">Rcon[]<pre><nowiki>

Rcon = array{
        array{0x00, 0x00, 0x00, 0x00},
        array{0x01, 0x00, 0x00, 0x00},
        array{0x02, 0x00, 0x00, 0x00},
        array{0x04, 0x00, 0x00, 0x00},
        array{0x08, 0x00, 0x00, 0x00},
        array{0x10, 0x00, 0x00, 0x00},
        array{0x20, 0x00, 0x00, 0x00},
        array{0x40, 0x00, 0x00, 0x00},
        array{0x80, 0x00, 0x00, 0x00},
        array{0x1b, 0x00, 0x00, 0x00},
        array{0x36, 0x00, 0x00, 0x00}
    };

</nowiki></pre></blockquote>
{| class="wikitable" style="text-align:left"
|+ Вспомогательные процедуры
|-
!'''AddRoundKey()'''
|трансформация при шифровании и обратном шифровании, при которой Round Key XOR’ится c State. Длина RoundKey равна размеру State (то есть если ''Nb'' = 4, то длина RoundKey равна 128 бит или 16 байт)
|-
!'''InvMixColumns()'''
|трансформация при расшифровании, которая является обратной по отношению к MixColumns()
|-
!'''InvShiftRows()'''
|трансформация при расшифровании, которая является обратной по отношению к ShiftRows()
|-
!'''InvSubBytes()'''
|трансформация при расшифровании, которая является обратной по отношению к SubBytes()
|-
!'''MixColumns()'''
|трансформация при шифровании, которая берёт все столбцы State и смешивает их данные (независимо друг от друга), чтобы получить новые столбцы
|-
!'''RotWord()'''
|функция, использующаяся в процедуре Key Expansion, которая берёт 4-байтовое слово и производит над ним циклическую перестановку
|-
!'''ShiftRows()'''
|трансформации при шифровании, которые обрабатывают State, циклически смещая последние три строки State на разные величины
|-
!'''SubBytes()'''
|трансформации при шифровании, которые обрабатывают State, используя нелинейную таблицу замещения байтов (S-box), применяя её независимо к каждому байту State
|-
!'''SubWord()'''
|функция, используемая в процедуре Key Expansion, которая берёт на входе четырёхбайтовое слово и, применяя S-box к каждому из четырёх байтов, выдаёт выходное слово
|}

=== Шифрование ===
<!--[[Файл:Pseudo_code_for_cypher.JPG |left|640px|thumbnail|In the <code>SubBytes</code> step, each byte in the state is replaced with its entry in a fixed 8-bit lookup table, ''S''; ''b<sub>ij</sub>'' = ''S(a<sub>ij</sub>)''.]] -->
AES является стандартом, основанным на алгоритме Rijndael. Для AES длина input (блока входных данных) и State (состояния) постоянна и равна 128 бит, а длина шифроключа '''K''' составляет 128, 192, или 256 бит. При этом исходный алгоритм Rijndael допускает длину ключа и размер блока от 128 до 256 бит с шагом в 32 бита. Для обозначения выбранных длин input, State и Cipher Key в 32-битных словах используется нотация Nb = 4 для input и State, Nk = 4, 6, 8 для Cipher Key соответственно для разных длин ключей.
<!-- Вставить картинку 1 с набором всевозможных длин ключей и состояний -->

В начале зашифровывания input копируется в массив State по правилу <math> \mathrm{state}[r,c] = \mathrm{input}[r+4c] </math>, для <math> 0 \le r < 4 </math> и <math> 0 \le c < Nb </math>. После этого к State применяется процедура AddRoundKey(), и затем State проходит через процедуру трансформации (раунд) 10, 12, или 14 раз (в зависимости от длины ключа), при этом надо учесть, что последний раунд несколько отличается от предыдущих. В итоге, после завершения последнего раунда трансформации, State копируется в output по правилу <math>\mathrm{output}[r+4c] = \mathrm{state}[r,c]</math>, для <math> 0 \le r < 4 </math> и <math> 0 \le c < Nb </math>.

Отдельные трансформации SubBytes(), ShiftRows(), MixColumns() и AddRoundKey() — обрабатывают State. Массив w[] — содержит [[:en:AES_key_schedule|key schedule]].

<blockquote style="background: white; border: 1px solid black; padding: 1em;"><pre><nowiki>

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
    byte state[4,Nb]
    
    state = in

    AddRoundKey(state, w[0, Nb-1])

    for round = 1 step 1 to Nr-1
        SubBytes(state)
        ShiftRows(state)
        MixColumns(state)
        AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])
    end for

    SubBytes(state)
    ShiftRows(state)
    AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

    out = state
end

</nowiki></pre> Рис1. Псевдокод для Cipher </blockquote>

==== SubBytes() ====
[[Файл:AES-SubBytes.svg|right|320px|thumbnail|В процедуре <code>SubBytes</code>, каждый байт в state заменяется соответствующим элементом в фиксированной 8-битной таблице поиска, ''S''; ''b<sub>ij</sub>'' = ''S(a<sub>ij</sub>)''.]]
Процедура SubBytes() обрабатывает каждый байт состояния, независимо производя нелинейную замену байтов, используя таблицу замен (S-box). Такая операция обеспечивает нелинейность алгоритма шифрования. Построение S-box состоит из двух шагов. Во-первых, производится взятие обратного числа в [[поле Галуа]] <math>GF\left( {2^8 } \right)</math>. Для всех операций в этом поле используется неприводимый полином <math>z^8 + z^4 + z^3 + z + 1</math>. Во-вторых, к каждому байту b, из которых состоит S-box, применяется следующая операция:
: <math>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 </math>
где <math>0 \le i < 8</math>, и где <math>b_i</math> есть i-ый бит b, а <math>c_i</math> — i-ый бит константы <math>c = 63_{16}  = 99_{10}  = 01100011_2</math>. Таким образом обеспечивается защита от атак, основанных на простых алгебраических свойствах. <!--The S-box is also chosen to avoid any fixed points (and so is a derangement), and also any opposite fixed points.-->

<center><math>
\begin{Vmatrix} b^{'}_{0}\\b^{'}_{1}\\b^{'}_{2}\\b^{'}_{3}\\b^{'}_{4}\\b^{'}_{5}\\b^{'}_{6}\\b^{'}_{7} \end{Vmatrix} = 
 \begin{Vmatrix} 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{Vmatrix} *
 \begin{Vmatrix} b_{0}\\b_{1}\\b_{2}\\b_{3}\\b_{4}\\b_{5}\\b_{6}\\b_{7} \end{Vmatrix} +  \begin{Vmatrix} 1\\1\\0\\0\\0\\1\\1\\0 \end{Vmatrix}   
</math></center>

==== ShiftRows() ====
[[Файл:AES-ShiftRows.svg|right|320px|thumbnail|В процедуре <code>ShiftRows</code> байты в каждой строке state циклически сдвигаются влево. Размер смещения байтов каждой строки зависит от её номера]]
<code>ShiftRows</code> работает со строками State. При этой трансформации строки состояния циклически сдвигаются на r байт по горизонтали в зависимости от номера строки. Для нулевой строки r = 0, для первой строки r = 1 Б и т. д. Таким образом, каждая колонка выходного состояния после применения процедуры <code>ShiftRows</code> состоит из байтов из каждой колонки начального состояния. Для алгоритма Rijndael паттерн смещения строк для 128- и 192-битных строк одинаков. Однако для блока размером 256 бит отличается от предыдущих тем, что 2-е, 3-и и 4-е строки смещаются на 1, 3 и 4 байта соответственно. Это замечание не относится к AES, так как он использует алгоритм Rijndael только с 128-битными блоками, независимо от размера ключа.

==== MixColumns() ====
[[Файл:AES-MixColumns.svg|right|320px|thumbnail|В процедуре <code>MixColumns</code> каждая колонка состояния перемножается с фиксированным многочленом ''c(x)''.]]
В процедуре <code>MixColumns</code> четыре байта каждой колонки State смешиваются, используя для этого обратимую линейную трансформацию. <code>MixColumns</code> обрабатывает состояния по колонкам, трактуя каждую из них как полином третьей степени. Над этими полиномами производится умножение<ref>http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf {{Wayback|url=http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf |date=20150407153905 }} «5.1.3 MixColumns() Transformation .. The columns are considered as polynomials over GF(2^8) and multiplied modulo x^4 + 1 with a fixed polynomial a(x), given by a(x) = {03}x³ + {01}x² + {01}x + {02}.»</ref> в <math>GF(2^8)</math> по модулю <math>x^4+1</math> на фиксированный многочлен <math>c(x) = 3x^3 + x^2 + x + 2</math>. Вместе с <code>ShiftRows</code><code> MixColumns </code> вносит диффузию в шифр.

==== AddRoundKey() ====
[[Файл:AES-AddRoundKey.svg|right|320px|thumbnail|В процедуре <code>AddRoundKey</code> каждый байт состояния объединяется с RoundKey, используя операцию [[Exclusive or|XOR]] (⊕).]]
В процедуре <code>AddRoundKey</code><code> RoundKey</code> каждого раунда объединяется со State. Для каждого раунда <code>Roundkey </code>получается из <code>CipherKey</code> c помощью процедуры <code>KeyExpansion</code>; каждый RoundKey такого же размера, что и State. Процедура производит побитовый [[Сложение по модулю 2|XOR]] каждого байта <code>State</code> с каждым байтом <code>RoundKey</code>.

== Алгоритм обработки ключа ==
Алгоритм обработки ключа состоит из двух процедур:
* Алгоритм генерации раундовых ключей (алгоритм расширения ключа)
* Алгоритм выбора раундового ключа (ключа итерации)

=== Алгоритм генерации раундовых ключей ===
Алгоритм AES, используя процедуру KeyExpansion() и подавая в неё Cipher Key, K, получает ключи для всех раундов. Всего получается Nb*(Nr + 1) слов: изначально для алгоритма требуется набор из Nb слов, и каждому из Nr раундов требуется Nb ключевых набора данных. Полученный массив ключей для раундов обозначается как <math>w \left[ i \right]</math>, <math> 0 \le i < Nb*(Nr + 1) </math>. Алгоритм KeyExpansion() показан в псевдокоде ниже.

Функция SubWord() берёт четырёхбайтовое входное слово и применяет S-box к каждому из четырёх байтов. То, что получилось, подаётся на выход. На вход RotWord() подаётся слово <math>[a_{0}, a_{1}, a_{2}, a_{3}]</math>, которое она циклически переставляет и возвращает <math> [a_{1}, a_{2}, a_{3}, a_{0}]</math>. Массив слов, постоянный для данного раунда, <math>Rcon\left[ i \right]</math>, содержит значения <math>[x^{i-1}, {00}, {00}, {00}] </math>, где x = {02}, а <math> x^{i-1} </math> является степенью <math>x</math> в <math>GF \left( 2^8 \right) </math> (<math>i</math> начинается с 1).

Из рисунка можно видеть, что первые <math>Nk</math> слов расширенного ключа заполнены Cipher Key. В каждое последующее слово, <math>w[i]</math>, кладётся значение, полученное при операции XOR <math>w[i-1]</math> и <math>w\left[ {i - Nk} \right]</math>, те XOR’а предыдущего и на Nk позиций раньше слов. Для слов, позиция которых кратна Nk, перед XOR’ом к w[i-1] применяется трансформация, за которой следует XOR с константой раунда Rcon[i]. Указанная выше трансформация состоит из циклического сдвига байтов в слове (RotWord()), за которой следует процедура SubWord() — то же самое, что и SubBytes(), только входные и выходные данные будут размером в слово.

Важно заметить, что процедура KeyExpansion() для 256-битного Cipher Key немного отличается от тех, которые применяются для 128- и 192- битных шифроключей. Если <math>Nk = 8</math> и <math>i - 4</math> кратно <math>Nk</math>, то SubWord() применяется к <math>w[i-1]</math> до XOR’а.

<blockquote style="background: white; border: 1px solid black; padding: 1em;"><pre>
KeyExpansion(byte key[4 * Nk], word w[Nb * (Nr+1)], Nk)
begin
    word temp
    i = 0;
    
    while(i < Nk)
        w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
        i = i + 1
    end while
    
    i = Nk

    while(i < Nb * (Nr+1))
        temp = w[i - 1]
        if (i mod Nk = 0)
            temp = SubWord(RotWord(temp)) xor Rcon[i / Nk]
        else if (Nk > 6 and i mod Nk = 4)
            temp = SubWord(temp)
        end if
        w[i] = w[i - Nk] xor temp
        i = i + 1
    end while
end
</pre> Псевдокод для Key Expansion </blockquote>

=== Расшифрование ===
<blockquote style="background: white; border: 1px solid black; padding: 1em;"><pre><nowiki>

InvCipher(byte in[4 * Nb], byte out[4 * Nb], word w[Nb * (Nr+1)])
begin
    byte state[4, Nb]
    
    state = in

    AddRoundKey(state, w[Nr * Nb, Nb * (Nr+1) - 1])

    for round = Nr - 1 step -1 downto 1
        InvShiftRows(state)
        InvSubBytes(state)
        AddRoundKey(state, w[Nb * round, Nb * (round+1) - 1])
        InvMixColumns(state)
    end for

    InvShiftRows(state)
    InvSubBytes(state)
    AddRoundKey(state, w[0, Nb - 1])

    out = state
end

</nowiki></pre>Псевдокод для Inverse Cipher </blockquote>

=== Алгоритм выбора раундового ключа ===
На каждой итерации <math>i</math> раундовый ключ для операции ''AddRoundKey'' выбирается из массива <math>w \left[ i \right]</math>,начиная с элемента <math>w \left[ Nb * i \right]</math> до <math>w \left[ Nb * \left( i + 1 \right) \right]</math>.

== Варианты алгоритма ==
На базе алгоритма Rijndael, лежащего в основе AES, реализованы альтернативные криптоалгоритмы. Среди наиболее известных — участники [[NESSIE|конкурса Nessie]]: [[Anubis]] на инволюциях, автором которого является Винсент Рэймен и усиленный вариант шифра — [[Grand Cru]] Йохана Борста.

== Криптостойкость ==
В июне 2003 года [[Агентство национальной безопасности]] США постановило, что шифр AES является достаточно надёжным, чтобы использовать его для защиты сведений, составляющих государственную тайну ({{lang-en|classified information}}). Вплоть до уровня SECRET было разрешено использовать ключи длиной 128 бит, для уровня TOP SECRET требовались ключи длиной 192 и 256 бит<ref>{{cite web|url=http://cryptome.org/aes-natsec.htm|title=National Policy on the Use of the Advanced Encryption Standard (AES) to Protect National Security Systems and National Security Information|date=2003-06|publisher=Committee on National Security Systems|lang=en|accessdate=2010-10-27|archiveurl=https://www.webcitation.org/65Yixk1FT?url=http://cryptome.org/aes-natsec.htm|archivedate=2012-02-19}}</ref>.

=== XSL-атака ===
{{main|XSL-атака}}

В отличие от большинства других шифров, AES имеет простое математическое описание. Это беспокоило в том числе и [[Фергюсон, Нильс|Нильса Фергюсона]], который в своей работе отметил, что безопасность шифра основывается на новом непроверенном предположении о сложности решения определённых видов уравнений ({{lang-en|«The security of Rijndael depends on a new and untested hardness assumption: it is computationally infeasible to solve equations of this type»}})<ref>{{книга|автор=James McLaughlin|часть=The XSL controversy|заглавие=A survey of block cipher cryptanalysis techniques|ссылка=https://www-users.cs.york.ac.uk/~jmclaugh/XSL_chapter.pdf|издание=preprint|место=York|издательство=University of York|год=2009}}{{Недоступная ссылка|date=Август 2018 |bot=InternetArchiveBot }}</ref><ref>{{статья|автор=Niels Ferguson, Richard Schroeppel, and Doug Whiting|заглавие=A simple algebraic representation of Rijndael|ссылка=http://www.macfergus.com/pub/rdalgeq.html|язык=en|издание=Selected Areas in Cryptography, Proc. SAC 2001, Lecture Notes in Computer Science #2259|издательство=Springer Verlag|год=2001|страницы=103—111|archiveurl=https://web.archive.org/web/20160116051445/http://www.macfergus.com/pub/rdalgeq.html|archivedate=2016-01-16}}</ref>, а также Брюса Шнайера, который написал в совместной с Нильсом книге:
{{Начало цитаты}}
У нас есть одно критическое замечание к AES: мы не совсем доверяем его безопасности. Что беспокоит нас больше всего в AES, так это его простая алгебраическая структура… Ни один другой блочный шифр не имеет столь простого алгебраического представления. Мы понятия не имеем, ведёт это к атаке или нет, но незнание этого является достаточной причиной, чтобы скептически относиться к использованию AES.
{{oq|en|We have one criticism of AES: we don't quite trust the security… What concerns us the most about AES is its simple algebraic structure… No other block cipher we know of has such a simple algebraic representation. We have no idea whether this leads to an attack or not, but not knowing is reason enough to be skeptical about the use of AES}}
{{Конец цитаты|источник=''[[Фергюсон, Нейлс|Niels Ferguson]], [[Шнайер, Брюс|Bruce Schneier]]'' Practical Cryptography — 2003 — pp. 56—57}}

{{Не переведено 2|Куртуа, Николя|Николя Куртуа|en|Nicolas Courtois}} и {{Не переведено 2|Пепшик, Йозеф|Йозеф Пепшик|en|Josef Pieprzyk}} в 2002 году опубликовали статью, в которой описали теоретическую атаку, названную ими [[XSL-атака|XSL-атакой]] ({{lang-en|eXtended Sparse Linearization}}), которая могла бы позволить вскрыть шифры AES и [[Serpent]]<ref>{{cite web|url=http://www.schneier.com/crypto-gram-0209.html|title=Crypto-Gram Newsletter|author=Bruce Schneier|date=2002-09-15|work=Schneier on Security|lang=en|accessdate=2010-10-27|archiveurl=https://www.webcitation.org/65YiyrUTe?url=http://www.schneier.com/crypto-gram-0209.html|archivedate=2012-02-19}}</ref><ref>{{статья|автор=Nicolas Courtois, Josef Pieprzyk|заглавие=Cryptanalysis of Block Ciphers with Overdefined Systems of Equations|издание=Advances in Cryptology — ASIACRYPT 2002 8th International Conference on the Theory Application of Cryptology and Information Security Queenstown, New Zealand, December 1—5, 2002 Proceedings. Lecture Notes in Computer Science (2501)|ссылка=https://eprint.iacr.org/2002/044|язык=en|издательство=Springer|год=2002|страницы=267—287|doi=10.1007/3-540-36178-2|archivedate=2020-10-26|archiveurl=https://web.archive.org/web/20201026090457/https://eprint.iacr.org/2002/044}}</ref>. Тем не менее, результаты работы не всеми были восприняты оптимистично:
{{Начало цитаты}}
Я считаю, что в работе Куртуа-Пепшика есть ошибка. Они переоценили число линейно-независимых уравнений. В результате у них нет достаточного количества линейных уравнений для решения системы, и [указанный] метод не может взломать Rijndael. Он имеет определённые достоинства и заслуживает изучения, но не взламывает Rijndael в его нынешнем виде.
{{oq|en|I believe that the Courtois-Pieprzyk work is flawed. They overcount the number of linearly independent equations. The result is that they do not in fact have enough linear equations to solve the system, and the method does not break Rijndael… The method has some merit, and is worth investigating, but it does not break Rijndael as it stands.}}
{{Конец цитаты|источник=[[Дон Копперсмит]], [http://www.schneier.com/crypto-gram-0210.html#8 комментарий к записи] в блоге [[Брюс Шнайер|Брюса Шнайера]]}}

На странице, посвящённой обсуждению конкурса [[NESSIE]], в конце 2002 года один из авторов шифра, Винсент Рэймен, заявил, что XSL-атака является всего лишь мечтой ({{lang-en|The XSL attack is not an attack. It is a dream}}) (данная точка зрения позже была повторена в 2004 году на 4-й конференции AES в [[Бонн]]е). На это Куртуа ответил, что данная мечта может стать для автора AES кошмаром ({{lang-en|It may also be a very bad dream and turn into a nightmare}})<ref>[https://web.archive.org/web/20031108050830/http://www.cosic.esat.kuleuven.ac.be/nessie/forum/read.php?f=1&i=82&t=82 NESSIE Discussion Forum]</ref> (игра слов: ''dream'' переводится и как ''мечта'' и как ''сновидение''. ''Nightmare'' переводится как ''кошмарный сон, ночной кошмар'').

В 2003 году [[Мёрфи, Шон (криптограф)|Шон Мёрфи]] и {{Не переведено 2|Робшоу, Мэтт|Мэтт Робшоу|en|Matt Robshaw}} опубликовали работу, в которой (в предположении, что результаты Куртуа и Пепшика верны) обосновали возможность атаки на алгоритм AES, сокращающей количество операций для взлома с 2<sup>128</sup> до 2<sup>100</sup>. Однако на 4-й конференции AES Илья Толи ({{lang-en|Ilia Toli}}) и Альберто Дзанони ({{lang-en|Alberto Zanoni}}) показали, что работа Мёрфи и Робшоу неверна<ref>{{статья|автор=Ilia Toli, Alberto Zanoni|заглавие=An Algebraic Interpretation of AES-128|ссылка=http://www.springerlink.com/content/3q790mfnr6bk70pf/|язык=en|издание=Proc. of AES Conference|год=2005|том=2005|страницы=84—97|doi=10.1007/11506447_8}}{{Недоступная ссылка|date=Март 2020 |bot=InternetArchiveBot }}</ref>. Позже, в 2007 году, Чу-Ви Лим ({{lang-en|Chu-Wee Lim}}) и Хунгминг Ху ({{lang-en|Khoongming Khoo}}) также показали, что данная атака не может работать в том виде, как она была описана<ref>{{статья|автор=Chu-wee Lim, Khoongming Khoo|заглавие=An Analysis of XSL Applied to BES|ссылка=http://www.springerlink.com/content/6x35t1u383824353/|язык=en|издание=Fast Software Encryption|место=Heidelberg|издательство=Springer Berlin / Heidelberg|год=2007|том=4593|страницы=242—253|doi=10.1007/978-3-540-74619-5_16}}{{Недоступная ссылка|date=Март 2020 |bot=InternetArchiveBot }}</ref>.

=== Атака по сторонним каналам ===
{{main|Атака по сторонним каналам}}

Атаки по сторонним каналам не связаны с математическими особенностями шифра, но используют определённые особенности реализации систем, использующих данные шифры, с целью раскрыть частично или полностью секретные данные, в том числе ключ. Известно несколько подобных атак на системы, использовавшие алгоритм AES.

В апреле 2005 года {{нп2|Бернштейн, Дэниел Джулиус|Дэниел Бернштейн|en|Daniel J. Bernstein}} опубликовал работу с описанием атаки, использующей для взлома информацию о времени выполнения каждой операции шифрования<ref>{{статья|автор=Daniel J. Bernstein|заглавие=Cache-timing attacks on AES|ссылка=http://cr.yp.to/papers.html#cachetiming|язык=en|год=2004|издание=|archivedate=2008-09-17|archiveurl=https://web.archive.org/web/20080917042758/http://cr.yp.to/papers.html#cachetiming}}</ref>. Данная атака потребовала более 200 миллионов выбранных шифротекстов для нахождения ключа<ref>{{cite web|url=http://www.schneier.com/blog/archives/2005/05/aes_timing_atta_1.html|title=AES Timing Attack|author=Bruce Schneier|date=2005-05-17|work=Schneier on Security|lang=en|accessdate=2010-10-27|archiveurl=https://www.webcitation.org/65YizbRPr?url=http://www.schneier.com/blog/archives/2005/05/aes_timing_atta_1.html|archivedate=2012-02-19}}</ref>.

В октябре 2005 года Даг Арне Освик, [[Ади Шамир]] и Эран Трумер представили работу с описанием нескольких атак, использующих время выполнения операций для нахождения ключа. Одна из представленных атак получала ключ после 800 операций шифрования. Атака требовала от криптоаналитика возможности запускать программы на той же системе, где выполнялось шифрование<ref>{{статья|автор=Dag Arne Osvik; Adi Shamir and Eran Tromer|заглавие=Cache Attacks and Countermeasures: the Case of AES|ссылка=https://eprint.iacr.org/2005/271.pdf|издание=Topics in Cryptology — CT-RSA 2006, The Cryptographers’ Track at the RSA Conference|издательство=Springer-Verlag|год=2005|pages=1—20|archivedate=2020-11-25|archiveurl=https://web.archive.org/web/20201125110812/https://eprint.iacr.org/2005/271.pdf}}</ref>.

В декабре 2009 года была опубликована работа, в которой использование дифференциального анализа ошибок ({{lang-en|Differential Fault Analysis}}), искусственно создаваемых в матрице состояния на 8-м раунде шифрования, позволило восстановить ключ за 2<sup>32</sup> операций<ref>{{статья|автор=Dhiman Saha, Debdeep Mukhopadhyay, Dipanwita RoyChowdhury|заглавие=A Diagonal Fault Attack on the Advanced Encryption Standar|ссылка=https://eprint.iacr.org/2009/581|язык=en|издание=Cryptology ePrint Archive|год=2009|archivedate=2020-08-06|archiveurl=https://web.archive.org/web/20200806111402/https://eprint.iacr.org/2009/581}}</ref>.
=== Квантовая угроза ===
{{Main|Квантовое превосходство}}
[[Национальный институт стандартов и технологий|Национальный институт стандартов и технологий США]] (NIST), определяющий национальную политику и стандарты, объявил, что, по его прогнозам, к 2029 г. [[Квантовый компьютер|квантовые компьютеры]] смогут взломать 128-битное {{Nobr|AES-шифрование}}, которым пользуются многие компании{{sfn|Каку|2024| с= 20|name=}}.

== См. также ==
* [[Статистические тесты генераторов случайных и псевдослучайных чисел#Конкурс AES|Тестирование алгоритмов, участвовавших в конкурсе AES]]
* [[TKIP]]
* [[WPA]]
* [[CCMP]]
* [[Кузнечик (шифр)|Кузнечик]]
* [[ГОСТ 28147-89|Магма]]

== Примечания ==
{{примечания|2}}

== Литература ==
* [http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf  Federal Information Processing Standards Publication 197 November 26, 2001 Specification for the ADVANCED ENCRYPTION STANDARD (AES)] {{Wayback|url=http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf |date=20150407153905 }}{{ref-en}}
* {{source|Q26959586|ref=Баричев, Гончаров, Серов|ref-year=2011|part=2.4.2. Стандарт AES. Алгоритм Rijdael|pages=30—35}} <!-- Основы современной криптографии -->
* {{книга |автор=[[Каку, Митио|Митио Каку]]|заглавие = Квантовое превосходство. Революция в вычислениях, которая изменит всё|оригинал= Michio Kaku. Quantum Supremacy: How the Quantum Computer Revolution Will Change Everything | место= М.|издательство= Альпина нон-фикшн|год= 2024|страницы= 412|isbn= 978-5-00139-728-1|ref =  Каку}}

== Ссылки ==
* [https://web.archive.org/web/20140529233954/http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf Подробная анимация про реализацию и устройство AES]
* [http://byrd.narod.ru/aes/aes2.htm О процессе принятия AES] {{Wayback|url=http://byrd.narod.ru/aes/aes2.htm |date=20080122132514 }}
* {{cite web|url=http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html|title=A Stick Figure Guide to the Advanced Encryption Standard (AES)|author=Jeff Moser|date=2009-09-22|lang=en|accessdate=2010-11-22|archiveurl=https://www.webcitation.org/65Yj0G6mK?url=http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html|archivedate=2012-02-19}} — AES в картинках ([http://www.pgpru.com/biblioteka/statji/aesvkartinkah русский перевод] {{Wayback|url=http://www.pgpru.com/biblioteka/statji/aesvkartinkah |date=20130623010741 }})

{{Внешние ссылки}}
{{симметричные криптоалгоритмы}}

[[Категория:Блочные шифры]]
[[Категория:SP-сеть]]