I'm supposed to show the complement property of DES ($c=DES(p,k) => \bar c = DES(\bar p, \bar k)$).

My idea was to just start the algorithm with $\bar p$ and see what happens (ignoring the initial permutation for now). I looked at it step by step and got the the point where $R1 = \bar L1 \oplus f(\bar k1, \bar R0)$. So I figured I had to show that $f(\bar k1, \bar R0) = \bar f(k1,R0)$. Is that even right so far? Because I got stuck at the point where the S-Boxes are used. Why would $S(\bar x) = \bar S(x)$?

Somewhere else I read something about a formal prove using induction, but I don't know how I would do that either...

  • 1
    $\begingroup$ Indeed, there is no reason that $S(\overline x)=\overline{S(x)}$, and it does not hold in general. Hint 1: look at how $\overline{k1}$ and $\overline{R0}$ are combined in DES, and what that gives. Hint 2: in fact $f(\overline{k1},\overline{R0})=\overline{f(k1,R0)}$ never holds; much to the contrary! $\endgroup$
    – fgrieu
    Commented May 22, 2014 at 13:35

1 Answer 1


I think I got it: I'm going to show that after round i the result will be $\overline{L_i}$ and $\overline{R_i}$ when the input was $\overline{L_{i-1}}$ and $\overline{R_{i-1}}$ and using $\overline k$ as key.

$L_i=R_{i-1} \implies \overline{L_i} = \overline{R_{i-1}}$

$\overline{R_i} = \overline{L_{i-1}} \oplus f(\overline{R_{i-1}}, \overline{k_i}) = \overline{L_{i-1}} \oplus f(R_{i-1}, {k_i}) = \overline{L_{i-1} \oplus f(R_{i-1}, k_i)}$.

$f(\overline R, \overline k)=f(R, k)$ because within the fuction the complement of expansion(R) and $\overline k$ are xored which eleminates the complement.

That way round the final result will be $\overline c$ when using $\overline m$ as input and $\overline k$ as key. The initial permutation does not change that.

  • 2
    $\begingroup$ You got the idea right, and as far as I can tell the details too! I made some minor reformatting, using e.g. $\overline{L_{i-1} \oplus f(R_{i-1}, k_i)}$to get $\overline{L_{i-1} \oplus f(R_{i-1}, k_i)}$ $\endgroup$
    – fgrieu
    Commented May 23, 2014 at 13:21
  • $\begingroup$ @fgrieu but how did yo get that $\overline{L_{i-1}} \oplus f(R_{i-1}, {k_i}) = \overline{L_{i-1} \oplus f(R_{i-1}, k_i)}$. $\endgroup$
    – Trey
    Commented May 16, 2020 at 3:47
  • 2
    $\begingroup$ @Trey: I did not get it, CGFoX did! That's easy. If $u$ and $v$ are bitstrings of equal size, then $\overline u\oplus v\,=\,\overline{u\oplus v}$. Proof: a possible definition of the complement of a $b$-bit bistring $x$ is: $x\oplus1^b$. Now$$\overline u\oplus v\,=\,(u\oplus1^b)\oplus v\,=\,u\oplus(1^b\oplus v)\,=\,u\oplus(v\oplus1^b)\,=\,(u\oplus v)\oplus1^b\,=\,\overline{u\oplus v}$$ by applying definition, associativity of $\oplus$, commutativity of $\oplus$, associativity of $\oplus$, and definition. $\endgroup$
    – fgrieu
    Commented May 16, 2020 at 4:43
  • $\begingroup$ @fgrieu Now I get it, thank you! $\endgroup$
    – Trey
    Commented May 16, 2020 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.