Слабые ключи

Групповая структура

Простые соотношения

DES обладает следующим свойством: если Е^Р) = С, то Е_К{Р^Г) = С, где Р', С" и К' - побитовые дополнения Р,СиК. Это свойство вдвое уменьшает сложность вскрытия грубой силой. Свойства комплиментарности алг о-ритма LOKI уменьшают сложность вскрытия грубой силой в 256 раз.

Простое соотношениеможно определить как [857]:

Если Eg{P) = С, то Е_т (g(P,K)) = h(C,K)

где/; g и h - простые функции. Под "простыми функциями" я подразумеваю функции, которые вычисляются легко, намного легче, чем выполнение итерации блочного шифра. В DES f представляет собой побитовое л о-полнение К, g - побитовое дополнение Р, a h - побитовое дополнение С. Это является результатом вкрапления ключа в часть текста с помощью XOR.

Для хорошего блочного шифра не существует простых соотношений. Методы поиска некоторых из подобных слабых мест можно найти в [917].

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

Полезным, однако, является не вопрос о том, действительно ли алгоритм является группой, а о том, наскол ь-ко он близок к группе. Если не хватает только одного элемента, то алгоритм не образует группу, но двойное шифрование было бы - статистически говоря - просто потерей времени. Работа над DES показала, что DES очень далек от группы. Существует также ряд интересных вопросов о полугруппе, получаемой при шифровании DES. Содержит ли она тождество, то есть, не образует ли она группу? Иными словами, не генерирует ли когда-нибудь некоторая комбинация операций шифрования (не дешифрирования) тождественную функцию? Если так, насколько длинна самая короткая такая комбинация?

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

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