Questo corso ha come finalita' principale l'introdurre e applicare gli strumenti matematici fondamentali per lo studio della crittografia contemporanea e della teoria dei codici.
In particolare, si studieranno e analizzeranno i piu' diffusi sitemi crittografici sia simmetrici (DES,AES) che asimmetrici (RSA, ElGamal, Diffie-Hellman) e le loro applicazioni a problemi quali l'anonimita', la segretezza e la mutua autenticazione.
Verra' inoltre presentata in dettaglio la teoria dei codici lineari (con limitazioni, proprieta', algoritmi di codifica e decodifica), per poi poter discutere i recenti sviluppi nell'ambito dei turbo-codice e degli LDPC.
PROGRAMMA DETTAGLIATO DEL CORSO
Problemi fondamentali della crittografia
Introduzione alla crittografia; crittografia classica e moderna; protocolli di comunicazione.
Modelli di attacco e nozioni di sicurezza. Crittografia a chiave segreta e a chiave pubblica.
Richiami di teoria dei gruppi
La nozione di gruppo; sottogruppi. Classi laterali e sottogruppi normali. Il teorema di omomorfismo. Gruppi ciclici. Ordine di un elemento. Il teorema di Lagrange. Il problema del logaritmo discreto.
Algoritmi crittografici basati sul logaritmo discreto
Il protocollo Diffie-Hellman. Sua crittoanalisi. Il problema dell'autenticazione. Il protocollo STS.
Il crittosistema ElGamal. Proprieta' e crittoanalisi. Osservazioni.
Aritmetica modulare e teoria dei numeri
L'algoritmo euclideo e l'algoritmo euclideo esteso. Classi di congruenza: proprieta'.
Anelli. Il piccolo teorema di Fermat. Il simbolo di Jacobi. La funzione di Eulero. Criteri di primalita'.
Il crittosistema RSA e le sue varianti
Il crittosistema RSA: definizione e prime proprieta'.
Crittoanalisi e attacchi contro RSA; il problema della sicurezza semantica. Il modello IND-CPA.
Varianti di RSA: il protocollo OAEP.
Algoritmo euclideo esteso, polinomi e campi finiti
Domini euclidei. L'algoritmo euclideo esteso in domini euclidei. Proprieta' nel caso degli anelli di polinomi. Costruzione di campi finiti. Proprieta' e caratterizzazione del gruppo moltiplicativo.
AES
Motivazione: DES e 3-DES. Vulnerabilita' degli stessi.
L'Advanced Encryption Standard: costruzione e implementazione. Crittoanalisi e attacchi di tipo algebrico.
Elementi di crittoanalisi algebrica
Aspetti di crittoanalisi algebrica: crittoanalisi differenziale e integrale. Attacchi contro protocolli effettivamente implementati.
Curve ellittiche e loro applicazioni alla crittografia
Definizione di curva ellittica. Curve ellittiche su campi finiti; il gruppo dei punti e la legge di gruppo. Osservazioni sulla struttura degli stessi. I protocolli basati su EC. Dettagli di implementazione.
Protocolli basati sul bilinear pairing
La nozione di bilinear pairing fra gruppi. Applicazioni ad attacchi crittografici ma anche alla costruzione di crittosistemi con proprieta' particolari. Firma digitale "breve".
Schemi per il Key-escrow
Bilinear pairing e key escrow: applicazioni e osservazioni.
ID-based encryption
Protocolli a conoscenza zero e anonimita'
La nozione di zero-knowledge. Protocolli distribuiti e applicazioni.
Schemi di anonimita' digitale e di verificabilita' dei dati. Applicazioni ai problemi del voto elettronico.
Cenni di crittografia omomorfica
Codici correttori lineari
Teoria matematica della comunicazione. La nozione di codice correttore. Codici a blocchi.
Distanza di Hamming. Codici lineari. Limitazioni. La decodifica a sindrome.
Codici ciclici
La costruzione dei codici ciclici. Proprieta'. Algoritmi di codifica e decodifica.
Codici di Reed-Solomon e DFT
Costruzione dei codici di Reed-Solomon. Limitazioni. L'algoritmo di Welch-Berlekamp. Legami con la DFT.
Codici LDPC e turbo codici
Network coding