Сеть Фе́йстеля, или конструкция Фейстеля (), — один из методов построения блочных шифров. Сеть состоит из ячеек, называемых ячейками Фейстеля. На вход каждой ячейки поступают данные и ключ. На выходе каждой ячейки получают изменённые данные и изменённый ключ. Все ячейки однотипны, и говорят, что сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру. Ключ выбирается в зависимости от алгоритма шифрования/расшифрования и меняется при переходе от одной ячейки к другой. При шифровании и расшифровании выполняются одни и те же операции; отличается только порядок ключей. Ввиду простоты операций сеть Фейстеля легко реализовать как программно, так и аппаратно. Ряд блочных шифров (DES, RC2, RC5, RC6, Blowfish, FEAL, CAST-128, TEA, XTEA, XXTEA и др.) использует сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть (AES и др.).
История В 1971 году Хорст Фейстель запатентовал два устройства, реализующих различные алгоритмы шифрования, позже получившие название «Люцифер» (). Одно из этих устройств использовало конструкцию, впоследствии названную «сетью Фейстеля» (, ). Тогда Фейстель работал над созданием новых криптосистем в стенах IBM вместе с Доном Копперсмитом. Проект «Люцифер» был скорее экспериментальным, но стал основой для алгоритма DES (). В 1973 году журнал «Scientific American» опубликовал статью Фейстеля «Криптография и компьютерная безопасность» ()Хорст Фейстель «Cryptography and computer privacy» («Криптография и компьютерная безопасность»). Перевод Андрея Винокурова., в которой раскрыты некоторые важные аспекты шифрования и приведено описание первой версии проекта «Люцифер». В первой версии проекта «Люцифер» сеть Фейстеля не использовалась.
На основе сети Фейстеля был спроектирован алгоритм DES. В 1977 году власти США приняли стандарт , признающий DES стандартным методом шифрования данных. DES некоторое время широко использовался в криптографических системах. Итеративная структура алгоритма позволяла создавать простые программные и аппаратные реализации.
Согласно некоторым даннымВинокуров А. Статья «Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86». Часть материалов, вошедших в данную статью, была опубликована в выпуске «#1,5/1995 год» журнала «Монитор»., в СССР уже в 1970-е годы КГБ разрабатывала блочный шифр, использовавший сеть Фейстеля, и, вероятно, именно этот шифр в 1990 году был принят в качестве ГОСТ 28147-89.
В 1987 году были разработаны алгоритмы FEAL и RC2. Сети Фейстеля получили широкое распространение в 1990-е годы — в годы появления таких алгоритмов, как Blowfish (1993), TEA (1994), RC5 (1994), CAST-128 (1996), XTEA (1997), XXTEA (1998), RC6 (1998) и других.
2 января 1997 года институт NIST объявил конкурс по созданию нового алгоритма шифрования данных, призванного заменить DES. Новый блочный шифр получил название AES () и был утверждён 26 мая 2002 года. В AES вместо сети Фейстеля используется подстановочно-перестановочная сеть.
Конструкция блочного шифра на основе сетей Фейстеля
Простое описание
Шифрование Пусть требуется зашифровать некоторую информацию, представленную в двоичном виде (в виде последовательности нулей и единиц) и находящуюся в памяти компьютера или иного устройства (например, в е).
Алгоритм шифрования. Информация разбивается на блоки одинаковой (фиксированной) длины. Полученные блоки называются входными, так как поступают на вход алгоритма. В случае, если длина входного блока меньше, чем размер, который выбранный алгоритм шифрования способен зашифровать единовременно (размер блока), блок удлиняется каким-либо способом. Как правило, длина блока является степенью двойки, например, составляет 64 бита или 128 бит.
Далее будем рассматривать операции, происходящие только с одним блоком, так как в процессе шифрования с другими блоками выполняются те же самые операции.
Выбранный блок делится на два подблока одинакового размера — «левый» () и «правый» (). «Правый подблок» изменяется функцией F с использованием раундового ключа :
Результат складывается по модулю 2 («xor») с «левым подблоком» :
Результат будет использован в следующем раунде в роли «правого подблока» :
«Правый подблок» текущего раунда (в своем не измененном на момент начала раунда виде) будет использован в следующем раунде в роли «левого подблока» :
По какому-либо математическому правилу вычисляется раундовый ключ — ключ, который будет использоваться в следующем раунде.
Перечисленные операции выполняются N-1 раз, где N — количество раундов в выбранном алгоритме шифрования. При этом между переходами от одного раунда (этапа) к другому изменяются ключи: заменяется на , — на и т. д.).
Расшифрование Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи следуют в обратном порядке, то есть не от первого к N-му, а от N-го к первому.
Алгоритмическое описание Блок открытого текста делится на две равные части: . В каждом раунде вычисляются:
где: i — номер раунда; N — количество раундов в выбранном алгоритме шифрования; — некоторая функция; — ключ i-1-го раунда (раундовый ключ).
Результатом выполнения раундов является . В N-м раунде перестановка и не производится, чтобы была возможность использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования ключей ( вместо ):
Небольшим изменением можно добиться и полной идентичности процедур шифрования и расшифрования.
Достоинства: обратимость алгоритма независимо от используемой функции f; возможность выбора сколь угодно сложной функции f.
Математическое описание Рассмотрим пример. Пусть: X — блок данных, поступающий на вход (входной блок); A — некоторое инволютивное преобразование (или инволюция) — взаимно-однозначное преобразование, которое является обратным самому себе, то есть для каждого X справедливо выражение:
Y — блок данных, получаемый на выходе (результат).
При однократном применении преобразования A к входному блоку X получится выходной блок Y:
При применении преобразования A к результату предыдущего преобразования — Y получится:
Пусть входной блок X состоит из двух подблоков L и R равной длины:
Определим два преобразования: — шифрование данных X с ключом K:
— перестановка подблоков L и R:
Введём обозначения: однократное применение преобразования G:
двукратное применение преобразования G:
Докажем инволютивность двукратного преобразования G ().
Несложно заметить, что преобразование G меняет только левый подблок L, оставляя правый R неизменным:
Поэтому далее будем рассматривать только подблок L. После двукратного применения преобразования G к L получим:
Таким образом:
следовательно
и G — инволюция.
Докажем инволютивность двукратного преобразования T ().
Рассмотрим процесс шифрования. Пусть: X — входное значение; — преобразование с ключом ; — выходное значение, результат i-го раунда.
Тогда преобразование, выполняемое на i+1-м раунде, можно записать в виде: . Преобразование, выполняемое на 1-м раунде:
Следовательно, выходное значение после m раундов шифрования будет равно:
Можно заметить, что на последнем этапе не обязательно выполнять перестановку T.
Расшифрование ведётся применением всех преобразований в обратном порядке. В силу инволютивности каждого из преобразований обратный порядок даёт исходный результат:
Функции, используемые в сетях Фейстеля В своей работе «Криптография и компьютерная безопасность» Хорст Фейстель описывает два блока преобразований (функций ): блок подстановок (s-блок, ); блок перестановок (p-блок, ).
Можно показать, что любое двоичное преобразование над блоком данных фиксированной длины может быть реализовано в виде s-блока. В силу сложности строения N-разрядного s-блока при больших N на практике применяют более простые конструкции.
Термин «блок» в оригинальной статье используется вместо термина «функция» вследствие того, что речь идёт о блочном шифре и предполагалось, что s- и p-блоки будут цифровыми микросхемами (цифровыми блоками).
S-блок
Блок подстановок (s-блок, ) состоит из следующих частей: дешифратор — преобразователь n-разрядного двоичного сигнала в одноразрядный сигнал по основанию ; система коммутаторов — внутренние соединения (всего возможных соединений ); шифратор — преобразователь сигнала из одноразрядного -ричного в n-разрядный двоичный.
Анализ n-разрядного S-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений крайне велико (). На практике блок подстановок используется как часть более сложных систем.
В общем случае s-блок может иметь несовпадающее число входов/выходов, в этом случае в системе коммутации от каждого выхода дешифратора может идти не строго одно соединение, а 2 или более или не идти вовсе. То же самое справедливо и для входов шифратора.
В электронике можно непосредственно применять приведённую справа схему. В программировании же генерируют таблицы замены. Оба этих подхода являются эквивалентными, то есть файл, зашифрованный на компьютере, можно расшифровать на электронном устройстве и наоборот.
+ Таблица замены для приведённого 3-разрядного s-блока№ комбинации 0 1 2 3 4 5 6 7Вход000 001 010 011 100 101 110 111Выход011 000 001 100 110 111 010 101
P-блок Блок перестановок (p-блок, ) всего лишь изменяет положение цифр и является линейным устройством. Этот блок может иметь очень большое количество входов-выходов, однако в силу линейности систему нельзя считать криптоустойчивой.
Криптоанализ ключа для n-разрядного p-блока проводится путём подачи на вход n-1 различных сообщений, каждое из которых состоит из n-1 нуля («0») и 1 единицы («1») (или наоборот, из единиц и нуля).
Циклический сдвиг
Можно показать, что циклический сдвиг является частным случаем p-блока.
В простейшем случае (сдвиг на 1 бит), крайний бит отщепляется и перемещается на другой конец регистра или шины. В зависимости от того какой бит берётся, правый или левый, сдвиг называется вправо или влево. Сдвиги на большее число бит можно рассматривать, как многократное применение сдвига на 1.
+Циклический сдвиг на m бит для n-разрядного входа (m < n)Направление сдвигаПорядок следования битов до сдвигаПорядок следования битов после сдвигаВлевоВправо
Сложение по модулю n
Операция «сложение по модулю n» обозначается как (A + B) mod n и представляет собой остаток от деления суммы на n, где A и B — числа.
Можно показать, что сложение двух чисел по модулю n представляется в двоичной системе счисления в виде s-блока, у которого на вход подаётся число A, а в качестве системы коммутации s-блока используется циклический сдвиг влево на B разрядов.
В компьютерной технике и электронике операция сложения, как правило, реализована как сложение по модулю , где m — целое (обычно m равно разрядности машины). Для получения в двоичной системе A + B mod достаточно сложить числа, после чего отбросить разряды начиная с m-го и старше.
Умножение по модулю n Умножение по модулю n обозначается как (A * B) mod n и представляет собой остаток от деления произведения на n, где A и B — числа.
В персональных компьютерах на платформе x86 при перемножении двух m-разрядных чисел получается число разрядностью 2*m. Чтобы получить остаток от деления на , нужно отбросить m старших бит.
Пример реализации на языке Си Общий вид алгоритма шифрования, использующего сеть Фейстеля:
/* Функция, выполняющая преобразование подблока с учётом значения ключа (по ключу). Реализация зависит от выбранного алгоритма блочного шифрования. */ int f ( int subblock, /* преобразуемый подблок */ int key /* ключ */ ); /* возвращаемое значение - преобразованный блок */
/* Функция, выполняющая шифрование открытого текста */ void crypt ( int * left, /* левый входной подблок */ int * right, /* правый входной подблок */ int rounds, /* количество раундов */ int * key /* массив ключей (по ключу на раунд) */ ) { int i, temp; for ( i = 0; i < rounds; i++ )