Teorema dell'impilamento

In crittanalisi il teorema dell'impilamento (piling-up lemma) è un principio utilizzato nella crittanalisi lineare per costruire le approssimazioni lineari dei cifrari a blocchi. È stato introdotto da Mitsuru Matsui nel 1993 come uno strumento analitico della crittanalisi lineare.

Teoria modifica

Il teorema dell'impilamento permette al crittanalista di determinare la probabilità che la seguente equazione sia valida:

 

dove le x indicano variabili binarie (vale a dire con valore 0 o 1).

Poniamo P(A) come indice della "probabilità che A sia vera": se è uguale a 1, A è certo che si verifichi; se è uguale a 0, A non si può verificare. Prima di tutto consideriamo il teorema dell'impilamento per 2 variabili binarie:

 
 

Adesso consideriamo:

 

A causa delle proprietà dell'operazione di XOR, questa equazione è equivalente a

 

X1 = X2 = 0 e X1 = X2 = 1 sono eventi mutuamente esclusivi, per cui possiamo dire che

 

Adesso dobbiamo impostare l'assunto centrale del teorema dell'impilamento: le variabili binarie che stiamo trattando sono indipendenti: questo significa che lo stato di una non ha effetto sullo stato di nessuna delle altre. Possiamo così espandere la funzione della probabilità come segue:

   
 
 
 

Adesso esprimiamo le probabilità p1 e p2 come ½ + ε1 e ½ + ε2, dove le ε indicano la quantità dello scostamento dalla probabilità rapportata a ½.

   
 
 

Lo scostamento dalla probabilità ε1,2 per le somme XOR qui sopra è così 2ε1ε2.

Questa formula può essere estesa a più X come segue:

 

È da notare che se nessuna delle ε è pari a 0, cioè che lo scostamento dalla probabilità di una delle variabili binarie è 0, allora lo scostamento dalla probabilità dell'intera funzione della probabilità sarà pari a ½.

Una definizione un po' diversa dello scostamento è

 

infatti due segni meno danno il valore precedente. Il vantaggio è che adesso con

 

abbiamo

 

aggiungendo i valori di variabili casuali per moltiplicare i loro scostamenti (seconda definizione).

Pratica modifica

In pratica le X sono approssimazione delle S-box (componenti di sostituzione) dei cifrari a blocchi. Di solito i valori X sono i dati in ingresso delle S-box ed i valori Y sono i corrispondenti dati in uscita. Guardando semplicemente alle S-box, il crittanalista può dire quali sono i valori degli scostamenti. Il trucco sta nel trovare le combinazioni di valori in ingresso ed in uscita che hanno probabilità pari a 0 o 1. Più l'approssimazione si avvicinerà a 0 o 1, più utile sarà per la crittanalisi lineare.

Nella pratica, le variabili binarie non sono comunque indipendenti, così come si intende nel significato ipotizzato dal teorema dell'impilamento. Questa considerazione deve essere tenuta a mente quando si applica il teorema, dato che non si tratta di una formula crittanalitica automatica.

Bibliografia modifica

  • Mitsuru Matsui: Linear Cryptanalysis Method for DES Cipher - EUROCRYPT 1993

Voci correlate modifica

  Portale Crittografia: accedi alle voci di Wikipedia che trattano di crittografia