Crittografia
Una Panoramica
del Corso
Luciano Margara
Dipartimento di Scienze dell’Informazione,
Università di Bologna
Obiettivo:
Comunicazioni private in
ambienti pubblici
?
Strumento: Cifrari
1
Esiste un cifrario “perfetto” ?
Perfetto ~ inattaccabile.
La risposta è né SI né NO !!
Esistono cifrari perfetti ma costosi
Esistono cifrari pratici meno perfetti ma economici ed efficienti
Robustezza
Conquistata sul campo
Relazione con problemi matematici difficili
Alcune Definizioni
Crittologia: Crittografia + Crittoanalisi
Crittografia: progetto di cifrari sicuri ed efficienti.
Crittoanalisi: metodi, strumenti e tecniche per attaccare
i cifrari (~ valutare la loro bontà).
Difficoltà di risoluzione
impossibilità: NO
improponibilità: SI
L’intruso X
Lo Scenario
Mitt
c
c
…
Dest
X
Mitt = mittente del messaggio m in chiaro
Dest = destinatario del crittogramma c
X = impostore che ascolta (crittoanalista)
C e D funzioni di cifratura e decifrazione
Motivo: curiosità, spionaggio, malvagità,…
Ruolo
Passivo: si limita ad ascoltare
Attivo: può inserirsi nella comunicazione o modificarla
Informazioni in suo possesso:
Cipher-text attack: serie di crittogrammi c1,…., cn
Known plain-text attack: collezione di coppie (mi, ci)
Chosen plain-text attack: collezione di coppie scelte
2
Definizioni e Notazione
Funzione di cifratura
C(m) = c
è il crittogramma
Come realizzare C e D ?
Due grandi famiglie:
Cifrari per uso ristretto
Cifrari per uso generale (con chiave segreta)
Funzione di decifrazione
D(c) = m
è il messaggio in chiaro originale
Matematicamente D è l’inversa di C:
D(C(m)) = m
Se D(C(m)) = C(D(m)) = m, allora commutativa
Siamo al punto di partenza ?
Quanto costa scambiare la chiave ?
Incontro face-to-face ma una tantum
Posso ammortizzare il costo dello scambio
Posso usare canali costosi e disponibili poco frequentemente
Lo spazio delle chiavi deve essere grande:
No brute-force attacks (visita esaustiva dello spazio)
Prerequisito cruciale ma non sufficiente
Passo in avanti sostanziale:
Dal punto di vista teorico
Dal punto di vista economico
Esempi: DES, RC5, IDEA, … (hanno superato la prova del fuoco)
Uso della chiave segreta k comporta:
C e D diventano C k e Dk
(funzioni parametriche)
Ck e Dk sono note a tutti, k è tenuta segreta
Sicurezza si fonda solo su k
Cosa significano ora “facile” e “impossibile” ?
Cifrari Simmetrici
Ruolo di Ck e Dk completamente interscambiabile
Mittente ~ Destinatario:
Conoscono la stessa chiave k
Entrambi possono cifrare e decifrare
Incontro segreto per accordarsi sulla chiave
Segretezza della chiave dipende da entrambi
Cifratura e decifrazione sono molto efficienti in pratica
Qual è il limite di questi cifrari ?
Dati n utenti, abbiamo bisogno di [n (n-1) / 2] chiavi
Troppe per essere memorizzate e scambiate segretamente
3
Crittografia a Chiave Pubblica
Anno 1976: punto di svolta!
Il Nuovo Scenario
U1
(Diffie-Hellman e Merkle)
Obiettivo: rompere il legame tra Ck e Dk
c1
Chiunque sappia come cifrare non deve sapere come decifrare
Dest
Chiave k scomposta in due parti < k[priv], k[pub] > :
La chiave k viene creata da Dest
Un
k[priv] tenuta segreta da Dest e usata per costruire D k[priv]
k[pub] resa pubblica da Dest e usata da tutti per definire Ck[pub]
cn
Difficile andare da k[pub] a k[priv] !!
Concetto funzione one-way trap-door:
Numero chiavi per n utenti ---> soltanto n !!
Lasciano penetrare qualche informazione...
Ck[pub] facile, ma Dk[priv] difficile senza k[priv] !
Esempi: RSA, El Gamal, … (sono considerati oggi robusti)
Panacea delle comunicazioni segrete?
Conclusioni
Cifrari asimmetrici sono inefficienti !
Confidenzialità è il solo requisito dei sistemi crittografici moderni ?
Sistemi Ibridi = asimmetrici + simmetrici !!
Oggigiorno se ne richiedono altri 4:
Mitt e Dest scelgono “pubblicamente” una chiave “segreta” K* utilizzando un
cifrario asimmetico
Mitt e Dest comunicano con un cifrario simmetrico basato su
K*
K* viene sostituita più volte nel corso di una comunicazione
(session-key)
Lentezza degli asimmetrici incontrata solo nello scambio sporadico delle session-key.
Incontro face-to-face per scambio chiavi segrete (nei simmetrici) aggirato attraverso l’uso
dei cifrari asimmetrici per raggiungere l’accordo.
N2 chiavi segrete (nei simmetrici) nascoste dall’uso delle session-key (usa e getta).
User Identification:
Identification: Dest può accertare che è proprio Mitt che sta
parlando o vuole parlare con lui.
Integrità
Integrità: Deve essere possibile per Dest stabilire che il messaggio
ricevuto non ha subito modifiche parziali o totali (sostituzione).
Autenticazione: Deve essere possibile per Dest accertare che il
messaggio ricevuto proviene proprio da Mitt.
Firma Elettronica: Mitt non può sottrarsi dall’ammettere che è stato
lui a spedire il messaggio, e Dest può convincere una terza persona
(giudice) che questo è il caso.
4