Алгоритм Double DES

Наиболее логичным способом противодействия полному перебору ключа DES выглядит многократное зашифровывание данных алгоритмом DES с различными ключами. Следующий алгоритм получил название Double DES (двойной DES):

где:

?                    — половины двойного ключа алгоритма Double DES, каждая из которых представляет собой обычный 56-битный ключ DES;

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

для любых значений, то двойное шифрование не приводило бы

к усилению против полного перебора ключа — всегда нашелся бы такой ключ к, однократное зашифровывание которым было бы эквивалентно двукратному шифрованию на ключах, а для нахождения ключа к достаточно было бы перебрать 255 ключей. К счастью, DES не обладает таким свойством, что доказано в [112] и [188], поэтому Double DES действительно удваивает эффективный размер ключа— до 112 битов, а при современном развитии вычислительной техники полный перебор 112-битного ключа невозможен.

Однако у Double DES есть другая проблема — атака «встреча посередине», предложенная известными криптологами Ральфом Мерклем и Мартином Хеллманом [266]. С помощью этой атаки криптоаналитик может получить k\j2 и ?2/2 ПРИ наличии всего двух пар открытого текста и шифртекста Х,С\) и (М22) следующим образом (см. также разд. 1.6):

1.     Выполняется зашифровывание Ekx(Ml) на всем ключевом пространстве с записью результатов в некоторую таблицу.

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

3.     Если какой-либо результат, полученный на шаге 2, совпал с одним из результатов шага 1, то можно предположить, что нужный ключ найден, т. е. найдены соответствующие совпадающему резальтату

Однако таких совпадений может быть много, их количество оценивается в [3] как 248.

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

до

приводящих к совпадениям (т. е. примерно 2 ). Вероятность наличия более, чем одного совпадения после повторного перебора оценивается в [3] как 2~16.

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100