CRITTOGRAFIA

Il corso fornisce un'introduzione ai concetti fondamentali della crittografia moderna. Obiettivo del corso sarà definire e costruire adeguati strumenti crittografici quali cifrari, message authentication codes e firme digitali. Cercheremo di capire che proprietà dovrebbero soddisfare tali strumenti, come formalizzare rigorosamente tali proprietà e come costruire schemi che le soddisfano. Ci soffermeremo soprattutto su schemi ampiamente diffusi in pratica, come AES, SHA, HMAC e RSA. In particolare, cercheremo di capire in dettaglio come sono costruiti e che livello di sicurezza garantiscono.

Il corso non prevede moduli di programmazione

Obiettivi formativi generali dell'insegnamento in termini di risultati di apprendimento attesi.

1. Conoscenza e capacità di comprensione (knowledge and understanding): l'obiettivo del corso è quello di far acquisire conoscenze che consentano allo studente di comprendere le idee ed i principi che stanno alla base della crittografia moderna; in particolare lo studente acquisirà le conoscenze dei principali strumenti crittografici utilizzati in pratica.
2. Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): lo studente acquisirà le competenze necessarie per utilizzare in modo sicuro strumenti crittografici quali schemi di cifratura, di autentica e funzioni hash crittografiche.
3. Autonomia di giudizio (making judgements): Attraverso esempi concreti di errori derivanti dall'utilizzo di soluzioni solo all'apparenza sicure lo studente sarà in grado di utilizzare autonomamente soluzioni crittografiche in grado di garantire elevati livelli di sicurezza.
4. Abilità comunicative (communication skills): lo studente acquisirà le necessarie abilità comunicative e di appropriatezza espressiva nell'impiego del linguaggio tecnico nell'ambito generale della crittografia moderna.
5. Capacità di apprendimento (learning skills): il corso si propone, come obiettivo, di fornire allo studente le necessarie metodologie teoriche e pratiche per poter affrontare e risolvere autonomamente nuove problematiche che dovessero richiedere l'utilizzo di strumenti crittografici quali cifrari, schemi di firme digitali e funzioni hash.

Le lezioni sono tenute in aula con l'ausilio di slide, rese disponibili agli studenti sulla pagina web del docente (www.dmi.unict.it/catalano/). Le slide non sostituiscono i testi di riferimento, ma, oltre che agevolare la comprensione della lezione, forniscono un dettaglio puntuale sul programma svolto.

Per una adeguata comprensione dei contenuti del corso sono necessari i seguenti prerequisiti.

• Basi di matematica discreta.
• Nozioni basilari di algoritmi

La frequenza delle lezioni non è obbligatoria ma fortemente consigliata.

1. Introduzione e breve panoramica del corso

Materiale: Cap 1 di [1]

2. Cifrari Storici e One Time Pad. Il cifrario shift cipher. Il cifrario substituition cipher. Crittanalisi di substitution cipher. Perfetta Sicurezza. Subst. Cipher non offre perfetta sicurezza (dimostrazione). One time pad. One time pad offre perfetta sicurezza (dimostrazione). One time pad è ottimo (dimostrazione). Teorema di Shannon (enunciato)

Materiale: Cap 2 di [1] e cap. 2 di [3]

3. Cifrari a Blocchi: AES

Materiale: Cap 3 di [1]

4. Funzioni e permutazioni Pseudo Casuali. Introduzione e definizioni. Applicazioni ai cifrari a blocchi. Qualche esempio. La sicurezza in senso prf implica sicurezza in senso key recovery (dimostrazione). Il paradosso del compleanno.

Materiale: Cap. 4 e Appendice di [1]

5. Cifrari Simmetrici: modi d'operazione. Modo ECB, Modo CBC$, Modi CTR (a stati e randomizzato). Nozione di sicurezza per cifrari simmetrici: IND-CPA. Attacchi a messaggio scelto e attacchi a crittotesto scelto. Prova che un cifrario deterministico non può essere sicuro. Ind-cpa security implica plaintext recovery security (dimostrazione). Indistinguibilità relativamente ad attacchi a crittotesto scelto: IND-CCA security. Ind-cpa security non implica ind-cca security: il caso di CTR$ (dimostrazione)

Materiale: Cap 5 di [1] e Cap 3 di [3]

6. Funzioni Hash.. Resistenza alle collisioni: funzioni universali, funzioni universali unidirezionali, funzioni resistenti alle collisioni. Attacchi generici alle funzioni hash. Attacchi alle funzioni MD4, MD5, SHA1 (cenni). La trasformazione Merkle-Damgard. Cenni su SHA3.

Materiale: Cap 6 di [1] e Appunti

7. Message Authentication. Definizione di sicurezza per MAC. Il paradigma PRF as a MAC. CBC-MAC. Basic CBC-MAC se applicato a messaggi di lunghezza variabile non è sicuro (dimostrazione). (In)sicurezza di CBC-MAC randomizzato. CBC-MAC per messaggi di lunghezza variabile. MAC da funzioni hash: HMAC.

Materiale: Cap 7 di [1] e Cap 4 di [3]

8. Introduzione alla crittografia asimmetrica. Funzioni unidirezionali e funzioni trapdoor. Richiami di teoria dei numeri computazionale. Generalità sui gruppi. Algoritmo di Euclide, teorema cinese del resto. Quadrati residui.

Materiale: Cap 9 di [1], capitoli vari di [2]

9. Primitive Asimmetriche. Il problema del logaritmo discreto su campi finiti. Il problema computazionale Diffie Hellman. Il problema decisionale Diffie-Hellman. Fattorizzazione. La funzione RSA. Cenni su test di primalità. Algoritmo Miller-Rabin. L'algoritmo square and multiply.

Materiale: Cap 10 di [1]. Appunti delle lezioni.

10. Cifrari Asimmetrici. Definizioni di sicurezza per cifrari asimmetrici. Cifrari Asimmetrici. Definizione di sicurezza per cifrari asimmetrici. Il cifrario El Gamal. Il cifrario El Gamal è sicuro (in senso IND-CPA) relativamente all'ipotesi decisional Diffie-Hellman (dimostrazione).

Il cifrario Paillier. Preliminari matematici. Il cifrario Paillier gode della proprietà di omomorfismo additivo (dimostrazione).

Il cifrario RSA-OAEP. Proprietà del cifrario.

Cifrari basati sull'identità: il cifrario Boneh Franklin. Mappe bilineari. Proprietà del cifrario.

Materiale: Cap 11 di [1] Cap 11 di [3] e appunti delle lezioni.

11. Firme digitali. Preliminari. Definizione di sicurezza per firme digitali. Hash and Sign.

Materiale: Cap 12 di [1] Appunti delle lezioni.

12. Inntroduzione a Bitcoin. Blockchain e Merkle Trees. Esempi di cryptocurrencies elementari. Consenso. Come Bitcoin realizza consenso. Proofs of Work. Mining. Bitcoin e anonymity.

Materiale: capitoli vari di [4].

[1] M. Bellare, P. Rogaway “Introduction to Modern Cryptography”

• Scaricabile da http://www.cs.ucsd.edu/~mihir/cse107/classnotes.html

[2] V. Shoup A Computational Introduction to Number Theory and Algebra

• Scaricabile da http://shoup.net/ntb/

[3] J. Katz, Y. Lindell “Introduction to Modern Cryptography” CRC press

[4] A. Miller, A. Narayanan, E. Felten, J. Bonneau, and S. Goldfeder “Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction”. Princeton University Press.

L'esame consiste di una prova scritta ed un colloquio orale. La prova scritta consiste, tipicamente, di 5 domande a risposta aperta.

Per superare la prova scritta è necessario ottenere una valutazione di almeno 18. La prova scritta può essere visionata prima di sostenere la prova orale.

Prove in itinere: Sono previste tre prove in itinere. La prima prova verte, tipicamente, sul concetto di perfetta sicurezza, sui cifrari a blocchi e sulle funzioni e permutazioni pseudocasuali. La seconda prova verte su: cifrari simmetrici, funzioni hash e message authentication. La terza prova copre il resto del programma (crittografia asimmetrica)

• Definizioni di sicurezza (cifrari simmetrici, asimmetrici, firme digitali, ecc)
• Esercizi sulle primitive crittografiche studiate (ad esempio: dimostrare che un dato cifrario è insicuro)
• Algoritmi (ad es. fornire e spiegare lo pseudocodice di algoritmi studiati a lezione)