Il sottolivello AES MixColumn include una trasformazione non lineare che può essere rappresentata da una moltiplicazione di matrice 4×4?

/ / Pubblicato in Cybersecurity, Fondamenti di crittografia classica EITC/IS/CCF, Crittografia a blocchi AES, Introduzione ai campi di Galois per l'AES

L'Advanced Encryption Standard (AES) è un cifrario a blocchi a chiave simmetrica ampiamente adottato, la cui sicurezza deriva da una serie attentamente orchestrata di trasformazioni lineari e non lineari sul blocco di dati. Uno dei componenti chiave di AES è il sottolivello MixColumns, che svolge un ruolo fondamentale nel garantire la diffusione combinando le colonne della matrice di stato. Una domanda frequente riguarda la natura della trasformazione MixColumns, in particolare se includa una trasformazione non lineare rappresentabile da una moltiplicazione di matrici 4x4.

Per affrontare questo problema, è necessaria una comprensione approfondita delle operazioni matematiche alla base delle MixColumn e della loro implementazione sul campo finito GF(2^8). Innanzitutto, è importante chiarire le definizioni di trasformazioni lineari e non lineari nel contesto degli algoritmi crittografici e dei campi di Galois. Una trasformazione è *lineare* se soddisfa le proprietà di additività e omogeneità; ovvero, per qualsiasi coppia di vettori. \mathbf{x} e \mathbf{y} e qualsiasi scalare a, la trasformazione T soddisfa: T(\mathbf{x} + \mathbf{y}) = T(\mathbf{x}) + T(\mathbf{y}) e T(a \cdot \mathbf{x}) = a \cdot T(\mathbf{x}).

La trasformazione MixColumns in AES

AES crittografa i dati in blocchi da 128 bit, rappresentati internamente come una matrice di byte 4x4 chiamata matrice di stato. Ogni ciclo di AES (tranne l'ultimo) elabora lo stato attraverso una serie di trasformazioni: SubBytes, ShiftRows, MixColumns e AddRoundKey. Tra queste, MixColumns opera su ciascuna colonna dello stato in modo indipendente.

Il passaggio MixColumns trasforma ogni vettore colonna \mathbf{un} (composto da quattro byte un_0, un_1, un_2, un_3) moltiplicandolo per una matrice fissa 4×4 M sul campo finito Fidanzata(2^8):

    \[ M = \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \\ \end{bmatrix} \]

La nuova rubrica \mathbf{b} è calcolato come:

    \[ \mathbf{b} = M \cdot \mathbf{a} \]

dove tutte le operazioni (addizione e moltiplicazione) vengono eseguite in Fidanzata(2^8), utilizzando il polinomio irriducibile x^8 + x^4 + x^3 + x + 1.

Per ogni byte di output bi nella colonna il calcolo è:

    \[ b_i = \text{mult}(M_{i,0}, a_0) \oplus \text{mult}(M_{i,1}, a_1) \oplus \text{mult}(M_{i,2}, a_2) \oplus \text{mult}(M_{i,3}, a_3) \]

where \testo{multiplo} indica la moltiplicazione in Fidanzata(2^8) e \ oplus è XOR bit a bit (addizione nel campo).

Linearità di MixColumns

L'operazione MixColumns è fondamentalmente una trasformazione lineare. Ciò è dovuto ai seguenti fatti:

1. Moltiplicazione di matrici e linearità: La struttura matematica della trasformazione è quella di una moltiplicazione matrice-vettore, che è intrinsecamente lineare, a condizione che le operazioni vengano eseguite in un campo. In AES, sia l'addizione (XOR) che la moltiplicazione sono definite in Fidanzata(2^8).

2. Nessuna non linearità intrinseca in MixColumns: Le trasformazioni non lineari sono quelle che non possono essere espresse come moltiplicazione di matrici, come la S-box utilizzata nel livello SubBytes di AES, che utilizza inverse moltiplicative e trasformazioni affini. L'operazione MixColumns non possiede tali proprietà; non prevede inverse, lookup o mapping non lineari, ma solo moltiplicazioni e addizioni fisse nel campo.

3. Omogeneità e additività: La matrice MixColumns M e le operazioni sul campo assicurano la trasformazione di \mathbf{a} + \mathbf{b} è la stessa della trasformazione di \mathbf{un} più la trasformazione di \mathbf{b}, e che moltiplicare l'input per uno scalare prima della trasformazione equivale a trasformare e poi moltiplicare. Ciò soddisfa entrambe le condizioni di linearità.

Perché MixColumns è lineare, non non lineare

È fondamentale distinguere tra operazioni non lineari dovute alla struttura del campo e operazioni non lineari dal punto di vista degli spazi vettoriali sul campo. Mentre la moltiplicazione in Fidanzata(2^8) può essere visto come non lineare rispetto ai bit dei byte coinvolti (poiché non è lineare su fidanzata(2)), rimane un'operazione lineare sullo spazio vettoriale definito sopra Fidanzata(2^8).

Il passaggio MixColumns, per sua stessa costruzione, applica una trasformazione lineare (moltiplicazione di matrici) a ciascuna colonna dello stato. L'unica componente non lineare in AES è l'operazione SubBytes, che impiega una S-box basata sull'inversione moltiplicativa in Fidanzata(2^8) (tranne per il fatto che zero viene mappato a zero), seguito da una trasformazione affine.

Esempi che illustrano la linearità

Supponiamo una colonna \mathbf{a} = (a_0, a_1, a_2, a_3)^T e un'altra colonna \mathbf{c} = (c_0, c_1, c_2, c_3)^TLa loro somma \mathbf{d} = \mathbf{a} \oplus \mathbf{c}Applicazione di MixColumns a \mathbf{un} e \mathbf{c} separatamente e poi sommando i risultati, si ottiene:

    \[ M \cdot \mathbf{a} \oplus M \cdot \mathbf{c} = M \cdot (\mathbf{a} \oplus \mathbf{c}) \]

Questa è una conseguenza diretta della proprietà distributiva della moltiplicazione delle matrici rispetto all'addizione nel campo.

Contrasto con livelli AES non lineari

Per chiarire ulteriormente, si consideri l'operazione SubBytes. La S-box viene costruita applicando l'inverso moltiplicativo in Fidanzata(2^8), che è un'operazione altamente non lineare, seguita da una trasformazione affine (che è lineare). Questa non linearità è essenziale per la resistenza di AES alla crittoanalisi. In netto contrasto, MixColumns non contiene alcun passaggio non lineare.

Esempio di implementazione

Considera una colonna con valori \mathbf{a} = (0xdb, 0x13, 0x53, 0x45)^T in esadecimale. Applicando la trasformazione MixColumns (secondo la specifica Rijndael), la colonna risultante è (0x8e, 0x4d, 0xa1, 0xbc)^TOgni byte di output viene calcolato come la somma delle moltiplicazioni di campo dei byte di input per le corrispondenti voci della matrice. Ogni passaggio è un'operazione di campo; nessuno di essi comporta una ricerca o una mappatura non lineare.

Il sottolivello MixColumns in AES non include una trasformazione non lineare. Si tratta di un'operazione strettamente lineare, rappresentata da una moltiplicazione di una matrice 4x4 su Fidanzata(2^8)Il requisito di non linearità per la sicurezza crittografica in AES è fornito dal livello SubBytes, non da MixColumns. Il ruolo di MixColumns è quello di fornire diffusione mescolando i byte nello stato, garantendo così che le modifiche in un byte influenzino più byte nei round successivi. Ciò aumenta la resistenza del cifrario a determinati attacchi, ma lo fa in modo lineare.

Rilevanza per la crittoanalisi e la sicurezza

Comprendere la linearità delle MixColumn è importante per la crittoanalisi. Le trasformazioni lineari sono generalmente più facili da modellare e invertire, quindi non forniscono sicurezza direttamente; servono invece a propagare gli effetti delle S-box non lineari lungo il blocco. Questa interazione tra diffusione lineare (MixColumn e ShiftRows) e confusione non lineare (SubBytes) è fondamentale per la progettazione di cifrari a blocchi robusti come AES.

Valore Didattico

Una chiara comprensione della distinzione tra operazioni lineari e non lineari in AES è fondamentale per studenti e professionisti della crittografia. Demistifica i meccanismi del cifrario e aiuta a comprendere l'esistenza di ogni passaggio e il suo contributo alla sicurezza complessiva. Studiando MixColumns come operazione lineare, si acquisiscono anche competenze pratiche nell'aritmetica dei campi finiti, ampiamente applicabile nella crittografia moderna, al di là di AES.

Altre domande e risposte recenti riguardanti Crittografia a blocchi AES:

Visualizza altre domande e risposte nel sistema crittografico di cifratura a blocchi AES

Altre domande e risposte:

Etichettato sotto: , , , , ,