- Oggetto:
- Oggetto:
Crittografia e Codici Correttori (DM 509) - a.a. 2009/10
- Oggetto:
Anno accademico 2009/2010
- Codice dell'attività didattica
- MFN0145
- Docente
- Prof. Umberto Cerruti (Titolare del corso)
- Corso di studi
- Laurea in Matematica
- Anno
- 3° anno
- Periodo didattico
- Secondo semestre
- Tipologia
- D.M. 509
- Crediti/Valenza
- 5
- SSD dell'attività didattica
- MAT/02 - algebra
- Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
Tra le infinite applicazioni della Matematica moderna, sono particolarmente importanti, sia per l'impatto che hanno nella vita di ogni giorno sia per la profondità e la novità dei risultati teorici, la Crittografia e la Teoria dei Codici Correttori di Errore. La finalità del corso è duplice: 1) Mostrare che la Matematica è in grado di offrire metodi e algoritmi che permettono di trasmettere su canali insicuri informazioni risevate, in modo tale che: - solo gli utenti abilitati possano accedere ad esse - sia certa l'identità del mittente (firma elettronica) - il contenuto del messaggio non possa essere alterato da nessuno. 2) Studiare alcune tecniche di base per correggere gli errori dovuti alla trasmissione di un messaggio su un canale disturbato. Vale la pena di osservare che, mentre tutti ormai sono al corrente dell'esistenza della crittografia, e ne riconoscono facilmente la necessità (evidente quando comunicano, per esempio, con una banca), pochi conoscono i codici correttori, dei quali si parla poco. In realtà essi sono indispensabili ad ogni forma di comunicazione digitale. Senza di essi non si potrebbe nemmeno ascoltare un CD, non parliamo di vedere le foto di Marte! Lo studente, al termine del corso, è in grado di comprendere meglio il funzionamento effettivo delle comunicazioni digitali. Matematicamente ha imparato la differenza tra il vedere se un numero è primo e il fattorizzarlo (differenza attualmente abissale). Possiede alcuni strumenti fondamentali della teoria dei numeri, come la Legge di Reciprocità Quadratica. Ha esperienza concreta dei campi finiti e di certi importantissimi quozienti dell'anello dei polinomi. Conosce protocolli crittografici recenti e efficaci codici di correzione di errori.
- Oggetto:
Risultati dell'apprendimento attesi
Metodi di fattorizzazione, test di primalità, teoria elementare dei numeri, crittografia e protocolli crittografici, fondamenti della teoria dei codici correttori con esempi efficaci.
- Oggetto:
Programma
Parte prima: i fondamenti della Crittografia
Storia breve della crittografia.
Cifrari monoalfabetici. Crittoanalisi statistica dei cifrari monoalfabetici.
Cifrari polialfabetici.
Crittoanalisi statistica dei cifrari polialfabetici. Teorema di Friedman.
Macchine a rotori (Enigma).
Codici perfetti (Vernam).
Realizzazione dei codici perfetti. Cenni sui generatori di numeri pseudocasuali.
Il problema dello scambio delle chiavi. Doppio lucchetto e sue debolezze.
La crittografia a chiave pubblica e i suoi vantaggi.
Parte seconda: i metodi matematici
Simbolo di Legendre e legge di reciprocità quadratica.
Simbolo di Jacobi.
Soluzione delle equazioni di secondo grado modulo p e modulo pq.
Teorema di Soloway - Strassen.
Pseudoprimi di Fermat, Eulero, Miller.
Fattorizzazione: metodi p-1 e rho di Pollard.
Parte terza: i protocolli crittografici
Diffie - Hellman.
RSA.
ElGamal.
Rabin e altri.
Autenticazione e firma digitale.
Firma cieca.
Secret splitting e secret sharing.
Cena dei crittografi.
Lancio della moneta digitale.
Poker mentale.
Autenticazione e dimostrazioni a conoscenza nulla.
Denaro digitale.
Parte quarta: i codici correttori, le basi della teoria
Generalità, distanza di Hamming, sfere e loro volume, quantità di informazione e efficienza.
Limite di Hamming.
(n,k)-codici e posti di informazione. Limite di Singleton.
Codici lineari e loro vantaggi.
Matrice di controllo, teorema di Hamming.
I codici di Hamming.
Metodo di decodifica per i codici lineari (metodo della sindrome).
Algebra R(n,q) e codici ciclici.
Divisori e zeri dei codici. Polinomio generatore.
Codici BCH con distanza minima garantita.
Parte quinta: approfondimenti sui codici correttori
Laterali e classi ciclotomiche.
La struttura dell'algebra R(n,q), divisori e ideali.
Codici di Reed - Solomon.
Codici estesi, proiezione dei codici.
Correzione delle raffiche di errore.
Congiunzione di codici.
Codici di Reed - Muller.
Codici correttori e crittografia: Mc Eliece.
Cenni sui codici che provengono dai piani proiettivi.
Brief history of Cryptography. Mono and polyalphabetic codes.
Statistical analysis. Friedman’s theorem.
Rotor machines and perfect codes.
Introduction to PRNG (Pseudo Random Numbers Generators).
Key exchange and public key cryptography.
Legendre and Jacobi symbols. The quadratic reciprocity law.
Second order equations Mod p and Mod pq.
Primality testing and pseudoprimes.
Factorization.
Cryptographic protocols.
Digital cash.
The essentials of ECC (Error Correcting Codes).
Hamming and Singleton limits.
Perfect and optimal codes.
Linear and cyclic codes.
BCH codes.
Reed-Solomon and Reed-Muller codes.
Mc Eliece cryptography.
Testi consigliati e bibliografia
- Oggetto:
A. Languasco – A. Zaccagnini, Introduzione alla crittografia , Hoepli L. Berardi, Algebra e teoria dei codici correttori , FrancoAngeli D. R. Hankerson ... [et al.] , Coding theory and cryptography : the essentials, Marcel Dekker A. J. Menezes - P. C. van Oorschot - S. A. Vanstone , Handbook of Applied Cryptography, CRC Press
- Oggetto:
Note
CRITTOGRAFIA E CODICI CORRETTORI, MFN0145 (DM509), 5 CFU: 5 CFU, MAT/02, TAF G (CFU di sede), Ambito aggregato per crediti di sede
Modalità dell'esame
Lo studente deve scrivere una relazione di 10-12 pagine su un argomento che concorda prima con me (per evitare troppe sovrapposizioni). La relazione mi deve essere inviata, come allegato a una e-mail, almeno tre giorni prima dell'esame.
Durante l'esame lo studente espone la sua relazione. Successivamente viene interrogato su alcuni argomenti trattati nel corso. Si veda questo file per l'elenco dettagliato degli argomenti e le regole dell'esame:
Elenco degli argomenti e modalità dell'esame
- Oggetto:
