Механизм блочного шифрования защиты информации

Стандарт шифрования данных (DES - DATA ENCRIPTION STANDARD) блочный шифр с симметричными ключами, разработан Национальным Институтом Стандартов и Технологии (NIST - National Institute of Standards and Technology).

В l973 году NIST издал запрос для разработки предложения национальной криптографической системы с симметричными ключами.

Предложенная IBM модификация проекта, названная Lucifer, была принята как DES. DES были изданы в эскизном виде в Федеральном Регистре в марте 1975 года как Федеральный Стандарт Обработки Информации (FIPS - Federal Information Processing Standard).

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

Они подозревали, что некоторая часть структуры (S-блоки) может иметь скрытую лазейку, которая позволит расшифровывать сообщения без ключа. Впоследствии проектировщики IBM сообщили, что внутренняя структура была доработана, чтобы предотвратить криптоанализ.

DES был наконец издан как FIPS 46 в Федеральном Регистре в январе 1977 года. Однако FIPS объявил DES как стандарт для использования в неофициальных приложениях. DES был наиболее широко используемым блочным шифром с симметричными ключами, начиная с его публикации. Позже NIST предложил новый стандарт (FIPS 46-3), который рекомендует использование тройного DES (трехкратно повторенный шифр DES) для будущих приложений.

1.1Структура DES

DES использует 16 раундов. Каждый раунд DES применяет шифр Файстеля, как это показано на рис. 4.

Раунд принимает L_I-1 R_I-1 от предыдущего раунда (или начального блока перестановки) и создает для следующего раунда L_I И R_I , которые поступают на следующий раунд (или конечный блок перестановки). Можно принять, что каждый раунд имеет два элемента шифра (смеситель и устройство замены). Каждый из этих элементов является обратимым. Устройство замены - очевидно обратимо, оно меняет местами левую половину текста с правой половиной. Смеситель является обратимым, потому что операция ИСКЛЮЧАЮЩЕЕ ИЛИ обратима. Все необратимые элементы сосредоточены в функции f (R_I-1,K_I).

Функция DES

Основной блок DES - функция DES. Функция DES с помощью 48-битового ключа зашифровывает 32 самых правых бит R_I-1, чтобы получить на выходе 32-битовое слово. Эта функция содержит, как это показано на рис. 5, четыре секции: отбеливатель (whitener), P-блок расширения, группу S-блоков и прямой P-блок.

P-блок расширения. Так как вход R_I-1 имеет длину 32 бита, а ключ K_I -- длину 48 битов, мы сначала должны расширить R_I-1 до 48 бит. R_I-1 разделяется на 8 секций по 4 бита. Каждая секция на 4 бита расширяется до 6 бит. Эта перестановка расширения следует по заранее определенным правилам. Для секции значения входных бит 1, 2, 3 и 4 присваиваются битам 2, 3, 4 и 5 соответственно на выходе. Выходной бит 1 формируется на основе входного бита 4 из предыдущей секции; бит выхода 6 формируется из бита 1 в следующей секции. Если секции 1 и 8 рассматривать как соседние секции, то те же самые правила применяются к битам 1 и 32. Рисунок 6 показывает входы и выходы в перестановке расширения.

Хотя отношения между входом и выходом могут быть определены математически, но чтобы определить этот P-блок, DES использует таблицу 8.2. Обратите внимание, что число выходов 48, но диапазон значений - только от 1 до 32. Некоторые из входов идут к больше чем одному выходу. Например, значение входного бита 5 становится значением битов выхода 6 и 8.

Отбеливатель (whitener). После расширения DES использует операцию XOR (ИСКЛЮЧАЮЩЕЕ ИЛИ) над расширенной частью правой секции и ключом раунда. Заметим, что правая секция и ключ имеют длину 48 бит. Также заметим, что ключ раунда использует только эту операцию.

Пример 3

Входная последовательность S блока 1 - . Какая последовательность будет на выходе?

Решение

Если мы запишем первый и шестой биты вместе, мы получим в двоичном исчислении 11, который выражается как число 3 при десятичном исчислении. Остающаяся часть битов 0001 в двоичном исчислении является 1 в десятичном исчислении. Мы ищем значение строки 3 и столбца 1 в таблице 3 (S-блок 1). Результат - 12 в десятичном исчислении или 1100 в двоичном исчислении. Тогда вход 1100011 дает выход 1100.

Пример 8.4

Входная последовательность S-блока 8 - . Какая последовательность будет на выходе?

Решение

Если мы запишем первый и шестые биты вместе, то получим в двоичном исчислении число 00, которое выражается числом 0 при десятичном исчислении. Остающаяся часть битов - 0000 в двоичном исчислении, то есть 0 в десятичном исчислении. Мы ищем значение строки 0 и столбца 0 в таблице 10 (S-блок 8). Результат -- 13 в десятичном исчислении или 1101 в двоичном исчислении. Тогда вход 000000 дает выход 1101.

Прямая перестановка - последняя операция в функции DES - прямая перестановка с 32 битами на входе и 32 битами на выходе. Отношения "вход-выход" для этой операции показаны в Таблице 11. Они следуют тем же самым общим правилам, как и предыдущие таблицы перестановки. Например, седьмой бит входа становится вторым битом выхода.

Шифр и обратный шифр

Используя смеситель и устройство замены, мы можем создать шифр и обратный шифр для каждого из 16-ти раундов. Шифр используется на стороне шифрования; обратный шифр - на стороне дешифрования. Алгоритмы создания шифра и обратного шифра аналогичны.

Первый способ

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

Смеситель и устройство замены самоинверсны. Конечные и начальные перестановки также инверсны друг другу. Левая секция исходного текста на стороне шифрования шифруется L₀ как L₁₆, и L₁₆ дешифруется на стороне дешифратора как L₀. Аналогичная ситуация с R₀ и R₁₆.

Нужно запомнить очень важное положение, которое касается шифров: ключи раундов (K₁ и K₁₆) применяются при шифровании и дешифровании в обратном порядке. На стороне шифрования первый раунд применяет ключ K₁, а раунд 16 - ключ K₁₆; при дешифровании раунд 1 использует ключ K₁₆, а раунд 16 - ключ K₁.

В первом методе последний раунд не имеет устройства замены.

Альтернативный способ

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

Генерация ключей

Генератор ключей создает шестнадцать ключей по 48 битов из ключа шифра на 56 битов. Однако ключ шифра обычно дается как ключ из 64-х битов, в котором 8 дополнительных битов являются битами проверки. Они отбрасываются перед фактическим процессом генерации ключей, который показан на рис. 10.

Удаление битов проверки

Предварительный процесс перед расширением ключей - перестановка сжатия, которую мы называем удалением битов проверки. Он удаляет биты четности (биты 8, 16, 24, 32..., 64) из 64-битового ключа и переставляет остальную часть битов согласно таблице 8.12. Остающееся значение на 56 битов - фактический ключ шифра, который используется, чтобы генерировать ключи раунда. Биты удаляются с помощью перестановки (P-блока сжатия), как это показано в таблице 12.

Сдвиг влево

После прямой перестановки ключ разделен на две части по 28 битов. Каждая часть сдвигается влево (циклический сдвиг) на один или два бита. В раундах 1, 2, 9 и 16 смещение - на один бит, в других раундах - на два бита. Затем эти две части объединяются, чтобы создать часть в 56 бит. Таблица 13 показывает число сдвигов манипуляций для каждого раунда.

Перестановка сжатия

Перестановка сжатия (P-блок) изменяет 56 битов на 48 битов, которые используются для формирования ключа раунда. Перестановка сжатия показана в таблице 14.

Примеры

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

Пример 5

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

Plaintext: 123456ABCD 132536Key: AABB09182736CCDD

Cipher Text: COB7ASD05F3AS29C

Покажем результат каждого раунда и текста, созданного до и после раундов. Таблица 15 показывает результаты первых шагов перед началом раунда. Исходный текст -- прошедший через начальную перестановку для получения различных 64 бит (16 шестнадцатеричных цифр).

Таблица показывает результат 16 раундов, которые включают смешивание и замену (исключая последний раунд). Результаты последних раундов (L₁₆ и R₁₆) объединены. Наконец, текст проходит конечную перестановку, для того чтобы получить зашифрованный текст.

Следует отметить некоторые положения. Правая секция каждого раунда совпадает с левой секцией следующего раунда. Причина в том, что правая секция проходит через смеситель без изменения, а устройство замены переносит ее в левую секцию. Например, R₁ передается через смеситель второго раунда без изменения, но затем, пройдя устройство замены, он становится L₂. Второе интересное положение: на последнем раунде мы не имеем устройства замены. Именно поэтому R₁₅ становится R₁₆ вместо того чтобы стать L₁₆.

Пример 6

Давайте рассмотрим, как Боб в пункте назначения может расшифровать зашифрованный текст, полученный от Алисы, с помощью совпадающего ключа. Для экономии времени мы разберем только несколько раундов. Таблица 16 показывает интересующие нас точки. Первое правило: ключи раунда должны использоваться в обратном порядке. Сравните таблицу 8.15 и таблицу 8.16. Ключ раунда 1 - такой же как ключ для раунда 16. Значения L₀ и R₀ при дешифрации те же самые, что и значения L₁₆ и R₁₆ при шифровании. Аналогичные совпадения будут получены и в других раундах. Это доказывает не только, что шифр и обратный шифр инверсны друг другу, но также то, что каждый раунд при шифрации имеет соответствующий раунд при дешифрации в обратном шифре. Результат свидетельствует, что начальные и конечные перестановки также являются инверсиями друг друга.

1.2Анализ DES

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

Свойства

Два желательных свойства блочного шифра - эффект лавины и законченность.

Лавинный эффект

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

Пример 7

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

Исходный текст: 0000000000000000 Ключ: 22234512987ABB23

Зашифрованный текст: 4789FD476E82A5F1

Исходный текст: 0000000000000001 Ключ: 22234512987ABB23

Зашифрованный текст: OA4ED5C15A63FEA3

Хотя два блока исходного текста отличаются только самым правым битом, блоки зашифрованного текста отличаются на 29 бит. Это означает, что изменение приблизительно в 1,5 процентах исходного текста создают изменение приблизительно 45 процентов зашифрованного текста. Таблица 17 показывает изменение в каждом раунде. Можно увидеть, что существенные изменения возникают уже в третьем раунде.

Эффект полноты

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

Критерии разработок DES

S-блоки

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

1. Входы каждой строки есть перестановки значений между 0 и 15.

2. S-блоки - нелинейные. Другими словами, выход - не аффинное преобразование.

3. Если мы изменяем единственный бит на входе, на выходе будут изменены два или больше бита.

4. Если два входа S-блока отличаются только двумя средними битами (битами 3 и 4), выходная информация должна отличаться по крайней мере двумя битами. Другими словами, S (x) и должны отличаться по крайней мере двумя битами, где x -- вход и S(x) -- выход.

5. Если два входа в S-блок отличаются первыми двумя битами (биты 1 и 2) и последними двумя битами (5 и 6), два выхода должны быть различны. Другими словами, мы должны иметь следующее отношение: , в котором b и с - произвольные биты.

6. Есть только 32 шестибитовые пары "вход-выход" (x_i и x_j ), в которых . Эти 32 входных пары создают 32 пары слова выхода по 4 бита. Если мы создаем какие-то различия между 32 выходами пар, , то из этих d должны быть одинаковыми не больше чем 8.

7. Такой же критерий, как в пункте 6, применяется к трем S-блокам.

8. В любом S-блоке, если единственный входной бит сохраняется как константа (0 или 1), то другие биты изменяются случайно так, чтобы разности между числом нулей и единиц были минимизированы.

P-блоки

Между двумя рядами S-блоков (в двух последующих раундах), есть один прямой P-блок (32 на 32) и один P-блок расширения (32 на 48). Эти два P-блока вместе обеспечивают рассеивание битов. Здесь мы обсудим прикладные P-блоки, используемые в DES. В структуре P-блоков были реализованы следующие критерии:

1. Каждый вход S-блока подключается к выходу другого S-блока (в предыдущем раунде).

2. Ни один вход к данному S-блоку не соединяется с выходом от того же самого блока (в предыдущем раунде).

3. Четыре бита от каждого S-блока идут в шесть различных S-блоков (в следующем раунде).

4. Ни один из двух битов выхода от S-блока не идет в тот же самый S-блок (в следующем раунде).

5. Если число блоков S-блоков 8, то S₁, S₂,..., S ₈.

o Выход S_j-2 переходит в один из первых двух битов S_j (в следующем раунде).

o Бит выхода от S_i-1 переходит в один из последних двух битов S_j (в следующем раунде).

o Выход S_{j +1} переходит в один из двух средних битов S_j (в следующем раунде).

6. Для каждого S-блока два бита выхода идут в первые или последние два бита S-блока в следующем раунде. Другие два бита выхода идут в средние биты S-блока в следующем раунде.

7. Если выход от S_j переходит в один из средних битов в S_k (в следующем раунде), то бит выхода от S_k не может идти в средний бит S_j. Если мы допускаем j = k, то подразумеваем, что ни один средний бит S-блока не может идти в один из средних битов того же самого S-блока в следующем раунде.

Число раундов

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

Слабости DES

S-блоки. В литературе указываются по крайней мере три проблемы S-блоков.

1. В S-блоке 4 три бита выхода могут быть получены тем же самым способом, что и первый бит выхода: дополнением некоторых из входных битов.

2. Два специально выбранных входа к массиву S-блока могут создать тот же самый выход.

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

P-блоки. В структуре P-блока были найдены одна загадка и одна слабость.

1. Не ясно, почему проектировщики DES использовали начальную и конечную перестановки. Эти перестановки не вносят никаких новых свойств с точки зрения безопасности.

2. В перестановке расширения (в функции) первые и четвертые биты последовательностей на 4 бита повторяются.

Слабость в ключе шифра

Размер ключа. Критики утверждают, что самая серьезная слабость DES - это размер ключа (56 битов). Чтобы предпринять атаку грубой силы данного блока зашифрованного текста, злоумышленники должны проверить 2⁵⁶ ключей.

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

b. Если мы можем сделать компьютер с одним миллионом чипов процессоров (параллельная обработка), то сможем проверить все множество ключей приблизительно за 20 часов. Когда был введен DES, стоимость такого компьютера была более чем несколько миллионов долларов, но она быстро снизилась. Специальный компьютер был создан в 1998 году - и нашел ключ за 112 часов.

c. Компьютерные сети могут моделировать параллельную обработку. В 1977 году команда исследователей использовала 3500 компьютеров, подключенных к Internet, чтобы найти ключ RSA за 120 дней. Множество ключей было разделено среди всех этих компьютеров, и каждый компьютер был ответственен за проверку части домена DES. Если 3500 связанных в сеть компьютеров могут найти ключ через 120 дней, то секретное общество из 42 000 членов может найти ключ через 10 дней.

Приведенное выше показывает, что DES с размером ключа шифра 56 битов не обеспечивает достаточной безопасности. Позже мы увидим, что есть одно решение этой проблемы - это использование тройного DES(3DES) с двумя ключами (112 битов) или тройного DES с тремя ключами (биты 16).

Слабые ключи. Четыре ключа из 2⁵⁶ возможных ключей называются слабыми ключами. Слабые ключи -- это одни из тех, которые после операции удаления проверочных бит (используя таблицу 8.12) состоят из всех нулей или всех единиц или половины нулей и половины единиц. Такие ключи показаны в таблице 18.

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

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

В чем опасность использования слабых ключей? Если мы зашифровали блок слабым ключом и впоследствии расшифровали результат тем же самым слабым ключом, мы получаем первоначальный блок. Процесс создает один и тот же первоначальный блок, если мы расшифровываем блок дважды. Другими словами, каждый слабый ключ есть инверсия самого себя: E_k. (E_k (P)) = P, как это показано на рис. 11.

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

Пример 8

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

Ключ: 0x0101 0101 0101 0101

Зашифрованный текст: 0x814FE938589154F7

Исходный текст: 0xl234.56887654321

Ключ: 0x0101 0101 0101 0101

Исходный текст: 0x814FE938589154F7

Зашифрованный текст: 0xl234.56887654321

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

Чтобы проиллюстрировать идею, мы создали ключи раунда от первой пары, как показано ниже:

Ключ раунда 19153E54319BD 6EAC1ABCE642

Ключ раунда 26EAC1ABCE6429153E54319BD

Ключ раунда 36EAC1ABCE6429153E54319BD

Ключ раунда 46EAC1ABCE6429153E54319BD

Ключ раунда 56EAC1ABCE6429153E54319BD

Ключ раунда 66EAC1ABCE6429153E54319BD

Ключ раунда 76EAC1ABCE6429153E54319BD

Ключ раунда 86EAC1ABCE6429153E54319BD

Ключ раунда 99153E54319BD6EAC1ABCE642

Ключ раунда 109153E54319BD6EAC1ABCE642

Ключ раунда 119153E54319BD6EAC1ABCE642

Ключ раунда 129153E54319BD6EAC1ABCE642

Ключ раунда 13 9153E54319BD6EAC1ABCE642

Ключ раунда 149153E54319BD6EAC1ABCE642

Ключ раунда 159153E54319BD6EAC1ABCE642

Ключ раунда 166EAC1ABCE6429153E54319BD

Как показывает список, имеется восемь одинаковых ключей раунда в каждом полуслабом ключе. Кроме того, ключи раунда 1 в первом множестве - те же самые, что и ключи раунда 16 во втором; ключи раунда 2 в первом - те же самые, что и ключи раунда 15 во втором, и так далее. Это означает, что ключи инверсны друг другу: E_k2. (E_k1E (P)) = P, как показано на рис. 12.

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

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

1.3Многократное применение DES

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

Подстановка, которая размещает все возможные входы во все возможные выходы, является группой с отображениями элементов множества и набором операций. В этом случае использование двух последовательных отображений бесполезно, потому что мы можем всегда найти третье отображение, которое эквивалентно композиции этих двух (свойство замкнутости). Это означает, что если DES - группа, то однократный DES с ключом k₃ делает то же самое (рисунок 13).

К счастью DES - не группа. Она базируется на следующих двух параметрах:

а. Номер возможных входов или выходов в DES - N = 2⁶⁴. Это означает, что N!= (2⁶⁴)! = 10^{347 380 000 000 000 000 000} отображений. Один из способов способ сделать DES группой - это поддержать все эти отображения с размером ключа log₂ (2⁶⁴!) -- 2⁷⁰ битов. Но мы знаем, что длина ключа в DES - 56 бит (только маленькая часть этого требуемого огромного ключа).

б. Другой способ сделать DES группой - сделать, чтобы множество отображений было подмножеством множества в смысле зависимости от первого параметра; но было доказано, что группы, созданные из группы с помощью первого параметра, имеют ключевой размер 56 битов.

Если DES не является группой, то очень маловероятно, что мы можем найти ключ k₃, такой, что

E_k2(E_k1(P)) = E_k3(P)

Это означает, что мы можем использовать двукратные или трехкратные DES, чтобы увеличить размер ключа.

Двукратный DES

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

На первый взгляд двукратные DES увеличивают число испытаний при поиске ключа от 2⁵⁶ (в однократном DES) к 2¹¹² (в двукратном DES). Однако при использовании атаки знания исходного текста, называемой атакой сведения к середине, можно доказать, что двукратный DES улучшает эту устойчивость (до 2⁵⁷ по испытаниям), но не чрезвычайно (к 2¹¹²). Рисунок 8.14 показывает диаграмму для двукратного DES. Алиса использует два ключа, k₁ и k₂, чтобы зашифровывать исходный текст P в зашифрованный текст C; Боб использует зашифрованный текст C и два ключа, k₂ и k₁, для восстановления P.

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

M = E_K1(P) и M = E_K2(C)

Предположим, что Ева перехватила предыдущую пару P и C (атака знания исходного текста). Базируясь на первом отношении из упомянутых выше, Ева зашифровывает P, используя все возможные значения (2⁵⁶) k₁, и записывает все значения, полученные для М. Базируясь на вторых отношениях, упомянутых выше, Ева расшифровывает C, используя все возможные значения (2⁵⁶) k₂. Она записывает все значения, полученные для М. Далее Ева создает две таблицы, отсортированные согласно значениям M. Она сравнивает значения для М, пока не находит те пары k₁ и k₂, для которых значение М является одним и тем же в обеих таблицах (как показано на рис. 8.15). Обратите внимание, что должна быть по крайней мере одна пара, потому что она делает исчерпывающий поиск комбинации двух ключей.

1. Если есть только одно соответствие. Ева нашла два ключа (k₁ и k₂). Если есть больше чем один кандидат, Ева перемещается в следующий шаг.

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

Было доказано, что после применения второго шага к нескольким перехваченным парам "зашифрованный текст - исходный текст" ключи были найдены. Это означает, что вместо того чтобы использовать поиск ключей с помощью 2¹¹² испытаний, Ева использует 2⁵⁶ испытаний поиска ключа и проверяет два раза (несколько больше испытаний требуется, если найден на первом шаге единственный кандидат). Другими словами, двигаясь от однократного DES до двукратного DES, мы увеличили объем испытаний от 2⁵⁶ до 2⁵⁷ (а не до 2¹¹², как это кажется при поверхностном подходе).

Трехкратный DES

Для того чтобы улучшить безопасность DES, был предложен трехкратный DES (3DES). Он использует три каскада DES для шифрования и дешифрования. Сегодня используются две версии трехкратных DES: трехкратный DES с двумя ключами и трехкратный DES с тремя ключами.

Трехкратный DES с двумя ключами

В трехкратном DES с двумя ключами есть только два ключа: k₁ и k₂. Первый и третий каскады используют k₁; второй каскад использует k₂. Чтобы сделать трехкратный DES совместимым с DES, средний каскад применяет дешифрование (обратный шифр) на стороне шифрования и шифрование (шифр) на стороне дешифрования. Таким способом сообщение, зашифрованное DES-ключом k, может быть расшифровано трехкратным DES, если k₁ = k₂ = k. Хотя трехкратный DES с двумя ключами также уязвим при атаке "знания исходного текста", он гораздо устойчивее, чем двукратный DES. Он был принят для банков. Рисунок 16 показывает трехкратный DES с двумя ключами.

Трехкратный DES с тремя ключами

Возможность атак "знания исходного текста" при трехкратном DES с двумя ключами "соблазнила" некоторые приложения использовать трехкратный DES с тремя ключами. Алгоритм может применять три каскада шифра DES на стороне шифрования и три каскада обратных шифров на стороне дешифрования. Для совместимости с однократным DES сторона шифрования использует EDE, а сторона дешифрования -- DED. E (encryption) -- каскад шифрования, D (decryption) -- каскад дешифрования. Совместимость с однократным DES обеспечивается при k₁ = k и установкой k₂ и k₃ к одному и тому же произвольному ключу, выбранному приемником. Трехкратный DES с тремя ключами используется многими приложениями, такими как PGP (Pretty Good Privacy), поскольку гарантирует очень хорошую конфиденциальность.

1.4Безопасность DES

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

Атака грубой силы

Мы уже обсуждали слабость шифра с коротким ключом. Слабость ключа совместно с другими рассмотренными недостатками, делает очевидным, что DES может быть взломан с числом испытаний 2⁵⁵. Однако сегодня большинство приложений использует либо 3DES с двумя ключами (размер ключа 2¹¹²), либо 3DES с тремя ключами (размер ключа 2¹⁶⁸). Эти две многократных версии DES позволяют ему показывать существенную стойкость к атакам грубой силы.

Дифференциальный криптоанализ

DES не является устойчивым к такому виду атаки. Однако многое указывает, что разработчики DES уже знали об этом типе атаки и проектировали S-блоки и специально выбрали число раундов, чтобы сделать DES стойким к этому типу атаки. Сегодня показано, что DES может быть взломан, используя дифференциальный криптоанализ, если мы имеем 2⁴⁷ выборок исходного текста или 2⁵⁵ известных исходных текстов. Хотя это выглядит более эффективно, чем в атаке грубой силы, предположить, что кто-то знает 2⁴⁷ выборок исходного текста или 2⁵⁵ выборок исходного текста, практически невозможно. Поэтому мы можем сказать, что DES является стойким к дифференциальному криптоанализу. Также показано, что увеличение числа раундов до 20 увеличивает число требуемых выборок исходного текста для атаки более чем до 2⁶⁴. Такое увеличение невозможно, потому что число блоков исходного текста в DES только 2⁶⁴.

Линейный криптоанализ

Линейный криптоанализ - более новая методика, чем дифференциальный криптоанализ. DES более уязвим к применению линейного криптоанализа, чем к дифференциальному криптоанализу - вероятно потому, что этот тип атак не был известен проектировщикам DES и S-блоки не являются очень стойкими к линейному криптоанализу. Показано, что DES может быть взломан с использованием 2⁴³ пары известных исходных текстов. Однако с практической точки зрения перехват такого количества пар очень маловероятен.

Заключение