# Complement property of DES

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...

-
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! – fgrieu May 22 '14 at 13:35

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.
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)}$ – fgrieu May 23 '14 at 13:21