Le S-box

Fino ad ora sono state utilizzate funzioni di tipo lineare (cioè gli xor, le permutazioni e le espansioni), e se un sistema fosse realizzato utilizzando solo funzioni di questo tipo sarebbe molto facile romperlo.

L'unico punto in cui il sistema DES non utilizza funzioni di tipo lineare è nelle S-box, che costituiscono quindi il fulcro dell'algoritmo. Riportiamo qui di seguito, a titolo di esempio, la tabella che specifica la S-box 1:

Figura 2.4.1: Tabella S-Box 1.

Vediamo come si leggono. Dato Bi (l'input a 6 bit dell'S-box Si), il primo e l'ultimo bit di Bi vengono interpretati come indice di riga, mentre i bit centrali come indice di colonna. La prima riga di Si è la riga 00, la seconda riga è la 01, la terza riga è la 10 e la quarta riga è la 11. Per le colonne abbiamo un'indicizzazione analoga: la prima colonna è la colonna 0000, la seconda colonna è la colonna 0001, ... , l'ultima colonna è la colonna 1111. Si consulta la tabella Si alle coordinate prescritte e il valore in uscita dall'S-box è l'equivalente binario del decimale trovato. In Figura 2.4.2 vi è un esempio di applicazione di S1 sull'input B1 = 101110.

Figura 2.4.2: Esempio di applicazione di S1.

Come abbiamo già detto in precedenza le S-box appaiono a molti come qualcosa di misterioso: alcuni asseriscono addirittura che esse nascondano in sé delle trapdoor. Tali sospetti nascono dal fatto che i criteri di progettazione delle S-box non sono al momento completamente noti.

Ad ogni modo nel 1976 l'NSA rese note alcune proprietà di cui le S-box godevano:

  1. Ogni riga deve essere una permutazione degli interi 0,..,15.
  2. Nessuna S-box è una funzione affine o lineare dei suoi input.
  3. Cambiando un solo bit di input ad una S-box devono variare almeno due bit nell'output.
  4. Per ogni S-box e per ogni input x a 6 bit, S(x) e S(x Å 001100) differiscono in almeno due bit.
  5. Per ogni S-box, per ogni input x e per ogni d,gÎ{0,1} S(x) ¹ S(x Å 11dg00).
  6. Per ogni S-box, se fissiamo un bit di input e osserviamo il valore di un fissato bit di output, il numero degli input per i quali il bit di output vale 0 è circa uguale al numero degli input per i quali tale bit vale 1.

Le ultime due proprietà sono conseguenza dei criteri di progettazione. In tutti i casi non è noto se altre proprietà furono usate nel progetto delle S-box.

Pagina precedente | Torna in cima | Pagina successiva