5.4 AES : стандарт блочных шифров 5.4.1 Общие сведения о конкурсе AES В 80-х годах в США был принят стандарт симметричного криптоалгоритма для внутреннего применения DES (Data Encryption Standard), который получил достаточно широкое распространение в свое время. Однако на текущий момент этот стандарт полностью неприемлем для использования по двум причинам : 1) основной – длина его ключа составляет 56 бит, что чрезвычайно мало на современном этапе развития ЭВМ, 2) второстепенной – при разработке алгоритм был ориентирован на аппаратную реализацию, то есть содержал операции, выполняемые на микропроцессорах за неприемлемо большое время (например, такие как перестановка бит внутри машинного слова по определенной схеме). Все это сподвигло Американский институт стандартизации NIST – National Institute of Standards & Technology на объявление в 1997 году конкурса на новый стандарт симметричного криптоалгоритма. На сей раз уже были учтены основные промахи шифра-предшественника, а к разработке были подключены самые крупные центры по криптологии со всего мира. Тем самым, победитель этого соревнования, названного AES – Advanced Encryption Standard, станет де-факто мировым криптостандартом на ближайшие 10-20 лет. Требования, предъявленные к кандидитам на AES в 1998 году, были предельно просты : 1. алгоритм должен быть симметричным, 2. алгоритм должен быть блочным шифром, 3. алгоритм должен иметь длину блока 128 бит, и поддерживать три длины ключа : 128, 192 и 256 бит. Дополнительно кандидатам рекомендовалось: 1. Использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах); 2. Ориентироваться на 32-разрядные процессоры; 3. Не усложнять без необходимости структуру шифра для того, чтобы все заинтересованные стороны были в состоянии самостоятельно провести независимый криптоанализ алгоритма и убедиться, что в нем не заложено каких-либо недокументированных возможностей. На первом этапе в оргкомитет соревнования поступило 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, указанном выше. 5.4.2 Шифр MARS Шифр состоит из трех видов операций, которые повторяются сначала в прямом, а затем в инверсном порядке. На первом шаге идет классическое входное забеливание : ко всем байтам исходного текста добавляются байты из материала ключа. Второй этап : прямое перемешивание, однотипная операция, имеющая структуру сети Фейштеля повторяется 8 раз. Однако, на этом этапе не производится добавление материала ключа. Цель данного преобразования – тщательная рандомизация данных и повышение стойкости шифра к некоторым видам атак (рис.1). Третий этап : собственно шифрование. В нем используется сеть Фейштеля треьего типа с 4 ветвями, то есть значения трех функций, вычисленных от одной ветви накладываются соответственно на три других, затем идет перестановка машинных слов. Эта операция также повторяется 8 раз (рис.1). Именно на этом этапе происходит смешивание текста с основной (большей) частью материала ключа. Сами функции, накладываемые на ветви, изображены на рис.2. Как видим, в алгоритме MARS использованы практически все виды операций, применяемых в криптографических преобразованиях : сложение, "исключающее ИЛИ", сдвиг на фиксированное число бит, сдвиг на переменное число бит, умножение и табличные подстановки. Во второй части операции шифрования повторяются те же операции, но в обратном порядке : сначала шифрование, затем перемешивание, и, наконец, забеливание. При этом во вторые варианты всех операций внесены некоторые изменения таким образом, чтобы криптоалгоритм в целом стал абсолютно симметричным. То есть, в алгоритме MARS для любого X выполняется выражение EnCrypt(EnCrypt(X))=X
Рис. 5.13.
Рис. 5.14 5.4.3 Шифр RC6 Алгоритм является продолжением криптоалгоритма RC5, разработанного Рональдом Ривестом (англ. Ron Rivest) – очень известной личностью в мире криптографии. RC5 был незначительно изменен для того, чтобы соответствовать требованиям AES по длине ключа и размеру блока. При этом алгоритм стал еще быстрее, а его ядро, унаследованное от RC5, имеет солидный запас исследований, проведенных задолго до объявления конкурса AES. Алгоритм является сетью Фейштеля с 4 ветвями смешанного типа : в нем два четных блока используются для одновременного изменения содержимого двух нечетных блоков. Затем производится обычный для сети Фейштеля сдвиг на одно машинное слово, что меняет четные и нечетные блоки местами. Сам алгоритм предельно прост и изображен на рисунке 1. Разработчики рекомендуют при шифровании использовать 20 раундов сети, хотя в принципе их количество не регламентируется. При 20 повторах операции шифрования алгоритм имеет самую высокую скорость среди 5 финалистов AES.
Рис. 5.14 Преобразование T(x) очень просто : T(X)=(X*(X+1)) mod 2N. Оно используется в качестве нелинейного преобразования с хорошими показателями перемешивания битового значения входной величины. 5.4.4 Шифр Serpent Алгоритм разработан группой ученых из нескольких исследовательских центров мира. Алгоритм представляет собой сетей Фейштеля для четырех ветвей смешанного типа : 2 четные ветви изменяют совместо значения нечетных, затем меняются местами. В качестве криптопреобразований используются только исключающее "ИЛИ", табличные подстановки и битовые сдвиги. Алгоритм состоит из 32 раундов. Сами раунды составлены таким образом, что добавление к ветвями материала ключа на первом и последнем раундах образует входное и выходное забеливание.
Рис. 5.15 5.4.5 Шифр TwoFish Алгоритм разработан команией Counterpain Security Systems, возглавляемой Брюсом Шнайером (англ. Bruce Schneier). Предыдущая программная разработка этой фирмы, называвшаяся BlowFish, являлась и до сих пор является признанным криптостойким алгоритмом. В алгоритме TwoFish разработчики оставили некоторые удачные решения из проекта-предшественника, кроме этого произвели тщательные исследования по перемешиванию данных в сети Фейштеля. Алгоритм представляет собой сеть Фейштеля смешанного типа: первая и вторая ветвь на нечетных раундах производят модификацию третьей и четвертой, на четных раундах ситуация меняется на противоположную. В алгоритме используется криптопреобразование Адамара (англ. Pseudo-Hadamar Transform) – обратимое арифметическое сложение первого потока со вторым, а затем второго с первым. Единственным нарицанием, поступившим в адрес TwoFish от независимых исследователей, является тот факт, что при расширении материала ключа в алгоритме используется сам же алгоритм. Двойное применение блочного шифра довольно сильно усложняет его анализ на предмет наличия слабых ключей или недокументированных замаскированных связей между входными и выходными данными.
