Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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
up vote 3 down vote accepted

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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