Teorema dell'impilamento

Da Wikipedia, l'enciclopedia libera.

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 | modifica wikitesto]

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

X_1\oplus X_2\oplus\cdots\oplus X_n=0

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:

P(X_1 = i)=\left\lbrace\begin{matrix}p_1 & \hbox{for }i=0 \\ 1-p_1 & \hbox{for }i=1\end{matrix}\right.
P(X_2 = j)=\left\lbrace\begin{matrix}p_2 & \hbox{for }j=0 \\ 1-p_2 & \hbox{for }j=1\end{matrix}\right.

Adesso consideriamo:

P(X_1 \oplus X_2 = 0)

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

P(X_1=X_2)

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

P(X_1=X_2)=P(X_1=X_2=0) + P(X_1=X_2=1)=P(X_1=0, X_2=0) + P(X_1=1, X_2=1)

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:

P(X_1 \oplus X_2 = 0) =P(X_1=0)P(X_2=0)+P(X_1=1)P(X_2=1)\
=p_1p_2 + (1-p_1)(1-p_2)\
=p_1p_2 + (1-p_1-p_2+p_1p_2)\
=2p_1p_2-p_1-p_2+1\

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

P(X_1 \oplus X_2 = 0) =2(1/2+\varepsilon_1)(1/2+\varepsilon_2)-(1/2+\varepsilon_1)-(1/2+\varepsilon_2)+1\
=1/2+\varepsilon_1+\varepsilon_2+2\varepsilon_1\varepsilon_2-1/2-\varepsilon_1-1/2-\varepsilon_2+1\
=1/2+2\varepsilon_1\varepsilon_2\

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:

P(X_1\oplus X_2\oplus\cdots\oplus X_n=0)=1/2+2^{n-1}\prod_{i=1}^n \varepsilon_i

È 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 è

 \varepsilon_i = P(X_i=1) - P(X_i=0),

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

\varepsilon_{total}= P(X_1\oplus X_2\oplus\cdots\oplus X_n=1)- P(X_1\oplus X_2\oplus\cdots\oplus X_n=0)

abbiamo

\varepsilon_{total}=\prod_{i=1}^n \varepsilon_i,

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

Pratica[modifica | modifica wikitesto]

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.

Voci correlate[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

  • Mitsuru Matsui: Linear Cryptanalysis Method for DES Cipher - EUROCRYPT 1993
crittografia Portale Crittografia: accedi alle voci di Wikipedia che trattano di crittografia