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

Многие современные блоковые шифры реализуются на основе так называемой структуры Файстеля. Для этого предварительно из секретного ключа = ₀ при помощи заданного детерминированного преобразования, входящего в описание алгоритма шифрования, формируется последовательность текущих ключей _i , i = 1, 2,..., d, где d – число итераций.

Сама структура Файстеля предполагает следующий способ преобразования блоков. Сначала каждый блок сообщения, образованный последовательностью двоичных символов. длиною n, разбивается пополам на подблоки длиною n ₀= n/ 2 (рис. 10). Для этого n должно быть четным

Шифрование каждого блока выполняется отдельно с использованием рекуррентного соотношения

Рис. 10. Подготовка блока для шифрования на основе структуры Файстеля

, i = 1, 2,..., d.   Здесь f (,) – открытая нелинейная детерминированная функция, i – текущие ключевые элементы, сформированные детерминированным образом из основного секретного ключа данной криптосистемы. Криптограмма образуется на заключительной итерации (i = d)и имеет вид блока

= ( _d , _{d +1})

 

длиною n. Этот блок также составлен из последовательно записанных друг за другом подблоков, но теперь уже _d и _{d +1} .Отметим, что примененное объединение подблоков в единый блок называется конкатенация.

Преимущества структуры Файстеля состоят в том, что, во-первых, для нее выполняется принцип перемешивания подблоков и, во-вторых, хотя функция f (,) может и не иметь обратную f ^–1(,), весьма просто реализуется алгоритм дешифрования при ключе, известном законному пользователю.

Имеется много различных блоковых шифров, основанных на структуре Файстеля, которые отличаются выбором функции f и способом формирования текущих ключевых элементов _i, i = 1, 2,…, d, из секретного ключа .

 

64 Какова общая схема алгоритма DES? Что такое поразрядное суммирование? Как получить расширенный подблок? Как формируются двоичные векторы V 1 и V 2? Как выполняется операция подстановки?

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

Рис. 1. Цикл шифрования DES - схема преобразования данных.

Рис. 2. Цикл шифрования DES - схема алгоритма.

Зашифрование 64-битового блока данных T (входной параметр алгоритма, рис.2, шаг 0) начинается с начальной перестановки битов в нем (IP, шаг 1). Затем шифруемый блок разделяется на две 32-битовые части (шаг 2), с которыми выполняются 16 раундов преобразования в соответствии с архитектурными принципами сети Файстеля. Через Hi_n (X) и Lo_n (X) обозначены функции, возвращающие в качестве результата соответственно n старших или младших битов своего аргумента. На каждом раунде старшая половина блока модифицируется путем побитового прибавления к ней по модулю 2 (операция " ") результата вычисления функции шифрования (f), зависящей от младшей половины блока (L_{i –1}) и 48-битового ключевого элемента (k_i). Между раундами старшая и младшая половины блока меняются местами. Таким образом, на каждом раунде кроме последнего младшая половина блока становится старшей, а модифицированная с помощью функции шифрования старшая – младшей половиной блока (шаг 3). На последнем раунде происходит то же самое за исключением обмена значениями половин блока. Затем полублоки объединяются в полный блок (шаг 4), в котором выполняется конечная битовая перестановка (IP ^–1, шаг 5), обратная начальной. Результат последней операции и является выходным значением цикла шифрования – зашифрованным блоком T ' (шаг 6). Шестнадцать 48-битовых ключевых элементов k_i, 1 i 16, используемых в цикле шифрования, являются параметрами алгоритма и вырабатываются из 56-битового ключа в ходе рассмотренной ниже процедуры генерации ключевой последовательности. Процедура расшифрования блока данных идентична процедуре зашифрования с тем отличием, что ключевые элементы в ней используются в порядке, обратном порядку их использования при зашифровании. Таким образом, если при зашифровании ключевые элементы используются в "естественном" порядке возрастания номеров

k ₁, k ₂, k ₃, k ₄, k ₅, k ₆, k ₇, k ₈, k ₉, k ₁₀, k ₁₁, k ₁₂, k ₁₃, k ₁₄, k ₁₅, k ₁₆,

то при расшифровании они должны использоваться в обратном порядке:

k ₁₆, k ₁₅, k ₁₄, k ₁₃, k ₁₂, k ₁₁, k ₁₀, k ₉, k ₈, k ₇, k ₆, k ₅, k ₄, k ₃, k ₂, k ₁.

Поразрядное сложение - заключается в сложении одноименных разрядов чисел по модулю 2 в соответствии с правилом

0 + 0 = 0, 1 + 0 =1, 0+ 1=1, 1 + 1= 0.

Применяется для сравнения двух чисел на равенство