[МУЗЫКА] Первый подход к построению блочных шифров,

о котором мы с вами поговорим, это подход на основе сети Фейстеля.

Сеть Фейстеля названа в честь Хорста Фейстеля, американского учёного,

который принял участие в проекте Lucifer компании IBM.

Он автор схемы построения шифров, названной сетью Фейстеля в его честь.

Кроме того, он внёс значительный вклад в разработку первого американского стандарта

шифрования DES, Digital Encryption Standard, цифровой стандарт шифрования.

Сеть Фейстеля — это один из методов построения стойких блочных шифров,

и этот метод основан на том, что при образовании шифруемого блока некоторые

функции повторяются многократно, то есть реализуются так называемые раунды,

каждый из которых зависит от ключа, раундового ключа каждой итерации.

То есть из вот этого не очень длинного ключа, который пользователь вводит в

алгоритм шифрования, развёртывается необходимое количество раундовых ключей,

каждоый из которых может быть даже длиннее входного ключа,

это не исключается данной моделью.

То есть из вот этого не очень длинного ключа с

помощью функции развёртки развёртывается ключ сколь угодно требуемой длины.

Принципиальная модель схемы Фейстеля сейчас показана у вас на слайде,

и она заключается в следующем.

Блок открытого текста, поступающий на вход функции зашифрования,

делится на два подблока — левый и правый.

Далее левый подблок поступает на функцию усложнения,

так называемую функцию Фейстеля, которая как раз-таки зависит от раундового ключа.

После чего результат применения этой функции складывается по модулю два с

правым подблоком.

После чего результат этого сложения становится левым подблоком следующего

раунда, а левый подблок данного раунда в неизменном виде занимает место правого

подблока следующего раунда.

Происходит нужное количество итераций,

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

полученные в результате применения последнего раунда,

в результате реализации последнего раунда, предъявляются как зашифрованный текст.

Рассмотрим некоторое количество шифров,

которые в различное время являлись действующими государственными стандартами

Соединённых Штатов Америки и Российской Федерации, построенные на сети Фейстеля.

Первый пример — это американский шифр DES, тот самый, к созданию которого

был причастен Хорст Фейстель, который принял участие в проекте Lucifer.

Данный алгоритм шифрования принят в качестве стандарта в

Соединённых Штатах в 1977 году.

Это реализация сети Фейстеля с размером входного блока 64 бита,

с размером ключа 56 бит, то есть первого исходного ключа,

и с реализацией 16 раундов.

Здесь исходный блок делится на два подблока.

Его правая часть попадает на функцию фейстеля,

после чего складывается по модулю два с левым подблоком,

после чего подблоки меняются местами.

Реализуется 16 раундов, и на этом последний раунд завершается.

Помимо собственно операции обработки в раундах в данном шифре реализуется

начальная и конечная перестановки, из которых первая предваряет первый раунд,

а вторая применяется после завершения шестнадцатого раунда, после чего результат

конечной перестановки предъявляется в качестве зашифрованного текста.

Функция Фейстеля в данном шифре выглядит следующим образом.

Поступивший на вход один из подблоков длинной 32 бита изначально расширяется с

помощью так называемой функции расширения до двоичной строки длиной 48 бит.

После чего эта строка складывается по модулю два с раундовым ключом,

а затем делится на восемь подстрок, каждая длиной в восемь бит.

Каждая из таких строк попадает на блоки замены, S-блоки так называемые.

В результате обработки каждым их таких блоков на выходе получается

строка снова четыре бита, после чего эти строки сцепляются

в одну итоговую строку снова длинной 32 бита.

Далее над этой строкой осуществляется перестановка битов или так

называемый P-блок применяется.

И результат этого применения выходит из функции Фейстеля как результат обработки.

В данной схеме впервые применены и показаны такие объекты,

как S-блок и P-блок.

Собственно, S-блок — это некий логический блок шифров подобного типа,

реализующий замену.

От английского слова substitution.

В прямом переводе — подстановка, но в русскоязычной литературе, как правило,

применяется термин замена.

Это блоки, которые осуществляют замену.

Например, просто по таблице заменяют некоторое количество двоичных векторов на

некоторое количество других двоичных векторов.

Я имею ввиду,

что размерность входа и выхода этих блоков может быть неодинаковая.

В данном случае, если входная длина восемь бит, а выходная — четыре бита,

то реализована, по сути, в каждом из S-блоков кодовая таблица,

которая заменяет два в восьмой степени различных входных строк

на в некотором не очевидном и не явным образом восстанавливаемом

порядке на два в четвёртой степени различных выходных строк.

Вообще говоря, S-блоки не относятся в строгом понимании к ключевым элементам

шифра, то есть не должны являться секретными, хотя в некоторых случаях они

объявляются секретными или оставляются на выбор конкретного пользователя шифра.

Другим примером шифра, построенного на основе сети Фейстеля,

является советский алгоритм блочного шифрования, вошедший в ГОСТ 28147-89,

государственный стандарт ещё Советского Союза,

в настоящее время известный как блочный шифр «Магма».

Он описан в действующем стандарте Российской Федерации,

и в этом стандарте прямо указано, что данный шифр можно именовать шифр «Магма».

Данный стандарт с 1990 года принят как действующий,

до 94-го года имел гриф «Для служебного пользования».

И у данного шифра размер блока уже 64 бита, размер ключа 256 бит,

а число раундов 32, то есть увеличены здесь размер

ключа и число раундов по сравнению с американским стандартом.

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

после чего правый подблок длиной 32 бита поступает в качестве аргумента на

операцию сложения по модулю два в тридцать второй степени с раундовым ключом.

После чего результат этой операции подаётся на вход S-блока,

об устройстве которого я расскажу чуть далее.

Результат обработки S-блоком подвергается циклическому сдвигу на 11 бит,

после чего складывается по модулю два, то есть обычная операция исключающая,

или с левым подблоком.

Результат этой операции двоичного сложения занимает

место правого подблока в следующем раунде, а правый подблок текущего раунда

в неизменном виде занимает место левого подблока следующего раунда.

На этом раунд завершается.

Всего реализуется 32 раунда, и таким образом работа одного такта зашифрования,

то есть зашифрования одного блока совершена.

Функция усложнения, объединяющая в себе сложение по модулю два в тридцать второй

степени, S-блок и циклический сдвиг на 11 символов, выглядит следующим образом.

32-битный входной блок складывается по модулю два в тридцать второй

степени с ключом раунда, после чего получившаяся строка в 32 бита делится

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

После чего каждая из этих подстрок попадает на свой S-блок.

В данном случае S-блок не является сжимающим,

его размерность входа равна размерности выхода.

И в итоге получается снова восемь подстрок длиной по четыре бита,

которые снова сцепляются в единую строку,

которая затем подвергается циклическому сдвигу на 11 бит влево,

и получившаяся в итоге двоичная строка является 32-битным выходным блоком.

Далее этот выходной блок поступает на операцию двоичного сложения,

и таким образом раунд завершается.

[МУЗЫКА]

Шифры на основе сети Фейстеля

Методы и средства защиты информации

与讲师见面