ФЭНДОМ


<tr><th style="">Создатель:</th><td class="" style="">

Винсент Риджмен, Джоан Даймон </td></tr><tr><th style="">Создан:</th><td class="" style=""> 1998 г. </td></tr><tr><th style="">Опубликован:</th><td class="" style=""> 2001 г. </td></tr><tr><th style="">Размер ключа:</th><td class="" style=""> 128/192/256 бит </td></tr><tr><th style="">Размер блока:</th><td class="" style=""> 128 бит </td></tr><tr><th style="">Число раундов:</th><td class="" style=""> 10/12/14 (зависит от размера ключа) </td></tr><tr><th style="">Тип:</th><td class="" style=""> Substitution permutation network </td></tr> </table>


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

История AES Править

Необходимость в принятии нового стандарта была вызвана небольшой длиной ключа DES (56 бит), что позволяло применить метод грубой силы (полный перебор ключей) против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала достаточного быстродействия. Модификация 3-DES обладала достаточной длиной ключа, но при этом была ещё медленнее.

Начало конкурса Править

2 января 1997 года NIST объявляет [1] о намерении выбрать преемника для DES, являвшегося американским стандартом с 1977 года. Однако, вместо опубликования алгоритма, NIST принял различные предложения от заинтересованных сторон о том, каким образом следует выбирать алгоритм. Бурный отклик со стороны открытого криптографического сообщества привёл к объявлению конкурса (12 сентября 1997 г.). Свой алгоритм могла предложить любая организация или группа исследователей. Требования к новому стандарту были следующими:

  • блочный шифр.
  • длина блока, равная 128 битам.
  • ключи длиной 128, 192 и 256 бит.

Подобные шифры были довольно редки во время объявления конкурса; возможно, лучшим был Square. Дополнительно кандидатам рекомендовалось:

  • использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах)
  • ориентироваться на 32-разрядные процессоры
  • не усложнять без необходимости структуру шифра для того, чтобы все заитересованные стороны были в состоянии самостоятельно провести независимый криптоанализ алгоритма и убедиться, что в нём не заложено каких-либо недокументированных возможностей.

Кроме того, алгоритм, претендующий на то, чтобы стать стандартом, должен распространяться по всему миру на неэксклюзивных условиях и без платы за пользование патентом.

1-й и 2-й раунды Править

20 августа 1998 года на 1-й конференции AES был объявлен список из 15 кандидатов: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish. В последующих обсуждениях эти алгоритмы подвергались всестороннему анализу, причём исследовались не только криптографические свойства, такие как стойкость к известным атакам, отсутствие слабых ключей, но и практические аспекты реализации: оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распаралелливания. В марте 1999 года прошла 2-я конференция AES, а в августе 1999 года были объявлены 5 финалистов: MARS, RC6, Rijndael, Serpent и Twofish. Все эти алгоритмы были разработаны авторитетными криптографами с мировым именем. На 3-й конференции AES в апреле 2000 года авторы выступили с докладами о своих алгоритмах.

Третья конференция AES Править

Третья конференция AES прошла в Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа. На ней присутствовало 250 участников, многие из которых приехали из-за рубежа. Двухдневная конференция была разделена на восемь сессий, по четыре в день, плюс к тому состоялась неформальная дополнительная сессия, подводившая итоги первого дня. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FPGA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На сессиях второго дня был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael рассказал Винсент Риджмен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.

Выбор победителя Править

2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael[1], и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197.

Историческую ретроспективу конкурса можно проследить на веб-сайте NIST [2].

Описание AES Править

Определения и вспомогательные процедуры Править

AES, Rijndael-AES, Rijndael
изображение </span>
Определения
Block последовательность бит, из которых состоит input, output, State и Round Key. Также под Block можно понимать последовательность байт
Cipher Key секретный, криптографический ключ, который используется Key Expansion процедурой, чтобы произвести набор ключей для раундов(Round Keys); может быть представлен как прямоугольный массив байтов, имеющий четыре строки и Nk колонок.
Ciphertext выходные данные алгоритма шифрования
Key Expansion процедура используемая для генерации Round Keys из Cipher Key
Round Key Round Keys получаются из Cipher Key используя процедуру Key Expansion. Они применяются к State при шифровании и расшифровании
State промежуточный результат шифрования, который может быть представлен как прямоугольный массив байтов имеющий 4 строки и Nb колонок
S-box нелинейная таблица замен использующаяся в нескольких трансформациях замены байт и в процедуре Key Expansion для взаимнооднозначной замены значения байта
Nb число столбцов(32-ух битных слов), составляющих State. Для, AES Nb = 4
Nk число 32-ух битных слов, составляющих шифроключ. Для AES, Nk = 4,6, или 8
Nr число раундов, которое является функцией Nk и Nb. Для AES, Nr = 10, 12, 14
Rcon[] массив, который состоит из битов 32-х разрядного слова и является постоянным для данного раунда


Вспомогательные процедуры
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 к каждому из четырех байтов выдает выходное слово

Шифрование Править

AES является стандратом, основанным на алгоритме Rijndael. Для AES длина input(блока входных данных) и State(состояния) постоянна и равна 128 бит, а длина шифроключа K составляет 128, 192, или 256 бит. Для обозначения выбранных длин input, State и Cipher Key в байтах используется нотация Nb = 4 для input и State, Nk = 4, 6, 8 для Cipher Key соответственно для разных длин ключей.

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

Шифр описан в псевдокоде на рис1. Отдельные трансформации SubBytes(), ShiftRows(), MixColumns(), и AddRoundKey() - обрабатывают State. Массив w[] - содержит key schedule.


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

Рис1. Псевдокод для Cipher


SubBytes() Править

Файл:AES-SubBytes.svg

Процедура SubBytes() обрабатывает каждый байт состояния, независимо производя нелинейную замену байтов используя таблицу замен( S-box). Такая операция обеспечивает нелинейность алгоритма шифрования. Построение S-box состоит из двух шагов. Во-первых, производится взятие обратного числа в GF{2^8}. Во-вторых, к каждому байту b из которых состоит S-box применяется следующая операция: b^{'}_{i} = b_{i} \oplus b_{(i+4)mod8} \oplus b_{(i+5)mod8} \oplus b_{(i+6)mod8} \oplus b_{(i+7)mod8} \oplus c_{i} , где 0 \le i < 8, и где bi есть i-ый бит b, а ci - i-ый байт c = {63} или {01100011}. Таким образом обеспечивается защита от аттак основанных на простых алгебраических свойствах.



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

ShiftRows() Править

Файл:AES-ShiftRows.svg

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






MixColumns() Править

Файл:AES-MixColumns.svg

В процедуре MixColumns, четыре байта каждой колонки State смешиваются используя для этого обратимую линейную трансформацию. MixColumns обрабатывает состояния по колонкам, трактуя каждую из них как полином четвертой степени. Над этими полиномами производится умножение в GF(2^8) по модулю x^4+1 на фиксированный многочлен c(x) = 3x^3 + x^2 + x + 2. Вместе с ShiftRows , MixColumns вносит diffusion в шифр






AddRoundKey() Править

Файл:AES-AddRoundKey.svg

В процедуре AddRoundKey, RoundKey каждого раунда объединяется со State. Для каждого раунда Roundkey получается из CipherKey используя процедуру KeyExpansion; каждый RoundKey такого же размера, что и State. Процедура производит побитовый XOR каждого байта State с каждым байтом RoundKey .

KeyExpansion() Править

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

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

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

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


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

Рис.6 Псевдокод для Key Expansion

Расшифрование Править


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, (Nr+1)*Nb-1])

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

    InvShiftRows(state)
    InvSubBytes(state)
    InvAddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

    out = state
end

Рис.7 Псевдокод для Inverse Cipher

Примечания Править

Ссылки Править

af:Rijndael

ar:إيه إي إس cs:Advanced Encryption Standard da:Advanced Encryption Standard de:Advanced Encryption Standard en:Advanced Encryption Standard eo:AES (kriptado) es:Advanced Encryption Standard eu:Advanced Encryption Standard fi:AES fr:Standard de chiffrement avancé gl:Advanced Encryption Standard he:Advanced Encryption Standard hr:Advanced Encryption Standard id:AES it:Advanced Encryption Standard ja:AES暗号 ka:შიფრაციის სტანდარტი ko:고급 암호 표준 lt:AES nl:Advanced Encryption Standard no:Advanced Encryption Standard pl:AES pt:AES ro:AES simple:Advanced Encryption Standard sv:Advanced Encryption Standard tg:AES tr:AES uk:AES vi:AES (mã hóa) zh:高级加密标准

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики