0
$\begingroup$

My cryptology professor gave us this problem on a past homework assignment and I only managed to get one of the 3 parts correct. Needless to say, I want to know how to do the other two parts as well. The question is as follows:

Consider the following DES-like encryption system that operates on 16-bit strings. The system takes the input and divides it into two 8-bit string $L_0$ and $R_0$. One round of encryption starts with $L_{i-1}$ and $R_{i-1}$ and the output is $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus S(R_{i-1})\oplus K$, where $K$ is the key.

The function S rotates the bits of $R_{i-1}$ to the right. More precisely, if $R_{i-1}=b_0\|b_1\|b_2\|b_3\|b_4\|b_5\|b_6\|b_7$ then $S(R_{i-1})=b_7\|b_0\|b_1\|b_2\|b_3\|b_4\|b_5\|b_6$.

The two parts that I was not able to get are:

1) Explain briefly why if $A$ and $B$ are bit strings, then $S(A\oplus B)=S(A)\oplus S(B)$

2) If $M$ is the plaintext, let $E_K(M)$ denote the process of encrypting $M$ using one round of the above process. Show that $E_K$ has the equal difference property, namely that if $A\oplus B = C\oplus D$, then $E_K(A)\oplus E_K(B)=E_K(C)\oplus E_K(D)$.

Anyway, if someone could provide a complete explanation (answer included) on how to the 2 above questions, I would greatly appreciate it! Thanks in advance!

$\endgroup$
  • $\begingroup$ On this website, basic $\TeX$ is easy as $E_K(A)\oplus E_K(B)=E_K(C)\oplus E_K(D)$. I often use this reference card, and a lot of it works. $\;$ Hint for 1: break down $A$ and $B$ as bit strings, apply definition of $S$, and watch the desired property unfold. $\;$ For 2: Break 16-bit strings into two 8-bit ones (not individual bits); perhaps, evaluate the Exclusive-OR of what's on both sides of the equality, and simplify until you get zero; use result in 1, associativity+commutativity of $⊕$, and that $\forall X, X⊕X=0$. $\endgroup$ – fgrieu Nov 1 '14 at 16:27
  • $\begingroup$ @fgrieu: thanks for the link to the reference card! I will definitely be using that in the future! $\endgroup$ – Jok3r Nov 2 '14 at 20:09
1
$\begingroup$

For 1) you need to show that $S(X)$ is linear with respect to xor.

We can define $S(X)$ as:

$S(X) = (x_{7}, x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6})$

And define $A \oplus B$ as:

$A \oplus B = (a_0 \oplus b_0, a_1 \oplus b_1,a_2 \oplus b_2,a_3 \oplus b_3,a_4 \oplus b_4,a_5 \oplus b_5,a_6 \oplus b_6,a_7 \oplus b_7,)$

So we have:

$S(A \oplus B) = (a_7 \oplus b_7,a_0 \oplus b_0,a_1 \oplus b_1,a_2 \oplus b_2,a_3 \oplus b_3,a_4 \oplus b_4,a_5 \oplus b_5,a_6 \oplus b_6)$

$=(a_{7}, a_{0}, a_{1}, a_{2}, a_{3} a_{4}, a_{5}, a_{6}) \oplus (b_{7}, b_{0}, b_{1}, b_{2}, b_{3} b_{4}, b_{5}, b_{6})$

Which by definition is:

$=S(A) \oplus S(B)$


For number 2) we'll first show that if there is some difference $D = A \oplus B$ then $E_k(D) = E_k(A) \oplus E_k(B)$.

We can define $E_K(M)$ as:

$M_R || (M_L \oplus S(M_R))$

So given:

$E_k(A) \oplus E_k(B)$

$=\big[A_R || (A_L \oplus S(A_R))\big] \oplus \big[B_R||(B_L \oplus S(B_R))\big]$

$=(A_R \oplus B_R)||(A_L \oplus S(A_R) \oplus B_L \oplus S(B_R))$

And using the property proved in 1) you get:

$=(A_R \oplus B_R)||(A_L \oplus B_L \oplus S(A_R \oplus B_R))$

And because $D = A \oplus B$:

$=(D_R||(D_L \oplus S(D_R))$

$=E_k(D)$

Now we can show the equal difference property holds:

$A \oplus B = C \oplus D$

$E_k(A \oplus B) = E_k(C \oplus D)$

$E_k(A) \oplus E_k(B) = E_k(C) \oplus E_k(D)$

$\endgroup$
  • $\begingroup$ awesome answer! Very clearly explained and easily understood! $\endgroup$ – Jok3r Nov 2 '14 at 20:26

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.