🌂 👨🏽‍🔧 🉐 Lineare Kryptoanalyse am Beispiel des Blockverschlüsselungsalgorithmus NUSH 🍻 🌟 ♠️

Einführung

In der modernen Welt gibt es ein akutes Problem der Vertraulichkeit von Daten während ihres Austauschs und ihrer Speicherung, das durch alle möglichen Verschlüsselungsmethoden erreicht wird. Mit dem Aufkommen neuer Verschlüsselungsalgorithmen wird jedoch nach Möglichkeiten gesucht, die Vertraulichkeit von Daten zu verletzen, dh sie suchen nach Angriffen auf diese.

Heutzutage werden häufig Blockverschlüsselungsalgorithmen wie AES, Grasshopper usw. verwendet. Die lineare Kryptoanalyse ist eine der potenziell wirksamen Methoden, um sie anzugreifen. Das Grundkonzept dieser Methode wurde von Mitsuru Matsui in seiner Arbeit „Lineare Kryptoanalyse-Methode für DES-Chiffre“ [1] in den 90er Jahren vorgestellt. Das Wesentliche dieser Methode wird in Abschnitt 2 dieses Artikels beschrieben.

Als Beispiel für die effektive Verwendung dieser Methode wird eine lineare Kryptoanalyse des Blockverschlüsselungsalgorithmus NUSH [2] vorgestellt , auf die im Folgenden kurz Bezug genommen wird.

Grundlagen der linearen Kryptoanalyse

Wie oben geschrieben, wird das Wesen der linearen Kryptoanalyse in der „Methode der linearen Kryptoanalyse für DES-Verschlüsselung“ beschrieben. Bei Verwendung der linearen Kryptoanalyse wird davon ausgegangen, dass die Struktur der Chiffre bekannt ist und dass der Kryptoanalytiker über eine ausreichende statistische Stichprobe „Chiffretext-öffentlicher Schlüssel“ verfügt, die auf einem Schlüssel erhalten wurde.

Nachdem die obigen Anforderungen erfüllt wurden, wird die Struktur des Algorithmus durch eine einfache lineare Funktion ersetzt. In der Regel ist die Analyse linearer Funktionen viel einfacher als nichtlineare Funktionen der Chiffre selbst, was das Problem der Analyse einer Chiffre auf die Analyse ihrer linearen Modifikation reduzieren kann. Ferner errät der Kryptoanalytiker aus dem erhaltenen Funktionssystem die Bits des Schlüssels mit einer bestimmten Wahrscheinlichkeit.

Lassen Sie das <x, y> = x_1 * y_1 + x_2 * y_2 + ... + x_n * y_n Punktprodukt der binären Vektoren Modulo 2. Und lassen Sie den P, C, K. Klartext, den Chiffretext bzw. den Schlüssel.

Definition 1

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

$1 \ backslash 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. , .

Der Artikel stellt das Grundkonzept der linearen Kryptoanalyse vor und betrachtet ein Beispiel für ihre Anwendung bei der Analyse des NUSH-Verschlüsselungsalgorithmus.

Literatur

1. Mitsuru Matsui, Lineare Kryptoanalyse für DES-Chiffre, Advances in Cryptogy-Eurocrypt'93, Berlin: Springer-Verlag, 1993, 386-397.

2. Wu Wenling & Feng Dengguo, Lineare Kryptoanalyse der NUSH-Blockchiffre, Science in China (Seria F), Februar 2002, Vol. 45, Nr. 1.

3. M. Heys, Ein Tutorial zur linearen und differentiellen Kryptoanalyse, Cryptologia, Juni 2001, Bd. 26 Nr. 3.

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

Lineare Kryptoanalyse am Beispiel des Blockverschlüsselungsalgorithmus NUSH

Einführung

Grundlagen der linearen Kryptoanalyse

NUSH

NUSH

Literatur

More articles: