блочный шифр

Обзор начнем с самого популярного в мире симметричного алгоритма шифрования — алгоритма DES (Data Encryption Standard).

Алгоритм DES был разработан фирмой IBM и в 1977 г. принят Национальным институтом стандартов и технологий (National Institute of Standards and Technology) в качестве стандарта Правительства США для шифрования информации категории «less-than-top-secret» (ниже, чем высшей категории секретности). С тех пор он повторно сертифицировался в качестве такого стандарта каждые 5 лет вплоть до 1993 г. В 1998 г. Национальный институт стандартов и технологий США отказался сертифицировать DES, что было связано с тем, что уровень развития вычислительной техники сделал возможным вскрытие DES относительно дешевыми средствами.

DES является так называемым «блочным шифром» (когда шифруемая информация обрабатывается блоками фиксированной длины, в случае DES длина блока составляет 64 бита) и имеет ключ длиной 56 битов (ключ представляется двоичной последовательностью длиной 64 бита, которая получается из последовательности битов ключа добавлением после каждых 7 битов ключа бита проверки на нечетность; таким образом, в двоичном представлении ключа в позициях 8, 16, 24,…, 64 стоят биты проверки на нечетность).

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

Очень схематично опишем работу алгоритма DES. Сначала 64-битовый блок шифруемой информации W подвергается начальной фиксированной перестановке (каждый бит w занимает положение, задаваемое специальной таблицей, определенной DES). Получившийся в результате блок w представляется в виде W=L(0)R(0), где L(0),R(0) соответственно первые и последние 32 бита W.

Алгоритм DES является циклическим. Если вычислены значения L(n-1),

R(n-1) для 1≤n≤16 , то L(n), R(n), определяются следующими равенствами:

где означает побитовое сложение, функция / определена далее, а К(п) — 48-битовые последовательности, получаемые из ключа DES с помощью фиксированного набора определенных в стандарте DES перестановок, сдвигов и подстановок. Криптотекст оригинального блока W представляет собой блок L(16)R(16).

Очевидно, что расшифрование криптотекста осуществляется с помощью следующего набора равенств:

для 1≤n≤16. После вычисления с помощью этих равенств значений L(0), R(0) расшифрование начального блока очевидно. Функция /(х,у), где х — двоичная переменная длиной 32 бита, а у — переменная длиной 48 битов, имеет областью допустимых значений множество всевозможных последовательностей длиной 32 бита и строится следующим образом. Переменная х «расширяется» до блока xt длиной 48 битов с помощью определенной в стандарте DES следующей таблицы:

После такого «расширения» блок х, побитно складывается по модулю 2 с блоком у. Результирующий блок В, состоящий из 48 битов, делится на 8 шестибитовых блоков В=В1 В2 В3 В4 В5 В6 В7 В8. В свою очередь, каждый из этих восьми блоков преобразуется в четырехбитовые блоки А1 А2 А3 А4 А5 А6 А7 А8 с помощью специальных нелинейных преобразований S,,…, S8. Каждое S-преобразование задается определенной в алгоритме DES таблицей, состоящей из 4 строк и 16 столбцов. Элементами таблицы являются целые десятичные числа, принимающие значения от 0 до 15.

Рассмотрим таблицу для преобразования S7. В соответствии с DES таблица имеет следующий вид:

4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

Строки таблицы пронумерованы сверху вниз от 0 до 3, а столбцы — слева направо от 1 до 16.

Тогда преобразование S7, отображающее В7 (последовательность из 6 битов Z1,Z2, Z3, Z4, Z5, Z6) в Ay, строится следующим образом. Определяются два числа, двоичные представления которых соответственно равны ST=(Z,Z6), CL=(Z2 Z3 Z4 Z5). Далее из таблицы выбирается элемент, расположенный на пересечении строки ST и столбца CL. Вспомним, что элементами таблицы являются числа от 0 до 15. Поэтому для двоичного представления любого числа таблицы достаточно 4 битов. Двоичное представление выбранного элемента таблицы и есть последовательность А7.

Завершается определение функции / применением к 32-битному блоку А,А2 А3 А4 А5 А6 А7 А8 определенной в стандарте DES перестановки. Алгоритм DES обладает рядом интересных свойств. Первое свойство, касающееся симметрии, почти очевидно и состоит в том, что если в шифруемом блоке и ключе DES все 0 заменить на 1 и наоборот, то в результате шифрования получится блок, который образуется из первоначального криптотекста инверсией 0 и 1. Действительно, в DES используются только операции перестановки, подстановки, сдвиги и сложение по модулю 2, которые не зависят от того, как «называются» цифры 0 и 1.

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

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

Сегодня известны два метода вскрытия DES. Первый метод состоит в полном переборе всех возможных вариантов ключа и их проверки на правильность расшифрования до получения истинного значения. В случае DES необходимо перебрать 256 (или примерно 7,2×1016) возможных вариантов ключа.

Конечно, прогресс вычислительной техники за последние годы был настолько большим, что перебор всех возможных вариантов ключа DES уже не кажется сейчас столь же невероятной задачей, какой он представлялся еще в 1993 г. Известны две успешные атаки на алгоритм DES, совершенные в 1999 г. с привлечением компьютеров, подключенных к Интернету (open project). В первом случае ключ был скомпрометирован примерно за 3 месяца, и для его поиска было проанализировано 85 % всех возможных значений ключа. Во втором случае ключ был вскрыт за 6 недель, и для этого потребовалось перебрать около 25 % всех значений ключа. Кроме того, известен случай, когда компьютер, построенный за деньги организации Electronic Privacy Information Center и состоящий из 1728 процессоров, обеспечивающих перебор 88 млрд вариантов ключа в секунду, вскрыл DES за 56 часов работы.

В результате сегодня алгоритм DES уже не считается надежным, и в качестве наиболее простой альтернативы ему предлагается алгоритм Triple DES (другое обозначение — 3DES), использующий ключ длиной 112 битов.

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

Важным достоинством DES является его высокая производительность. Так, DES быстрее алгоритма RSA (см. далее) той же криптостойкости, что и DES (для этого длина ключа в RS А должна быть равна 384 бита), в 100 раз, если используется программная реализация обоих криптоалгоритмов, и в 1000—10 000 раз, если применяется реализация алгоритмов в специализированных вычислительных устройствах, называемых Hardware Security Module.

Даже программная реализация DES на 486 PC позволяет шифровать данные со скоростью 400 Кбит/с. Экспорт программного обеспечения, использующего DES, до последнего времени контролировался Агентством национальной безопасности США. В результате в экспортируемом программном обеспечении использовался DES с ограниченной длиной ключа, равной 40 бит.

Как уже отмечалось, в 1998 г. Национальный институт стандартов и технологий отказался сертифицировать DES в качестве стандарта Правительства США.

После нескольких лет обсуждений американский Национальный институт стандартов и технологий 2 октября 2000 г. утвердил вместо DES новый стандарт блочного симметричного алгоритма шифрования AES (Advanced Encryption Standard).

Новый стандарт имеет очень хорошие шансы стать международным, если не де-юре, то, по крайней мере, де-факто. Во-первых, он был принят на основе открытого конкурса, в котором участвовали алгоритмы, предложенные математиками из многих стран (США, Канады, Австралии, Бельгии, Германии, Норвегии, Франции, Южной Кореи, Японии и даже Коста-Рики). Во-вторых, победителем стал алгоритм Rijndael, разработанный бельгийскими криптографами Винсентом Рэменом и Ионом Даменом. Название этого алгоритма образовано из первых букв фамилий его авторов, поэтому в транскрипции с фламандского оно произносится примерно как «рэндал». Бельгийское, а не американское происхождение Rijndael наверняка поможет AES получить признание в Европе, долгое время с подозрением относившейся к DES.

Алгоритм Rijndael был подвергнут скрупулезному анализу не только специалистами Национального института стандартов и технологий и Агентства национальной безопасности США, но и их конкурентами, среди которых были самые блестящие криптографы и криптоаналитики мира. Однако никому не удалось выявить уязвимые места этого алгоритма.

Rijndael может работать с ключами длиной 128, 192 и 256 битов, и поэтому в обозримом будущем он защищен от атак методом полного перебора всех возможных ключей. Кроме того, алгоритм сочетает в себе высокое быстродействие и умеренные требования к памяти. Поэтому он может быть реализован в самых различных устройствах, включая SIM мобильного телефона и смарт-карты. И наконец, Rijndael не защищен патентами и доступен для свободного использования в любых продуктах.

Большое распространение в последние годы получил симметричный алгоритм Triple DES. Этот алгоритм использует ключ, состоящий из двух ключей DES, и состоит из трех шагов. На первом шаге с помощью первого ключа и алгоритма DES 64-битный блок шифруется. На втором шаге с помощью второго ключа и в соответствии с алгоритмом DES полученный на первом шаге криптотекст дешифруется. На последнем, третьем шаге результат дешифрования, полученный на втором шаге, вновь шифруется с помощью первого ключа и алгоритма DES. Полученный 64-битный блок является криптотекстом Triple DES. Таким образом, алгоритм Triple DES требует трехкратного использования DES, откуда и происходит его название.

Очевидно, что для вскрытия алгоритма Triple DES методом полного перебора потребуется проверить 2112(или примерно 5,2х1033) различных ключей.

Скорость шифрования алгоритма Triple DES примерно в 3 раза ниже производительности DES и в случае программной реализации алгоритма на компьютере 486 PC составляет около 150 Кбит/с.

Следуя примеру США в разработке открытого национального стандарта шифрования, в 1989 г. государственный стандарт шифрования данных для сетей ЭВМ приняли в СССР. Он получил обозначение ГОСТ 28147-89 и имел гриф «Для служебного пользования» до конца существования самого СССР. В России он был принят официально с 1992 г. как стандарт шифрования данных наряду с другими бывшими стандартами СССР. Стандарт был формально объявлен полностью открытым в мае 1994 г. Стандарт ГОСТ 28147-89 так же, как и DES, является блочным шифром. Длина блока информации составляет также 64 бита. Длина ключа равняется 256 битам, и ни о какой практической возможности перебора всех допустимых вариантов ключа не только сегодня, но и в XXI веке не может быть и речи.

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

В 1990 г. К. Лэй и Дж. Мэсси (Швейцария) предложили проект международного стандарта шифрования данных, получивший обозначение IDEA (International Data Encryption Algorithm), который в международном криптографическом сообществе оценивается весьма высоко и за последние годы усилиями международных организаций по стандартизации (прежде всего европейских) активно выдвигался на роль официального общеевропейского стандарта шифрования данных. Длина ключа алгоритма IDEA равна 128 битов для шифрования блока длиной 64 бита. Как будет показано далее, алгоритм будет оставаться стойким к взлому на протяжении нескольких ближайших десятилетий.

Алгоритм IDEA использует три группы операций — побитовое сложение по модулю 2, сложение по модулю 216, умножение по модулю 216+1. Операции производятся над блоками длиной 16 битов, получающимися в результате деления шифруемого блока на 4 подблока. Алгоритм является циклическим — используется 8 циклов преобразований.

Сегодня алгоритм IDEA запатентован в США и большинстве европейских стран. Держателем патента является компания Ascom-Tech. Некоммерческое применение стандарта является бесплатным.

Алгоритм IDEA быстрее Triple DES, но медленнее DES. Скорость шифрования алгоритма в случае его программной реализации на компьютере 486 PC составляет около 200 Кбит/с. Алгоритм Skipjack был разработан Агентством национальной безопасности США для проектов Клиппер-чип (Clipper Chip) и Кэпстоун-чип (Capstone chip). Алгоритм использует ключ длиной 80 битов и использует 32 цикла на каждую операцию шифрования/дешифрования.

Проект Клиппер-чип был объявлен администрацией президента США в 1994 г. и должен был положить начало внедрению в США «Стандарта шифрования с депонированием ключа». Главный замысел проекта состоял в том, чтобы по решению суда предоставить правоохранительным органам беспрепятственный доступ к шифруемой с помощью Клиппер-чипа информации. Для этого в чипе используется алгоритм Skipjack с двумя ключами. Знание одного из ключей (мастер-ключа) достаточно для того, чтобы было возможно дешифровать любое сообщение, зашифрованное с помощью Клиппер-чипа. При изготовлении микросхемы этот мастер-ключ разделялся на две половины, подлежащих хранению в государственных организациях. Если правоохранительные органы получают необходимую санкцию в суде, они могут получить обе половины ключа и читать любую информацию, шифруемую с помощью соответствующей микросхемы. Сегодня можно утверждать, что идея проекта Клиппер-чипа провалилась. В то же время, известно, что Агентство национальной безопасности использует алгоритм Skipjack для шифрования собственных сообщений. Это подтверждает высокий уровень криптостойкости этого алгоритма.

Алгоритмы RC2 и RC4 — шифры с переменной длиной ключа для очень быстрого шифрования больших объемов информации (были разработаны Роном Райвестом). Эти два алгоритма быстрее, чем DES, и способны повышать степень защиты за счет выбора более длинного ключа. RC2 — блочный алгоритм, и его можно применять как альтернативу DES. RC4 представляет собой потоковый шифр и работает почти в десять раз быстрее DES.

Результаты сравнительного анализа рассмотренных алгоритмов приведены в таблице ниже