S-scatole resistenti alla criptanalisi lineare e differenziale

Capitolo 1
Criptografia: nozioni
preliminari
1.1 Terminologia
L'obiettivo della criptografia è permettere a due persone, mittente e destina-
tario, di comunicare fra loro mediante un canale non sicuro, in modo che un
qualsiasi estraneo in ascolto, non sia in grado di capire ciò che si stanno dicen-
do. Chiameremo testi veri, (o testi chiari) le informazioni da inviare. Il testo
vero viene codificato usando una chiave predeterminata e si trasforma così in
testo cifrato che può essere immesso nel canale. In questo modo soltanto il de-
stinatario, che conosce la chiave, può ricostruire il messaggio originario.
Formalmente, si adottano le seguenti notazioni.
Definizione 1.1.1 Un criptosistema è una 5-pla (P, C,K, E ,D), che soddisfa
le seguenti condizioni:
1. P è un insieme finito di possibili testi veri;
2. C è un insieme finito di possibili testi cifrati;
3. K, lo spazio delle chiavi, è un insieme finito di possibili chiavi;
4. Per ogni k ∈ K, esistono una codifica ek ∈ E, ek : P → C, ed una decodifica
ad essa associata dk ∈ D, dk : C → P, tali che dk(ek(x)) = x per ogni
testo vero x ∈ P.
La condizione 4 è fondamentale: stabilisce che se un testo vero x è codificato
usando ek ed il testo cifrato risultante è successivamente decodificato usando
dk, ne risulta il testo vero originario. Chiaramente ogni funzione ek deve essere
iniettiva, e quindi biiettiva, altrimenti la decodifica non può avvenire in maniera
non ambigua. Per esempio, se
y = ek(x1) = ek(x2), con x1 6= x2
non c'è modo di stabilire quale fra x1 ed x2 sia la decodifica corretta per y.
Se P = C, ogni codifica è una permutazione, cioè se l'insieme dei testi veri coin-
cide con l'insieme dei testi cifrati, allora la codifica semplicemente permuta gli
7
8 CAPITOLO 1. CRIPTOGRAFIA: NOZIONI PRELIMINARI
elementi di questo insieme. Consideriamo due semplici esempi di criptosistemi
siffatti, che saranno rilevanti per il seguito:
Definizione 1.1.2 Criptosistema di Sostituzione
Poniamo P = C = Z26 e K = Sym26. Per ogni permutazione pi ∈ K, definiamo
epi(x) = pi(x),
e definiamo
dpi(y) = pi−1(y),
dove pi−1 è la permutazione inversa di pi.
Una chiave nel criptosistema di sostituzione è una permutazione delle 26
lettere dell'alfabeto. Il numero di permutazioni possibili su 26 elementi è 26! >
4×1026, un numero abbastanza alto da rendere una ricerca di tipo esaustivo della
chiave alquanto difficile anche per un computer. Ciononostante il criptosistema
di sostituzione può venir facilmente infranto con metodi che vedremo.
Definizione 1.1.3 Criptosistema di Permutazione
Sia m un intero positivo. Poniamo P = C = Z26m e K = Symm.
Per ogni chiave pi, definiamo
epi(x1, . . . , xm) = (xpi(1), . . . , xpi(m))
e
dpi(y1, . . . , ym) = (ypi−1(1), . . . , ypi−1(m)),
dove pi−1 è la permutazione inversa di pi.
L'idea su cui si basa il criptosistema di permutazione è mantenere inalterati
i simboli che compongono il testo vero e modificarne la posizione mediante una
permutazione.
Una permutazione su un insieme finitoX è una funzione biiettiva pi : X → X.
Dunque, per ogni x ∈ X, esiste un unico elemento x′ ∈ X tale che pi(x′) = x.
Questo permette di definire la permutazione inversa, pi−1 : X → X, come
pi−1(x) = x′ se e solo se pi(x′) = x.
Quindi anche pi−1 è una permutazione su X.
1.2 Cenni di criptanalisi
Il processo di tentare di ricostruire la chiave K, data una stringa di testo cifrato
y, è detto criptanalisi.
In questo paragrafo saranno esposte alcune tecniche di criptanalisi. L'ipotesi
che si fa in generale è che il tipo di criptosistema che si utilizza per scambiare
informazioni sia noto a chi è interessato ad intercettarle, questo è detto Principio
di Kerchoffs. Certo, se il criptosistema da infrangere non è noto al nemico, le
difficoltà che incontrerà nel provarci saranno maggiori, ma non si può basare la
sicurezza di un criptosistema su una premessa di questo tipo, quindi ogni volta
che si stima la sicurezza di un criptosistema si suppone che valga il principio di
Kerchoffs.
Le altre informazioni di cui il nemico può disporre definiscono differenti modelli
di attacco al criptosistema. I più comuni sono elencati qui di seguito:
1.3. SICUREZZA 9
• Attacco con solo testo cifrato
Il nemico possiede una stringa di testo cifrato, y;
• Attacco con testo vero noto
Il nemico possiede una stringa di testo vero, x, e la corrispondente stringa
di testo cifrato, y;
• attacco con testo vero scelto
Il nemico ha ottenuto accesso temporaneo al congegno di codifica, pertanto
può scegliere una stringa di testo vero, x, e costruire la corrispondente
stringa di testo cifrato y;
• attacco con testo cifrato scelto
Il nemico ha ottenuto accesso temporaneo al congegno di decodifica, per-
tanto può scegliere una stringa di testo cifrato, y, e costruire la stringa
corrispondente di testo vero, x.
In ogni caso, lo scopo del nemico è scoprire quale sia la chiave utilizzata per
cifrare i testi; questo infatti gli permetterebbe di infrangere completamente il
criptosistema e venire in possesso di tutte le informazioni scambiate attraverso
di esso.
1.3 Sicurezza
Se un criptosistema è progettato per venir utilizzato in pratica, deve soddisfare
alcune proprietà che si possono informalmente tradurre come:
1. Ogni codifica eK ed ogni decodifica dK devono essere calcolabili in maniera
efficiente.
2. Un nemico, venendo in possesso di una stringa di testo cifrato y, non
dovrebbe essere in grado di determinare né quale chiave K sia stata
utilizzata, né la corrispondente stringa di testo vero.
La seconda proprietà definisce, in maniera ancora piuttosto vaga, il concetto
di sicurezza per un criptosistema, che sarà approfondito in questo paragrafo.
Nel 1949 Claude Shannon pubblicò un articolo, intitolato Communication
Theory of Secrecy Systems che ebbe una grande influenza sullo studio scien-
tifico della criptografia. Qui discuteremo alcune delle idee di Shannon; pri-
ma, però, consideriamo i vari approcci possibili per valutare la sicurezza di un
criptosistema. Definiamo di seguito alcuni criteri utili.
• sicurezza computazionale
Questa misura riguarda lo sforzo computazionale necessario ad infrangere
un criptosistema. Si può definire un criptosistema computazionalmente
sicuro se il migliore algoritmo per infrangerlo richiede almeno N opera-
zioni, dove N è un numero abbastanza grande. Il problema è che nessun
criptosistema noto si può dimostrare sicuro sotto questa definizione. In
realtà, la sicurezza computazionale di un criptosistema si studia sempre
rispetto ad un determinato tipo di attacco, che può essere ad esempio la
ricerca esaustiva della chiave. Naturalmente, la sicurezza contro un tipo
specifico di attacco non fornisce garanzie di sicurezza nei confronti di tutti
gli altri.
10 CAPITOLO 1. CRIPTOGRAFIA: NOZIONI PRELIMINARI
• Sicurezza dimostrabile
Un altro approccio è fornire una prova di sicurezza per mezzo di una
riduzione. In altri termini, si fa vedere che se il criptosistema potesse ve-
nir infranto in una determinata maniera, allora sarebbe possibile risolvere
in modo efficiente un problema matematico noto, ritenuto difficile. Per
esempio, si può provare un'affermazione del tipo Un dato criptosistema è
sicuro se un intero dato n non può essere fattorizzato. I criptosistemi di
questo tipo vengono chiamati dimostrabilmente sicuri, anche se in realtà
questo tipo d'approccio fornisce garanzie di sicurezza solo relative ad un
altro problema e non una dimostrazione di sicurezza assoluta.
• Sicurezza incondizionata
Questa misura riguarda la sicurezza dei criptosistemi quando non sono
posti limiti alla capacità computazionale del nemico, né al numero di ope-
razioni che può fare. Un crittositema si definisce incondizionatamente
sicuro se non può venir infranto, nemmeno con infinite risorse di calcolo
a disposizione.
Quando si discute della sicurezza di un criptosistema, si deve sempre speci-
ficare che tipo di attacco si sta considerando.
1.3.1 Probabilità
La sicurezza incondizionata di un criptosistema ovviamente non può essere stu-
diata dal punto di vista della complessità computazionale, perché stiamo sup-
ponendo che il tempo di calcolo possa essere infinito. Quindi si ricorrerà alla
teoria della probabilità.
Definizione 1.3.1 Una variabile aleatoria discreta, X, è composta da un in-
sieme finito X e da una distribuzione di probabilità definita su X. La probabilità
che la variabile aleatoria X assuma il valore x si indica con Pr[X = x]; a volte
abbrevieremo questa scrittura con Pr[x] se la variabile aleatoria X è fissata. Si
deve avere che Pr[x] ≥ 0 per ogni x ∈ X, e∑
x∈X
Pr[x] = 1.
Definizione 1.3.2 Supponiamo che X ed Y siano variabili aleatorie definite
sugli insiemi X ed Y , rispettivamente.
La probabilità congiunta Pr[x, y] è la probabilità che X assuma il valore x ed
Y assuma il valore y.
La probabilità condizionata Pr[x|y] indica la probabilità che X assuma il valore
x quando Y assume il valore y.
Le variabili aleatorie X ed Y si dicono indipendenti se Pr[x, y] = Pr[x]Pr[y]
per ogni x ∈ X ed y ∈ Y .
La probabilità congiunta è legata alla probabilità condizionata dalla relazione
Pr[x, y] = Pr[x|y]Pr[y].
Scambiando x ed y, si ha che
Pr[x, y] = Pr[y|x]Pr[x].
1.3. SICUREZZA 11
Da queste due relazioni si ottiene immediatamente il risultato seguente, noto
come Teorema di Bayes.
Teorema 1.3.1 Se Pr[y] > 0, allora
Pr[x|y] = Pr[x]Pr[y|x]Pr[y] .
Corollario 1.3.1 X ed Y sono variabili aleatorie indipendenti se e solo se
Pr[x|y] = Pr[x], per ogni x ∈ X ed ogni y ∈ Y .
1.3.2 Perfetta segretezza
In questo paragrafo supponiamo di aver scelto un criptosistema (P, C,K, E ,D),
e che ogni chiave fissata K ∈ K sia usata per una sola codifica, supponiamo
inoltre che ci sia una distribuzione di probabilità sullo spazio dei testi veri,
P. Quindi al testo vero è associata una variabile aleatoria X. Indichiamo con
Pr[X = x] la probabilità che si presenti il testo vero x. Assumiamo inoltre che
la chiave K sia scelta usando una fissata distribuzione di probabilità, così anche
la chiave definisce una variabile aleatoria che denoteremo con K ed indicheremo
con Pr[K = K] la probabilità che sia scelta la chiave K. Ricordiamo che la
scelta della chiave è precedente alla scelta del testo da cifrare, pertanto è lecito
supporre che la chiave ed il testo vero siano variabili aleatorie indipendenti.
Le due distribuzioni di probabilità su P e su K inducono una distribuzione di
probabilità su C, abbiamo dunque un'altra variabile aleatoria, Y.
Sia K ∈ K, definiamo C(K) = {ek(x) : x ∈ P}, questo è l'insieme di tutti i
testi cifrati che si possono ottenere con la chiave K.
Sia y ∈ C, allora
Pr[Y = y] =
∑
{K:y=eK(x)}
Pr[K = K]Pr[X = dK(y)]
=
∑
{K:y∈C(K)}
Pr[K = K]Pr[X = dK(y)]
e
Pr[Y = y|X = x] =
∑
{K:x=dK(y)}
Pr[K = K]
ed usando il teorema di Bayes
Pr[X = x|Y = y] = Pr[X = x]
∑
{K:x=dK(y)}Pr[K = K]∑
{K:y∈C(K)}Pr[K = K]Pr[X = dK(y)]
.
Ora siamo in grado di definire il concetto di perfetta segretezza; informal-
mente significa che il nemico non può ottenere informazioni sul testo vero x,
osservando il testo cifrato y.
Definizione 1.3.3 Un criptosistema possiede perfetta segretezza se Pr[x|y] =
Pr[x], per ogni x ∈ P ed ogni y ∈ C, cioé la probabilità a posteriori che il testo
vero sia x, dato che il testo cifrato osservato è y, è eguale alla probabilità a
priori che il testo vero sia x.
12 CAPITOLO 1. CRIPTOGRAFIA: NOZIONI PRELIMINARI
Discutiamo ora, in generale, la perfetta segretezza. SePr[x0] = 0 per qualche
x0 ∈ P, siamo banalmente nel caso Pr[x0|y] = Pr[x0], per ogni y ∈ C. Quindi
possiamo ridurci a considerare solo i testi veri x ∈ P tali che Pr[x] > 0.
Per testi veri siffatti, osserviamo che, usando il teorema di Bayes, la condizione
Pr[x|y] = Pr[x] per ogni y ∈ C, è equivalente a Pr[y|x] = Pr[y] per ogni y ∈ C.
Assumiamo ora Pr[y] > 0 per ogni y ∈ C (se Pr[y] = 0, allora il testo cifrato y
non viene mai utilizzato, quindi si può escludere da C).
Fissiamo un qualsiasi x ∈ P. Per ogni y ∈ C, si ha Pr[y|x] = Pr[y] > 0.
Quindi per ogni y ∈ C deve esistere almeno una chiave tale che eK(x) = y. Ne
segue che |K| ≥ |C|. Ed in ogni criptosistema si ha |C| ≥ |P|, dato che le funzioni
eK devono essere iniettive.
Nel caso del'uguaglianza K = C = P, si può dare una caratterizzazione della
perfetta segretezza.
Teorema 1.3.2 Supponiamo che (P, C,K, E ,D) sia un criptosistema dove |K| =
|C| = |P|. Allora il criptosistema garantisce perfetta segretezza se e solo se ogni
chiave è usata con probabilità uniforme 1
|K| , e per ogni x ∈ P e per ogni y ∈ C,
esiste un'unica chiave K ∈ K tale che eK(x) = y.
Dimostrazione.
Supponiamo che il criptosistema dato possieda perfetta segretezza. Allora, per
ogni x ∈ P ed ogni y ∈ C, deve esistere almeno una chiave K tale che eK(x) = y.
Si ha quindi:
|C| = |{eK(x) : K ∈ K}| ≤ |K|.
E dato che stiamo supponendo |C| = |K|, si deve avere
|{eK(x) : K ∈ K}| = |K|.
Cioè non esistono due chiavi distinte K1 e K2 tali che eK1(x) = eK2(x) = y.
Dunque abbiamo dimostrato che, per ogni x ∈ P e per ogni y ∈ C, esiste
esattamente una chiave, K, tale che eK(x) = y.
Poniamo n = |K|. Sia P = {xi : 1 ≤ i ≤ n} e fissiamo un testo cifrato
y ∈ C. Possiamo denominare le chiavi K1,K2, . . . ,Kn, in modo che eKi(xi) = y,
1 ≤ i ≤ n. Usando il teorema di Bayes, si ha
Pr[xi|y] =
Pr[y|xi]Pr[xi]
Pr[y]
= Pr[K = Ki]Pr[xi]Pr[y] .
Consideriamo la condizione di perfetta segretezza Pr[xi|y] = Pr[xi]. Ne
segue che Pr[K = Ki] = Pr[y], per 1 ≤ i ≤ n. Questo ci dice che tutte le
chiavi sono utilizzate con la stessa probabilità, precisamente Pr[y]. E dato che
il numero delle chiavi è |K|, si deve avere che Pr[K] = 1
|K| per ogni K ∈ K.♦
Un criptosistema che realizza la perfetta segretezza è il One-time Pad, de-
scritto per la prima volta da Gilbert Vernam nel 1917 per essere impiegato nella
codifica e decodifica automatica di messaggi telegrafici.