# Regarding matsui's Paper on Linear Cryptanalysis of DES

I's going throught the the Paper by Matsui on Linear Cryptanalysis of DES . In that he says

$NS_{5}(16,15)=12$

And then in the next paragraph he says considering the expansion and permutation phases the following equation holds good

$X(15)\bigoplus F(X,K)[7,18,24,29]=k[22]$ Can somebody help me understand this because i cant find a relation between the first equation and the second one . ?

-
Please find the paper at www.cs.bgu.ac.il/~crp042/Handouts/Matsui.pdf –  Malice Jun 17 '12 at 20:56

## 1 Answer

Let us denote by $x = x_5x_4x_3x_2x_1x_0$, where $x_i \in \{0, 1\}$ the input of a DES S-box and by $y = y_3y_2y_1y_0$, with $y_i \in \{0, 1\}$ its output. Basically, $\mathrm{NS}_5(16, 15) = 12$ means that for S-box #5, the relation $x_4 = y_3 \oplus y_2 \oplus y_1 \oplus y_0$, where $y = S_5(x)$, holds with probability $\frac{\mathrm{NS}_5(16, 5)}{64} = \frac{12}{64} = \frac{1}{2}-\frac{5}{16}$, which is a fairly biased value (one would expect this value to be very close to $\frac{1}{2}$ in an ideal situation).

Starting from this observation, Matsui builds the 1-round linear approximation $X_{15} \oplus F(X, K)_7 \oplus F(X, K)_{18} \oplus F(X, K)_{24} \oplus F(X, K)_{29} = K_{22}$ that holds with the same probability $\frac{1}{2}-\frac{5}{16}$. Note that, for S-box #5, $x_4$ can be traced back to $X_{15} \oplus K_{22}$, taking into account the $\mathrm{EP}(.)$ transformation as well as the key-schedule algorithm, and $y_3y_2y_1y_0$ can be propagated to bits 7, 18, 24 and 29 of the output of the round function, this time taking into account the effect of the bit permutation $\mathrm{P}(.)$.

-
Exactly . But I'm looking for is how did he manage the 1 round linear approximation from the $NS_{5}(16,15)$ equation . He did not describe that in the paper and nor can i find it anywhere on internet –  Malice Jun 20 '12 at 12:04
And please note that it's $NS_{5}(16,15)$ not $NS_{5}(16,5)$ . Typo . I've edited the Question –  Malice Jun 20 '12 at 12:07
I have corrected and expanded my answer, hope this is more clear for you now :-) –  cryptopathe Jun 20 '12 at 15:52
Oh My mistake . I's counting bits starting from left handside and was getting a differnt expression,should start counting from right hand side . Spent hours trying to find this .A bucketfull of thanks –  Malice Jun 20 '12 at 17:33
While expanding this Equation to a single round of DES, the Output of the function f is XORed with plain text . How does this equation we're talking about hold true because plain text is of random content but Matsui says this equation holds true $X_{2}[7,8,24,29]\bigoplus P_H[7,18,24,29]\bigoplus P_{L}[15]=K_{1}[22]$ –  Malice Jun 20 '12 at 17:58