МПС РФ

Московский Государственный Университет

Путей Сообщения (МИИТ)

Кафедра «Электроника и защита информации»

Курсовая работа по дисциплине: «Криптографические методы защиты информации»

На тему: «Композиции шифров»

Выполнил: Ефалов П.А.

Студент гр. АКБ-311

ИСУТЭ

Проверил: Титов Е.В.

Москва-2003

СОДЕРЖАНИЕ:

Введение…………………………………………………..…………………….4

1. Комбинированные методы шифрования

Комбинирование простых способов шифрования..………………………5

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

2.1. Сети Файстеля………………………………………………………..8

2.2. Простые соотношения……………………………………………….9

2.3. Групповая структура………………………………………………...9

2.4. Слабые ключи………………………………………………………10

2.5. Устойчивость алгоритма к дифференциальному и линейному криптоанализу…………………………………………10

2.6. Проектирование S-блоков…………………………………………11

2.7. Проектирование блочного шифра………………………………...13

3. Блочные шифры……………………………………………………………14

3.1. Алгоритм Lucifer……………………………………………………14

3.2. Алгоритм Madryga………………………………………………….15

3.2.1. Описание алгоритма Madryga………………………………16

3.2.1. Криптоанализ алгоритма Madryga………………………….17

3.3. Алгоритм REDOC…………………………………………………..18

3.3.1. Алгоритм REDOC III………………………………………..18

3.4. Алгоритм LOKI……………………………………………………..19

3.4.1. Алгоритм LOKI91…………………………………………...19

3.4.2. Описание алгоритма LOKI91……………………………… 21

3.4.3. Криптоанализ алгоритма LOKI91………………………….21

3.5. Алгоритм Knufu и Knafre…………………………………………..22

3.5.1. Алгоритм Knufu…………………………………………..…23

3.5.2. Алгоритм Knafre………………………………………….....23

3.6. Алгоритм ММВ…………………………………………………….24

3.6.1. Стойкость алгоритма ММВ………………………………...25

3.7. Алгоритм Blowfish…………………………………………………26

3.7.1. Описание алгоритма Blowfish……………………………...26

3.7.2. Стойкость алгоритма Blowfish……………………………..29

3.8. Алгоритм RC5………………………………………………………29

4. Объединение блочных шифров…………………………………………....32

4.1. Двойное шифрование………………………………………………32

4.2. Тройное шифрование……………………………………………....33

4.2.1. Тройное шифрование с двумя ключами…………………..33

4.2.2. Тройное шифрование с тремя ключами…………………...35

4.2.3. Тройное шифрование с минимальным ключом…………..35

4.2.4. Режимы тройного шифрования……………………………35

4.2.5. Варианты тройного шифрования………………………….37

4.3. Удвоение длины блока…………………………………………… 38

4.4. Другие схемы многократного шифрования……………………...39

4.4.1. Двойной режим OFB/счетчика…………………………….39

4.4.2. Режим ECB+OFB…………………………………………...39

4.4.3. Схема xDESi………………………………………………...40

4.4.4. Пятикратное шифрование………………………………….41

4.5. Уменьшение длины ключа в CDMF……………………………...42

4.6. Отбеливание………………………………………………………..42

4.7. Каскадное применение блочных алгоритмов……………………43

4.8. Объединение нескольких блочных алгоритмов…………………44

Заключение…...……………………………………………………………….45
Список литературы…………...………………………………………………46

ВВЕДЕНИЕ

Шифрсистемы классифицируются по различным признакам: по видам защищаемой информации (текст, речь, видеоинформация), по криптографической стойкости, по принципам обеспечения защиты информации (симметричные, ассиметричные, гибридные), по конструктивным принципам (блочные и поточные) и др. При построении отображений шифра используются с математической точки зрения два вида отображений: перестановки элементов открытого текста и замены элементов открытого текста на элементы некоторого множества. В связи с этим множество шифров делится на 3 вида: шифры перестановки, шифры замены и композиционные шифры, использующие сочетание перестановок и замен.
Рассмотрим последний класс шифров, то есть шифры композиции.

На практике обычно используют два общих принципа шифрования: рассеивание и перемешивание. Рассеивание заключается в распространении влияния одного символа открытого текста на много символов шифртекста: это позволяет скрыть статистические свойства открытого текста. Развитием этого принципа является распространение влияния одного символа ключа на много символов шифрограммы, что позволяет исключить восстановление ключа по частям. Перемешивание состоит в использовании таких шифрующих преобразований, которые исключают восстановление взаимосвязи статистических свойств открытого и шифрованного текста. Распространенный способ достижения хорошего рассеивания состоит в использовании составного шифра, который может быть реализован в виде некоторой последовательности простых шифров, каждый из которых вносит небольшой вклад в значительное суммарное рассеивание и перемешивание. В качестве простых шифров чаще всего используют простые подстановки и перестановки. Известны также методы аналитического преобразования, гаммирования, а также метод комбинированного шифрования.

Примерно до конца 19 века все используемые шифры практически представляли собой различные комбинации шифров замены и перестановки, причем часто весьма изощренных. Например, использовались шифры с несколькими таблицами простой замены, выбор которых осуществлялся в зависимости от шифрования предыдущего знака, в шифрах замены перестановки строились с использованием специальных правил и т.д. Особенно надежными шифрами отличался российский «Черный кабинет» - организация занимавшаяся разработкой собственных шифров и дешифрованием шифров зарубежных. При отсутствии современных методов, а главное вычислительной техники, данные шифры могли считаться вполне надежными. Некоторые из них просуществовали вплоть до второй мировой войны, например, широко известный шифр «Два квадрата» применялся немцами вплоть до 1945 года (метод дешифрования данного шифра был разработан советскими криптографами и активно использовался во время войны).

1. Комбинированные методы шифрования

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

Рассмотрим несколько примеров:

Пример 1. Возьмем в качестве открытого текста сообщение: «Я пишу курсовую».

Защитим этот текст методом простой перестановки, используя в качестве ключа слово "зачет" и обозначая пробел буквой "ь". Выписываем буквы открытого текста под буквами ключа. Затем буквы ключа расставляем в алфавитном порядке. Выписываем буквы по столбцам и получаем шифртекст: ььоиууяусшрюпкв.

Полученное сообщение зашифруем с помощью метода подстановки:
Пусть каждому символу русского алфавита соответствует число от 0 до 32. То есть букве А будет соответствовать 0, букве Б - 1 и т.д. Возьмем также некое число, например, 2, которое будет ключом шифра. Прибавляя к числу, соответствующему определенному символу 2, мы получим новый символ, например, если А соответствует 0, то при прибавлении 2 получаем В и так далее. Пользуясь этим, получаем новый шифртекст: ююркххбхуьтасмд.

Итак, имея открытый текст: «Я пишу курсовую», после преобразований получаем шифртекст: ююркххбхуьтасмд, используя методы перестановки и замены. Раскрыть текст расшифровщик сможет, зная, что ключами являются число 2 и слово "зачет" и соответственно последовательность их применения.

Пример 2. В качестве примера также рассмотрим шифр, предложенный Д.
Френдбергом, который комбинирует многоалфавитную подстановку с генератором псевдослучайных чисел. Особенность данного алгоритма состоит в том, что при большом объеме шифртекста частотные характеристики символов шифртекста близки к равномерному распределению независимо от содержания открытого текста.
1. Установление начального состояния генератора псевдослучайных чисел.
2. Установление начального списка подстановки.
3. Все символы открытого текста зашифрованы?
4. Если да - конец работы, если нет - продолжить.
5. Осуществление замены.
6. Генерация случайного числа.
7. Перестановка местами знаков в списке замены.
8. Переход на шаг 4.

Пример 3. Открытый текст: "АБРАКАДАБРА".
Используем одноалфавитную замену согласно таблице 1.
Таблица 1:
|А |Б |Д |К |Р |
|X |V |N |R |S |

Последовательность чисел, вырабатываемая датчиком: 31412543125.
1. у1=Х.
После перестановки символов исходного алфавита получаем таблицу 2 (h1=3).
Таблица 2:
|Д |Б |А |К |Р |
|X |V |N |R |S |

2. у2=V. Таблица 2 после перестановки (h2=1) принимает вид, представленный в таблице 3.
Таблица 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) и Ларе Кнудсен, которые описали метод создания блочных шифров, доказуемо устойчивых к дифференциальному криптоанализу. Эта теория была расширена на дифференциалы высших порядков и частные дифференциалы. Как представляется, дифференциалы высших порядков применимы только к шифрам с малым числом раундов, но частные дифференциалы прекрасно объединяются с дифференциалами.

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

Кнудсен добился известного успеха, рассматривая некоторые необходимые
(но, возможно, недостаточные) критерии того, что он назвал практически стойкими сетями Файстеля - шифров, устойчивых как к дифференциальному, так и к линейному криптоанализу. Ниберг ввел для линейного криптоанализа аналог понятия дифференциалов в дифференциальном криптоанализе.

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

2.6. Проектирование S-блоков

Мощь большинства сетей Файстеля, а особенно их устойчивость к дифференциальному и линейному криптоанализу, напрямую связана с их S- блоками. Поэтому вопрос о том, что же образует хороший S-блок, стал объектом многочисленных исследований.

S-блок - это просто подстановка: отображение m-битовых входов на n- битовые выходы. Применяется большая таблица подстановок 64-битовых входов на 64-битовые выходы. Такая таблица представляет собой S-блок размером
64*64 бит. S-блок с m-битовым входом и n-битовым выходом называется m*n- битовым S-блоком. Как правило, обработка в S-блоках - единственная нелинейная операция в алгоритме. Именно S-блоки обеспечивают стойкость блочного шифра. В общем случае, чем больше S-блоки, тем лучше.

В алгоритме DES используются восемь различных 6*4-битовых S-блоков. В алгоритмах Khufu и Khafre предусмотрен единственный 8*32-битовый S-блок, в
LOKI – 12*8-битовый S-блок, а в Blowfish и CAST – 8*32-битовые S-блоки. В
IDEA S-блоком, по сути, служит умножение по модулю, это 16+16-битовый S- блок. Чем больше S-блок, тем труднее обнаружить статистические данные, нужные для вскрытия методами дифференциального или линейного криптоанализа.
Кроме того, хотя случайные S-блоки обычно не оптимальны с точки зрения устойчивости к дифференциальному и линейному криптоанализу, стойкие S-блоки легче найти среди S-блоков большего размера. Большинство случайных S-блоков нелинейны, невырождены и характеризуются высокой устойчивостью к линейному криптоанализу, причем с уменьшением числа входных битов устойчивость снижается достаточно медленно.

Размер т важнее размера п. Увеличение размера п снижает эффективность дифференциального криптоанализа, но значительно повышает эффективность линейного криптоанализа. Действительно, если п ? 2m - т, наверняка существует линейная зависимость между входными и выходными битами S-блока.
А если п ? 2m , линейная зависимость существует даже только между выходными битами. Заметная доля работ по проектированию S-блоков состоит в изучении булевых функций. Для обеспечения безопасности, булевы функции S- блоков должны отвечать определенным требованиям. Они не должны быть ни линейными, ни аффинными, ни даже близкими к линейным или аффинным функциям.
Число нулей и единиц должно быть сбалансированным, и между различными комбинациями битов не должно быть никаких корреляций. При изменении значения любого входного бита на противоположное выходные биты должны вести себя независимо. Эти критерии проектирования так же связаны с изучением бент-функций (bent functions): функций, которые, как можно показать, оптимально нелинейны. Хотя они определены просто и естественно, их изучение очень трудно.

По-видимому, очень важное свойство S-блоков - лавинный эффект: сколько выходных битов S-блока изменяется при изменении некоторого подмножества входных битов. Нетрудно задать для булевых функций условия, выполнение которых обеспечивает определенный лавинный эффект, но проектирование таких функций задача сложная. Строгий лавинный критерий (Strict Avalanche
Criteria - SAC) гарантирует изменение ровно половины выходных битов при изменении единственного входного бита. В одной из работ эти критерии рассматриваются с точки зрения утечки информации.

Несколько лет назад крипгографы предложили выбирать S-блоки так, чтобы таблица распределения различий для каждого S-блока была однородной. Это обеспечило бы устойчивость к дифференциальному криптоанализу за счет сглаживания дифференциалов на любом отдельном раунде. В качестве примера такого проектирования можно назвать алгоритм LOKI. Однако такой подход иногда облегчает дифференциальный криптоанализ. На самом деле, удачнее подход, гарантирующий наименьшее значение максимального дифференциала.
Кванджо Ким (Kwangjo Kim) выдвинул пять критериев проектирования S-блоков, напоминающих критерии проектирования S-блоков DES.

Выбор хороших S-блоков - нелегкая задача. Известно множество конкурирующих подходов ее решения; среди hих можно выделить четыре основных.

V Случайный выбор. Ясно, что небольшие случайные S-блоки ненадежны, но крупные случайные S-блоки могут оказаться достаточно хорошими.

Случайные S-блоки с восемью и более входами достаточно стойки, еще лучше 12-битовые S-блоки. Стойкость S-блоков возрастает, если они одновременно и случайны, и зависят от ключа.

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

V Разработка вручную. При этом математический аппарат используется крайне незначительно: S-блоки создаются с использованием интуитивных приемов. Барт Пренел (Bart Preneel) заявил, что «... теоретически интересные критерии недостаточны (для выбора булевых функций S- блоков)...», и «... необходимы специальные критерии проектирования».

V Математическая разработка. S-блоки создаются в соответствии с законами математики, поэтому обладают гарантированной устойчивостью к дифференциальному и линейному криптоанализу и хорошими рассеивающими свойствами.

Раздавались призывы объединить «математический» и «ручной» подходы, но реально, по-видимому, конкурируют случайно выбранные S-блоки и S-блоки с определенными свойствами. К преимуществам последнего подхода можно отнести оптимизацию против известных методов вскрытия — дифференциального и линейного криптоанализа. Однако в этом случае неясна степень защиты от неизвестных методов вскрытия. Разработчики DES знали о дифференциальном криптоанализе, поэтому S-блоки DES оптимизированы надлежащим образом. Но, вероятнее всего, о линейном криптоанализе они не знали, и S-блоки DES очень слабы по отношению к такой атаке. Случайно выбранные S-блоки в DES были бы слабее к дифференциальному криптоанализу, но устойчивее к линейному криптоанализу.

С другой стороны, случайные S-блоки могут быть и неоптимальны к данным атакам, но они могут быть достаточно большими и, следовательно, достаточно стойкими. Кроме того, они, скорее всего, окажутся достаточно устойчивыми к неизвестным методам вскрытия. Споры все еще кипят, но лично мне кажется, что S-блоки должны быть такими большими, насколько это возможно, случайными и зависящими от ключа.

2.7. Проектирование блочного шифра

Спроектировать блочный шифр нетрудно. Если рассматривать 64-битовый блочный шифр как перестановку 64-битовых чисел, ясно, что почти все эти перестановки безопасны. Трудно спроектировать такой блочный шифр, который не только стоек, но также может быть легко описан и реализован.

Нетрудно спроектировать блочный шифр, если объем памяти достаточен для размещения 48*32-битовых S-блоков. Трудно спроектировать нестойкий вариант алгоритма DES, если нужно использовать в нем 128 раундов. При длине ключа
512 битов нет нужды беспокоиться о какой-либо зависящей от ключа комплементарности.

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

3. Блочные шифры

3.1. Алгоритм Lucifer

В конце шестидесятых годов корпорация IBM запустила исследовательскую программу по компьютерной криптографии, названную Lucifer (Люцифер) и руководимую сначала Хорстом Файстелем (Horst Feistel), а затем Уолтом
Тачменом (Walt Tuchman). Такое же имя - Lucifer - получил блочный алгоритм, появившийся в результате этой программы в начале семидесятых годов. В действительности существует, по меньшей мере, два различных алгоритма с таким именем. Один из них содержит ряд пробелов в спецификации алгоритма.
Все это привело к заметной путанице.

Алгоритм Lucifer представляет собой сеть перестановок и подстановок, его основные блоки напоминают блоки алгоритма DES. В DES результат функции f складывается операцией XOR с входом предыдущего раунда, образуя вход следующего раунда. У S-блоков алгоритма Lucifer 4-битовые входы и выходы, вход S-блоков представляет собой перетасованный выход S-блоков предыдущего раунда, входом S-блоков первого раунда служит открытый текст. Для выбора используемого S-блока из двух возможных используется бит ключа. (Lucifer реализует все это в едином Т-блоке с 9 битами на входе и 8 битами на выходе). В отличие от алгоритма DES, половины блока между раундами не переставляются, да и само понятие половины блока в алгоритме Lucifer не используется. У этого алгоритма 16 раундов, 128-битовые блоки и более простая, чем в DES, схема развертки ключа.

Применив дифференциальный криптоанализ к первой реализации алгоритма
Lucifer, Бихам и Шамир показали, что Lucifer с 32-битовыми блоками и 8 раундами можно взломать с помощью 40 подобранных открытых текстов за 229 операций. Этот же метод позволяет вскрыть Lucifer с 128-битовыми блоками и
8 раундами с помощью 60 подобранных открытых текстов за 253 шагов. Другая дифференциальная атака вскрывает 18-раундовый, 128-битовый Lucifer с помощью 24 подобранных открытых текстов за 221 операций. Во всех этих вскрытиях использовались стойкие S-блоки алгоритма DES. Применив дифференциальный криптоанализ ко второй реализации Lucifer, Бихам и Шамир обнаружили, что его S-блоки намного слабее, чем в алгоритме DES. Дальнейший анализ показал нестойкость более половины возможных ключей. Криптоанализ на основе связанных ключей позволяет взломать 128-битовый Lucifer с любым числом раундов с помощью 233 подобранных открытых текстов для подобранных ключей или 265 известных открытых текстов для подобранных ключей. Вторая реализация Lucifer еще слабее.

Некоторые полагают, что Lucifer надежнее DES из-за большей длины ключа и малочисленности опубликованных сведений. Но очевидно, что это не так. На алгоритм Lucifer выданы нескольких патентов США. Сроки действия всех этих патентов уже истекли.
3.2. Алгоритм Madryga

В. Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984 году. Его можно эффективно реализовать программным путем: в алгоритме нет раздражающих перестановок, и все операции выполняются над байтами.

Стоит перечислить задачи, которые решал автор при проектировании алгоритма:

V Без помощи ключа открытый текст невозможно получить из шифртекста.

(Это означает только то, что алгоритм стоек).

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

(Это означает, что никакое вскрытие с открытым текстом не может быть эффективнее лобового вскрытия).

V Опубликование алгоритма не влияет на стойкость шифра. (Безопасность полностью определяется ключом).

V Изменение одного бита ключа должно радикально изменять шифртекст одного и того же открытого текста, а изменение одного бита открытого текста должно радикально изменять шифртекст для того же ключа

(лавинный эффект).

V Алгоритм должен содержать некоммутативную комбинацию подстановок и перестановок.

V Подстановки и перестановки, используемые в алгоритме, должны определяться как входными данными, так и ключом.

V Избыточные группы битов открытого текста должны быть полностью замаскированы в шифртексте.

V Длина шифртекста должна совпадать с длиной открытого текста.

V Между любыми возможными ключами и особенностями шифртекста недопустимы простые взаимосвязи.

V Все возможные ключи должны обеспечивать стойкость шифра. (Не должно быть слабых ключей).

V Длина ключа и текст должны иметь возможность варьирования для реализации различных требований к безопасности.

V Алгоритм должен допускать эффективную программную реализацию на мэйнфреймах, мини- и микрокомпыотерах и с помощью дискретной логики.

(По существу, число функций, используемых в алгоритме, ограничено операциями XOR и битовым сдвигом).

Алгоритм DES удовлетворял первым девяти требованиям, но последние три появились впервые. Если допустить, что лучший способ взлома алгоритма - лобовое вскрытие, переменная длина ключа, конечно же, заставит замолчать тех, кто считает, что 56 битов - слишком малая величина. Такие люди могут реализовать этот алгоритм с любой длиной ключа. А любой, кто когда-нибудь пытался реализовать DES программными средствами, обрадуется алгоритму, который учитывает особенности программных реализаций.

3.3.1. Описание алгоритма Madryga

Алгоритм Madryga состоит из двух вложенных циклов. Внешний цикл повторяется восемь раз (для гарантии надежности число циклов можно увеличить) и заключается в применении внутреннего цикла к открытому тексту.
Внутренний цикл превращает открытый текст в шифртекст и выполняется однократно над каждым 8-битовым блоком (байтом) открытого текста. Таким образом, весь открытый текст последовательно восемь раз обрабатывается алгоритмом.

Итерация внутреннего цикла оперирует с 3-байтовым окном данных, называемым рабочим кадром (Рис. 1.). Это окно сдвигается на 1 байт за итерацию. (При работе с последними 2 байтами данные полагаются циклически замкнутыми). Первые два байта рабочего кадра циклически сдвигаются на переменное число позиций, а для последнего байта исполняется операция XOR с несколькими битами ключа. По мере перемещения рабочего кадра все байты последовательно циклически сдвигаются и подвергаются операции XOR с частями ключа. Последовательные циклические сдвиги перемешивают результаты предыдущих операций XOR и циклического сдвига, причем на циклический сдвиг влияют результаты XOR. Благодаря этому процесс в целом обратим.

|Движущийся |WF(1) |WF(2) | |WF(3) | | | |
|рабочий кадр | | | | | | | |
| |8 битов|8 битов| |8 битов | | | |
| |ROT | | | | | |
|Перемещение |Объект сдвига | | |Счетчик сдвига | | |
| |16 бит | |3 бита | | |
| | | | |XOR | | | |
|Хэш ключа |1|2|3|… |KL | | |
| | | | | | | | |

Рис. 1. Одна итерация алгоритма Madryga

Поскольку каждый байт данных влияет на два байта слева и на один байт справа от себя, после восьми проходов каждый байт шифртекста зависит от
16 байтов слева и 8 байтов справа.

При зашифровании каждая итерация внутреннего цикла устанавливает рабочий кадр на предпоследний байт открытого текста и циклически перемещает его к третьему с конца байту открытого текста. Сначала весь ключ подвергается операции XOR со случайной константой и затем циклически сдвигается вправо на 3 бита (ключ и данные двигаются в разных направлениях, чтобы минимизировать избыточные операции с битами ключа). Младшие три бита младшего байта рабочего кадра сохраняются, они определяют циклический сдвиг остальных двух байтов. Далее конкатенация двух старших байтом циклически сдвигается влево на переменное число битов (от 0 до 7). Затем над младшим байтом рабочего кадра выполняется операция XOR с младшим байтом ключа.
Наконец рабочий кадр смещается вправо на один байт и весь процесс повторяется.

Случайная константа предназначена для превращения ключа в псевдослучайную последовательность. Длина константы должна быть равной длине ключа. При обмене данными абоненты должны пользоваться одной и той же константой. Для 64-битового ключа Мадрига рекомендует константу
0x0fle2d3c4b5a6978.

При расшифровании процесс повторяется в обратном порядке. В каждой итерации внутреннего цикла рабочий кадр устанавливается на байт, третий слева от последнего байта шифртекста, и циклически сдвигается в обратном направлении до байта, расположенного на 2 байта левее последнего байта шифртекста. 2 байта шифртекста в процессе циклически сдвигаются вправо, а ключ - влево. После циклических сдвигов выполняется операция XOR.

3.2.2. Криптоанализ алгоритма Madryga

Ученые Квинслендского технического университета (Queensland University of Technology) исследовали алгоритм Madryga и некоторые другие блочные шифры. Они обнаружили, что лавинный эффект при преобразовании открытого текста в шифртекст в этом алгоритме не проявляется. Кроме того, во многих шифртекстах доля единиц превышала доли нулей.

Формальный анализ этого алгоритма не производит впечатления особо надежного. При поверхностном знакомстве с ним Эли Бихам пришел к следующим выводам:

Алгоритм состоит только из линейных операций (циклический сдвиг и XOR), незначительно изменяемых в зависимости от данных.

Это ничуть не напоминает мощь S-блоков DES.

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

Само по себе ни одно из этих замечаний нельзя назвать убийственным, однако этот алгоритм не вызывает у многих криптоаналитиков положительных эмоций. Некоторые вообще не рекомендуют использовать алгоритм Madryga.

3.3. Алгоритм REDOC

REDOC II представляет собой еще один блочный алгоритм, разработанный
Майклом Вудом (Michael Wood) для корпорации Cryptech. В нем используются 20- байтовый (160-битовый) ключ и 80-битовый блок.

Алгоритм REDOC II выполняет все манипуляции - перестановки, подстановки и операции XOR с ключом - с байтами. Этот алгоритм удобен для программной реализации. В REDOC II использованы переменные таблицы функций.
В отличие от алгоритма DES, имеющего фиксированный (хотя и оптимизированный с точки зрения стойкости) набор таблиц подстановок и перестановок, в REDOC
II используются зависимые от ключа и открытого текста наборы таблиц (по сути, S-блоки). В REDOC II 10 раундов, каждый р