DEAL

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
DEAL
изображение
Создатель:

Кнудсен, Ларс

Создан:

1997 г.

Опубликован:

1998 г.

Размер ключа:

128/192/256 бит

Размер блока:

128 бит

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

6 (для ключа в 128/192 бит), 8 (для 256 бит)

В криптографии, DEAL (Алгоритм Шифрования Данных с Крупными блоками — англ. Data Encryption Algorithm with Larger blocks) — это блочный шифр, производный от DES. DEAL был впервые представлен Ларсом Кнудсеном в виде доклада на конференции Selected Areas in Cryptography в 1997 году. Впоследствии этот же алгоритм был представлен Ричардом Аутербриджем на конкурсе AES в 1998 году.

DEAL представляет собой сеть фейстеля использующую DES как функцию в раунде сети. Удовлетворяя требованиям AES, DEAL имеет длину блока 128 бит и длину ключа 128, 192 или 256 бит. В случае длины в 128 или 192 бит используется 6 раундов, в случае 256 бит — 8 раундов. Алгоритм сопоставим по производительности с Triple DES, но по сравнению с конкурентами в конкурсе AES алгоритм оказывается довольно медленным.

Предпосылки к созданию[править | править исходный текст]

К 1998 году стало ясно, что существовавший до этого на правах стандарта шифр DES совершенно не удовлетворяет требованиям времени. Было показано, что за сумму порядка одного миллиона долларов можно создать устройство, перебирающее все ключи DES меньше чем за 3,5 часа. Существовавшая альтернатива — т. н. «тройной DES» так же не обеспечивал требуемой надежности, так как (в некоторых режимах своей работы) уязвим к атаке по подобранному шифро-тексту. Учитывая широкую распространенность DES к тому моменту (в том числе в виде эффективных аппаратных реализаций) Ларсом Кнудсеном был предложен шифр DEAL — шифр с Фейстелевой структурой, использующий DES в качестве раундовой функции и имеющий r раундов. Таким образом DEAL представляет собой шифр с размером блока 128 бит и r — 64 битами раундовых ключей, вычисляемых с помощью алгоритма расписания ключей. Расписание ключей предусматривает что размер исходного ключа один принимает одно из трех различных значений: 128, 192 или 256 бит. Для первых двух размеров ключей предлагалось положить r = 6, а при размере ключа 256 бит r = 8. Полученный таким образом ключ по скорости сопоставим с Triple DES

Алгоритм[править | править исходный текст]

Режимы работы с ключами длиной 128, 192 и 256 бит обозначаются соответственно DEAL-128, DEAL-192 и DEAL-256. Каждая из модификаций с разными длинами ключа может использовать все четыре стандартных режима DES-а.

Режим ECB[править | править исходный текст]

Рассмотрим первый режим работы — ECB (Electronic Code Book). Обозначим С =  E_B (А) результат шифрования 64-битного блока А на ключе В, и Y =  EA_Z (X) — результат шифрования с помощью DEAL-128 блока X на ключе Z. Согласно требованиям AES, исходный текст Р разбивается на блоки P_i по 128 бит каждый,  P = P_1, P_2,.. , P_n Из исходного ключа K с помощью расписания ключей получается r ключей для работы DES RK_i, где i = 1, … , r. Алгоритм расписания описан ниже. Обозначим X^L и X^R «правую» и «левую» части блока Х соответственно. Шифрование описывается следующими выражениями:
Положим X^R_0 = P^R_i и X^L_0 = P^L_i, и вычислим для j = 1,.. ,r

X^L_j = E_{RK_i}(X^L_{j-1}) \oplus X^R_{j-1}
X^R_j = X^L_{j-1}

Положим  C_i = X^L_r \parallel X^R_r

Один раунд DEAL

На рисунке изображена одна итерация цикла для DEAL. Для DEAL-128 и DEAL-192 используются 6 циклов, полагая r = 6. Однако, такого количества раундов может оказаться недостаточно для DEAL-256, в котором необходимо использовать большее количество раундов: r = 8. По замыслу разработчиков DEAL-256 должен использоваться только когда требуется особенно сильное шифрование.

В заключительном раунде DEAL «правая» и «левая» половинки блока так же меняются (а не остаются на местах как в DES). Это обусловлено следующем: «правая» часть шифруемого блока  C_i не шифруется в последнем раунде i-ого прохода DEAL, и только «левая» половина блока на i + 1-м проходе (исходный блок которого равен  C_i  \oplus P_{i+1} ) шифруется в первом раунде. Это означает, что «правая» часть  C_i не будет шифроваться вообще в течение двух раундов. Это можно рассматривать как уязвимость алгоритма, учитывая что с DEAL используется всего 6 или 8 раундов. Подобной «особенностью» обладает и DES в режиме CBC. Но, учитывая что у DES 16 раундов, это не становиться столь яркой уязвимостью. Так или иначе — эта перестановка не влияет на стойкость блочного шифра в режиме ECB

Режим CBC[править | править исходный текст]

Итак, обозначим блоки открытого текста по 128 бит   P_1, P_2,.. , P_n и  C_1, C_2,.. , C_n — соответствующие им блоки шифр-текста. Тогда используя рекуррентное соотношение:  C_i = EA_K(C_{i-1} \oplus P_i)  , где  C_0 — начальное значение
получаем шифроблоки в режиме CBC.

Расписание ключей[править | править исходный текст]

Входными параметрами для расписания ключей являются s ключей DES, каждый по 56 бит плюс 8 «проверочных» бит. Для разных исходных длин ключа s = 2, 3, 4, и входные ключи обозначаются:  K_1,.. , K_s . На выходе получаем r ключей DES, RK_i. Расписание ключей единообразно для всех трех длин исходного ключа. Сначала расширяем s ключей до r ключей, создавая отсутствующие ключи операцией XOR с новой константой для каждого нового ключа. Константа используется чтобы исключить слабые ключи. К полученным ключам применим DES в режиме CBC с фиксированным ключом и нулевым начальным значением. Из полученных блоков шифр-текста и формируются подключи  RK_i. Далее — точные описания вышеописанных операций. Здесь  K = 0x1234 5678 90ab cdef_x (шестнадцатеричное число) — фиксированный ключ для DES.
В DEAL-128 подключи генерируются следующим образом:

 RK_1 = E_k(K^1_1),
 RK_2 = E_k(K_2 \oplus RK_1),
 RK_3 = E_k(K_1 \oplus \langle 1 \rangle \oplus RK_2),
 RK_4 = E_k(K_2 \oplus \langle 2 \rangle \oplus RK_3),
 RK_5 = E_k(K_1 \oplus \langle 4 \rangle \oplus RK_4),
 RK_6 = E_k(K_2 \oplus\langle 8 \rangle \oplus RK_5),

где  \langle i \rangle — 64-х битное целое число, в котором i — 1-й бит (нумерация с 0) установлен в «1», а остальные — в «0». Например,  \langle 1 \rangle может быть представлено как шестнадцатеричное « K = 0x8000 0000 0000 0000_x».


В DEAL-192 подключи генерируются следующим образом:

 RK_1 = E_k(K^1_1),
 RK_2 = E_k(K_2 \oplus RK_1),
 RK_3 = E_k(K_1 \oplus  \oplus RK_2),
 RK_4 = E_k(K_2 \oplus \langle 1 \rangle \oplus RK_3),
 RK_5 = E_k(K_1 \oplus \langle 2 \rangle \oplus RK_4),
 RK_6 = E_k(K_3 \oplus\langle 4 \rangle \oplus RK_5),


В DEAL-256 подключи генерируются следующим образом:

 RK_1 = E_k(K^1_1),
 RK_2 = E_k(K_2 \oplus RK_1),
 RK_3 = E_k(K_3 \oplus RK_2),
 RK_4 = E_k(K_4 \oplus RK_3),
 RK_5 = E_k(K_1 \oplus \langle 1 \rangle \oplus RK_4),
 RK_6 = E_k(K_2 \oplus \langle 2 \rangle \oplus RK_5),
 RK_7 = E_k(K_3 \oplus \langle 4 \rangle \oplus RK_6),
 RK_8 = E_k(K_4 \oplus \langle 8 \rangle \oplus RK_7),

Таким образом для генерации раундовых ключей DEAL необходимо 8 «проходов» DEAL. Чтобы не тратить процессорное время эти ключи следует сохранить для всего процесса шифрования или расшифрования.


Стойкость алгоритма[править | править исходный текст]

Анализ алгоритма показал множество недостатков: наличие подмножеств слабых ключей, подверженность дифференциальному криптоанализу, отсутствие усиления при использовании 192-битных ключей по сравнению с 128-битными. Во-первых, алгоритм расписания ключей не дает достаточно сильных ключей. Действительно, в случае «нулевого» исходного ключа DEAL раундовые ключи получаются слабыми: у первых трех только один-два бита отличаются от нулей. Во-вторых, после разбиения исходного блока на два по 64 бита, полученные шифротексты «сшиваются» либо с помощью CBC, либо конкатенацией. Разумеется такая схема уязвима для дифференциального анализа. Получаемая надежность оказывается порядка 2^{65} , вместо 2^{128} .

В связи с этими недостатками шифр DEAL не смог пройти в финал конкурса AES, и не рассматривался как кандидат в промышленный стандарт. Но тем не менее он получил некоторое распространение.

Литература[править | править исходный текст]

Ссылки[править | править исходный текст]