🎦 🧜 🈸 Cryptanalyse linéaire sur l'exemple de l'algorithme de chiffrement par blocs NUSH 👋🏼 🦇 🔼

introduction

Dans le monde moderne, il existe un problème aigu de la confidentialité des données lors de leur échange et de leur stockage, qui est atteint par toutes les méthodes de cryptage possibles. Cependant, avec l'avènement de nouveaux algorithmes de cryptage, les travaux commencent pour étudier les moyens de violer la confidentialité des données, c'est-à-dire qu'ils recherchent des attaques contre elles.

De nos jours, les algorithmes de chiffrement par blocs tels que AES, "Grasshopper" et d'autres sont largement utilisés. La cryptanalyse linéaire est l'une des méthodes potentiellement efficaces pour les attaquer. Le concept de base de cette méthode a été présenté par Mitsuru Matsui dans son travail «Linear Cryptoanalysis Method for DES Cipher» [1] dans les années 90. L'essence de cette méthode sera décrite dans la section 2 de cet article.

A titre d'exemple d'utilisation efficace de cette méthode, une cryptanalyse linéaire de l'algorithme de chiffrement par blocs NUSH [2] est présentée , dont une brève référence sera donnée ci-dessous.

Fondamentaux de la cryptanalyse linéaire

Comme il a été écrit ci-dessus, l'essence de la cryptanalyse linéaire est décrite dans la «Méthode de crypto-analyse linéaire pour le chiffrement DES». Lors de l'utilisation de la cryptanalyse linéaire, on suppose que la structure du chiffrement est connue et que le cryptanalyste dispose d'un échantillon statistique suffisant «texte chiffré-clé publique» obtenu sur une seule clé.

Après avoir satisfait aux exigences ci-dessus, la structure de l'algorithme est remplacée par une simple fonction linéaire. En règle générale, l'analyse des fonctions linéaires est beaucoup plus simple que les fonctions non linéaires du chiffre lui-même, ce qui peut réduire le problème de l'analyse d'un chiffre à l'analyse de sa modification linéaire. En outre, à partir du système de fonctions obtenu, le cryptanalyste devine les bits de clé avec une certaine probabilité.

Soit le <x, y> = x_1 * y_1 + x_2 * y_2 + ... + x_n * y_n produit scalaire des vecteurs binaires modulo 2. Et laisse le P, C, K texte en clair, le texte chiffré et la clé, respectivement.

Définition 1

$<P, \ alpha> \ oplus <C, \ beta> = <K, \ gamma>$

$1 \ barre oblique inverse 2 + \ varepsilon$ $\ varepsilon$ , $\ \ alpha, \ beta, \ gamma$ - .

, .

(Pilling-up , “ ”)

X_i $1 \ leq i \ leq n$ - , $\ mathbb {Z} _2$ .

$P \{X_i = 0\} = 1 \backslash 2 + \varepsilon_i$

$1 \leq \varepsilon_i \leq 1 \backslash 2$ . $X_1 \oplus X_2 \oplus ... \oplus X_n$ 0 $1 \backslash 2 + \varepsilon$ , $\varepsilon = 2^{n-1} \prod^{n}_{i=1} \varepsilon_i$

1: $\varepsilon_j = 0$ , $j \in \overline{1,n}$ .

NUSH

2000 NESSIE , , LAN Crypto – NUSH. , (64, 128, 192 256 ).

S- P-, (XOR, AND ..). . , , O(k) , k – .

N = 4n — P = P_0 P_1 P_2 P_3 . KS_i (start key) . : $a_0 b_0 c_0 d_0 = P_0 P_1 P_2 P_3 \oplus KS_0 KS_1 KS_2 KS_3$ . r-1 , KR_i (subKey) - , # — , , C_i,S_i , $\gg j$ — j :

${ for ( i=1...r-1 ) \\ a_i = b_{i-1} b_i=((c_i \oplus (KR_{i-1}+C_{i-1}))+b_{i-1}) \gg S_{i-1} \\ c_i = d_{i-1} \\ d_i = a_i \oplus (b_i \# d_i)}$

${a_r = a_{r-1} + (c_r \# d_{r-1}) \\ b_r = b_{r-1} \\ c_r = ((c_{r-1} \oplus (KR_r+C_{r-1})+b_{r-1})) \gg S_{r-1} \\ d_r = d_{r-1}}$

: $M_0 M_1 M_2 M_3 = a_r b_r c_r d_r \oplus KF_0 KF_1 KF_2 KF_3$

${d_{r-1} = d_r \\ b_{r-1} = b_r a_{r-1} = a_r - (c_r \# d_{r-1}) \\ a_{r-1} = a_r - (c_r \# d_r{r-1}) \\ c_{r-1} = c_r \gg (n- S_{r-1}) }$

r-1

${ for(i=r-1...1) \\ d_{i-1} = c_i \\ b_{i-1} = a_i \\ a_{i-1} = d_i - (b_i \# c_{i-1}) \\ c_{i-1} = (b_i \gg (n-S_{i-1}))-KR_{i-1}-a_{i-1}}$

NUSH

, , , 1

${ a_i[0] = b_{i-1}[0] \quad (1) }$

$f(x,y)=x \# y$ . , p=0.75 p=0.25 . p=0.75 p=0.25 d_i :

${d_i = a_{i-1}[0] \oplus b_i[0] \oplus d_{i-1}[0] \quad (2)}$

(1) (2) p=0.75

$a_i[0] \oplus b_i[0] \oplus d_i[0] = a_{i-1}[0] \oplus b_{i-1}[0] \oplus d_{i-1}[0] \oplus \theta \quad (3)$

$\theta = 0$ # “AND” $\theta = 1$ # “OR”.

, .

$a_1[0] \oplus b_1[0] \oplus d_1[0]$ . , S_0 = 4 , b_1[0] c_0[0-4] , b_0[0-4] , KR_0[0-4] .

5 c_0 . $a_1[0] \oplus b_1[0] \oplus d_1[0]$ a_0[0-4] , b_0[0] , c_0[0] , d_0[0-4] , KR_0[0-4] C_0[0-4] .

f_1 :

$a_1[0] \oplus b_1[0] \oplus d_1[0] = f_1 \begin{pmatrix} P_0[0], P_1[0-4], P_2[0-4], P_3[0], \\ KS_0[0], KS_1[0-4], KS_2[0-4], KS_3[0], KR_0[0-4] \end{pmatrix} \quad (4)$

$a_2[0] \oplus b_2[0] \oplus d_2[0]$ . , $a_2[0] \oplus b_2[0] \oplus d_2[0]$ $P_3[0] \oplus KS_0[0]$ , $P_2[0-11] \oplus KS_1[0-11]$ , $P_1[0-11] \oplus KS_2[0-11]$ , $P_0 [0-7] \oplus KS_2[0-7]$ , KR_0 [0-11] KR_1[0-7] . f_2 :

$a_2[0] \oplus b_2[0] \oplus d_2[0] = f_2 \begin{pmatrix} P_0[0-7], P_1[0-11], P_2[0-11], P_3[0], \\ KS_0[0], KS_1[0-11], KS_2[0-11], KS_3[0-7], KR_1[0-7] \end{pmatrix} \quad (5)$

$a_3[0] \oplus b_3[0] \oplus d_3[0]$ . , $a_3[0] \oplus b_3[0] \oplus d_3[0]$ , KS_0[0-11] , KS_1 , KS_2 , KS_3 , KR_0 , KR_1[0] KR_2[0-11] . f_3 :

$a_3[0] \oplus b_3[0] \oplus d_3[0] = f_3(P, KS_0[0-11], KS_1, KS_2, KS_3, KR_0, KR_1, KR_2[0-11]) \quad (6)$

$a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ . ,

${ d_{32}[0] = c_{33}[0] \\ b_{32}[0] = a_{33}[0] \\ a_{32}[0] = d_{33}[0] \oplus (b_{33}[0] \& c_{32}[0])} \quad { \space \\ (7)}$

$a_{32}[0] b_{32}[0] c_{32}[0] d_{32}[0]$ $a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ . $a_{34}[0], b_{34}[0], c_{34}[0], d_{34}[0]$ $KR_{33}[0]$ . , $a_{35}[0,1], b_{35}[0,1], c_{35}[0,1], d_{35}[0,1]$ $a_{36}[0,1], b_{36}[0,1], c_{36}[0,1], d_{36}[0,1]$ $KR_{35}[0]$ .

, $a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0]$ M_0[0,1] , M_1[0-2] , M_2[0,12] , M_3[0,1] , KF_0[0] , KF_1[0,12] , KF_2[0-2] , KF_3[0,1] , $KR_{33}[0]$ , $KR_{34}[0]$ , $KR_{35}[0]$ , , . f_4 :

$a_{32}[0] \oplus b_{32}[0] \oplus d_{32}[0] = f_4 \begin{pmatrix} {M_0[0,1], M_1[0-2], M_2[0-12], M_3[0,1], \\ KF_0[0,1], KF_1[0-12], KF_2[0-2], KF_3[0,1], \\ KR_{33}[0], KR_{34}[0], KR_{35}[0] } \end{pmatrix} \quad (8)$

$a_{31}[0] \oplus b_{31}[0] \oplus d_{31}[0]$ f_5 :

$a_{31}[0] \oplus b_{31}[0] \oplus d_{31}[0] = f_5 \begin{pmatrix} {M_0[0-9], M_1[0-11], M_2[0-12], M_3[0,1], \\ KF_0[0,1], KF_1[0-12], KF_2[0-11], KF_3[0-9], \\ KR_{32}[0], KR_{33}[0], KR_{34}[0], KR_{35}[0-9] } \end{pmatrix} \quad (9)$

. (3) , 29-

$a_2[0] \oplus b_2[0] \oplus d_2[0] = a_{31}[0] \oplus b_{31}[0] \oplus d_{31}[0] \quad (10)$

$1/2+2^{-30}$ .

${f_2(P, KS_0[0], KS_1[0-11], KS_2[0-11], KS_3[0-7], KR_1[0-7]) = \\ = f_5 \begin{pmatrix} {M, \\ KF_0[0,1], KF_1[0-12], KF_2[0-11], KF_3[0-9], \\ KR_{32}[0], KR_{33}[0], KR_{34}[0], KR_{35}[0-9] } \end{pmatrix}} { \space \\ \space \\ \quad (11)}$

NUSH , (11) m_0 - . , .

1. $K ^ i (i = 1, ..., 2 ^ {m_0})$ T_i - , (11).

2. T_j T_i , K ^ j .

3. , .

L'article présente le concept de base de la cryptanalyse linéaire et considère un exemple de son application dans l'analyse de l'algorithme de chiffrement NUSH.

Littérature

1. Mitsuru Matsui, méthode de cryptoanalyse linéaire pour le chiffrement DES, Advances in Cryptogy-Eurocrypt'93, Berlin: Springer-Verlag, 1993, 386-397.

2. Wu Wenling et Feng Dengguo, Cryptoanalyse linéaire du chiffrement par blocs NUSH, Science in China (Seria F), février 2002, Vol. 45, n ° 1.

3. M. Heys, un tutoriel sur la crypto-analyse linéaire et différentielle, Cryptologia, juin 2001, vol. 26 n ° 3.

4.https: //www.youtube.com/watch? V = nEHVfeaPjNw

Cryptanalyse linéaire sur l'exemple de l'algorithme de chiffrement par blocs NUSH

introduction

Fondamentaux de la cryptanalyse linéaire

NUSH

NUSH

Littérature

More articles: