Ключи-дополнения

Выполним побитное дополнение ключа, заменяя все 0 на 1 и все 1 - на 0. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение блока открытого текста в дополнение блока шифротекста. Если x' обозначает дополнение x, то следующее верно:

E_K(P) = C

E_K'(P') = C'

В этом нет ничего таинственного. На каждом этапе после перестановки с расширением подключи подвергаются операции XOR с правой половиной. Прямым следствием этого факта и является приведенное свойство комплиментарности.

Это означает, что при выполнении вскрытия DES с выбранным открытым текстом нужно проверять только половину возможных ключей: 2⁵⁵ вместо 2⁵⁶ [1080]. Эли Бихам (Eli Biham) и Ади Шамир показали [172], что существует вскрытие с известным открытым текстом, имеющее ту же сложность, для которого нужно не меньше 2³³ известных открытых текстов.

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