3. Алгоритм шифрования aes

Advanced Encryption Standard (AES), также известный как Rijndael — симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), принятый в качестве стандарта шифрования правительством США по результатам конкурса AES. Этот алгоритм хорошо проанализирован и сейчас широко используется, как это было с его предшественником DES. Национальный институт стандартов и технологий США (англ. National Institute of Standards and Technology, NIST) опубликовал спецификацию AES 26 ноября 2001 года после пятилетнего периода, в ходе которого были созданы и оценены 15 кандидатур. 26 мая 2002 года AES был объявлен стандартом шифрования. По состоянию на 2009 год AES является одним из самых распространённых алгоритмов симметричного шифрования. Поддержка AES (и только его) введена фирмой Intel в семейство процессоров x86 начиная с Intel Core i7-980X Extreme Edition, а затем на процессорах Sandy Bridge.

Дизайн AES основан на принципе substitution-permutation networks (сети замен-перестановок). Он быстр как для программного, так и для аппаратного обеспечения. В отличие от своего предшественника, DES, AES не использует сети Фейстеля. AES имеет фиксированный размер блока в 128 бит и размер ключа 128, 192 или 256 бит (в DES – 56 бит, в Triple DES – 168), в то время как Rijndael специфицирован с блоками и размерами ключей кратными 32 битам: минимум 128 и максимум 256 бит.

AES оперирует матрицами байтов 4 x 4 (column-major order), называемые State (версии Rijndael с большими блоками имеют дополнительные колонки в state). Большие расчеты AES производятся в конечном поле.

Шифр AES определяется количеством циклов повторений преобразований, которые конвертируют входящий текст в конечный шифротекст. Количество повторений следующее: 10 циклов повторений для 128-битного ключа, 12 циклов повторений для 192-битного ключа, 14 циклов повторений для 256-битного ключа.

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

Высокоуровневое описание алгоритма

1. KeyExpansion—round - ключи получаются из ключа шифрования с использованием таблицы ключей Rijndael's

2. Initial Round

   1. AddRoundKey—каждый байт состояния складывается с round-ключом побитовым XOR.

3. Rounds

   1. SubBytes—нелинейная замена, в которой байты переставляются между собой согласно таблице перестановок

   2. ShiftRows—перестановочный цикл, в котором каждая строка состояния циклически перемешивается за определенное количество шагов.

   3. MixColumns—операция перемешивания, которая оперирует столбцами состояния, складывая 4 бита в каждом столбце

   4. AddRoundKey

4. Final Round (без MixColumns)

   1. SubBytes

   2. ShiftRows

   3. AddRoundKey

В начале шифрования input копируется в массив State по правилу 

, для   и  . После этого к State применяется процедура AddRoundKey() и затем State проходит через процедуру трансформации (раунд) 10, 12, или 14 раз (в зависимости от длины ключа), при этом надо учесть, что последний раунд несколько отличается от предыдущих. В итоге, после завершения последнего раунда трансформации, State копируется в output по правилу

, для   и  .

SubBytes()

П роцедура SubBytes() обрабатывает каждый байт состояния, независимо производя нелинейную замену байтов используя таблицу замен (S-box). Такая операция обеспечивает нелинейность алгоритма шифрования. Построение S-box состоит из двух шагов. Во-первых, производится взятие обратного числа в поле Галуа  . Во-вторых, к каждому байту b из которых состоит S-box применяется следующая операция:

где  , и где   есть i-ый бит b, а   — i-ый бит константы  . Таким образом, обеспечивается защита от атак, основанных на простых алгебраических свойствах.

S hiftRows()

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

M ixColumns()

В процедуре MixColumns, четыре байта каждой колонки State смешиваются, используя для этого обратимую линейную трансформацию. MixColumns обрабатывает состояния по колонкам, трактуя каждую из них как полином четвёртой степени. Над этими полиномами производится умножение в   по модулю   на фиксированный многочлен  . Вместе с ShiftRows, MixColumns вносит диффузию в шифр.

AddRoundKey()

В процедуре AddRoundKey, RoundKey каждого раунда объединяется со State. Для каждого раунда Roundkey получается из CipherKey используя процедуру 

KeyExpansion; каждый RoundKey такого же размера, что и State. Процедура производит побитовый XOR каждого байта State с каждым байтом RoundKey .

Алгоритм обработки ключа

Алгоритм обработки ключа состоит из двух процедур:

• Алгоритм расширения ключа

• Алгоритм выбора раундового ключа (ключа итерации)

Алгоритм расширения ключа

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

,  .

Функция SubWord() берет четырёхбайтовое входное слово и применяет S-box к каждому из четырёх байтов. То, что получилось, подается на выход. На вход RotWord() подается слово   которое она циклически переставляет и возвращает  . Массив слов, постоянный для данного раунда,  , содержит значения  , где x = {02}, а   является степенью   в   ( начинается с 1).

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

Важно заметить, что процедура KeyExpansion() для 256 битного Cipher Key немного отличается от тех, которые применяются для 128 и 192 битных шифроключей. Если   и   кратно  , то SubWord() применяется к   до XOR’а.

Режимы шифрования AES

Вектор инициализации

В таких режимах шифрования, как CBC, CFB и OFB на вход функций   и   подаётся вектор инициализации (IV). Причём как отправитель, так и получатель в начале сеанса связи должны иметь один и тот же IV. Значение IV вовсе не обязано быть секретным и вполне может быть передано вместе с первым блоком шифротектса. Что действительно важно, так это то, что в режимах CBC и CFB это значение должно быть непредсказуемым, а в режиме OFB – уникальным.

Непредсказуемости   в режимах CBC и CFB можно достичь несколькими способами. Например, можно подвергнуть преобразованию той же функцией   значение какого-либо счётчика (скажем счётчика сообщений). Или использовать ГПК для генерации псевдослучайной последовательности нужной длины.

В режиме OFB вектор инициализации не обязан быть непредсказуемым, зато он должен быть уникален для всех сеансов связи в которых в OFB используется один и тот же секретный ключ шифрования K. Этого можно достичь опять же используя счётчик сообщений. Если же не следовать этому требованию, то секретность сообщения в режиме OFB может быть легко скомпрометирована. Пример приведён выше при описании самого режима OFB. Одним из следствий этого требования является то, что очередной вектор инициализации для режима OFB нельзя генерировать путём применения функции   с тем же ключом K.

Режим шифра ECB (Electronic codebook) означает, что каждый 16-байтовый блок шифруется независимо (размер блока AES — 128 бит или 16 байт).

Например, если у нас есть сообщение

In cryptography, the Advanced Encryption Standard (AES) is a symmetric-key encryption standard adopted by the U.S. government. The standard comprises three block ciphers, AES-128, AES-192 and AES-256

Зашифровав его, мы получим шифротекст:

95c4f38712a0c5041576c4037d8bb6d2

b206863b09afa7ea454f301cc78b4f87

bf2f29285b0a299ac648e4e3ba41b5e3

9c486beabddb36234dc3f3c7896b0aae

...

Теперь, если переставить первую и вторую строчку, а затем расшифровать, то получим:

b206863b09afa7ea454f301cc78b4f87 ; Это была вторая строчка

95c4f38712a0c5041576c4037d8bb6d2 ; Это была первая строчка

bf2f29285b0a299ac648e4e3ba41b5e3

9c486beabddb36234dc3f3c7896b0aae

...

the Advanced EnIn cryptography,cryption Standard (AES) is a symmetric-key encryption standard adopted by the U.S. government. The standard comprises three block ciphers, AES-128, AES-192 and AES-256

Т.е. текст расшифровался, но с переставленными блоками. Так же, если бы мы заменили блок из другого шифротекста, он бы у нас так же успешно расшифровался с ожидаемым результатом. Удаление блока и дублирование блока аналогично приводит к успешной расшифровке и ожидаемым результатом.

Вместо ECB можно использовать другие режимы шифрования, в который каждый последующий блок зависит от предыдущего. Например, режим CBC (Cipher-block chaining)

В режиме CBC удаление блока, смена порядка следований блоков, дублирование и т.п. приводят к порче тех блоков, над которыми была проведена операция и соседних блоков.

CFB (Cipher Feed Back) – обратная загрузка шифротекста.

В алгоритме режима обратной загрузки шифротектса очередной блок открытого текста суммируется по модулю с блоком предыдущего шифротекста, но только после того, как этот шифротекст подвергнется дополнительной обработке функцией  . Так происходит зашифрование сообщения в этом режиме. Для расшифрования нужно просто суммировать (естественно по модулю 2) очередной блок шифротекста с предыдущим, пропущенным опять-таки через функцию  . При за- и расшифровании в этом режиме блочный шифр используется только в режиме зашифрования (то есть функции   нет вообще). Такие режимы, в которых функция преобразования блочным шифром применяется до суммирования с блоком открытого текста называютпоточными (далее будет видно почему), если же функция преобразования блочным шифром вызывается в алгоритме режима после наложения блока открытого текста, то такой режим шифрования будет блочным.

В поточных режимах шифрования можно применить трюк, позволяющий сгладить проблему дополнения последнего блока сообщения. Вместо того, чтобы скармливать алгоритму режима на каждой его итерации сообщение полными блоками, текст подаётся порциями длиной  , где b – длина блока в битах. И далее, при суммировании используется только s старших бит выходных данных функции  , остальные попросту отбрасываются. Следующая итерация режима получает на входе s бит шифротекста, которые сдвигают влево на s бит входные данные функции  , оставшиеся там с предыдущей итерации.

Режим OFB, как и CFB является поточным, то есть функция   вызывается в алгоритме досуммирования с порцией открытого текста. Но на этот раз на вход   подаётся не шифротекст с предыдущей итерации, а просто её же выходные данные. То есть происходит как бы зацикливание функции  . В такой ситуации становится важным однократное использование вектора инициализации. И вот почему. Допустим два различных сообщения шифруются в режиме OFB с использованием одного и того же вектора инициализации. Тогда, если противнику становится известен какой-либо j-ый блок открытого текста первого сообщения, то, имея j-ыйблок шифротекста он легко может вычислить O_j – выходные данные  , а поскольку они зависят только от вектора инициализации, который одинаков для обоих сообщений, то можно утверждать, что и во втором сообщении это будет тот же O_j , отсюда, имея j-ый блок шифротекста второго сообщения противник тутже получит открытый текст j-го блока второго сообщения. Поэтому в алгоритме OFB необходимо избегать не только повторения векторов инициализации, но и того, что бы любой j-ый блок входных данных функции   для одного сообщения не использовался как вектор инициализации для другого сообщения.

В потоковом режиме шифрования со счётчиком на каждой итерации алгоритма шифрования на вход функции   подаётся некое случайное значение Т. Эти входные данные должны быть различны для всех итераций алгоритма в которых блочный шифр использует один и тот же ключ шифрования, поэтому генератор таких значений иногда называют счётчиком (что даёт наиболее простой способ генерации уникальных значений T). На самом деле требование уникальности входных данных функции   при определённом значении K будет удовлетворено и в случае использования ГПК (генератора псевдослучайных кодов), но тогда необходим начальный вектор инициализации для ГПК со стороны отправителя и получателя сообщений.

Криптостойкость и минусы AES

В июне 2003 года Агентство национальной безопасности США постановило, что шифр AES является достаточно надёжным, чтобы использовать его для защиты сведений, составляющих государственную тайну (англ. classified information). Вплоть до уровня SECRET было разрешено использовать ключи длиной 128 бит, для уровня TOP SECRET требовались ключи длиной 192 и 256 бит.

По сравнению с DES, AES имеет более криптостойкий ключ (128 – 256 бит против 56 у DES). Имеются опасения по поводу взлома XSL атаками, но возможность таких атак пока не доказана (но и не опровергнута).

В целом, пока AES остается стандартом де-факто и хорошо зарекомендовал себя как алгоритм шифрования.

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