Алгоритмы DES, Triple DES и их заменяющие.

Digital Encryption Standard

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

Появление компьютеров сделало возможным отказаться от старых прие­мов криптографии и создать новую парадигму. Исследователи из IBM под руководством криптографа Хорста Фейстеля разработали новый алгоритм под названием Lucifer специально для компьютеров. Они также прибегли к помощи Управления национальной безопасности (NSA — National Secu­rity Agency), которое обеспечивает защиту секретных данных Правительст­ва США, что в свою очередь предполагает использование криптографии. Ре­зультатом работы совместной команды стало появление DES.

DES — это блочный шифр, использующий 56-битный ключ — ни боль­ше, ни меньше — для построения таблицы ключей. Используя таблицу ключей, DES выполняет битовые операции под открытым текстом. Чтобы расшифровать шифротекст, все действия следует выполнить в обратном порядке.

После своего появления DES стал свободно доступным и подвергся все­стороннему изучению. В 80-х годах криптографы пришли к выводу, что он не имеет слабых мест. Это означало, что самым быстрым способом взлома сообщения, зашифрованного с помощью DES, является атака методом пря­мого перебора. Поскольку 56-битному ключу соответствует число в диапа­зоне от 0 до примерно 72 квадрильонов, даже самым быстрым компьюте­рам того времени требовалось несколько лет, чтобы взломать одно сообще­ние.

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

Как уже упоминалось, в 1999 г. на конференции, организованной RSA компания Electronic Frontier Foundation взломала ключ DES менее чем за 24 часа. Встала необ­ходимость замены алгоритма.

Алгоритм Triple DES

Одной из замен DES, получившей широкое распространение, стал алго­ритм Triple (тройной) DES, Название говорит само за себя: Triple DES вы­полняет алгоритм DES три раза. Вот как это происходит. Вы пропускаете ваш блок данных через DE3 с использованием ключа, а затем зашифровы­ваете этот результат с помощью другого ключа DES. Затем вы делаете это в третий раз (см. рис. 29).

Рис. 29. Triple DES. Троекрат­ное применение алго­ритма DES

При этом используются три ключа, каждый из которых состоит из 56 битов. Это, по сути, соответствует использованию 168-битного ключа. Можно подумать, что если для взлома одного ключа требуется 24 часа, то взлом трех ключей должен занять 72 часа. Однако это не так. Для взлома одного ключа потребуется 24 часа, если вы будете знать, что взломали его. Но при использовании Triple DES вы не узнаете, что нашли первый ключ, пока не примените два оставшихся ключа.

Представим это следующим образом. Допустим, есть три ключа, назо­вем их А, В и С, а каждое возможное значение ключа находится в диапазо­не от 0 до 72 квадрильонов. Предположим также, что корректной комби­нацией ключей является А=1, В=33717 и С=1419222. Атакующий может испробовать значение 0 для ключа А, значение 0 для ключа В и значение 0 для ключа С. Это не дает верного ответа, поэтому он испробует комбина­цию А=1, В=О и С=0. Как показано на рис. 30, первый ключ правиль­ный. Но значение, которое атакующий получил в результате применения комбинации из трех ключей, не является верным значением. Правильный открытый текст появится только в том случае, если все три ключа верны. Но как атакующий узнает, что первый ключ правильный?

Рис. 30. Чтобы взломать Triple DES, нужно знать все три ключа

Для Triple DES, однако, имеются две проблемы. Во-первых, криптоана-литики обнаружили способ, позволяющий сделать атаку прямого перебора более эффективной. Первоначально считалось, что эт<1 атака эквивалентна атаке на 168-битный ключ, однако есть возможность сделать такую атаку эквивалентной атаке на 108-битный ключ. 108-битный ключ по-прежнему обеспечивает защиту (см. таблицу пункта 3.11.1, где даны оценки для наихудшего случая при атаке на 108-битный ключ), но это слабое место вызывает бес­покойство. Что, если дальнейшие исследования криптоаналитиков выявят дополнительные слабые места? Не будут ли еще больше скомпрометирова­ны защитные свойства Triple DES?

Второй проблемой является скорость. Алгоритму DES требуется доста­точно длительное время для того, чтобы зашифровать или расшифровать данные, a Triple DES для этого требуется в три раза больше времени. Для некоторых приложений необходимо с высокой скоростью передавать мега­байты важной информации. Triple DES настолько снижает производитель­ность, что некоторые приложения просто не могут работать.

По этим двум причинам потребовался новый алгоритм.