Se al posto della chiave k, nel DES, si considera la chiave ¬k(complemento bit a bit di k), allora si può osservare il seguente fenomeno: dati un qualsiasi messaggio M e una chiave k, se
C = DESK(M) allora ¬C = DES¬K(¬M).
Diamo ora una prova che vale questa implicazione. Considerando la struttura del DES avremo che se il testo in chiaro M è complementato, allora l'input alla prima iterazione è dato da ¬L0 e ¬R0. Vediamo ora cosa accade nella prima iterazione:
come si evince dalla figura, avremo che l'output è dato da ¬L1 e ¬R1, in accordo con le formule:
¬L1 = ¬R0
¬R1 = f(¬R0, ¬k1) Å ¬L0
Questo accade perché la parte sinistra dell'output corrisponde alla parte destra dell'input che è complementata rispetto al caso in cui facciamo DESk(M), mentre per quanto riguarda la parte destra, notando che
f(¬R0, ¬k1) = f(R0, k1)
avremo che essa è complementata, rispetto al caso in cui facciamo DESk(M), perché effettuiamo lo XOR con l'input ¬L0 invece che con L0.
Infatti :
f(¬R0, ¬k1) Å ¬L0 =f(R0, k1) Å ¬L0 = ¬(f(R0, k1) Å L0) = ¬R1
in quanto f(R0, k1)ÅL0=R1
Notiamo inoltre che, nella prima iterazione utilizziamo il valore ¬k1, perché la schedulazione delle chiavi, partendo da una chiave ¬k, produce 16 sottochiavi ¬ki. Vediamo ora perché vale l'uguaglianza
f(¬R0,¬k1) = f(R0, k1)
Se ci rifacciamo allo schema della funzione f, avremo che ad un certo punto, viene calcolato E(¬R0)Ŭk1, che risulta uguale a E(R0)ÅK1, per cui il valore della f è lo stesso in entrambi i casi. Quanto detto per la prima iterazione vale anche per le altre, per cui dopo la sedicesima iterazione, scambiando parte destra e sinistra, ed applicando la permutazione inversa, quello che otteniamo è ¬C, a differenza del caso in cui facciamo DESk(M) dove l'output è C.
La proprietà di complementazione non è di aiuto ad un crittoanalista se per la ricerca esaustiva della chiave sceglie un attacco known-plaintext, mentre se sceglie di effettuare un attacco chosen plaintext esaminerà la metà delle chiavi cioè 255 e questo consegue proprio dalla proprietà di complementazione. Ci si può chiedere se questa sia una debolezza o meno dal momento che molti messaggi (la maggior parte) non hanno blocchi che sono l'uno il complemento dell'altro.