- Основы криптографии с секретным ключом

Лекция 4:  Основы криптографии с секретным ключом.

Вопросы:

1. Диффузия. Конфузия. Сети Файстеля.

2. Стандарт шифрования данных DES. (Упрощенный S-DES).

3. Режимы работы блочных шифров.

4. Характеристика современных симметричных блочных шифров. Объединение блочных шифров.

1. Сети Файстеля.

Блочный шифр предполагает преобразование n-битового блока открытого текста в блок шифрованного текста такого же размера. Число различных блоков при этом равно , и, чтобы шифрование было обратимым (т.е. чтобы обеспечивалась возможность дешифрования), каждый из таких блоков должен преобразовываться в свой уникальный блок шифрованного текста. Такие преобразования называются обратимыми, или несингулярными. Вот примеры несингулярного и сингулярного преобразований для .

Шифр, в котором попеременно используются  подстановки и перестановки называется продукционным.  Иногда блочный шифр, который использует последовательность перестановок и подстановок, называют сетью перестановок-подстановок или SP-сетью. Большинство современных блочных алгоритмов, используемых в наши дни, относятся к так называемым сетям Файстеля (Feistel’s network). Это алгоритмы DES, Lucifer, FEAL, Khufu, Khafre, LOKI, ГОСТ, CAST, Blowfish и др..

Практически все эти алгоритмы основаны на блочном шифре Файстеля" (Feistel block cipher).

В начале 70-х г.г. для защиты электронной информации в сетях ЭВМ компания IBM финансировала научные исследования в области криптографии. Команду разработчиков возглавил Хорст Файстель, до того работавший с Клодом Шенноном.

Основной задачей, которую ставил перед собой Шеннон еще в 1945 г., было воспрепятствовать попыткам криптоанализа, основанным на статистическом анализе сообщений. Шеннон ввел понятие идеального шифра — шифра, который полностью скрывает в шифрованном тексте все статистические закономерности открытого текста.

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

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

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

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

Необходимый уровень конфузии призваны гарантировать алгоритму строгий критерий лавинного эффекта и критерий независимости битов.

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

Например, алгоритм DES демонстрирует достаточно сильный лавинный эффект. (Изменение одного бита открытого текста приводит к изменению 34 битов шифрованного текста).

Аналогичный более сильный критерий, называемый строгим критерием лавинного эффекта (SAC — strict avalanche criterion), требует, чтобы для любых i и j при инвертировании входного бита i S-матрицы любой выходной бит j изменялся с вероятностью 1/2. Хотя приведенный здесь строгий критерий лавинного эффекта формулируется для S-матриц, подобный критерий можно сформулировать и для функции F в целом.

Другим критерием является критерий независимости битов (BIC — bit independence criterion), согласно которому для любых значений i, j и k при инвертировании входного бита i S-матрицы выходные биты j и k должны меняться независимо.

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

Структура шифра Файстеля.

На вход алгоритма шифрования подается блок открытого текста длиной m битов и ключ K. Блок открытого текста разделяется на две  части и .

Если размер левой части равен размеру правой, такую архитектуру называют классической или сбалансированной сетью Файстеля. Если левая и правая части не равны, то алгоритм называют разбалансированной сетью Файстеля.

Рис. 1    i-й раунд шифрования

Все раунды обработки проходят по одной и той же схеме. Сначала выполняется операция подстановки. Она заключается в применении к правой половине блока данных некоторой функции раунда F и последующем сложении полученного результата с левой половиной блока данных с помощью операции XOR (исключающего "ИЛИ"). Для всех раундов функция раунда имеет одну и ту же структуру, но зависит от параметра — подключа раунда ().

Подключи раундов отличаются от общего ключа  и друг от друга и вычисляются на основе общего ключа К.

После подстановки выполняется перестановка, представляющая собой обмен местами двух половин блока данных.

Т.о. результат i-го раунда определяется по результату предыдущего раунда:

L_i+1 = R_i

R_i+1 = L_i Å F(R_i, K_i)

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

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

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

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

Криптоаналитическая стойкость сети Файстеля зависит от следующих параметров:

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

§ Размер ключа. Чем длиннее ключ, тем выше надежность шифра, но большая длина ключа тоже может быть причиной слишком медленного выполнения операций шифрования и расшифрования. На сегодня ключи длиной 64 бита и меньше считаются недостаточно надежными — обычно используются 128 и 256-битовые ключи.

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

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

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

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

2. Стандарт шифрования данных DES. (Упрощенный S-DES).

Среди современных методов традиционного шифрования самым распространенным является семейство алгоритмов DES (Data Encryption Standard – Стандарт шифрования данных).

Хотя со времени создания DES было разработано много других алгоритмов, основанных на применении схемы традиционного шифрования,DES по-прежнему остается самым важным из них.

В начале 70-х IBM начала научно-исследовательский проект в области компьютерной криптографии, который возглавил Хорст Файстель (Horst Feistel). В результате работы над проектом к 1971 году был создан алгоритм под кодовым названием LUCIFER. Шифр LUCIFER представлял собой блочный шифр Файстеля, оперировавший блоками размером 64 бита и использовавший ключ длиной 128 битов. Основываясь на многообещающих результатах проекта LUCIFER, IBM взяла курс на создание коммерческого варианта шифра, который в идеале можно было бы разместить в одной микросхеме. Это направление возглавили Уолтер Тачман (Walter Tuchman) и Карл Мейер (Carl Meyer). В результате их усилий была создана усовершенствованная версия шифра LUCIFER, обладающая большей устойчивостью к криптоанализу, но уменьшенным до 56 битов ключом, чтобы алгоритм мог уместиться в одной микросхеме.

В 1973 году Национальное бюро стандартов (NBS) США, теперь Национальный институт стандартов и технологий (NIST), объявило конкурс на лучший проект по созданию общегосударственного стандарта шифрования. Компания IBM представила на конкурс результаты проекта Тачмана-Мейера. Их алгоритм оказался безусловно лучшим из всех предложенных.

В 1977 году он был утвержден в качестве стандарта шифрования данных (DES). Этот стандарт получил официальное имя Federal Information Processing Standard 46 (FIPS PUB 46).

Но прежде чем стать официальным стандартом, предложенный IBM алгоритм был подвергнут жесткой критике, которая не утихает и по сей день. Нападкам подвергаются в основном две особенности шифра. Во-первых, в исходном алгоритме LUCIFER фирмы IBM использовались ключи длиной 128 битов, а в предложенном стандарте длина ключа уменьшена до 56 битов. Критики опасались (и опасаются до сих пор), что такой размер ключа слишком мал для того, чтобы шифр мог гарантированно противостоять попыткам криптоанализа с простым перебором всех возможных вариантов. Второе серьезное возражение критиков было направлено против того факта, что внутренняя структура DES, а именно структура S-матриц, была засекречена. Поэтому пользователи не могли быть уверены в том, что во внутренней структуре DES нет каких-либо скрытых дефектов. Дальнейшие исследования, в частности последние работы по дифференциальному криптоанализу, позволяют с большей уверенностью утверждать, что DES обладает весьма надежной внутренней структурой.

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

В 1998 г. NIST объявил конкурс на принятие нового стандарта со 128-битным ключом (к тому времени DES был вскрыт «в лоб» с использованием Интернет). В 2001 г. был принят AES (Advanced Encryption Standard).

Основные достоинства алгоритма DES:

- используется один ключ длиной 56 бит (ключ 64 бита: 56 бит значащие, 8 бит проверки контроля четности);

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

- высокая скорость работы;

- достаточно высокая криптостойкость алгоритма;

- регулярность, удобная для аппаратной реализации.

В сравнении со схемами на основе открытого ключа, например с RSA, структура DES очень сложна.

Поэтому мы рассмотрим упрощенную версию DES.

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

S-DES был разработан профессором Эдвардом Шейфером из университета Санта-Клара.

S-DES на входе получает 8-битовый блок открытого текста и 10-битовый ключ, а на выходе генерируется 8-битовый блок шифрованного текста.

Алгоритм шифрования включает последовательное выполнение 5 операций:

1) Начальная перестановка (IP);

2) Функция f_k, являющаяся композицией перестановки и подстановки и зависящая от ключа;

3) Перестановка (SW);

4) Функция f_k;

5) Перестановка, обратная начальной (IP^-1).

(См. лабораторную работу )

Надежность DES

После того как DES был утвержден в качестве федерального стандарта США, постоянно возникали дискуссии по поводу его надежности и того уровня безопасности, который им обеспечивается. Эти дискуссии касаются в основном двух вопросов: размера ключа и внутренней природы алгоритма.

5. Использование 56-битовых ключей

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

Уязвимость DES была продемонстрирована в ходе объявленного RSA Laboratories конкурса на поиск секретного ключа. Суть конкурса, победителям которого полагалась премия в 10 тыс. долл. США, состояла в том, чтобы найти ключ DES, имея в распоряжении шифрованное сообщение для неизвестного открытого сообщения, начинающегося тремя известными блоками текста (24-символьной фразой "the unknown message is:"). Конкурс был объявлен RSA 29 января 1997 года. Решив принять участие в конкурсе, независимый консультант Рок Версер (Rocke Verser) разработал программу перебора вариантов ключа и распространил ее в Internet. В общей сложности в выполнение проекта было вовлечено более 70000 систем, на каждой из которой добровольцы подбирали ключ в выделенных им областях пространства возможных ключей DES. Проект начался 18 февраля 1997 года и успешно закончился спустя 96 дней, когда после перебора примерно четверти всех возможных комбинаций был найден правильный ключ. Этот конкурс показал возможность решения сложных криптографических задач с помощью распределенных систем персональных компьютеров.

С 1997 года компания RSA DSI проводит конкурсы DES Challenge по криптоанализу DES «грубой силой».

Рекордные достижения:

1) Старт 13.03.97 г., распределенные вычисления, группа пользователей Internet (координатор Роки Версер) – 96 суток.

2) Старт 13.01.98 г., распределенные вычисления, компания Distributed.net – 39 суток.

Старт 13.07.98 г., специализированный компьютер, компания Electronic Frontier Foundation – 56 часов.

3) Старт 18.01.99 г., спец. компьютер + распределенные вычисления – 22 часа 15 мин..

Т.о. уязвимость DES была продемонстрирована, но он остался базовым строительным блоком для современных симметричных блочных шифров.

6.

7. 3. Режимы работы блочных шифров

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

Таблица 6. Режимы работы DES

8. Режим электронной шифровальной книги

Простейшим режимом является режим электронной шифровальной книги, (ЕСВ- Electronic Codebook). Открытый текст обрабатывается блоками по 64 бита. Каждый 64-битовый блок текста шифруется независимо от других с одним и тем же ключом. Т.о., блоки шифрованного текста не зависят друг от друга. Дешифрование тоже выполняется поблочно на основе одного и того же ключа.

                                                  . . .

Если длина сообщения превышает 64 бита, оно разделяется на 64-битовые блоки с добавлением при необходимости заполнителей к последнему блоку.

Возникает проблема – как при расшифровке отличить исходный текст от дополняющих байтов. Для решения этой проблемы компанией RSA Data Encryption было разработано дополнение к стандарту PKCS#5 (Public Key Cryptography Standard # 5 padding). Дополнение заключается в следующем:

- Если n – число байтов, которыми нужно дополнить блок открытого текста, то значение каждого из дополняющих байтов устанавливается равным n.

- Если не требуется ни одного дополняющего байта, то добавляется 8-байтовый блок, в котором значение каждого из дополняющих байтов устанавливаются равным 8.

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

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

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

9. Режим сцепления шифрованных блоков (CBC)

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

Открытый                 Вектор                                                       Шифрованный

     текст               инициализации                                                      текст

                                                  

                                                . . .

Чтобы получить n-й блок шифрованного текста, необходимо n-й блок открытого текста объединить с помощью XOR с блоком зашифрованного текста, полученным в результате шифрования (n-1)-го блока открытого текста. А затем применить DES с ключом К.

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

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

10. Режим шифрованной обратной связи (CFB)

Схема DES представляет собой блочный шифр с размером блока 64 бита. Но DES можно преобразовать и в потоковый шифр, используя либо режим шифрованной обратной связи (CFB), либо режим обратной связи по выходу (OFB). Использование поточного шифра избавляет от необходимости дополнять сообщение до целого числа блоков. Кроме того, с поточным шифром можно работать в режиме реального времени. Каждый символ можно шифровать и сразу же передавать адресату, не дожидаясь окончания шифрования остальной части сообщения.

Метод CFB используется в приложениях, которые не приспособлены для работы с 8-байтовыми блоками данных. Например, telnet (работает побайтно - поточно).

Предполагается, что единицей передачи данных являются j битов (обычно j = 8). Как и в режиме СВС, происходит сцепление элементов открытого текста, поэтому шифрованный текст, соответствующий любому элементу открытого текста, будет зависеть от всех предыдущих элементов открытого текста.

Алгоритм:

1) Задается начальное значение 64-битового вектора инициализации.

2) Вектор инициализации шифруется DES и записывается в сдвиговый регистр.

3) Первые 8 бит (j бит) открытого текста с помощью операции XOR объединяются с 8 крайними левыми битами из сдвигового регистра. Получаются 8 битов зашифрованного текста.

4) Данные в регистре сдвигаются на 8 битов влево. 8 битов зашифрованного текста, полученных последними, переносятся в крайние правые разряды регистра.

11. Режим обратной связи по выходу (OFB)

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

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

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

   Вектор инициализации                                                                       Данные регистра

                                                                                                                 сдвигаются влево

                                                                                                                              на j битов.

                                                                                                                             С₁ помещ.

                                                                                                                              справа

Открытый текст

        (j бит)

Каждому из рассмотренных режимов (ECB, CBC, CFB, OFB) свойственны свои достоинства и недостатки, что обусловливает области их применения (о которых упоминалось выше).

DES используется для:

- интерактивного шифрования;

- шифрования криптографических ключей при автоматизированном распределении ключей;

- шифрования файлов;

- шифрования почтовых отправлений;

- защиты сообщений электронной системы платежей;

- др. практических задач.

Первоначально стандарт DES применялся только для шифрования данных. Однако его применение было обобщено и на аутентификацию. Для аутентификации пригодны режимы CBC и CFB.

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

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

Этот процесс описывается стандартом аутентификации данных ЭВМ (FIPS 113). Суть стандарта состоит в том, что данные зашифровываются в режиме шифрованной обратной связи (CFB) или в режиме сцепления шифрованных блоков (CBC), в результате чего получается окончательный блок шифра, представляющий собой функцию всех разрядов открытого текста.

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

Выбор режима шифрования:

Какого типа информацию необходимо зашифровать?

Данные                                                  Поток аудио, видео

Необходимо зашифровать

информацию побайтно?                                            Режим OFB

Да                                  Нет

Режим CFB                      Необходимо расшифровывать отдельные блоки    

шифрованного текста независимо от остальных?

Да                                                  Нет

Режим ECB                                Режим CBC

4. Характеристика современных симметричных блочных шифров. Объединение блочных шифров.

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

Наиболее популярными в приложениях, ориентированных на работу с Internet, и обладающими достаточной криптоаналитической стойкостью являютя следующие современные алгоритмы: «двойной» и «тройной» DES, IDEA, Blowfish, RC5, RC6, CAST.

Международный алгоритм шифрования данных (IDEA – International Data Encryption Algorithm) представляет собой симметричный блочный шифр, использующий 128-битовый ключ для шифрования данных блоками по 64 бита. Его разработали сотрудники Швейцарского федерального института технологий Сюдзя Лай (Lai) и Джеймс Массей (Massey) в 1990г.. Этот алгоритм один из самых вероятных кандидатов на замену DES. Например, IDEA включен в PGP, и уже это обеспечивает ему повсеместное использование.

В алгоритме IDEA используются следующие математические операции:

- поразрядное сложение по модулю 2 (исключающее или);

- сложение беззнаковых целых по модулю 2¹⁶ (65536);

- умножение целых по модулю 2¹⁶ + 1.

Операции выполняются с 16-битными подблоками. Комбинирование этих трех операций обеспечивает комплексное преобразование данных, существенно затрудняя криптоанализ IDEA по сравнению с DES, который базируется только на операциях «исключающее ИЛИ».

Алгоритм IDEA может работать в любом режиме блочного шифра.

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

Преимущества перед DES:

1) Значительно безопаснее, т.е. более стоек к криптоанализу (длина ключа 128 бит);

2) Существующие программные реализации примерно вдвое быстрее DES.

По мнению Брюса Шнайера: «IDEA – это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени».

Blowfish – это симметричный блочный шифр (64-битовые блоки), разработанный Брюсом Шнайером. Он может выполняться в области памяти  размером менее 5 кБайт. Длина ключа является переменным параметром и может изменяться до 448 битов. Это позволяет выбрать оптимальное соотношение между скоростью работы и обеспечиваемым уровнем защиты.

Шнайер пытался удовлетворить следующим критериям:

- скорость;

- компактность;

- простота (сложение, XOR, подстановка из таблицы);

- настраиваемая стойкость.

В алгоритме Blowfish подключи и S-матрицы генерируются путем последовательного применения самого алгоритма Blowfish. В результате исходная последовательность битов невообразимо искажается, превращая криптоанализ в очень трудную задачу. О слабых местах этого алгоритма,  вообще ничего неизвестно. Он заметно быстрее DES при реализации на современных микропроцессорах.

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

Компания Kent Marsh Ltd. встроила Blowfish в свой продукт FolderBolt, предназначенный для защиты MS Windows и Macintosh. Blowfish используется в PGPfone.

RC – RivestCipher (Шифр Ривеста) - алгоритм с переменной длиной ключа, спроектированный Роном Ривестом (Rivest) для корпорации RSA Data Security.

RC представляет собой семейство алгоритмов шифрования, имеющее 3 переменных параметра: число байтов в секретном ключе (b), число раундов (r), размер слова в битах (w) – данные шифруются блоками в 2 слова. RC5 шифрует блоки открытого текста длиной 32, 64 или 128 битов в блоки шифрованного текста той же длины. Длина ключа может меняться от 0 до 2040 битов. Конкретная версия RC обозначается RC5-w/r/b. Райвест предлагает использовать RC5-32/12/16 (32-битовые слова, т.е. 64-битовые блоки, 12 раундов шифрования, ключ длиной 16 байтов, т.е. 128 битов) в качестве «стандартной» версии RC5.

Скорость шифрования не зависит от длины ключа. S-матрицы не используются. Программные реализации RC2 втрое быстрее DES.

CAST (cast - догадка) представляет собой процедуру построения алгоритмов симметричного шифрования, разработанную Карлайлом Адамсом и Стаффордом Таваресом. CAST-128 описан в документе RFC-2144. В нем допускается использование ключей от 40 до 128 битов с шагом 8 битов. CAST имеет структуру классической схемы Файстеля (64-битовые блоки, 16 раундов). Отличия:  в каждом раунде шифрования CAST использует 2 подключа, функция F зависит от раунда. Применяется в PGP.

Вся сила этого алгоритма в его S- матрицах. У него нет фиксированных S- матриц. Для каждого приложения они проектируются заново, но зависят от реализации алгоритма, а не от ключа. Алгоритм устойчив к дифференциальному и линейному криптоанализу. Его можно взломать только «в лоб».

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

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

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

Один из методов объединения – многократное шифрование, т.е. использование блочного алгоритма несколько раз с разными ключами для шифрования одного и того же блока открытого текста.

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

У.Тачмен предложил следующую идею.

Блок открытого текста Х шифруется 3 раза с помощью 2-х ключей К₁ и К₂:

Y = E_К1 (D_К2 (E_К1(X)))

Т.е. Х сначала шифруется с помощью К₁, затем расшифровывается К₂ и окончательно шифруется К₁. Если блочный алгоритм использует n-битовый ключ, то длина ключа данной схемы 2n бит.

               К₁                                                          К₂                                   К₁

X                            A                                    B                                 Y

            E_К1                                                       D_К2                                                  E_К1

Этот режим называется режимом EDE (encrypt-decrypt-encrypt). Исходный текст получается:

X = D_К1 (E_К2 (D_К1(Y)))

Данная схема разработана в корпорации IBM и приводится в стандартах X9.17, ISO8732 в качестве средств улучшения характеристик DES.

При трехкратном шифровании можно применить  3 различных ключа:

Y = E_К3 (D_К2 (E_К1(X))),

X = D_К1 (E_К2 (D_К3(Y))).

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

Отметим некоторые важные характеристики этих алгоритмов, отсутствующие в DES.

1. Переменная длина ключа. Криптоаналитическая стойкость алгоритма зависит от длины ключа – чем длиннее ключ, тем больше времени требуется на перебор всех возможных вариантов ключа. Алгоритмы Blowfish, RC5, CAST-128 и RC2 обеспечивают возможность выбора длины ключа.

2. Смешивание операций. Использование более одной арифметической и/или булевой операции усложняет задачу криптоанализа, особенно, если эти операции не связаны дистрибутивным и ассоциативным законами. Данный подход позволяет обеспечить нелинейность в противовес S-матрицам. В алгоритмах IDEA, Blowfish, RC5, CAST-128, RC2 предусмотрено смешивание операций.

3. Зависимость сдвига от данных. Альтернативой использованию S-матриц является использование циклических сдвигов, величина которых зависит от обрабатываемых данных. При достаточно большом числе раундов этот механизм может обеспечить алгоритму прекрасные свойства конфузии и диффузии. Более того, т.к. сдвиги зависят от блоков обрабатываемых данных, а не от подключей, это значительно усложняет задачу восстановления подключей. Зависимые от данных сдвиги используются в RC5.

4. Зависимость сдвига от ключа. Можно использовать циклические сдвиги, зависящие не от шифруемых данных, а от ключа. Это сделано, например, в CAST-128.

5. Зависимость S-матриц от ключа. Вместо статических S-матриц с заданными криптографическими характеристиками, как в DES и CAST-128, S-матрицы можно генерировать в зависимости от ключа. Тогда для разных ключей будут получаться разные S-матрицы. Данный подход, особенно для больших S-матриц (например, 8x32), должен обеспечивать сильную нелинейность и значительно усложнять криптоанализ. Зависящие от ключа S-матрицы используются в алгоритме Blowfish.

Рекомендация для Вас - 13 Резюме.

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

7. Переменная функция F. Использование функции F, изменяющейся от раунда к раунду, также может усложнить задачу криптоанализа. Данный подход применяется в CAST-128.

8. Переменная длина блока открытого/шифрованного текста. Данная стратегия применена в RC5.

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

10.Обработка обеих половин блока данных в каждом раунде. В классическом шифре Файстеля в каждом раунде изменяется только одна половина блока данных. Но если со второй половиной данных выполнить хотя бы элементарные преобразования, это не потребует больших затрат времени, но повысит надежность шифра. В алгоритмах IDEA, Blowfish, RC5 в каждом раунде обрабатываются обе половины блока шифруемых данных.

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