👈🏼 🤳🏾 🙎🏽 ブロック暗号化アルゴリズムNUSHの例に関する線形暗号分析 💲 🚓 👊🏽

前書き

現代の世界では、交換および保管中のデータの機密性という深刻な問題があります。これは、考えられるすべての暗号化方法によって実現されます。ただし、新しい暗号化アルゴリズムの出現により、データの機密性を侵害する方法の研究が始まります。つまり、データへの攻撃を探しています。

現在、AES、Grasshopperなどのブロック暗号化アルゴリズムが広く使用されています。線形暗号分析は、それらを攻撃するための潜在的に効果的な方法の1つです。この方法の基本的な考え方は、松井満氏の著書「DES暗号の線形暗号解析法」[1]で90年代に発表されました。この方法の本質については、この記事のセクション2で説明します。

この方法の効果的な使用例として、ブロック暗号化アルゴリズムNUSH [2]の線形暗号分析が示されています。これについては、以下で簡単に説明します。

線形暗号分析の基礎

上で書いたように、線形暗号分析の本質は「DES暗号の線形暗号分析法」で説明されています。線形暗号分析を使用する場合、暗号の構造は既知であり、暗号分析者は単一のキーで取得された十分な統計サンプル「ciphertext-publickey」を持っていると想定されます。

上記の要件を満たした後、アルゴリズムの構造は単純な線形関数に置き換えられます。原則として、線形関数の分析は、暗号自体の非線形関数よりもはるかに単純です。これにより、暗号の分析の問題を線形変更の分析に減らすことができます。さらに、得られた関数システムから、暗号分析者は特定の確率でキーのビットを推測します。

してみましょう <x、y> = x_1 * y_1 + x_2 * y_2 + ... + x_n * y_n バイナリーのベクトルの内積は、2を法とlet P、C、K それぞれ、平文、暗号文と鍵を。

定義1

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

$1 \バックスラッシュ2+ \バレプシロン$ $\ varepsilon$ , $\ \アルファ、\ベータ、\ガンマ$ - .

, .

(Pilling-up , “ ”)

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

$P \ {X_i = 0 \} = 1 \バックスラッシュ2+ \ varepsilon_i$

$1 \ leq \ varepsilon_i \ leq 1 \バックスラッシュ2$ . $X_1 \ oplus X_2 \ oplus ... \ oplus X_n$ 0 $1 \バックスラッシュ2+ \バレプシロン$ , $\ 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 ..). . , , OK） , 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 - . , .