7. Теория проектирования блочных шифров

К. Шеннон выдвинул понятия рассеивания и перемешивания. Спустя пятьдесят лет после формулирования этих принципов, они остаются краеугольным камнем проектирования хороших блочных шифров.

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

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

Для обеспечения надежности достаточно только перемешивания. Алгоритм, состоящий из единственной, зависимой от ключа таблицы подстановок 64 бит открытого текста в 64 бит шифртекста был бы достаточно надежным. Недостаток в том, что для хранения такой таблицы потребовалось бы слишком много памяти: 1020 байт. Смысл создания блочного шифра и состоит в создании чего-то подобного такой таблице, но предъявляющего к памяти более умеренные требования.

Тонкость, состоит в том, что в одном шифре следует периодически перемежать в различных комбинациях перемешивание (с гораздо меньшими таблицами) и рассеивание. Такой шифр называют составным шифром (product cipher). Иногда блочный шифр, который использует последовательные перестановки и подстановки, называют сетью перестановок-подстановок, или SP-сетью.

Рассмотрим функцию f алгоритма DES. Перестановка с расширением и Р-блок реализуют рассеивание, а S-блоки - перемешивание. Перестановка с расширением и Р-блок линейны, S-блоки - нелинейны. Каждая операция сама по себе очень проста, но вместе они работают превосходно.

Кроме того, на примере DES можно продемонстрировать еще несколько принципов проектирования блочных шифров. Первый принцип реализует идею итеративного блочного шифра. При этом предполагается, что простая функция раунда последовательно используется несколько раз. Двухраундовый алгоритм DES слишком ненадежен, чтобы все биты результата зависели от всех битов ключа и всех битов исходных данных. Для этого необходимо 5 раундов. Весьма надежен 16-раундовый алгоритм DES, а 32-раундовый DES еще более стоек.

8. Сеть Фе́йстеля (конструкция Фейстеля) — один из методов построения блочных шифров. Сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру, называющуюся ячейкой Фейстеля. При переходе от одной ячейки к другой меняется ключ, причём выбор ключа зависит от конкретного алгоритма. Операции шифрования и расшифрования на каждом этапе очень просты, и при определённой доработке совпадают, требуя только обратного порядка используемых ключей. Шифрование при помощи данной конструкции легко реализуется как на программном уровне, так и на аппаратном, что обеспечивает широкие возможности применения. Большинство современных блочных шифров используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть.

Конструкция блочного шифра на основе сетей Фейстеля

Рассмотрим случай, когда мы хотим зашифровать некоторую информацию, представленную в двоичном виде в компьютерной памяти (например, файл) или электронике, как последовательность нулей и единиц.

Вся информация разбивается на блоки фиксированной длины. В случае, если длина входного блока меньше, чем размер, который шифруется заданным алгоритмом, то блок удлиняется каким-либо способом. Как правило длина блока является степенью двойки, например: 64 бита, 128 бит. Далее будем рассматривать операции происходящие только с одним блоком, так как с другими в процессе шифрования выполняются те же самые операции.

Выбранный блок делится на два равных подблока — «левый» (L0) и «правый» (R0).

«Левый подблок» L0 видоизменяется функцией f(L0,K0) в зависимости от раундового ключа K0, после чего он складывается по модулю 2 с «правым подблоком» R0.

Результат сложения присваивается новому левому подблоку L1, который будет половиной входных данных для следующего раунда, а «левый подблок» L0 присваивается без изменений новому правому подблоку R1 (см. схему), который будет другой половиной.

После чего операция повторяется N-1 раз, при этом при переходе от одного этапа к другому меняются раундовые ключи (K0 на K1 и т. д.) по какому-либо математическому правилу, где N — количество раундов в заданном алгоритме.

Расшифрование

Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи идут в обратном порядке, то есть не от первого к N-ному, а от N-го к первому.

9. Алгоритм DES (Data Encryption Standard) был разработан в 1975 году компанией IBM, он базируется на алгоритме DEA.

Исходные идеи алгоритма шифрования данных DEA (data encryption algorithm) были предложены компанией IBM еще в 1960-х годах и базировались на идеях, описанных Клодом Шенноном в 1940-х годах. Первоначально эта методика шифрования называлась lucifer (разработчик Хорст Фейштель, название dea (см. http://snoopy.falkor.gen.nz/~rae/des.html) она получила лишь в 1976 году. Lucifer был первым блочным алгоритмом шифрования, он использовал блоки размером 128 бит и 128-битовый ключ. По существу этот алгоритм являлся прототипом DEA. В 1986 в Японии (NIT) разработан алгоритм FEAL(Fast data Encipherment ALgorithm), предназначенный для использования в факсах, модемах и телефонах (длина ключа до 128 бит). Существует и ряд других разработок.

DEA (ANSI x3.92-1981; www.cryptosoft.com/html/fips46-2.htm) оперирует с блоками данных размером 64 бита и использует ключ длиной 56 бит. Такая длина ключа соответствует 1017 комбинаций, что обеспечивало до недавнего времени достаточный уровень безопасности. В дальнейшем можно ожидать расширения ключа до 64 бит (например, LOKI) или вообще замены DES другим стандартом.

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

Вводится функция f, которая работает с 32-разрядными словами исходного текста (А) и использует в качестве параметра 48-разрядный ключ (J). Схеме работы функции f показана на рис. 6.4.1.1. Сначала 32 входные разряда расширяются до 48, при этом некоторые разряды повторяются. Схема этого расширения показана ниже (номера соответствуют номерам бит исходного 32-разрядного кода).