🤓 😥 🎰 Como as S-boxes são criadas 🗺️ 😼 🏆

A criptografia de chave simétrica é onipresente no mundo de hoje - armazenando e transmitindo informações, e-mail e até mesmo assistindo a vídeos no YouTube. Cifras simétricas fortes incluem S-box bem formadas. Nesta postagem, vou mostrar as diferentes maneiras de criar S-box e compará-las.

1. O que é bloco S

O bloco S é uma função que pega n bits na entrada, os transforma de acordo com um determinado algoritmo e retorna m bits na saída. Caixas S são amplamente utilizadas na maioria das cifras de bloco. Eles podem diferir em tamanhos de entrada e saída (n e m), podem ser gerados deterministicamente ou aleatoriamente e também podem ser imutáveis (fixos) ou gerados com base em uma chave. As S-boxes podem ser representadas como uma tabela (como no DES) ou como uma função booleana algébrica (como no AES). Critérios importantes na composição de uma S-box são sua não linearidade e o critério de propagação de funções booleanas. Para ver a S-box como uma sequência de funções booleanas, primeiro entendemos como as funções booleanas geralmente se relacionam com a criptografia.

2. Funções booleanas em criptografia

Em sistemas de criptografia tradicionais, que traduzem uma mensagem aberta em uma criptografada com uma chave secreta, o aparato de funções booleanas é amplamente utilizado. O principal requisito para eles é que eles complicem a descriptografia da mensagem por uma pessoa que não é seu destinatário.

Para ilustrar o uso de funções booleanas, apresentamos um esquema de criptografia de fluxo, em que cada caractere de entrada é imediatamente convertido em um caractere de texto cifrado. O texto original, a chave e o texto cifrado são cadeias binárias do mesmo comprimento. Na prática, o remetente e o receptor costumam escolher uma sequência pseudo-aleatória em vez de uma chave na cifra Vernam, que é gerada a partir de uma chave secreta curta de acordo com o algoritmo acordado. Essa sequência é chamada de keystream ou gama .

, (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 \ vezes 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} menos 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 . , , . , , .

, .

- -, -. . . - ( ).

- , - . , , - .

. -, (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 , $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, $5 \%$ ( , 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 - Critérios de não linearidade para funções criptográficas
Wikipedia - S-box (ciência da computação)
Wikipedia - S-box
Wikipedia - Funções Bent

Como as S-boxes são criadas

1. O que é bloco S

2. Funções booleanas em criptografia

3.

4.

5.-

6. -

6.1

6.2 -

7. S-

8.

More articles: