Сеть Фейcтеля

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

F

Ri

Li

Ki

I-ый раунд сети Фейстеля

Функция F называется образующей. Каждый раунд состоит из вычисления функции F для одной ветви и побитового выполнения операции XOR результата F с другой ветвью. После этого ветви меняются местами. Считается, что оптимальное число раундов - от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостойкость алгоритма. Именно эта особенность и повлияла на столь активное распространение сети Фейстеля, так как для большей криптостойкости достаточно просто увеличить количество раундов, не изменяя сам алгоритм. В последнее время количество раундов не фиксируется, а лишь указываются допустимые пределы.

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

До последнего времени в основном использовались различные разновидности сети Фейстеля для 128-битового блока с четырьмя ветвями. Увеличение количества ветвей, а не их размерности было связано с преобладанием 32-разрядных процессоров. Тенденция к все большему использованию 64-разрядных платформ приводит к увеличению размерности блока и ветвей сети.

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

DES — национальный стандарт шифрования коммерческой информации в США, разработанный фирмой IBM в 1974 г, и принятый в качестве стандарта в 1976 году. DES является классической сетью Фейстеля с двумя ветвями (Хорст Фейстель один из авторов DES). Представляет собой симметричный блочный алгоритм с секретным ключом длиной 56 бит. Алгоритм использует входные 64-битовые блоки и основан на 16-кратной перестановке данных; В каждом цикле шифрования 64-битовый блок перемешивается и разбивается на 2 32-битовые части L и R, подвергается преобразованию Фейстеля и перестановке. В конце алгоритма левая и правая половина меняются местами и так 16 раз. При этом исп-ся 16 48-битовых подключей. Каждый подключ образуется путем выбора 48 бит из 56-битового ключа шифрования, причем для каждого раунда этот выбор выполняется по-разному. В конце шифрования полученный 64-разрядный блок снова подвергается перестановке, обратной начальной (никакой криптостойкости это не добавляет). Все подстановки и перестановки, используемые в DES фиксированы.

Отечественным аналогом DES является ГОСТ 28147-89. Этот шифр был разработан в 70-х годах в КГБ СССР и имел гриф «совершенно секретно». С течением времени гриф снижался, и в 1989 году этот алгоритм стал применяться «для служебного пользования»; этот гриф, как известно, не является секретным, что дало возможность провести шифр через процедуру стандартизации. В начале 90-х годов гриф был окончательно снят, а сам алгоритм признан уже не советским, а российским стандартом.

Преимущества перед DES наш алгоритм имел существенные. Во-первых, в ГОСТ изначально использовались ключи длиной 128 бит, что позволяет ему до сих пор оставаться достаточно надежным для коммерческого использования. Во-вторых, этот алгоритм создавался с расчетом на то, чтобы в равной степени эффективно реализовываться как аппаратно, так и программно. Это позволило при большей надежности иметь и серьезное преимущество в скорости работы перед американским стандартом. Все эти плюсы стали залогом долголетия отечественного алгоритма и позволили ему пережить заморский аналог.

При использовании в шифре ГОСТ 256-битового ключа, объем ключевого пространства составляет 2²⁵⁶. Блок-схема алгоритма отличается от DES лишь отсутствием начальной перестановки и числом циклов шифрования (32). Ключ – это массив, состоящий из 32-значных двоичных векторов X1,X2….X8. Ключ i-того цикла Ki равен Xs, где ряду значений i от 1 до 32 соответствует следующий ряд значений s:

1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,8,7,6,5,4,3,2,1.

В ГОСТ 28147-89 помимо шифрования определен процесс выработки имитовставки для защиты данных от несанкционированного изменения. Имитовставка - это блок из p бит (имитовставка Иp), который вырабатывается либо перед шифрованием всего сообщения, либо парал­лельно с шифрованием по блокам. Первые блоки откры­тых данных, которые участвуют в выработке имитовставки, могут содержать служебную информацию (например, адресную часть, время, синхропосылку) и не зашифровы­ваться. Значение параметра p (число двоичных разрядов в имитовставке) определяется криптографическими тре­бованиями с учетом того, что вероятность навязывания ложных помех равна .

Для получения имитовставки открытые данные пред­ставляются в виде 64-разрядных блоков Т(i) (i = 1, 2, …, m, где m определяется объемом шифруемых данных). Первый блок открытых данных Т(1) подвергается преоб­разованию, соответствующему первым 16 циклам алго­ритма шифрования в режиме простой замены. Причем в качестве ключа для выработки имитовставки использу­ется ключ, по которому шифруются данные.

Полученное после 16 циклов работы 64-разрядное число суммируется по модулю 2 со вторым блоком откры­тых данных Т(2). Результат суммирования снова подвер­гается преобразованию, соответствующему первым 16 циклам алгоритма шифрования в режиме простой заме­ны.

Полученное 64-разрядное число суммируется по мо­дулю 2 с третьим блоком открытых данных Т(3) и т. д. Последний блок Т (m), при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на шаге m-1, после чего зашифровывается в режиме простой замены по первым 16 циклам работы алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной p бит.

Имитовставка Ир передается по каналу связи или в память ЭВМ после шифрованных данных. Поступив­шие шифрованные данные дешифруются и из по­лученных блоков открытых данных Т(i) вырабатывается собственная имитовставка Ир, которая затем сравнивается с имитовставкой Ир, полученной из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок все дешиф­рованные данные считают ложными.

Дата добавления: 2015-07-24