Материал: Информационная безопасность и защита информации. учебное пособие. Паринов А.В., Федорков Е.Д

2.2.2.2. Сеть Фейштеля

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

Классическая сеть Фейштеля имеет следующую структуру:

Рис. 2.3

Независимые потоки информации, порожденные из исходного блока, называются ветвями сети. В классической схеме их две. Величины V_i именуются параметрами сети, обычно это функции от материала ключа. Функция F называется образующей. Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами, называется циклом или раундом (англ. round) сети Фейштеля. Оптимальное число раундов K – от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптоскойстость любого блочного шифра к криптоанализу. Возможно, эта особенность и повлияла на столь активное распространение сети Фейштеля – ведь при обнаружении, скажем, какого-либо слабого места в алгоритме почти всегда достаточно увеличить количество раундов на 4-8, не переписывая сам алгоритм. Часто количество раундов не фиксируется разработчиками алгоритма, а лишь указываются разумные пределы (обязательно нижний, и не всегда – верхний) этого параметра.

Сразу же возникает вопрос, – является ли данная схема обратимой? Очевидно, да. Сеть Фейштеля обладает тем свойством, что даже если в качестве образующей функции F будет использовано необратимое преобразование, то и в этом случае вся цепочка будет восстановима. Это происходит вследствие того, что для обратного преобразования сети Фейштеля не нужно вычислять функцию F^-1.

Более того, как нетрудно заметить, сеть Фейштеля симметрична. Использование операции XOR, обратимой своим же повтором, и инверсия последнего обмена ветвей делают возможным раскодирование блока той же сетью Фейштеля, но с инверсным порядком параметров V_i. Заметим, что для обратимости сети Фейштеля не имеет значение является ли число раундов четным или нечетным числом. В большинстве реализаций схемы, в которых оба вышеперечисленные условия (операция XOR и уничтожение последнего обмена) сохранены, прямое и обратное преобразования производятся одной и той же процедурой, которой в качестве параметра передается вектор величин V_i либо в исходном, либо в инверсном порядке.

С незначительными доработками сеть Фейштеля можно сделать и абсолютно симметричной, то есть выполняющей функции шифрования и дешифрования одним и тем же набором операций. Математическим языком это записывается как "Функция EnCrypt тождественно равна функции DeCrypt". Если мы рассмотрим граф состояний криптоалгоритма, на котором точками отмечены блоки входной и выходной информации, то при каком-то фиксированном ключе для классической сети Фейштеля мы будем иметь картину, изображенную на рис. 2.4,а, а во втором случае каждая пара точек получит уникальную связь, как изображено на рис. 2.4,б. Модификация сети Фейштеля, обладающая подобными свойствами приведена на рис. 2.5. Как видим, основная ее хитрость в повторном использовании данных ключа в обратном порядке во второй половине цикла. Необходимо заметить, однако, что именно из-за этой недостаточно исследованной специфики такой схемы (то есть потенциальной возможности ослабления зашифрованного текста обратными преобразованиями) ее используют в криптоалгоритмах с большой осторожностью.

Рис. 2.4

Рис. 2.5

А вот модификацию сети Фейштеля для большего числа ветвей применяют гораздо чаще. Это в первую очередь связано с тем, что при больших размерах кодируемых блоков (128 и более бит) становится неудобно работать с математическими функциями по модулю 64 и выше. Как известно, основные единицы информации, обрабатываемые процессорами на сегодняшний день – это байт и двойное машинное слово 32 бита. Поэтому все чаще и чаще в блочных криптоалгоритмах встречается сеть Фейштеля с 4-мя ветвями. Самый простой принцип ее модификации изображен на рис. 2.6,а. Для более быстрого перемешивания информации между ветвями (а это основная проблема сети Фейштеля с большим количеством ветвей) применяются две модифицированные схемы, называемые "type-2" и "type-3". Они изображены на рис. 2.6,б и 2.6,в.

Рис. 2.6

Сеть Фейштеля надежно зарекомендовала себя как криптостойкая схема произведения преобразований, и ее можно найти практически в любом современном блочном шифре. Незначительные модификации касаются обычно дополнительных начальных и конечных преобразований (англоязычный термин – whitening) над шифруемым блоком. Подобные преобразования, выполняемые обычно также "исключающим ИЛИ" или сложением, имеют целью повысить начальную рандомизацию входного текста. Таким образом, криптостойкость блочного шифра, использующего сеть Фейштеля, определяется на 95% функцией F и правилом вычисления V_i из ключа. Эти функции и являются объектом все новых и новых исследований специалистов в области криптографии.

2.2.2.3. Блочный шифр tea

Рассмотрим один из самых простых в реализации, но признанно стойких криптоалгоритмов – TEA (Tiny Encryption Algorithm).

Параметры алгоритма : Размер блока – 64 бита. Длина ключа – 128 бит. В алгоритме использована сеть Фейштеля с двумя ветвями в 32 бита каждая. Образующая функция F обратима. Сеть Фейштеля несимметрична из-за использования в качестве операции наложения не исключающего "ИЛИ", а арифметического сложения. Ниже приведен код криптоалгоритма на языке программирования PASCAL.

type TLong2=array[0.. 1] of longint;

TLong2x2=array[0.. 1] of TLong2;

const Delta=$9E3779B9;

var key:TLong2x2;

procedure EnCryptRouting(var data);

var y,z,sum:longint; a:byte;

begin

y:=TLong2(data)[0];z:=TLong2(data)[1];sum:=0;

for a:=0 to 31 do

begin

inc(sum,Delta);

inc(y,((z shl 4)+key[0,0]) xor (z+sum) xor ((z shr 5)+key[0,1]));

inc(z,((y shl 4)+key[1,0]) xor (y+sum) xor ((y shr 5)+key[1,1]));

end;

TLong2(data)[0]:=y;TLong2(data)[1]:=z

end;

Схема работы алгоритма приведена на рис. 2.7

Рис. 2.7

Отличительной чертой криптоалгоритма TEA является его размер. Простота операций, отсутствие табличных подстановок и оптимизация под 32-разрядную архитектуру процессоров позволяет реализовать его на языке ASSEMBLER в предельно малом объеме кода. Недостатком алгоритма является некоторая медлительность, вызванная необходимостью повторять цикл Фейштеля 32 раза (это необходимо для тщательного "перемешивания данных" из-за отсутствия табличных подстановок).

2.2.2.4. Aes : cтандарт блочных шифров сша

2.2.2.4.1. Общие сведения о конкурсе aes

В 80-х годах в США был принят стандарт симметричного криптоалгоритма для внутреннего применения DES (Data Encryption Standard), который получил достаточно широкое распространение в свое время. Однако на текущий момент этот стандарт полностью неприемлем для использования по двум причинам : 1) основной – длина его ключа составляет 56 бит, что чрезвычайно мало на современном этапе развития ЭВМ, 2) второстепенной – при разработке алгоритм был ориентирован на аппаратную реализацию, то есть содержал операции, выполняемые на микропроцессорах за неприемлимо большое время (например, такие как перестановка бит внутри машинного слова по определенной схеме).

Все это сподвигло Национальный институт стандартизации США на объявление в 1997 году конкурса на новый стандарт симметричного криптоалгоритма. На сей раз уже были учтены основные промахи шифра-предшественника, а к разработке были подключены самые крупные центры по криптологии со всего мира. Тем самым победитель этого соревнования, названного AES – Advanced Encryption Standard, станет де-факто мировым криптостандартом на ближайшие 10-20 лет.

Требования, предъявленные к кандидитам на AES в 1998 году, были предельно просты :

1) алгоритм должен быть симметричным;

2) алгоритм должен быть блочным шифром;

3) алгоритм должен иметь длину блока 128 бит и поддерживать три длины ключа : 128, 192 и 256 бит.

Дополнительно кандидатам рекомендовалось:

1) использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах);

2) ориентироваться на 32-разрядные процессоры;

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

На первом этапе в оргкомитет соревнования поступило 15 заявок из совершенно разных уголков мира. В течение 2 лет специалисты комитета, исследуя самостоятельно и изучая публикации других исследователей, выбрали 5 лучших представителей, прошедших в "финал" соревнования.

Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа.

2 октября 2000 года NIST объявил о своем выборе – победителем конкурса стал бельгийский алгоритм RIJNDAEL. С этого момента с алгоритма-победителя сняты все патентные ограничения – его можно будет использовать в любой криптопрограмме без отчисления каких-либо средств создателю.

Ниже мы рассмотрим основные (рабочие) части алгоритмов победителей первого этапа. Объем лекции не позволяет привести для каждого алгоритма методы создания S-box'ов (таблиц для табличных подстановок) и методы расширения материала ключа. Полное описание всех 15 алгоритмов претендентов на AES, включая исследования по их криптостойкости, можно найти на сервере института NIST, указанном выше.

2.2.2.4.2. Финалист aes – шифр mars

Шифр состоит из трех видов операций, которые повторяются сначала в прямом, а затем в инверсном порядке. На первом шаге идет классическое входное забеливание : ко всем байтам исходного текста добавляются байты из материала ключа.

Второй этап : прямое перемешивание, однотипная операция, имеющая структуру сети Фейштеля, повторяется 8 раз. Однако на этом этапе не производится добавление материала ключа. Цель данного преобразования – тщательная рандомизация данных и повышение стойкости шифра к некоторым видам атак (рис. 2.8).

Третий этап : собственно шифрование. В нем используется сеть Фейштеля треьтего типа с 4 ветвями, то есть значения трех функций, вычисленных от одной ветви накладываются соответственно на три других, затем идет перестановка машинных слов. Эта операция также повторяется 8 раз (рис. 2.8). Именно на этом этапе происходит смешивание текста с основной (большей) частью материала ключа. Сами функции, накладываемые на ветви, изображены на рис. 2.9. Как видим, в алгоритме MARS использованы практически все виды операций, применяемых в криптографических преобразованиях : сложение, "исключающее ИЛИ", сдвиг на фиксированное число бит, сдвиг на переменное число бит, умножение и табличные подстановки.

Во второй части операции шифрования повторяются те же операции, но в обратном порядке : сначала шифрование, затем перемешивание и, наконец, забеливание. При этом во вторые варианты всех операций внесены некоторые изменения таким образом, чтобы криптоалгоритм в целом стал абсолютно симметричным. То есть, в алгоритме MARS для любого X выполняется выражение EnCrypt(EnCrypt(X))=X.

Рис. 2.8

Рис. 2.9

2.2.2.4.3. Финалист aes – шифр rc6

Алгоритм является продолжением криптоалгоритма RC5, разработанного Рональдом Ривестом (англ. Ron Rivest) – очень известной личностью в мире криптографии. RC5 был незначительно изменен для того, чтобы соответствовать требованиям AES по длине ключа и размеру блока. При этом алгоритм стал еще быстрее, а его ядро, унаследованное от RC5, имеет солидный запас исследований, проведенных задолго до объявления конкурса AES.

Алгоритм является сетью Фейштеля с 4 ветвями смешанного типа : в нем два четных блока используются для одновременного изменения содержимого двух нечетных блоков. Затем производится обычный для сети Фейштеля сдвиг на одно машинное слово, что меняет четные и нечетные блоки местами. Сам алгоритм предельно прост и изображен на рис. 2.10. Разработчики рекомендуют при шифровании использовать 20 раундов сети, хотя в принципе их количество не регламентируется. При 20 повторах операции шифрования алгоритм имеет самую высокую скорость среди 5 финалистов AES.

Рис. 2.10

Преобразование T(x) очень просто : T(X)=(X*(X+1)) mod 2^N. Оно используется в качестве нелинейного преобразования с хорошими показателями перемешивания битового значения входной величины.

2.2.2.4.4. Финалист aes – шифр Serpent

Алгоритм разработан группой ученых из нескольких исследовательских центров мира. Алгоритм представляет собой сеть Фейштеля для четырех ветвей смешанного типа : 2 четные ветви изменяют совместо значения нечетных, затем меняются местами. В качестве криптопреобразований используются только исключающее "ИЛИ", табличные подстановки и битовые сдвиги. Алгоритм состоит из 32 раундов. Сами раунды составлены таким образом, что добавление к ветвям материала ключа на первом и последнем раундах образует входное и выходное забеливание.