Реферат: Композиции шифров
Используемая операция: сложение по mod 2:
11001 01001 10101 10001 11100
Å
00100 00001 01101 01101 00001
Å
00100 00001 01101 01101 00001
=
11001 01001 10101 10001 11100.
Таким образом, результат шифрования представляет собой открытый текст.
2. Теория проектирования блочных шифров
К. Шеннон выдвинул понятия рассеивания и перемешивания. Спустя пятьдесят лет после формулирования этих принципов, они остаются краеугольным камнем проектирования хороших блочных шифров.
Перемешивание маскирует взаимосвязи между открытым текстом, шифртекстом и ключом. Даже незначительная зависимость между этими тремя составляющими может быть использована в дифференциальном и линейном криптоанализе. Хорошее перемешивание настолько усложняет статистику взаимосвязей, что пасуют даже мощные криптоаналитические средства.
Рассеивание распространяет влияние отдельных битов открытого текста на возможно больший объем шифртекста. Это тоже маскирует статистические взаимосвязи и усложняет криптоанализ.
Для обеспечения надежности достаточно только перемешивания. Алгоритм, состоящий из единственной, зависимой от ключа таблицы подстановок 64 бит открытого текста в 64 бит шифртекста был бы достаточно надежным. Недостаток в том, что для хранения такой таблицы потребовалось бы слишком много памяти: 1020 байт. Смысл создания блочного шифра и состоит в создании чего-то подобного такой таблице, но предъявляющего к памяти более умеренные требования.
Тонкость, состоит в том, что в одном шифре следует периодически перемежать в различных комбинациях перемешивание (с гораздо меньшими таблицами) и рассеивание. Такой шифр называют составным шифром ( product cipher ). Иногда блочный шифр, который использует последовательные перестановки и подстановки, называют сетью перестановок-подстановок, или SP-сетью.
Рассмотрим функцию f алгоритма DES. Перестановка с расширением и Р-блок реализуют рассеивание, а S-блоки - перемешивание. Перестановка с расширением и Р-блок линейны, S-блоки - нелинейны. Каждая операция сама по себе очень проста, но вместе они работают превосходно.
Кроме того, на примере DES можно продемонстрировать еще несколько принципов проектирования блочных шифров. Первый принцип реализует идею итеративного блочного шифра. При этом предполагается, что простая функция раунда последовательно используется несколько раз. Двухраундовый алгоритм DES слишком ненадежен, чтобы все биты результата зависели от всех битов ключа и всех битов исходных данных. Для этого необходимо 5 раундов. Весьма надежен 16-раундовый алгоритм DES, а 32-раундовый DES еще более стоек.
2.1. Сети Файстеля
Большинство блочных алгоритмов относятся к так называемым сетям Файстеля. Идея этих сетей датируется началом семидесятых годов. Возьмем блок длиной п и разделим его на две половины длиной n /2: L и R . Разумеется, число п должно быть четным. Можно определить итеративный блочный шифр, в котором результат j -го раунда определяется результатом предыдущего раунда:
Li = Ri -1
Ri = Li -1 Å f (Ri -1 , Ki )
Ki - подключ j -го раунда, а f - произвольная функция раунда.
Применение этой концепции можно встретить в алгоритмах DES, Lucifer, FEAL, Khufu, Khafre, LOKI, ГОСТ, CAST, Blowfish и других. Этим гарантируется обратимость функции. Так как для объединения левой половины с результатом функции раунда используется операция XOR, всегда истинно следующее выражение:
Li -1 Å f (Ri -1 , Ki ) Å Li -1 Å f (Ri -1 , Ki ) = Li -1
Шифр, использующий такую конструкцию, гарантированно обратим, если можно восстановить исходные данные f на каждом раунде. Сама функция f не важна, она не обязательно обратима. Мы можем спроектировать сколь угодно сложную функцию f , но нам не понадобится реализовывать два разных алгоритма - один для зашифрования, а другой для расшифрования. Об этом автоматически позаботится структура сети Файстеля.
2.2. Простые соотношения
Алгоритм DES характеризуется следующим свойством: если ЕК (Р ) = С, то Е K ' (Р' ) = С', где Р', С' и K ' - побитовые дополнения Р, С и K . Это свойство вдвое уменьшает сложность лобового вскрытия. Свойства комплементарности в 256 раз упрощают лобовое вскрытие алгоритма LOKI.
Простое соотношение можно определить так:
Если Е K (Р ) = С, то Ef ( K ) (g ( P , K )) = h (C , K )
где f , g и h - простые функции. Под «простыми функциями» подразумевают функции, вычисление которых несложно, намного проще итерации блочного шифра. В алгоритме DES функция f представляет собой побитовое дополнение K , g - побитовое дополнение Р, a h - побитовое дополнение C . Это - следствие сложения ключа и текста операцией XOR. Для хорошего блочного шифра простых соотношений нет.