Стандарт шифрования данных (DES)

Раунды

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

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

Функция DES

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

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

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

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

S-блоки. S -блоки смешивают информацию (операция перемешивания). DES использует S -блоки, каждый с 6 -ю входными битами и 4 -мя выходными (см. рис. 8.7).

Данные из 48 битов от второй операции DES разделены на восемь кусков по 6 битов, и каждый кусок поступает в блок. Результат каждого блока — кусок на 4 бита; когда они объединены, результат выражается в 32 -битовом тексте. Подстановка в каждом блоке следует по заранее определенным правилам, основанным на таблице из 4 -х строк и 16 -ти столбцов. Комбинация битов 1 и 6 на входе определяет одну из четырех строк; комбинация битов от 2 -го до 5 -го определяет один из шестнадцати столбцов, как показано на рис. 8.8. Далее мы поясним это примерами.

Поскольку для каждого S -блока есть собственная таблица, необходимо иметь восемь таблиц, например таких, как это показано в таблицах 8.3-8.10. Значение входа (номер строки и номер столбца) и значения выхода даются как десятичные номера, чтобы сэкономить место на странице. В реальности они могут быть заменены двоичными числами.

Пример 8.3

Входная последовательность S блока 1 — $$\underline 1 0001\underline 1$$. Какая последовательность будет на выходе?

Решение

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

Пример 8.4

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

Решение

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

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

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

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

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

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

Мы доказали в лекции 7, что смеситель и устройство замены самоинверсны. Конечные и начальные перестановки также инверсны друг другу. Левая секция исходного текста на стороне шифрования шифруется L0 как L16, и L16 дешифруется на стороне дешифратора как L0. Аналогичная ситуация с R0 и R16.

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

Алгоритм

Алгоритм 8.1. приведен в псевдокодах для шифрования и соответствует четырем шагам первого метода. Коды для остальных могут быть сделаны как упражнение.

Cipher (plainBlock[64], Round Keys[16,48])
{
   pemute (64,64, plainBlock, inBlock, IntialPermutationTable)
   spilt (64, 32, inBlock, leftBlock, right Block)
   for (round = 1 to 16)
   {
      mixer (leftBlock, right Block, RoundKey[round])
      if (round!=16) swapper(leftBlock, right Block)
   }
   combine (32, 64, leftBlock, right Block, outBlock)
   pemute (64,64, outBlock, cipherBlock, FinalPermutationTable)

mixer (leftBlock[48], right Block[48], RoundKey[48])
{
   copy (32, rightBlock, T1)
   function (T1, RoundKey,T2)
   exclusive Or (32, leftBlock, T2,T3)
   copy (32, rightBlock, T1)
}

swapper (leftBlock[32], right Block[32])
{
   copy (32, leftBlock, T)
   copy (32, rightBlock, leftBlock)
   copy (32, T, rightBlock)
}

Substitute (in block[32], outblock[48], SubstituteTables[8,4,16])
{
   for(I = 1 to 8)
   {
      row <- 2 x inBlock[i x 6+1] + inBlock[i x 6+6]
      col <- 8 x inBlock[i x 6+2] + 4 x inBlock[i x 6+3]+2 x inBlock[i x 6+4] + inBlock[i x 6+5]

      value = SubstituteTables[i][row][col]

      outBlock[i x 4+1] <- value/ 8         value <- value mod 8
      outBlock[i x 4+2] <- value/ 4         value <- value mod 4
      outBlock[i x 4+3] <- value/ 2         value <- value mod 8
      outBlock[i x 4+4] <- value
   }
}
}

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

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

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

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

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

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

Сдвиг влево

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

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

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

Алгоритм

Теперь напишем простой алгоритм для создания ключа из ключа с проверочными битами. Алгоритм 8.2 использует несколько процедур алгоритма 8.1. Имеется и одна новая процедура — левый сдвиг ( ShiftLeft ). Обратите внимание, что T — временный блок.

Key_Generator (keyWithParities[64], RoundKeys[16. 48]. SinfTable[16])
 {                                                      '                  
 permute (64, 56, keyWithParities, cipherKey, ParityDropTable)
spilt (56, 28, cipherKey, leftKey, rightKey) 
for (round = 1 to 16) 
   {                                                                      
   shiftLeft (leftKey, ShiftTable[round1])                                    I
   shiftLeft (rightKey, ShiftTable [round])
   combine (28, 56, leftKey, rightKey, preRoundKey)
   permute (56, 48, preRoundKey, RoundKeys[round], KevCompressionTable)
   }
}

shiftLeft (block[28], NumOfShifts)
{
   for (i = 1 to numShifts)
   {
      T <- block[ 1]
      for (j = 2 to 28)
      {
          block [j-1] <- block [j]
      }
      block[28] <- T
   }
}

Примеры

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

Пример 8.5

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

Plaintext: 123456ABCD 132536	Key: AABB09182736CCDD
Cipher Text: COB7ASD05F3AS29C

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

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

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

Пример 8.6

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

8.3. Анализ DES

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

Свойства

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

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

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

Пример 8.7

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

Исходный текст: 0000000000000000              Ключ: 22234512987ABB23
Зашифрованный текст: 4789FD476E82A5F1

Исходный текст: 0000000000000001              Ключ: 22234512987ABB23
Зашифрованный текст: OA4ED5C15A63FEA3

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

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

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

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

Проект DES был предъявлен IBM в 1994 году. Многочисленные испытания DES показали, что он удовлетворяет некоторым из заявленных критериев. Ниже кратко обсуждаются некоторые проблемы разработок DES.

S-блоки

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

P-блоки

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

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

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

Слабости DES

В течение прошлых нескольких лет критики нашли некоторые слабости в DES.

Мы кратко укажем на некоторые слабости, которые были обнаружены в структуре шифра.

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

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

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

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

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 ).

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

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

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

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

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

Пример 8.8

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

Ключ: 0x0101 0101 0101 0101	
Зашифрованный текст: 0x814FE938589154F7
Исходный текст: 0xl234.56887654321	
	
Ключ: 0x0101 0101 0101 0101	
Исходный текст: 0x814FE938589154F7	
Зашифрованный текст: 0xl234.56887654321

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

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

Ключ раунда 1	9153E54319BD 	6EAC1ABCE642
Ключ раунда 2	6EAC1ABCE642	9153E54319BD
Ключ раунда 3	6EAC1ABCE642	9153E54319BD
Ключ раунда 4	6EAC1ABCE642	9153E54319BD
Ключ раунда 5	6EAC1ABCE642	9153E54319BD
Ключ раунда 6	6EAC1ABCE642	9153E54319BD
Ключ раунда 7	6EAC1ABCE642	9153E54319BD
Ключ раунда 8	6EAC1ABCE642	9153E54319BD
Ключ раунда 9	9153E54319BD	6EAC1ABCE642
Ключ раунда 10	9153E54319BD	6EAC1ABCE642
Ключ раунда 11	9153E54319BD	6EAC1ABCE642
Ключ раунда 12	9153E54319BD	6EAC1ABCE642
Ключ раунда 13 	9153E54319BD	6EAC1ABCE642
Ключ раунда 14	9153E54319BD	6EAC1ABCE642
Ключ раунда 15	9153E54319BD	6EAC1ABCE642
Ключ раунда 16	6EAC1ABCE642	9153E54319BD

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

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

Пример 8.9

Какова вероятность случайного выбора слабого, полуслабого или возможно слабого ключа?

Решение

Множество ключей DES равно 256. Общее количество вышеупомянутых ключей — 64 (4 + 12 + 48). Вероятность выбора одного из этих ключей равна $$8,8 \times {10^{ - 16}}$$, т.е. исключительно мала.

Ключевое дополнение. Среди множества ключей (256) некоторые ключи могут быть получены инверсией (изменение из 0 в 1 или 1 в 0 ) каждого бита в ключе. Ключевое дополнение упрощает процесс криптоанализа. Ева может использовать только половину возможных ключей ( 255 ), чтобы выполнить атаку грубой силы, потому что

C=E(K,P) ->  C=E(K,P)

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

Пример 8.10

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

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

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

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

Как мы узнали в лекции 7, подстановка, которая размещает все возможные входы во все возможные выходы, является группой с отображениями элементов множества и набором операций. В этом случае использование двух последовательных отображений бесполезно, потому что мы можем всегда найти третье отображение, которое эквивалентно композиции этих двух (свойство замкнутости). Это означает, что если DES — группа, то однократный DES с ключом k3 делает то же самое (рисунок 8.13).

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

а. Номер возможных входов или выходов в DES — N = 264. Это означает, что N!= (264)! = 10347 380 000 000 000 000 000 отображений. Один из способов способ сделать DES группой — это поддержать все эти отображения с размером ключа log2 (264!) — 270 битов. Но мы знаем, что длина ключа в DES — 56 бит (только маленькая часть этого требуемого огромного ключа).

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

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

Ek2(Ek1(P)) = Ek3(P)

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

Двукратный DES

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

На первый взгляд двукратные DES увеличивают число испытаний при поиске ключа от 256 (в однократном DES) к 2112 (в двукратном DES). Однако при использовании атаки знания исходного текста, называемой атакой сведения к середине, можно доказать, что двукратный DES улучшает эту устойчивость (до 257 по испытаниям), но не чрезвычайно (к 2112 ). Рисунок 8.14 показывает диаграмму для двукратного DES. Алиса использует два ключа, k1 и k2, чтобы зашифровывать исходный текст P в зашифрованный текст C ; Боб использует зашифрованный текст C и два ключа, k2 и k1, для восстановления P.

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

M = EK1(P) и M = EK2(C)

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

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

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

Было доказано, что после применения второго шага к нескольким перехваченным парам "зашифрованный текст — исходный текст" ключи были найдены. Это означает, что вместо того чтобы использовать поиск ключей с помощью 2112 испытаний, Ева использует 256 испытаний поиска ключа и проверяет два раза (несколько больше испытаний требуется, если найден на первом шаге единственный кандидат). Другими словами, двигаясь от однократного DES до двукратного DES, мы увеличили объем испытаний от 256 до 257 (а не до 2112, как это кажется при поверхностном подходе).

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

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

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

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

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

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

8.5. Безопасность DES

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

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

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

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

Мы в лекции 7 уже обсуждали методику дифференциального криптоанализа для современных блочных шифров. DES не является устойчивым к такому виду атаки. Однако многое указывает, что разработчики DES уже знали об этом типе атаки и проектировали S -блоки и специально выбрали число раундов, чтобы сделать DES стойким к этому типу атаки. Сегодня показано, что DES может быть взломан, используя дифференциальный криптоанализ, если мы имеем 247 выборок исходного текста или 255 известных исходных текстов. Хотя это выглядит более эффективно, чем в атаке грубой силы, предположить, что кто-то знает 247 выборок исходного текста или 255 выборок исходного текста, практически невозможно. Поэтому мы можем сказать, что DES является стойким к дифференциальному криптоанализу. Также показано, что увеличение числа раундов до 20 увеличивает число требуемых выборок исходного текста для атаки более чем до 264. Такое увеличение невозможно, потому что число блоков исходного текста в DES только 264.

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

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

8.6. Рекомендованная литература

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

Книги

[Sta06], [Sti06], [Rhe03], [Sal03], [Mao04] и [TW06] — это книги, которые рассматривают DES.

Сайты

Нижеследующие сайты содержат боле подробную информацию о темах, обсужденных в этой лекции,

8.7. Итоги

8.8. Набор для практики

Обзорные вопросы

Упражнения

permute (n,m, inBlock [n], outBlock [m], permutationTable [m])

spilt(n, m, inBlock [n], leftBlock, rightBlock [m])

combine (n, m, leftBlock [n], rightBlock [n1, outBlock [m])

exclusiveOr (n, firstInBlock [n], второй! nBlock [n], outBlock [n])