Таблица 3:
| Б | Д | А | К | Р |
| X | V | N | R | S |
Осуществляя дальнейшие преобразования в соответствии с алгоритмом Френдберга, получаем шифртекст: "XVSNSXXSSSN".
Одной из разновидностей метода гаммирования является наиболее часто применяемый метод многократного наложения гамм. Необходимо отметить, что если уi=Гk(Г1(xi)), то Гk(Г1(xi))=Г1(Гk(xi)). (1*)
Тождество (1*) называют основным свойством гаммы.
Пример 4. Открытый текст: "ШИФРЫ"(25 09 21 17 28");
Г1 = "ГАММА" ("04 01 13 13 01");
Г2 = "ТЕКСТ" ("19 06 11 18 19"), согласно таблице 1.
Используемая операция: сложение по mod 2.
1. Y1i=xi Å h1i
11001 01001 10101 10001 11100
Å
00100 00001 01101 01101 00001
=
11101 01000 11000 11100 11101.
2. У2i=y1i Å h2i
11101 01000 11000 11100 11101
Å
10011 00110 01011 10010 10011
=
01110 01110 10011 01110 01110.
Проведем операцию шифрования, поменяв порядок применения гамм.
1. У1i =xi Å h2i
11001 01001 10101 10001 11100
Å
10011 00110 01011 10010 10011
=
01010 01111 11110 00011 01111.
2. У2i'=y1i' Å h1i
01010 01111 11110 00011 01111
Å
00100 00001 01101 01101 00001
=
01110 01110 10011 01110 01110.
Таким образом, y2i=y2i', что является подтверждением основного свойства гаммы.
При составлении комбинированных шифров необходимо проявлять осторожность, так как неправильный выбор составлявших шифров может привести к исходному открытому тексту. Простейшим примером служит наложение одной гаммы дважды.
Пример 5. Открытый текст: "ШИФРЫ"("25 09 21 17 28");
Г1 = Г2= "ГАММА" ("04 01 13 13 01"), согласно таблице 1.
Используемая операция: сложение по 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. Для хорошего блочного шифра простых соотношений нет.
2.3. Групповая структура
При изучении алгоритма возникает вопрос, не образует ли он группу. Элементами группы служат блоки шифртекста для каждого возможного ключа, а групповой операцией служит композиция. Изучение групповой структуры алгоритма представляет собой попытку понять, насколько возрастает дополнительное скрытие текста при многократном шифровании.
Важен, однако, вопрос не о том, действительно ли алгоритм - группа, а о том, насколько он близок к таковому. Если не хватает только одного элемента, алгоритм не образует группу, но двойное шифрование было бы, с точки зрения статистики, просто потерей времени. Работа над DES показала, что этот алгоритм весьма далек от группы. Существует также ряд интересных вопросов о полугруппе, получаемой при шифровании DES. Содержит ли она тождество, то есть, не образует ли она группу? Иными словами, не генерирует ли, в конце концов, некоторая комбинация операций зашифрования (не расшифрования) тождественную функцию? Если так, какова длина самой короткой из таких комбинаций?
Цель исследования состоит в оценке пространства ключей для теоретического лобового вскрытия, а результат представляет собой наибольшую нижнюю границу энтропии пространства ключей.
2.4. Слабые ключи
В хорошем блочном шифре все ключи одинаково сильны. Как правило, нет проблем и с алгоритмами, включающими небольшое число слабых ключей, например, DES. Вероятность случайного выбора одного из них очень мала, и такой ключ легко проверить и, при необходимости, отбросить. Однако если блочный шифр используется как однонаправленная хэш-функция, эти слабые ключи иногда могут быть задействованы.
2.5. Устойчивость алгоритма к дифференциальному и
линейному криптоанализу
Исследования дифференциального и линейного криптоанализа значительно прояснили теорию проектирования надежных блочных шифров. Авторы алгоритма IDEA ввели понятие дифференциалов, обобщение основной идеи характеристик. Они утверждали, что можно создавать блочные шифры, устойчивые к атакам такого типа. В результате подобного проектирования появился алгоритм IDEA. Позднее это понятие было формализовано в работах Кайса Ниберг (Kaisa Nyberg) и Ларе Кнудсен, которые описали метод создания блочных шифров, доказуемо устойчивых к дифференциальному криптоанализу. Эта теория была расширена на дифференциалы высших порядков и частные дифференциалы. Как представляется, дифференциалы высших порядков применимы только к шифрам с малым числом раундов, но частные дифференциалы прекрасно объединяются с дифференциалами.