🖐🏼 🎁 👩🏼‍🤝‍👨🏻 Wie S-Boxen erstellt werden 📚 🧗🏽 🛸

Die symmetrische Schlüsselverschlüsselung ist in der heutigen Welt allgegenwärtig - sie speichert und überträgt Informationen, E-Mails und sieht sich sogar Videos auf YouTube an. Starke symmetrische Chiffren umfassen wohlgeformte S-Boxen. In diesem Artikel werde ich die verschiedenen Möglichkeiten zum Erstellen von S-Boxen erläutern und vergleichen.

1. Was ist ein S-Block?

S-Block ist eine Funktion, die am Eingang n Bits nimmt, diese nach einem bestimmten Algorithmus transformiert und am Ausgang m Bits zurückgibt. S-Boxen sind in den meisten Blockchiffren weit verbreitet. Sie können sich in Eingabe- und Ausgabegröße (n und m) unterscheiden, deterministisch oder zufällig generiert werden und können auch unveränderlich (fest) oder basierend auf einem Schlüssel generiert werden. S-Boxen können entweder als Tabelle (wie in DES) oder als algebraische Boolesche Funktion (wie in AES) dargestellt werden. Wichtige Kriterien beim Zusammenstellen einer S-Box sind ihre Nichtlinearität und das Kriterium für die Ausbreitung von Booleschen Funktionen. Um die S-Box als eine Folge von Booleschen Funktionen zu betrachten, verstehen wir zunächst, wie sich Boolesche Funktionen im Allgemeinen auf die Kryptographie beziehen.

2. Boolesche Funktionen in der Kryptographie

In herkömmlichen Verschlüsselungssystemen, die eine offene Nachricht in eine mit einem geheimen Schlüssel verschlüsselte Nachricht übersetzen, ist der Apparat für boolesche Funktionen sehr weit verbreitet. Die Hauptanforderung für sie ist, dass sie die Entschlüsselung der Nachricht durch eine Person erschweren, die nicht der Adressat ist.

Um die Verwendung von Booleschen Funktionen zu veranschaulichen, stellen wir ein Stream-Verschlüsselungsschema vor, bei dem jedes eingehende Zeichen sofort in ein Chiffretextzeichen konvertiert wird. Der Originaltext, der Schlüssel und der Chiffretext sind Binärzeichenfolgen gleicher Länge. In der Praxis wählen Sender und Empfänger meistens eine Pseudozufallssequenz anstelle eines Schlüssels in der Vernam-Chiffre, der aus einem kurzen geheimen Schlüssel gemäß dem vereinbarten Algorithmus generiert wird. Diese Sequenz wird als Keystream oder Gamma bezeichnet .

, (Linear Feedback Shift Register, LSFR).

. ( ) ( ). LSFR , , LSFR.

, , L. L_i , L_1 + L_2 + ... + L_n = L. , .

, .

3.

F_2 - 2 ( $\ {0, 1 \}$ ), F_2 ^ j - j - F_2 .

S- $s \ times t$ :

$S: F_2 ^ {s} \ longrightarrow F_2 ^ {t}$

$f: F_2 ^ {s} \ longrightarrow F_2$

, S- :

$f_i: F_2 ^ {s} \ longrightarrow F_2, i = 1, 2, ..., t$ - ( x_1, x_2, ..., x_s ). y_z = f (x_1, x_2, ..., x_s) .

$[y_0, y_1, ..., y_ {2 ^ {s} minus 1}]$ .

( ) 2 ^ s :

$\displaystyle f(x) = a_o \oplus \sum_{i = 1}^{s}a_{i}x_{i} \oplus \sum_{1 \leq i < j \leq s}{}a_{ij}x_{i}x_{j} \oplus ... \oplus a_{12..s}x_{1}x_{2}...x_{s},$

$\sum$ 2.

, :

$f(x_1, x_2, ..., x_{s}) = a_{0} \oplus a_{1}x_{1} \oplus a_{2}x_{2} \oplus ... \oplus a_{s}x_{s}, a_{i} \in F_{2}.$

, () . "".

4.

$f: F_2^s \longrightarrow F_2$ , , .

$x \in F_2^s$ , hwt(x) - . $f, g: F_{2}^{s} \longrightarrow F_2$ :

$\displaystyle d(f, g) = \sum_{x \in \{ 0, 1 \}^s}f(x) \oplus g(x).$

( ord(f) f(x) - a_J , - $\{1,2,...,s\}$ . - , a_0 . a_1, a_2, ..., a_s - , $a_{12}, a_{13}, ..., a_{(s-1)s}$ - . - 2^s .

( ) $\sigma_{i}(f)$ . , ,

$\sigma_{i}(f) = \binom{s}i.$

X_s

$\displaystyle \delta(f) = min_{g \in X_s} d(f, g).$

A_s - $g \in A_s.$ N_f,

$\displaystyle N_f = min_{g \in A_{s}} d(f, g).$

, $\displaystyle N_f \leq min_{g \in A_{s}} d(f, g).$ - , $N_f = 2^{s - 1} - 2^{s/2 - 1}$ . -.

- .

5.-

- - , . - .

, -, .

$N_0[y_0, y_1, ..., y_{{2^s} - 1}]$ - $[y_0, y_1, ..., y_{2^s - 1}]$ , $N_1[y_0, y_1, ..., y_{2^s - 1}]$ - . , $N_0[y_0, y_1, ..., y_{2^s - 1}] = N_1[y_0, y_1, ..., y_{2^s - 1}]$ .

$f: F_2^{s} \longrightarrow F_2$ , $f(x) \oplus f(x \oplus \alpha)$ $\alpha \in F_2^{s}$ , $1 \leq hwt(\alpha) \leq s$ . $\frac{1}{2}$ .

6. -

6.1

B_s - .

: $a, b \in B_6, a \neq b$ .

: - B_8 - 8 .

: $g: F_2^8 \longrightarrow F_2$ , :

$\begin{equation*} g(x_0, ..., x_7) = \begin{cases} a(x_0, ..., x_5), x_6 = 0, x_7 = 0\\ a(x_0, ..., x_5), x_6 = 0, x_7 = 1\\ b(x_0, ..., x_5), x_6 = 1, x_7 = 0\\ b(x_0, ..., x_5) \oplus 1, x_6 = 1, x_7 = 1 \end{cases} \end{equation*}$

: - a(x) , b(x) c(x) , $a(x) \oplus b(x) \oplus c(x)$ - -.

: - s+2 .

$g(x, x_{s + 1}, x_{s + 2}) = a(x)b(x) \oplus b(x)c(x) \oplus c(x)a(x) \oplus [a(x)b(x)]x_{s + 1} \oplus [a(x) \oplus c(x)]x_{s + 2} \oplus x_{s + 1}x_{s + 2}$

( -) s+2 . . 4 6 . - "" (, ), .

: $\pi: F_2^{s/2} \longrightarrow F_2^{s/2}$ , $g: F_2^{s/2} \longrightarrow F_2$ , - .

: - $f_M:F_2^{s} \longrightarrow F_2$ , .

: $f_M(x||y) = \pi(x) * y \oplus g(x),$ $x, y \in F_2^{s/2}$ , - $(a_ {s / 2 - 1}, a_ {s / 2 - 2}, ..., a_0) * (b_ {s / 2 - 1}, b_ {s / 2 - 2}, ..., b_0 ) = a_ {s / 2 - 1} b_ {s / 2 - 1} \ oplus a_ {s / 2 - 2} b_ {s / 2 - 2} \ oplus ... \ oplus a_0b_0$

(a_0, a_1, ..., a_7) - $\ {0, 1, ..., 7 \}$ . $\ widehat {f} (x_0, x_1, ..., x_7) = f_ {M} (x_ {a0}, x_ {a1}, ..., x_ {a7})$ f_M - , -. .

6.2 -

"" - , . , , , .

, - 6 . . . - , , - .

- , . - s / 2 , - s / 2 . .

s / 2 . ich , , . ich , , ich .

, .

- -, -. . . - ( ).

- , - . , , - .

. -, (i> 2) - . (, 6 s = 8, i = 3, 4 ). -, - .

4. ( -)

- ( - )
, $0 \ leq s / 2$ $cmin_ {ord}$ $cmax_ {ord}$ ,

$0 \ leq cmin_ {ord} \ leq cmax_ {ord} \ leq \ binom {s} {ord}.$

(1.1) (1.2) , $0 \ leq ord \ leq s / 2$ :

- $f_ {ANF}$
$f_ {TT}$ .

(1.1) (1.2) , $0 \ leq ord \ leq s / 2$ :
- 1.1 $c_ {ord}$ , $cmin_ {ord} \ leq c_ {ord} \ leq cmax_ {ord}$ ,
  
  1.2 1 .
$f_ {ANF}$ $f_ {TT}$ .
$f_ {TT}$ .
, (3), $2 ^ {s -1} - 2 ^ {{s / 2} - 1}$ , $f_ {TT}$ $f_ {ANF}$ - -, ; (1).

, 4 . - (. - ), (4) - , , .

7. S-

S- - $S: F_2 ^ s \ longrightarrow F_2 ^ t$ , S (x_1, x_2, ..., x_s) = (f_1 (x_1, x_2, ..., x_s), f_2 (x_1, x_2, ..., x_s), ..., f_t (x_1, x_2, ..., x_s)) , , . ,

$N_S = min \ {N_ {f_ {J}} | f_ {J} = \ sum_ {i \ in J}, J \ subseteq (1, 2, ..., t) \}.$

S-, . S-.

S-, 8- .

1. S-, ,

2. S-, ,

1 2, , S-, , S- (98 100).

3. S-, ,

, S- , S- - ( 2) (. 3). , 98, S- .

4. S-, -,

S-, - (. 4). S- 112, ( , 104). 20 S- 100, S-, - .

, - S- .

, , - S- (80, ). S- (, ) S- .

8.

, S- . , , . S-, -.

. -
Anna Grocholewska-Czurylo and Janusz Stoklosa - Random Generation of S-Boxes for Block Ciphers
Meier, W., Staffelbach, O - Nichtlinearitätskriterien für kryptografische Funktionen
Wikipedia - S-Box (Informatik)
Wikipedia - S-Box
Wikipedia - Gebogene Funktionen

Wie S-Boxen erstellt werden

1. Was ist ein S-Block?

2. Boolesche Funktionen in der Kryptographie

3.

4.

5.-

6. -

6.1

6.2 -

7. S-

8.

More articles: