Рис.1.
Общие сведения о конкурсе AES
Требования к конкурсантам AES, краткая информация о Национальном Институте Стандартизации США. На конкурс было подано 15 заявок, первый этап отбора прошли только 5 претендентов – финалистов AES.
Финалист AES – шифр MARS
Разработка корпорации IBM, основанная на классической сети Фейштеля и многочисленных математических операциях.
Финалист AES – шифр RC6
Модификация широко известного блочного шифра RC5. Использует только основные математические преобразования, битовые сдвиги и, в качестве функции перемешивания, операцию T(X)=X*(X+1).
Финалист AES – шифр Serpent
Шифр использует только операции табличных подстановок, исключающего "ИЛИ" и битовых сдвигов в тщательно подобранной очередности.
Финалист AES – шифр TwoFish
Достаточно сложная в реализации разработка компании Counterpane Security Systems, воплотившая много интересных идей из алгоритма предшественника BlowFish.
Победитель AES – шифр Rijndael
Блочный шифр, реализованный не по принципу сети Фейштеля, и имеющий надежную математическую базу преобразований. Структура алгоритма позволяет достичь очень высокой степени оптимизации на персональных ЭВМ и серверах, и в то же время не слишком замедляет выполнение на электронных устройствах с ограниченными ресурсами.
В 80-х годах в США был принят стандарт симметричного криптоалгоритма для внутреннего применения DES (Data Encryption Standard), который получил достаточно широкое распространение в свое время. Однако к концу 90-х годов стали заметны его недостатки: 1) основной – длина его ключа составляет 56 бит, что слишком мало для существенно выросшей производительности ЭВМ, 2) второстепенной – при разработке алгоритм был ориентирован на аппаратную реализацию и содержал операции, выполняемые на универсальных микропроцессорах не слишком эффективно (например, такие как перестановка бит внутри машинного слова по определенной схеме).
Все это сподвигло Американский институт стандартизации NIST – National Institute of Standards & Technology на объявление в 1997 году конкурса на новый стандарт симметричного криптоалгоритма. На сей раз уже были учтены основные промахи шифра-предшественника, а к разработке были подключены самые крупные центры по криптологии со всего мира. Тем самым, победитель этого соревнования, названного AES – Advanced Encryption Standard , должен быть стать де-факто мировым криптостандартом на ближайшие 10-20 лет.
Требования, предъявленные к кандидитам на AES в 1998 году, были предельно просты :
Дополнительно кандидатам рекомендовалось:
На первом этапе в оргкомитет соревнования поступило 15 заявок из совершенно разных уголков мира. В течение 2 лет специалисты комитета, исследуя самостоятельно, и изучая публикации других исследователей, выбрали 5 лучших представителей, прошедших в "финал" соревнования.
| Алгоритм | Создатель | Страна | Быстродействие (asm, 200МГц) |
| MARS | IBM | US | 8 Мбайт/с |
| RC6 | R.Rivest & Co | US | 12 Мбайт/с |
| Rijndael | V.Rijmen & J.Daemen | BE | 7 Мбайт/с |
| Serpent | Universities | IS, UK, NO | 2 Мбайт/с |
| TwoFish | B.Schneier & Co | US | 11 Мбайт/с |
Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа.
2 октября 2000 года NIST объявил о своем выборе – победителем конкурса стал бельгийский алгоритм RIJNDAEL. С этого момента с алгоритма-победителя сняты все патентные ограничения – его можно будет использовать в любой криптопрограмме без отчисления каких-либо средств создателю.
Ниже мы рассмотрим основные (рабочие) части алгоритмов победителей первого этапа. Объем лекции не позволяет привести для каждого алгоритма методы создания S-box'ов (таблиц для табличных подстановок) и методы расширения материала ключа. Полное описание всех 15 алгоритмов претендентов на AES, включая исследования по их криптостойкости можно найти на сервере института NIST, указанном выше.
Шифр состоит из трех видов операций, которые повторяются сначала в прямом, а затем в инверсном порядке. На первом шаге идет классическое входное забеливание : ко всем байтам исходного текста добавляются байты из материала ключа.
Второй этап : прямое перемешивание, однотипная операция, имеющая структуру сети Фейштеля повторяется 8 раз. Однако, на этом этапе не производится добавление материала ключа. Цель данного преобразования – тщательная рандомизация данных и повышение стойкости шифра к некоторым видам атак (рис.1).
Третий этап : собственно шифрование. В нем используется сеть Фейштеля треьего типа с 4 ветвями, то есть значения трех функций, вычисленных от одной ветви накладываются соответственно на три других, затем идет перестановка машинных слов. Эта операция также повторяется 8 раз (рис.1). Именно на этом этапе происходит смешивание текста с основной (большей) частью материала ключа. Сами функции, накладываемые на ветви, изображены на рис.2. Как видим, в алгоритме MARS использованы практически все виды операций, применяемых в криптографических преобразованиях : сложение, "исключающее ИЛИ", сдвиг на фиксированное число бит, сдвиг на переменное число бит, умножение и табличные подстановки.
Во второй части операции шифрования повторяются те же операции, но в обратном порядке : сначала шифрование, затем перемешивание, и, наконец, забеливание. При этом во вторые варианты всех операций внесены некоторые изменения таким образом, чтобы криптоалгоритм в целом стал абсолютно симметричным. То есть, в алгоритме MARS для любого X выполняется выражение EnCrypt(EnCrypt(X))=X
Рис.1.
Рис.2.
Алгоритм является продолжением криптоалгоритма RC5, разработанного Рональдом Ривестом (англ. Ron Rivest) – очень известной личностью в мире криптографии. RC5 был незначительно изменен для того, чтобы соответствовать требованиям AES по длине ключа и размеру блока. При этом алгоритм стал еще быстрее, а его ядро, унаследованное от RC5, имеет солидный запас исследований, проведенных задолго до объявления конкурса AES.
Алгоритм является сетью Фейштеля с 4 ветвями смешанного типа : в нем два четных блока используются для одновременного изменения содержимого двух нечетных блоков. Затем производится обычный для сети Фейштеля сдвиг на одно машинное слово, что меняет четные и нечетные блоки местами. Сам алгоритм предельно прост и изображен на рисунке 3. Разработчики рекомендуют при шифровании использовать 20 раундов сети, хотя в принципе их количество не регламентируется. При 20 повторах операции шифрования алгоритм имеет самую высокую скорость среди 5 финалистов AES.
Рис.3.
Преобразование T(x) очень просто : T(X)=(X*(X+1)) mod 2 N . Оно используется в качестве нелинейного преобразования с хорошими показателями перемешивания битового значения входной величины.
Алгоритм разработан группой ученых из нескольких исследовательских центров мира. Алгоритм представляет собой сетей Фейштеля для четырех ветвей смешанного типа : 2 четные ветви изменяют совместо значения нечетных, затем меняются местами. В качестве криптопреобразований используются только исключающее "ИЛИ", табличные подстановки и битовые сдвиги. Алгоритм состоит из 32 раундов. Сами раунды составлены таким образом, что добавление к ветвями материала ключа на первом и последнем раундах образует входное и выходное забеливание.
Рис.4.
Алгоритм разработан команией Counterpain Security Systems, возглавляемой Брюсом Шнайером (англ. Bruce Schneier). Предыдущая программная разработка этой фирмы, называвшаяся BlowFish, являлась и до сих пор является признанным криптостойким алгоритмом.
В алгоритме TwoFish разработчики оставили некоторые удачные решения из проекта-предшественника, кроме этого произвели тщательные исследования по перемешиванию данных в сети Фейштеля. Алгоритм представляет собой сеть Фейштеля смешанного типа: первая и вторая ветвь на нечетных раундах производят модификацию третьей и четвертой, на четных раундах ситуация меняется на противоположную. В алгоритме используется криптопреобразование Адамара (англ. Pseudo-Hadamar Transform) – обратимое арифметическое сложение первого потока со вторым, а затем второго с первым.
Единственным нарицанием, поступившим в адрес TwoFish от независимых исследователей, является тот факт, что при расширении материала ключа в алгоритме используется сам же алгоритм. Двойное применение блочного шифра довольно сильно усложняет его анализ на предмет наличия слабых ключей или недокументированных замаскированных связей между входными и выходными данными.
Рис.5.
Данный алгоритм разработан двумя специалистами по криптографии из Бельгии. Он является нетрадиционным блочным шифром, поскольку не использует сеть Фейштеля для криптопреобразований. Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока. Далее на соответствующих этапах преобразования производятся либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами в таблице.
Все преобразования в шифре имеют строгое математическое обоснование. Сама структура и последовательность операций позволяют выполнять данный алгоритм эффективно как на 8-битных так и на 32-битных процессорах. В структуре алгоритма заложена возможность параллельного исполнения некоторых операций, что на многопроцессорных рабочих станциях может еще поднять скорость шифрования в 4 раза.
Алгоритм состоит из некоторого количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа), в которых последовательно выполняются следующие операции :
Рис.6.
Рис.7.
Рис.8.
Рис.9.
В последнем раунде операция перемешивания столбцов отсутствует, что делает всю последовательность операций симметричной.