Aspetti algoritmici
connessi alla sicurezza
nei sistemi informatici
distribuiti
Testo consigliato

Crittografia, P. Ferragina e F. Luccio, Ed.
Bollati Boringhieri, € 16.
2
Sommario

Introduzione
 computer
security vs network security
 attacchi, meccanismi di sicurezza

Cenni di crittografia
 Crittografia
a chiave privata
 Crittografia a chiave pubblica

Applicazioni di network security (??)
 servizi
di autenticazione (firma digitale)
3
Computer security vs
network security


Computer security: misure per
proteggere le informazioni di un
calcolatore
Network security: misure per
proteggere lo scambio di informazioni
durante la loro trasmissione
4
Network security

L’era di Internet…
 Informazioni
distribuite
 Posta elettronica
 Commercio elettronico
 Transazioni finanziarie

…e le nuove problematiche di sicurezza
 sicurezza
delle reti locali
da attacchi esterni
 da impiegati infedeli

 sicurezza
delle applicazioni (e-mail, http, ftp,…)
5
Problemi base
Le reti sono insicure perché molte delle
comunicazioni avvengono in chiaro
 Spesso non c’è autenticazione dei
server, ma solo (e non sempre) degli
utenti
 Le connessioni non avvengono tramite
linee punto-punto ma

 attraverso
linee condivise
 tramite router di terzi
6
Attacchi alla sicurezza su reti
7
Sicurezza dei dati: paradigmi
Segretezza: evitare che i dati inviati da
un soggetto A a un soggetto B vengano
compresi da un terzo soggetto C.
 Autenticazione: verificare l’identità di
chi manda o riceve i dati.
 Integrità: essere sicuri che i dati
ricevuti siano uguali a quelli inviati.
 Non ripudio: evitare che chi manda dei
dati possa in futuro negare di averli
mandati (firma digitale).

Meccanismi di sicurezza


Esiste una grande varietà di meccanismi
atti a garantire la sicurezza dei dati, quasi
tutti basati su tecniche crittografiche
La crittografia (dal greco kryptos,
nascosto, e graphein, scrivere) è la
disciplina che si occupa dello studio delle
scritture “segrete”.
9
Cenni storici



La crittografia è una scienza antichissima
utilizzata nell’antichità per nascondere il
contenuto di messaggi scritti.
La crittografia conobbe un enorme sviluppo
durante la Seconda Guerra Mondiale, quando il
matematico inglese Alan Turing formalizzò la
teoria necessaria per decrittare il
crittosistema tedesco Enigma.
Nel 1949 Shannon pubblicò un articolo che
diede l’inizio a quella che oggi viene chiamata la
Teoria dell’Informazione, che assieme alla
Teoria della Probabilità, la Teoria della
Complessità e la Teoria dei Numeri gettò le
basi della Crittografia Moderna.
Crittosistema
Def.: Un crittosistema (o cifrario) è una
quintupla (M,C,K,Cod,Dec), dove,
 M:
insieme finito dei testi in chiaro
 C: insieme finito dei testi cifrati
 K: insieme delle possibili chiavi
 Cod: MK→C funzione di cifratura (iniettiva e
invertibile)
 Dec: CK→M funzione di decifratura
Se Cod e Dec utilizzano la stessa chiave per
cifrare e decifrare un dato testo, allora si parla di
crittosistema simmetrico, altrimenti di
crittosistema asimmetrico.
Garantire la segretezza
Principio di Kerckhoffs: “La sicurezza di un sistema
crittografico deve essere basata esclusivamente sulla
inespugnabilità della chiave (gli algoritmi di cifratura e
decifratura devono essere considerati noti, e il testo cifrato
in transito deve essere considerato pienamente leggibile).”
Algoritmi a chiave simmetrica
Chiave simmetrica: i due soggetti (A e
B) usano la stessa chiave K per
codificare e decodificare i dati.
 Gli algoritmi di crittografia sono
pubblici  la chiave simmetrica deve
essere segreta  il principale problema
è lo scambio della chiave!

Lo scenario a chiave simmetrica
Il problema della trasmissione della chiave


Volendo utilizzare un cifrario simmetrico per
proteggere le informazioni tra due
interlocutori come posso scambiare la chiave
segreta?
Devo utilizzare una canale sicuro di
comunicazione (oppure A e B devono essersi
preventivamente accordati)
Un primo esempio di cifrario a chiave
simmetrica: il cifrario di Cesare



Consideriamo l’alfabeto italiano, e costruiamo un cifrario
che sostituisce ad ogni lettera di questo alfabeto la
lettera che si trova 3 posizioni in avanti.
Ad esempio il testo in chiaro “algoritmi distribuiti” viene
cifrato nel crittogramma “dolrunzpn gnvzuneanzn”.
Anche se la chiave rimane segreta, è facilmente
attaccabile tramite approcci statistici.
La crittoanalisi statistica

Tramite l’utilizzo di tecniche statistiche sulla frequenze
dei caratteri o sottostringhe del testo cifrato si
ottengono informazioni utili sul testo in chiaro.
Crittoanalisi del cifrario di Cesare

Il cifrario di Cesare, come la maggior parte dei
cifrari storici basati tu trasposizioni e traslazioni,
può essere facilmente violato utilizzando tecniche
statistiche (crittoanalisi statistica).
Si analizzano le frequenze relative dei caratteri nel testo
cifrato e le si confrontano con quelle di una lingua
conosciuta, ad esempio l'italiano.
 Con queste informazioni si ottiene un’ottima
approssimazione del testo in chiaro

NOTA: Il cifrario di Cesare può essere facilmente
violato anche con un approccio esaustivo: basta
testare le 21 possibili traslazioni (i.e., chiavi) fino ad
ottenere un testo comprensibile!
Cifrari perfetti


Un crittosistema si dice perfetto se il testo
in chiaro e quello cifrato sono statisticamente
indipendenti.
Formalmente, definiamo un cifrario perfetto
come segue: la comunicazione tra A e B è vista
come un processo stocastico (cioè variabile in
modo aleatorio nel tempo) in cui:
 P(m): probabilità che il messaggio spedito sia m;
 P(m|c): probabilità che il messaggio spedito sia m
avendo visto transitare il messaggio cifrato c;
Def.: Un cifrario è perfetto se per ogni mM e
per ogni cC vale la relazione:
P(m|c) = P(m).
Due cifrari molto imperfetti



Supponiamo che P(m)=p, 0<p<1, e che
P(m|c)=0≠p; allora, un crittoanalista che vede
transitare c, è in grado di dedurre che il
messaggio spedito non può essere m!
Supponiamo adesso che P(m)=p, 0<p<1, e che
P(m|c)=1≠p; allora, un crittoanalista che vede
transitare c, è in grado di dedurre che il
messaggio spedito corrisponde ad m!
In tutti i casi intermedi in cui P(m|c)≠p, il
crittoanalista può fare delle deduzioni
osservando i messaggi cifrati in transito!
Impraticabilità dei cifrari perfetti
Teorema (Shannon): condizione necessaria affinché
un crittosistema sia perfetto è che |K|≥|M|.
Dim.: Osserviamo che |M|≤|C|. Se per assurdo
fosse |K|<|M|, allora |K|<|C|. Sia m un messaggio
arbitrario t.c. P(m)=p≠0. Allora, da esso possono
essere generati al più |K| messaggi cifrati (uno per
ogni chiave). Ne consegue che esiste almeno un
messaggio cifrato c* che non è immagine di m,
ovvero:
P(m|c*)=0≠p=P(m)
contro l’ipotesi di perfezione.
□
Un cifrario (simmetrico) perfetto

One-time pad (G. Verman, AT&T, 1917):
1.
2.
3.
4.
Si costruisce una grande chiave casuale k nota ad A
e B (e non pseudocasuale…questo impedisce l’uso di
generatori algoritmici, e impone lo scambio della
chiave!), ad esempio utilizzando un rivelatore di raggi
cosmici
Il testo cifrato è costruito tramite uno XOR bit a
bit (ricorda: 10=01=0; 11=00=1) fra il
messaggio in chiaro m e la chiave casuale k  c=mk
B ricostruisce m=ck (infatti xyy=x)
La chiave non deve mai essere riutilizzata (one-time
pad).
One-time pad è perfetto!
Dobbiamo mostrare che P(m|c)=P(m). Siano m
e c di n bit; dal Teorema di Bayes si ha:
P(m|c)=P(m∩c)/P(c)
dove P(m∩c) è la probabilità che A abbia
generato il messaggio m e lo abbia cifrato
come c; allora
P(m∩c)=P(m∩c=mk)=P(m)P(c=mk)=P(m)2-n
indipendenza statistica di m e c
mentre:
P(c)=∑m P(m∩c)= ∑m P(m)2-n=2-n ∑m P(m)=2-n

P(m|c)=P(m)2-n/2-n=P(m).
□
One-time pad è solo
teoricamente perfetto…
1.
2.
3.
4.
In pratica, come fanno A e B a scambiarsi la
chiave k?
La soluzione è accordarsi preventivamente su una
supersequenza di bit casuali, da consumare a
mano a mano che ci si scambiano
messaggi…bisognerà solo specificare la porzione
della supersequenza da usare di volta in volta.
La supersequenza va trasferita a priori con
metodi tradizionali (messaggero…)
La linea rossa Cremlino-Casa Bianca è secretata
(si dice…) con il metodo one-time pad!
Dalla perfezione alla realtà…

A fronte dei cifrari perfetti (ovvero
dimostrabilmente sicuri ma praticamente
inutilizzabili) esistono anche cifrari:
 Computazionalmente
sicuri – Il problema
crittoanalitico (ovvero di decrittazione di un testo
cifrato senza conoscere la chiave) è
computazionalmente intrattabile.
 Probabilisticamente sicuri – Sono cifrari di cui è stata
dimostrata l’inattaccabilità, a patto che non si
verifichino alcuni eventi improbabili.

Tutti i cifrari moderni realmente utilizzati
appartengono alla classe dei computazionalmente
sicuri.
Lo stato dell’arte dei cifrari
simmetrici imperfetti: Rijndael


Sviluppato da Joan Daemen e Vincent Rijmen, ha
vinto la selezione per l’Advanced Encryption
Standard (AES) nel 2000. Ufficialmente il
Rijndael è diventato lo standard per la cifratura
del XXI secolo a chiavi simmetriche.
Il cifrario utilizza chiavi di lunghezza variabile a
128, 192, 256 bit (generate da un gestore
esterno), ed una rete di “confusione del
messaggio”, in cui si eseguono molteplici
operazioni (circa 10) di trasposizione, xoring e
sostituzione di blocchi di messaggio di lunghezza
pari a quella della chiave.
I limiti dei metodi a chiave simmetrica
Un canale sicuro di comunicazione per
scambiarsi la chiave segreta esiste
veramente nella realtà? E se esistesse,
perché ricorrere alla crittografia???
 Inoltre, per una comunicazione sicura
tra n utenti, si dovranno scambiare in
tutto (n-1)*n/2 chiavi, ad esempio con
100 utenti occorreranno 4950 chiavi!

Algoritmi a chiave asimmetrica

Chiave Pubblica/Privata: Ogni soggetto S ha
 una
propria chiave pubblica Kpub(S), nota a tutti;
 una propria chiave privata Kpriv(S) nota solo a lui.

I requisiti che un algoritmo a chiave pubblica
deve soddisfare sono:
i
dati codificati con una delle chiavi possono essere
decodificati solo con l’altra;
 la chiave privata non deve mai essere trasmessa in
rete;
 deve essere molto difficile ricavare una chiave
dall’altra (in particolare la chiave privata da quella
pubblica).
I vari scenari a chiave pubblica
Primo scenario: A codifica con la chiave pubblica associata a
B, il quale decodifica con la propria chiave privata:
garantisce segretezza e integrità (non l’autenticità,
perché tutti possono codificare, non solo A)
I vari scenari a chiave pubblica
Secondo scenario: A codifica con la propria chiave privata il
messaggio da inviare a B, il quale decodifica con la chiave
pubblica associata ad A: garantisce autenticità e non
ripudiabilità (non la segretezza, perché tutti possono
decodificare)
I vari scenari a chiave pubblica
Terzo scenario: A codifica con la chiave pubblica associata
a B ed autentica (i.e., firma) con la propria chiave privata:
garantisce segretezza, integrità, autenticità e non
ripudiabilità!
La nascita dei sistemi PKI
• Dove trovo le chiavi pubbliche dei miei destinatari?
• Creazione di “archivi di chiavi pubbliche”, i public
key server.
• Ma chi mi garantisce la corrispondenza delle chiavi
pubbliche con i legittimi proprietari?
• Nascita delle certification authority (CA) (ad
esempio, in Italia per la PEC, le Poste Italiane)
• A questo punto chi garantisce la validità delle
certification authority?
Atto di fede!
La matematica dei sistemi a
chiave pubblica
Venne introdotta da Diffie e Hellman nel 1976:
 Definizione: Una funzione f si dice one-way se per
ogni x il calcolo computazionale di y=f(x) è semplice (è
in P), mentre il calcolo di x=f-1(y) è
computazionalmente difficile (è NP-hard).
 Definizione: Una funzione one-way è detta trapdoor
(letteralmente, cassetta delle lettere) se il calcolo
x=f-1(y) può essere reso facile qualora si conoscano
informazioni aggiuntive (private).
… ma purtroppo per loro, essi non furono in grado di
costruire una funzione one-way trapdoor!
Il cifrario RSA



Progettato nel 1977 da Ron Rivest, Adi Shamir e
Leonard Adlemann, il cifrario è stato brevettato, ed è
diventato di dominio pubblico solo nel 2000.
Idea base: Dati due numeri primi p e q (molto grandi) è
facile calcolare il prodotto n=p∙q, mentre è molto
difficile calcolare la fattorizzazione di n (anche se tale
problema non è noto essere NP-hard).
I migliori algoritmi di fattorizzazione attualmente
disponibili (Quadratic Sieve, Elliptic Curve Method,
Euristica ρ di Pollard, ecc.) hanno tutti una complessità
esponenziale dell’ordine di:
Il cifrario RSA

Per garantire la sicurezza, occorre che p e q siano
almeno di 200 cifre decimali. Infatti, se p e q sono
di 200 cifre decimali ciascuno, allora n è di 400
cifre, cioè dell’ordine di 10400, da cui:
≈e79≈1034
da cui l’intrattabilità computazionale.
 le chiavi sono lunghe in genere
10200 = 2200*log10  1024 bitS.

RSA è molto più lento degli algoritmi a chiave
simmetrica, e spesso viene applicato a piccole
quantità di dati, ad esempio per la trasmissione
della chiave privata in un sistema simmetrico
Funzionamento di RSA: generazione delle chiavi
Ricorda: xy mod z  il resto della divisione intera tra
x e z e tra y e z è lo stesso, ovvero x mod z = y mod z
(o equivalentemente, se esiste un intero k t.c. x=y+kz)
1. Scegli due primi molto grandi p e q e calcola n =p∙q.
2. Calcola la funzione toziente di Eulero rispetto ad n, ovvero
la cardinalità dell’insieme dei numeri minori di n e primi con
esso:
ϕ(n)=ϕ(pq)=pq-[(q-1)+(p-1)]-1=pq-(p+q)+1=
=(p-1)(q-1)=ϕ(p)ϕ(q)
(poiché esistono q-1 multipli di p minori di n e p-1 multipli
di q minori di n)
3. Scegli un numero 0<e<ϕ(n) t.c. MCD(e,ϕ(n))=1.
4. Calcola d tale che e·d1 mod ϕ(n).
5. Definisci la chiave pubblica come (e,n).
6. Definisci la chiave privata come (d,n).
Funzionamento di RSA
Secretazione di un messaggio
1.
2.
La funzione di cifratura di A è Cod(x)=xe mod n (con x<n),
ove (e,n) è la chiave pubblica del destinatario B.
La funzione di decifratura di B è:
Dec(x)=Cod(x)d mod n = (xe mod n)d mod n
ove (d,n) è la chiave privata di B.
Autenticazione di un messaggio
1.
2.
La funzione di cifratura di A è Cod(x)=xd mod n (con x<n),
ove (d,n) è la chiave privata di A.
La funzione di decifratura di B è:
Dec(x)=Cod(x) e mod n = (xd mod n) e mod n
ove (e,n) è la chiave pubblica di A.
Correttezza di RSA: alcuni teoremi di
algebra modulare


Teorema (equazioni modulari): L’equazione axb mod n
ammette soluzione se e solo se MCD(a,n) divide b. In questo
caso si hanno esattamente MCD(a,n) soluzioni distinte.
 Corollario (esistenza dell’inverso): Se a e n sono primi
tra loro, allora ax1 mod n ammette esattamente una
soluzione positiva minore di n, detta l’inverso di a modulo
n.
Teorema di Eulero: Per ogni n>1, e per ogni a primo con n, si
ha che aϕ(n)1 mod n.
Correttezza di RSA



Si noti innanzitutto che e e ϕ(n) sono primi tra loro, e quindi
dal corollario sull’esistenza dell’inverso, esiste un unico d
minore di ϕ(n) tale che e∙d1 mod ϕ(n).
Qui sta la forza di RSA: per ricavare d da e bisogna conoscere ϕ(n), cioè p e q, e quindi bisogna saper fattorizzare!
Secretazione: occorre provare che  x<n, Dec(Cod(x))=x. Ma
Dec(Cod(x))=(xe mod n)d mod n=xed mod n,
quindi dobbiamo mostrare che x=xed mod n.
Dimostratelo!
Distinguiamo due casi:
1. p e q non dividono x (e quindi MCD(p,x)=MCD(q,x)=1, poiché
essi sono primi);
2. p (oppure q) divide x, ma q (oppure p) non divide x.
(si noti che p e q non possono entrambi dividere x, perché
altrimenti si avrebbe x≥n contro le ipotesi)
Correttezza di RSA (2)
Caso 1: Abbiamo MCD(x,n)=1, quindi per il th di Eulero, risulta
xϕ(n)1 mod n; poiché ed1 mod ϕ(n), si ha che ed=1+kϕ(n),
per un k opportuno. Quindi, poiché x<n, si ha:
xed mod n = x1+kϕ(n) mod n = x·(xϕ(n))k mod n = x·1k mod n = x.
Caso 2: Poiché p divide x, per qualunque intero positivo k
abbiamo xxk0 mod p, ovvero (xk-x)0 mod p. Poiché invece
q non divide x, analogamente al Caso 1, abbiamo anche xedx
mod q, e quindi (xed-x)0 mod q. Ne consegue che (xed-x) è
divisibile sia per p che per q, e quindi per il loro prodotto n,
da cui deriva
(xed-x)0 mod n  xedx mod n  xed mod n = x mod n = x.
□
Autenticazione: si noti che RSA gode della notevole proprietà:
Dec(Cod(x))=Cod(Dec(x)).








Esempio di funzionamento di RSA
B sceglie ad esempio p=3 e q=11.
Quindi n=33 e ϕ(n)=20.
Si può prendere e=3, poiché 3 non ha divisori comuni
con 20  (3,33) è la chiave pubblica di B
Cerco d t.c. 3d1 mod 20. Con l’equazione 3d= 1+k·20,
ponendo k=1 si trova d=7  (7,33) è la chiave
privata di B
Per cifrare un blocco P (P<33) da inviare a B, A
calcola
C:=Cod(P)=P3 mod 33
Per decifrare C, B calcola P=C7mod 33
Poiché n=33, si cifrano al più 5 bit alla volta (25<33)
Nella pratica, n è dell’ordine di 21024, e quindi si
possono cifrare blocchi di 1024 bit, cioè blocchi di
128 caratteri ASCII (di 8 bit ciascuno).
Esempio di funzionamento di RSA
Per visualizzare l’esempio precedente, supponiamo per
semplicità che le 26 lettere dell’alfabeto inglese possano
essere codificate con 5 bit, e quindi poiché n=33, posso
cifrare un carattere alla volta
Complessità computazionale di RSA





Si può dimostrare che le chiavi (e quindi p,q,e,d) possono
essere generate in tempo polinomiale (ovvero logaritmico
nel loro valore).
In particolare, e viene in genere scelto prendendo un
numero primo abbastanza piccolo (ad esempio, e=3).
Invece, d viene ricavato mediante un’estensione
(polinomiale) dell’algoritmo di Euclide per il calcolo del
MCD (basato sul fatto che MCD(a,b)=MCD(b,a mod b)).
Tuttavia, per trovare numeri primi molto grandi (cioè p e
q), i test di primalità utilizzati sono tutti di tipo
probabilistico, in quanto quelli deterministici sono troppo
lenti (sebbene polinomiali, ma dell’ordine di O(log10n)).
Infine, si noti che i processi di cifratura e decifrazione
possono essere eseguiti efficientemente tramite
successive esponenziazioni (potenza modulare).
Alla ricerca di p e q


Definizione (Algoritmo Monte Carlo): Un
algoritmo Monte Carlo “no-biased” è un algoritmo
randomizzato per la risoluzione di un dato
problema di decisione, in cui la risposta “no” è
sempre corretta, mentre la risposta “sì” può
essere inesatta con probabilità fissata ε.
Analogamente sono definiti gli algoritmi Monte
Carlo “yes-biased”.
L’algoritmo di Miller e Rabin è un algoritmo
Monte Carlo “no-biased” per testare la primalità
di un numero. Esso ha una complessità di O(log3
n), e una probabilità di inesattezza ε≈1/4 (cioè
se risponde SÌ, è corretto con probabilità ≈3/4).
Algoritmo di Miller-Rabin

E’ basato sulla seguente proprietà: per un intero n dispari,
e per un qualche 2≤y≤n, poniamo y-1=2wz, con z dispari
(quindi w è il max esponente consentito per 2), e definiamo
i 2 predicati:
(P1): MCD(n,y)=1;
i
(P2): (yz mod n = 1) OR (esiste 0≤i≤w-1 t.c. y2 z mod n=-1).
Teorema: Se n è primo soddisfa entrambi i predicati,
mentre se n è composto il numero di interi compresi tra 1 e
n-1 che soddisfano entrambi i predicati è minore di n/4.
 Eseguiamo MR(n) un certo numero k di volte, testando ogni
volta i due predicati su un intero a caso minore di n. Se
l’algoritmo risponde “no” anche una sola volta il numero è
sicuramente composto, mentre se risponde sempre “sì”, la
probabilità che il numero sia composto è 4-k, e quindi la
probabilità che il numero sia primo è:
P(primo)=1-P(composto)=1-4-k
(ad es., se k=100, si ha P≈1-10-60 ≈ 1)
Algoritmo di Miller-Rabin
Miller-Rabin(n)
1.
Set n-1=2sr con r dispari
2.
For i=1 to k do
2.1 scegli a caso un intero t t.c. 2≤t≤n-2
2.2 calcola y=tr mod n
2.3 if y≠1 esegui
2.3.1 j=1
2.3.2 while ((j≤s-1) and (y≠n-1))
y:=t2jr mod n
j++
3.
2.3.3 if y≠n-1 ritorna composto
Ritorna primo (w.h.p. 1-4-k)
E’ facile trovare numeri primi?



Nonostante l’efficienza nel testare se un numero sia
primo o meno resta l’incognita se i numeri primi siano
“pochi” e quindi difficili da scovare.
Teorema di Gauss (dei numeri primi): Sia π(n) la
funzione di distribuzione dei numeri primi, cioè il
numero di numeri primi che precedono n. Allora essa
soddisfa il seguente:
Quindi se si cerca un numero primo di 100 cifre
occorre verificare “solo” ln (10100) ≈ 230 numeri
consecutivi.