Алгоритм шифрирование DES

Схема расшифрования

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

R_{i − 1} = L_i 

Схема расшифрования  указана на Рис.6. 
Ключ k_i, i=1,…,16, функция f, перестановка IP и IP ^{− 1} такие же как и в процессе шифрования.

Режимы использования DES

DES может использоваться  в четырёх режимах.

1. Режим электронной кодовой книги (ECB — Electronic Code Book): обычное использование DES как блочного шифра. Шифруемый текст разбивается на блоки, при этом, каждый блок шифруется отдельно, не взаимодействуя с другими блоками (см. Рис.7).

Рис.7 Режим электронной кодовой книги — ECB

2. Режим сцепления блоков (СВС — Cipher Block Chaining) (см. Рис.8). Каждый очередной блок C_i i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста M_{i + 1}. Вектор C₀ — начальный вектор, он меняется ежедневно и хранится в секрете.

Рис.8 Режим сцепления блоков — СВС

3. Режим обратной связи по шифротексту (англ. Cipher Feed Back) (см. Рис.9). В режиме CFB вырабатывается блочная «гамма» Z₀,Z₁,...Z_i = DES_k(C_{i − 1}) . Начальный вектор C₀ является синхропосылкой и предназначен для того, чтобы разные наборы данных шифровались по-разному с использованием одного и того же секретного ключа. Синхропосылка посылается получателю в открытом виде вместе с зашифрованным файлом.

Рис.9 Режим обратной связи по шифротексту — CFB

4. Режим обратной связи по выходу (OFB — Output Feed Back) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» Z₀,Z₁,... , i>=1

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

Достоинства и недостатки режимов:

• В режимах ECB и OFB искажение при передаче одного 64-битового блока шифротекста C_i приводит к искажению после расшифрования только соответствующего открытого блока M_i, поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.

Криптостойкость алгоритма DES

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

• Каждая строка каждого блока должна быть перестановкой множества {0, 1, 2, …, 15}
• S-блоки не должны являться линейной или афинной функцией своих аргументов.
• Изменение одного бита на входе S-блока должно приводить к изменению по крайней мере двух битов на выходе.
• Для каждого S-блока и любого аргумента х значение S(x) и должны различаться по крайней мере двумя битами.

Из-за небольшого числа возможных ключей (всего 2⁵⁶), появляется возможность их полного перебора на быстродействующей вычислительной технике за реальное время. В 1998 году Electronic Frontier Foundation используя специальный компьютер DES-Cracker, удалось взломать DES за 3 дня.

Слабые ключи

Слабыми ключами  называется ключи k такие, что DES_k(DES_k(x)) = x, где x — 64-битный блок.

Известны 4 слабых ключа, они приведены в таблице 9. Для каждого слабого ключа  существует 2³² неподвижные точки, то есть, таких 64-битных блоков х, для которых DES_k(x) = x.

[0]²⁸ обозначает вектор, состоящий из 28 нулевых битов.

Частично слабые ключи

В алгоритме DES существуют слабые и частично слабые ключи. Частично-слабые ключи — это такие пары ключей (k₁,k₂), что DES_k1(DES_k2(x)) = x.

Существуют 6 частично-слабых пар ключей, они  приведены в таблице 10. Для каждого  из 12 частично-слабых ключей существуют 2³² «анти-неподвижные точки», то есть такие блоки х, что

Известные атаки на DES

• Метод полного перебора требует одну известную пару шифрованного и расшифрованного текста, незначительный объём памяти, и его выполнение требует около 2⁵⁵ шагов.
• Дифференциальный криптоанализ — первую такую атаку на DES заявили Biham и Shamir. Эта атака требует шифрования 2⁴⁷ открытых текстов выбранных нападающим, и для её выполнения нужны примерно 2⁴⁷ шагов. Теоретически являясь точкой разрыва, эта атака непрактична из-за чрезмерных требований к подбору данных и сложности организации атаки по выбранному открытому тексту. Сами авторы этой атаки Biham и Shamir заявили, что считают DES защищенным для такой атаки.
• Линейный криптоанализ разработан Matsui. Этот метод позволяет восстановить ключ DES с помощью анализа 2⁴³ известных открытых текстов, при этом требуется примерно 2⁴³ шагов для выполнения. Первый экспериментальный криптоанализ DES, основанный на открытии Matsui, был успешно выполнен в течение 50 дней на автоматизированных рабочих местах 12 HP 9735.

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

Увеличение криптостойкости DES

Чтобы увеличивать криптостойкость DES появляются несколько вариантов: double DES (2DES), triple DES (3DES), DESX, G-DES.

• Методы 2DES и 3DES основаны на DES, но увеличивают длину ключей (2DES — 112 бит, 3DES — 168 бит) и поэтому увеличивается криптостойкость.
• Схема 3DES имеет вид DES(k₃,DES(k₂,DES(k₁,M))), где k₁,k₂,k₃ ключи для каждого шифра DES. Это вариант известен как в ЕЕЕ так как три DES операции являются шифрованием. Существует 3 типа алгоритма 3DES:

• DES-EEE3: Шифруется три раза с 3 разными ключами.
• DES-EDE3: 3DES операции шифровка-расшифровка-шифровка с 3 разными ключами.
• DES-EEE2 и DES-EDE2: Как и предыдущие, за исключением того, что первая и третья операции используют одинаковый ключ.

Самый популярный тип при использовании 3DES — это DES-EDE3, для него алгоритм выглядит так:

Зашифрование: .

Расшифрование:

При выполнении алгоритма 3DES ключи могут выбрать  так:

• k₁,k₂,k₃ независимы.
• k₁,k₂ независимы, а k₁ = k₃
• k₁ = k₂ = k₃.

• Метод DESX создан Рональдом Ривестом и формально продемонстрирована Killian и Rogaway. Этод метод — усиленный вариант DES, поддерживаемый инструментарием RSA Security. DESX отличается от DES тем, что каждый бит входного открытого текста DESX логически суммируется по модулю 2 с 64 битами дополнительного ключа, а затем шифруется по алгоритму DES. Каждый бит результата также логически суммируется по модулю 2 с другими 64 битами ключа. Главной причиной использования DESX является простой в вычислительном смысле способ значительного повысить стойкость DES к атакам полного перебора ключа.

• Метод G-DES разработан Schaumuller-Bichl для повышения производительности DES на основе увеличения размером шфрованного блока. Заявлялось, что G-DES защищен так же как и DES. Однако, Biham и Shamir показали, что G-DES с рекомендуемыми параметрами легко взламывается, а при любых изменениях параметров шифр становится ещё менее защищен чем DES.
• Ещё другой вариант DES использует независимые суб-ключи. Различно от алгоритма DES, в котором на основе 56-битного секретного ключа пользователя алгоритм DES получает шестнадцать 48-битных суб-ключей для использования в каждом из 16 раундов, в этом варианте использует 768-битного ключа (разделенного на 16 48-битных подключей) вместо 16 зависимых 48-битных ключей, создаваемых по ключевому графику алгоритма DES. Хотя очевидно, что использование независимых суб-ключей значительно усложнит полный поиск ключа, но стойкость к атаке дифференциальным или линейным криптоанализом не намного превысит стойкость обычного DES. По оценке Biham для дифференциального криптоанализа DES с независимыми подключами требуется 2⁶¹ выбранных открытых текстов, в то время как для линейного криптоанализа требуется 2⁶⁰ известных открытых текстов.