# 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
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9314833283424377, "perplexity_flag": "middle"}