7
$\begingroup$

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

| improve this question | |
$\endgroup$
  • 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♦ May 22 '14 at 13:35
8
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 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♦ May 23 '14 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 May 16 at 3:47
  • 1
    $\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♦ May 16 at 4:43
  • $\begingroup$ @fgrieu Now I get it, thank you! $\endgroup$ – Trey May 16 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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