P(m)

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
Meccanismi di sicurezza su reti

Nei sistemi distribuiti in rete, la sicurezza si
persegue attraverso diversi strumenti:






Identificazione degli utenti: ogni utente che accede a servizi
riservati deve essere identificato univocamente
Autorizzazione di un utente: individuare quali sono i privilegi
di cui gode un utente presso un sistema
Secretazione dei contenuti che devono passare in rete
Autenticazione: ogni contenuto generato da un dato utente
deve essere mantenuto integro e deve potersi attribuire in
modo univoco
Uso di sistemi di controllo del traffico (firewall)
Monitoraggio e controllo dei sistemi (intrusion detection)
Attacchi alla sicurezza dei messaggi
8
Sicurezza dei messaggi: 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).

Identificazione informatica
Per dispiegare servizi in rete con assoluta sicurezza
ed affidabilità, in primis è necessario avere la
certezza che ad un’utenza digitale sia associato
univocamente un soggetto fisico o giuridico
 Identificazione informatica: identificazione di un
soggetto per via telematica, consistente nella
validazione dell’insieme di dati attribuiti in modo
esclusivo ad esso
 Rispetto ai 4 paradigmi di sicurezza dei messaggi,
l’identificazione è importante ai fini
dell’autenticazione e della non ripudibilità
 L’identificazione informatica deve essere tanto più
sicura quanto più è sensibile la transazione in cui è
coinvolto il soggetto da identificare

L’identificazione tramite username e
password


L’identificazione basata su username e password è
il più semplice sistema di riconoscimento digitale
È una forma di identificazione debole: funziona
bene per autenticazioni su sistemi locali, ma per
applicazioni sensibili su reti aperte, ove occorre
poter verificare aldilà di ogni ragionevole dubbio
che chi si presenta sia veramente chi dice di
essere, non è sufficiente, in quanto è
tendenzialmente violabile
La forza di una password



Formalmente, la forza di una password può essere
espressa in funzione del numero atteso di tentativi
necessari ad un avversario per forzarla mediante un
attacco esaustivo (brute-force)
Tale valore dipende dalla sua lunghezza, complessità ed
imprevedibilità
Quest’ultimo parametro, noto anche come entropia
informativa, è una misura dell’incertezza associata ad
ogni carattere (visto come una variabile casuale) che
costituisce la password
L’attacco brute-force
Ad esempio, una password di 8 caratteri ASCII (che comprendono 52
lettere minuscole/maiuscole dell’alfabeto inglese, 10 numeri, e 34
simboli non-alfanumerici, per un totale di 95 simboli), se scelta in
modo del tutto casuale, ha una forza di 53 bit:
958  253
ovvero, richiede la generazione di 253 stringhe binarie casuali di 53
bit prima di essere individuata con certezza
 il numero atteso di tentativi per forzarla è 253/2 = 252
 Osserviamo che 252  1016, un numero molto grande ma non enorme.
Ad esempio, esistono in commercio prodotti che garantiscono il
testing di circa 3 miliardi di password al secondo su un normale PC da
4 GigaHz. In tal modo, si può forzare la password in circa 107 secondi,
ovvero circa 4 mesi! (questo è anche il motivo per cui spesso si
richiede di cambiare la password ogni 3-6 mesi)

Dalla teoria alla realtà

In realtà le cose vanno un po’ diversamente:
Le password non vengono scelte in modo del tutto casuale: si
calcola che mediamente una password di 8 caratteri abbia una
forza effettiva di circa 30 bit (dato NIST, National Institute of
Standards and Technology of USA)
 testando 3 miliardi di password al secondo, una password da 8
caratteri verrà forzata in circa 1 secondo, e una da 10 in circa 1
giorno!
Tuttavia, non tutto è perduto:


I sistemi di identificazione godono di meccanismi di delay tra
l’inserimento di una password e la successiva
Ogni carattere casuale in più nella password aggiunge circa 6 bit di
forza, e ogni bit di forza in più raddoppia il numero di tentativi
necessari per forzare una password  una password di 14 caratteri
casuali avrebbe una forza sufficiente per resistere ad attacchi tipo
brute-force
Password cracking
Esistono tuttavia molte altre modalità di attacco ad
una password, tra cui:
 Wiretapping (monitoraggio dei tasti premuti)
 Phishing (spillaggio dei dati sensibili)
 Social engineering (induzione a rivelare informazioni
riservate)
 Dumpster diving (frugare nella spazzatura,
letteralmente)
 L’identificazione mediante password non garantisce in
modo certo l’identità di un determinato utente, e quindi
non soddisfa il requisito dell’autenticazione (né
tantomeno soddisfa gli altri paradigmi di sicurezza)

 Vedremo che la soluzione ci verrà fornita dalla tecnica
crittografica asimmetrica RSA
La crittografia
La crittografia (dal greco kryptos,
nascosto, e graphein, scrivere) è la
disciplina che si occupa delle problematiche
connesse alla sicurezza dei dati
 Anticamente si occupava unicamente dello
studio di tecniche atte a garantire la
secretazione dei dati, mentre oggi investe
l’analisi di tutti gli aspetti (teorici,
computazionali, implementativi) legati ai
vari paradigmi di sicurezza

16
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 (n1)*n/2 chiavi, ad esempio con 100 utenti
occorreranno 4950 chiavi!
Infine, come può un metodo simmetrico
garantire l’autenticazione e l’irripudiabilità,
dal momento che esso è pensato per
soddisfare unicamente il requisito della
secretazione?
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
(Public Key Infrastructure)




Dove trovo le chiavi pubbliche dei miei
destinatari?
Creazione di archivi di chiavi pubbliche, i
cosiddetti public key server (PKS) (ad
esempio, http://pgp.mit.edu/)
Un PKS può essere interrogato per risalire
alla chiave pubblica di un soggetto
Curiosità: il prefisso pgp sta per “pretty good
privacy”, ed è lo standard de facto, creato nel
1991 da Phil Zimmermann, per la trasmissione
di mail criptate
Fare una query su un PKS
La risposta ad una query
E cliccando su un soggetto…
Public Key Server -- Get ``0x77d987e3f2baf942 ''
-----BEGIN PGP PUBLIC KEY BLOCK----Version: SKS 1.1.0
mQENBEvtGsMBCACxCvcmPawOxaPjFkOi3dwhb6wJWFrCfbIhCrE7+klo58YqAJoaN9iMrd27
D2rD5jrGmqR4ah0QTE8QE3EOANNlz0jsVvyv5A/7LBT0xR9o5oJ+m0p2tdaMTJV05Atz2uEI
wkalcGb6pLFightrCIeJ5V94rHcw0xFTXPE3FCDKhuJ80OSKYZWj+jbv0l3ZbuN6KGEVdWHe
hwZMWcELx9C32a6HcvAgFlAmCzZk8RYzyORLgA/DBNzf8yl5Yn7rV9tWFyLREg9ytWs6JDwA
Hm7wOlUeogOoK+ORdrFdsV6Eges+ThUMlg33r/XQZ37MDs6reCua7+QbYBwWBYqO9ExDABEB
AAG0HG1hcmlvIHJvc3NpIDxtcm9zc2lAemV1cy5pdD6JAT4EEwECACgFAkvtGsMCGyMFCQlm
AYAGCwkIBwMCBhUIAgkKCwQWAgMBAh4BAheAAAoJEHfZh+PyuvlCSR0H+wTcejkqWCT7YoCv
RaGqXTaUljtdJ8L3m9yDmjJtJ2Hhr7xrFTdwxdOqjx9TdHtxyFvoyem0ez4rRslv3AKPbYHB
2ThEtc+Jtk9ITNtss7fEp/Ix3bE7v3NQmazxaEAhXqS9ra8s08UkydfaRqkw58IB/J9wHDJ1
nbvvbLjolZOU+val1WmFAZYKUbZ866BeF2rKRiRHvIN3ur28JpRIUM0Yma9LrAthm8PufnA4
qpSm8b/52ldG4S8rRfDWMcQJZQiL0JnRELlqz4ta6erg4fDHsWgUnDSrCP7TYEgT/aG/GV6T
SWwpXhnKEUMHuPvJy1hMF8Z/zjWxyJ0/kSZ1x++5AQ0ES+0awwEIAMEfDp/MNvdCyPplAqGh
ByxiYJjpokYYNJBY9ytMyYYpWSN+s3lc335KjX9n/K0AqCO2a3LXfUzxRQvh5eHuZWxaT3yV
oqnu86n/M10MFVziOx52x2cn+qhSLm8I82ESHDUjh9dFPTmBlmGhYHJa2bq6duchDx737ZuV
fQKgTtJIj8XdKtv5zrTMn2h9CBshmbzUJvIvxtWSZq0vmMlZZd5H8aVDBH1C30MOyyIwLF0c
zwf6dhJ6KTHM2AAwdcUvD/HyaOFKDeMWPPfUBmC4az0bLw1onIw6N0YmnfT+nupP3QXK6IKe
KIbsQYQA5po+5fZIEb2o9A7nIYB/i4wjlakAEQEAAYkBJQQYAQIADwUCS+0awwIbDAUJCWYB
gAAKCRB32Yfj8rr5QkwiCACit52gt9FWC1gjXSf7PSw2GSt/+NABt4F0yHoFidLRVNHRfWj1
J41dZUaHPzF+0zvk3E/j1oITGc0uKa201FMpflY/nUEOrwdzbRGZcgFJNVAGtm4glrCIv3c6
oVrmavRXPeWnmzdDzXRPQCItoMvniMhDMO1sfsWcMuGYuOB4oopjkAowc1s4M5qsOLA8pfsL
CTx6JmtLPA49YxaolB3NZiSSDy6A91lV66vJKmpNseaWQsNs3X4vhBWS89Ct39wCe6Cx+ddh
Ri2qLcPNEDQQVcDWP+DTHSrhJrStx14iJRBfHMQW6EaL2B4t7RZzKknRPxOw/wUE4gS62ay7
wJgz
=scGC
-----END PGP PUBLIC KEY BLOCK-----
Le certification authority
•
•
•
•
•
Ma chi mi garantisce la corrispondenza delle chiavi
pubbliche con i legittimi proprietari?
Nascita delle certification authority (CA), che
rilasciano a pagamento i cosiddetti certificati digitali
(firmati con la chiave privata della CA), che associano
in modo univoco un soggetto con la rispettiva chiave
pubblica
Le CA e i PKS sono le componenti principali di una PKI
I costi di un certificato digitale sono variabili (da 20 a
800 Euro circa) e dipendono dal livello di sicurezza e
dalla versatilità offerta
Le CA italiane sono vigilate da DigitPA (attualmente
abbiamo soltanto 17 CA accreditate in Italia)
Sicurezza sul Web


L'Hypertext Transfer Protocol (HTTP) è il
principale sistema per la trasmissione d'informazioni
sul Web, e si appoggia sul protocollo in chiaro
TCP/IP
Le architetture web basate su HTTP non
garantiscono la sicurezza:




non è sicuro che l’utente sia veramente chi dice di essere
(masquerading)
non è sicuro che le chiamate arrivino dall’indirizzo ip
presente nei pacchetti in arrivo (ip spoofing)
non è sicuro che i parametri delle request o i contenuti
delle response non siano stati letti o modificati da qualcuno
nel tragitto (la trasmissione è in chiaro)
non è sicuro il contenuto associato ai cookies (tracking di
sessioni e memorizzazione di informazioni specifiche
riguardanti gli utenti che accedono al server)
Il protocollo HTTPS
(HTTP over Secure Socket Layer)


È il risultato dell'applicazione del protocollo di
crittografia asimmetrica RSA (in forma debole, di solito a
chiavi da 128 bit) al protocollo HTTP
È il protocollo solitamente utilizzato per comunicazioni
protette client-server sul Web (ad esempio, per
effettuare un pagamento), e funziona come segue:
il client acquisisce il certificato digitale del server, e
attraverso il proprio browser interroga la CA emittente per
essere sicuro di dialogare con una parte fidata; quindi,
genera le proprie chiavi pubblica e privata (attraverso il
proprio browser, che le rinnova ad ogni nuova sessione
aperta), e invia la propria chiave pubblica al server;
 il server invia al client una chiave simmetrica (cosiddetta
session key) criptata con la chiave pubblica del client, per
stabilire una connessione protetta a chiave simmetrica;
 infine, il client decripta la chiave simmetrica inviata dal
server con la propria chiave privata, e le due parti sono
pronte per dialogare nel canale protetto a chiave simmetrica.

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: Per un intero positivo z, xy mod z  esiste un
intero k t.c. x-y=kz (se x ed y sono positivi, questo è
equivalente a dire che il resto della divisione intera tra
x e z e tra y e z è lo stesso, ovvero x mod z = y mod z)
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: secretazione








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 “nobiased” 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).
Osservazione: si noti la differenza sostanziale con il metodo
Las Vegas usato per il calcolo del MIS, in cui la risposta era
sempre e comunque corretta, mentre la complessità temporale
era invece data in forma probabilistica.
Algoritmo di Miller-Rabin

È basato sulla seguente proprietà: dato un intero (positivo) n dispari
(del quale vogliamo testare la primalità), riscriviamolo come n=2sr+1,
con r dispari (quindi s è la molteplicità del fattore 2 nella
scomposizione in fattori primi del numero pari n-1). Sia ora 2≤y≤n-1, e
definiamo i 2 predicati:
(P1): MCD(n,y)=1;
i
(P2): (yr mod n = 1) OR (esiste 0≤i≤s-1 t.c. y2 r-1 mod n).
Teorema: Se n è primo, allora ogni 2≤y≤n-1 soddisfa entrambi i
predicati (e quindi se esiste un 2≤y≤n-1 che non soddisfa almeno uno
dei due predicati, n è composto), mentre se n è composto il numero di
interi 2≤y≤n-1 che soddisfano entrambi i predicati è minore di n/4.
 Eseguiamo MR(n) un certo numero k di volte, testando ogni volta (P2)
su un intero positivo 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 %è falsa la prima condizione di (P2)
2.3.1 j=0
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 %è falsa anche la
seconda condizione di (P2), e
quindi è falso (P2)
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.