Encoding and Encryption
Insegnamento: Encoding and Encryption
Titolo insegnamento in inglese: Encoding and Encryption
Lingua: italiano
Anno di corso: 1
Semestre: 1
CFU: 6
Insegnamenti propedeutici previsti: Nessuno.
Docenti:
- Alessandro De Luca
Obiettivi Formativi
Il corso punta a introdurre i vari aspetti e scopi della codifica dei dati, quali la riduzione dei costi (compressione dei dati), affidabilità (correzione degli errori), e sicurezza (crittografia), il tutto nell’ambito della teoria dell’informazione di Shannon. Gli studenti padroneggeranno le tecniche basilari della teoria dei codici di sorgente e di canale, nonché gli algoritmi chiave per la crittografia classica e moderna (a chiave pubblica).
Programma
Nozioni preliminari: Il modello di comunicazione di Shannon; Scopi della codifica; Parole e linguaggi formali; Codici (di sorgente) come linguaggi univocamente decodificabili; Codici prefissi e suffissi. Codifica di sorgente: Caratterizzazioni di codici; Diseguaglianza di Kraft–McMillan; Codici massimali e completi; Codici prefissi massimali e rappresentazione con alberi; Sorgenti discrete a memoria 0 e loro entropia; Minimizzazione dei costi (teorema di Shannon sulla codifica di sorgente); Codici ottimali; Codici di Huffman; Ritardo di decifrazione e sincronizzazione. Entropia di più variabili: Variabili aleatorie ed entropia; Entropia congiunta e condizionata; Mutua informazione; Diseguaglianze sull’elaborazione dei dati (DPI) e di Fano; Cenni a catene di Markov e sorgenti con memoria. Codifica di canale: Canali discreti e loro capacità; Probabilità d’errore, tasso di codifica e sua raggiungibilità (teorema di Shannon sulla codifica di canale); Separazione sorgente–canale; Codici lineari e di Hamming; Cenni a codici ciclici e BCH. Codifica crittografica: Introduzione e aritmetica di base; Crittosistemi a chiave simmetrica, esempi e crittoanalisi; Cifratura in termini di canale di comunicazione; Cifrario perfetto; Crittografia a chiave pubblica e RSA; Funzioni hash e autenticazione; Scambio di chiavi Diffie–Hellman; Cenni ad altri problemi «difficili» usati in crittografia (logaritmo discreto, curve ellittiche).
Modalità didattiche
Lezioni frontali. Esercitazioni.
Materiale didattico
A. de Luca, F. D’Alessandro, Teoria degli automi finiti. Springer, 2013.
J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata. Cambridge University Press, 2010.
T.M. Cover, J.A. Thomas, Elements of Information Theory (2nd ed.). Wiley, 2012.
N.L. Biggs, Codes: An Introduction to Information Communication and Cryptography. Springer, 2008.
Modalità di esame
L'esame si articola in prova solo orale. Progetto.