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 e network security
 attacchi, meccanismi, servizi

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: strumenti
automatici per proteggere le
informazioni di un calcolatore
Network security: misure per
proteggere lo scambio di informazioni
durante la loro trasmissione
4
Network security

Nuovi paradigmi
 informazioni
distribuite
 accesso tramite sistemi distribuiti

Nuove problematiche di sicurezza
 sicurezza
delle reti locali
da attacchi esterni
 da impiegati infedeli

 sicurezza
ftp,…)

delle applicazioni (e-mail, http,
fondamentali per le funzioni aziendali e il
commercio elettronico
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 geografiche non
avvengono tramite linee punto-punto ma

 attraverso
linee condivise
 tramite router di terzi
6
Sicurezza: aspetti fondamentali
Attacchi alla sicurezza: azioni che
violano la sicurezza delle informazioni
possedute da un'organizzazione
 Meccanismi di sicurezza: misure
hardware e software progettate per
prevenire e contrastare gli attacchi alla
sicurezza
 Servizi di sicurezza: servizi che
garantiscono la sicurezza delle
informazioni mediante l’uso di uno o più
meccanismi di sicurezza

7
Attacchi alla sicurezza
8
Meccanismi di sicurezza


Esiste una grande varietà di meccanismi di
sicurezza, sia hardware che software, 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”.
 Insieme
delle tecniche che consentono di realizzare la
cifratura di un testo e la decifrazione di un
crittogramma. (Dizionario Garzanti, 1972)
9
Servizi di sicurezza: esempi
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).

Garantire segretezza e integrità
Garantire segretezza e integrità
Principio di Kerckhoffs: “La sicurezza di un sistema
crittografico deve essere basata esclusivamente sulla
inespugnabilità della chiave di cifratura (gli algoritmi di
cifratura e decifratura devono essere considerati noti).”
Crittografia: 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.
Crittografia moderna



Nel 1949 C. Shannon pubblicò un articolo che diede
l’inizio a quella che oggi viene chiamata la Teoria
dell’Informazione.
L’unione di questa nuova scienza, della Teoria della
Probabilità, della Teoria della Complessità e della
Teoria dei Numeri diede vita alla Crittografia
Moderna.
Definizione: Un crittosistema è una quintupla
(P,C,K,Cod,Dec), dove,
 P: insieme finito dei testi in chiaro
 C: insieme finito dei testi cifrati
 K: insieme delle possibili chiavi di cifratura
 Cod: PK→C funzione di cifratura (iniettiva
 Dec:
CK→P funzione di decifratura
e invertibile)
Proprietà di un crittosistema


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.
Un crittosistema si dice perfetto se il testo
in chiaro e quello cifrato sono statisticamente
indipendenti.
 Shannon ha dimostrato che condizione
necessaria affinché un crittosistema sia
perfetto è che la lunghezza della chiave sia
almeno pari alla lunghezza del testo da cifrare
Un cifrario perfetto

One-time pad (G. Verman, AT&T, 1917):
1. Si costruisce una grande chiave casuale (e
non pseudocasuale) ad esempio utilizzando un
rivelatore di raggi cosmici.
2. Il testo cifrato è costruito tramite uno
XOR bit a bit fra il messaggio in chiaro e la
chiave casuale.
3. La chiave non deve mai essere riutilizzata
(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 probabilisticamente
improbabili.

Tutti i cifrari moderni realmente utilizzati
appartengono alla classe dei computazionalmente
sicuri.
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!

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 “algoritmo distribuito” viene
cifrato nel crittogramma “dolrunzpr gnvzuneanzr”.
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
Lo stato dell’arte nella crittografia a
chiave simmetrica: Rijndael



Sviluppato da Joan Daemen e Vincent
Rijmen.
Questo algoritmo 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, ed una
rete di “confusione del messaggio”, in
cui si eseguono molteplici operazioni di
trasposizione, xoring e sostituzione di
blocchi di messaggio di lunghezza
prefissata.
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à.
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à!
I vari scenari a chiave pubblica
Terzo scenario: A codifica con la chiave pubblica associata
a B ed autentica 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).
• 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 digit, cioè dell’ordine di 10400, da cui:
O(∙)≈e79≈1034
da cui l’intrattabilità computazionale.
 le chiavi sono lunghe in genere 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+kn)
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
Invio di un messaggio cifrato
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)=xe mod n (con x<n),
ove (e,n) è la chiave privata di A.
La funzione di decifratura di B è:
Dec(x)=Cod(x)d mod n = (xe mod n)d mod n
ove (d,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, 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.
 Corollario (Piccolo teorema di Fermat): Per ogni primo
n>1, e per ogni a{1,…,n-1}, si ha che an-11 mod n (ovvero,
ana mod n).
Teorema cinese del resto: Siano n1, n2,…, nk primi tra loro a
due a due, e sia n= n1·n2 ·…·nk. Allora, comunque si scelgano
degli interi a1, a2,…, ak, esiste almeno un intero x soluzione
del sistema di congruenze
xai mod ni i=1,..,k.
e tutte le soluzioni di tale sistema, sono congruenti modulo 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!
Ora occorre provare che per ogni 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.
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, abbiamo xxk0 mod p, ovvero (xkx)0 mod p, per qualunque intero positivo k. 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.
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 “si” 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 SI, è 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 “si”, 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.