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

DES обладает следующим свойством: если E_K(P) = C, то E_K'(P') = C', где P', C' и K' - побитовые дополнения P, C и K. Это свойство вдвое уменьшает сложность вскрытия грубой силой. Свойства комплиментарности алгоритма LOKI уменьшают сложность вскрытия грубой силой в 256 раз.

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

Если E_K(P) = C, то E_f(K) (g(P,K)) = h(C,K)

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

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

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

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

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

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

Слабые ключи

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