Syllabus del corso
Obiettivi
Conoscenza e capacità di comprensione
Gli studenti comprenderanno i principi di funzionamento dei codici per la correzione d’errore, e di alcune semplici tecniche di compressione dati lossless (senza perdita di informazione). Comprenderanno inoltre il funzionamento di un crittosistema o di un protocollo crittografico.
Conoscenza e capacità di comprensione applicate
Gli studenti saranno in grado di scegliere gli strumenti crittografici adatti per proteggere i dati durante la loro trasmissione e/o memorizzazione.
Autonomia di giudizio
Gli studenti acquisiranno la capacità di valutare se gli algoritmi proposti di correzione degli errori, di compressione dati, e di cifratura, sono adeguati.
Abilità comunicative
La grande attenzione posta sugli aspetti formali permetterà agli studenti di comprendere l’importanza di una comunicazione non ambigua, utilizzando la terminologia corretta per esprimere le nozioni e i concetti appresi.
Capacità di apprendere
La formalizzazione dei concetti faciliterà i meccanismi di apprendimento deduttivo. Inoltre, l'esposizione di esempi ed esercizi svolti alla lavagna, subito dopo aver spiegato una tecnica o un algoritmo, consentirà di chiarire eventuali dubbi e casi particolari.
Contenuti sintetici
Nozioni e concetti alla base della Teoria dell’Informazione, della Teoria dei Codici e della Crittografia moderna. Il corso fornisce inoltre gli strumenti concettuali e teorici che consentono di comprendere le tecniche avanzate attualmente utilizzate per proteggere la trasmissione e la memorizzazione di informazioni in presenza di agenti ostili o di rumore nel canale.
Programma esteso
- Codici per la correzione degli errori:
- Definizione di sorgente, canale, codifica
- Codici per il riconoscimento di errori. Controlli di parità
- Codici a correzione d'errore. Approccio geometrico e approccio algebrico. Codici di Hamming
- Codifica di sorgente:
- Codici istantanei e loro costruzione
- Disuguaglianze di Kraft e di McMillan
- Codici di Huffman
- L’entropia:
- Definizione e proprietà matematiche
- Codici di Shannon-Fano
- Primo teorema di Shannon
- Il canale rumoroso:
- Definizione di canale, entropie di canale e mutua informazione
- Capacità di canale
- Il canale binario simmetrico
- Secondo teorema di Shannon
- Introduzione alla Crittografia:
- Definizione di crittosistema
- Modelli di attacco
- Crittosistemi storici, e loro crittoanalisi
- Crittosistemi simmetrici:
- Crittosistemi standard: DES, 3DES e AES
- Modi di funzionamento dei crittosistemi simmetrici
- Fondamenti teorici dei crittosistemi simmetrici:
- Confusione e diffusione
- Reti di permutazione e sostituzione
- Struttura di Feistel
- Crittosistemi a chiave pubblica:
- Funzioni one-way: logaritmi discreti e il problema della fattorizzazione
- Protocollo di Diffie-Hellman. Il crittosistema ElGamal. Crittosistemi ibridi
- Il crittosistema RSA. Alcuni semplici attacchi ad RSA. RSA randomizzato
- Generatori di numeri pseudo-casuali
- Schemi di firma digitale
- Funzioni di hash crittografiche
- Cenni alla crittografia post-quantum
Prerequisiti
Argomenti trattati nei corsi di matematica della laurea triennale in Informatica. È utile - ma non indispensabile - la conoscenza di alcune nozioni di base di informatica teorica (in particolare, macchine di Turing).
Modalità didattica
20 lezioni da 2 ore svolte in aula, in modalità erogativa, in presenza.
10 esercitazioni da 2 ore svolte in aula, in modalità erogativa, in presenza.
La lingua di erogazione prevista è l'Italiano. Tuttavia, lezioni ed esercitazioni potranno essere erogate in Inglese se si verifica almeno una delle seguenti condizioni:
- in aula c'è almeno uno studente straniero che non parla Italiano;
- gli studenti fanno richiesta di seguire lezioni ed esercitazioni erogate in Inglese.
Tutte le lezioni saranno videoregistrate, e le videoregistrazioni saranno disponibili nella pagina Web del corso.
Materiale didattico
Libri:
- R.W. Hamming. Coding and Information Theory. Second edition, Prentice-Hall, 1986
- D.R. Stinson. Cryptography: Theory and Practice. Fourth Edition, CRC Press, 2018
Appunti forniti dal docente.
Periodo di erogazione dell'insegnamento
Secondo semestre
Modalità di verifica del profitto e valutazione
La verifica dell'apprendimento è basata su un colloquio orale avente per oggetto gli argomenti svolti a lezione. Durante il colloquio verrà valutata la capacità dello studente di esporre gli argomenti del corso, e di effettuare brevi ragionamenti su di essi.
Non sono presenti prove in itinere.
Orario di ricevimento
Su appuntamento
Sustainable Development Goals
Aims
Knowledge and understanding
Students will understand the operating principles of error correction codes, and some simple lossless data compression techniques (that is, without loss of information). They will also understand how a cryptosystem or cryptographic protocol works.
Applied knowledge and understanding
Students will be able to choose the appropriate cryptographic tools to protect data during transmission and/or storage.
Independent judgment
Students will acquire the ability to evaluate whether the proposed error correction, data compression, and encryption algorithms are adequate.
Communication skills
The great attention paid to formal aspects will allow students to understand the importance of unambiguous communication, using the correct terminology to express the notions and concepts learned.
Learning skills
The formalization of concepts will facilitate deductive learning mechanisms. Furthermore, presenting examples and exercises on the board, immediately after explaining a technique or algorithm, helps clarify any doubts and particular cases.
Contents
Basic notions and concepts of Information Theory, Coding Theory, and modern Cryptography. The course also provides the conceptual and theoretical tools that allow the student to understand the advanced techniques which are currently used to protect data transmission and storage, in presence of malicious adversaries or noise in the communication channel.
Detailed program
- Error-correcting codes:
- Definitions of source, channel, and encoding
- Error-detecting codes. Parity checks
- Error-correcting codes. Geometric and algebraic approaches. Hamming codes
- Source encoding:
- Prefix-free codes and their construction
- Kraft and McMillan inequalities
- Huffman codes
- Entropy:
- Definition and mathematical properties
- Shannon-Fano codes
- Shannon's noiseless coding theorem
- The noisy channel:
- Definition of channel, associated entropies and mutual information
- Channel capacity
- The binary symmetric channel
- Shannon's main theorem
- Introduction to Cryptography:
- Definition of cryptosystems
- Attack models
- Historical cryptosystems, and their analysis
- Symmetric cryptosystems:
- Standard cryptosystems: DES, 3DES and AES
- Modes of operation of symmetric cryptosystems
- Theoretical foundations of symmetric cryptosystems:
- Confusion and diffusion
- Permutation-substitution networks
- Feistel’s structure
- Public-key cryptosystems:
- One-way functions: discrete logarithms and factorization
- Diffie-Hellman's protocol. The ElGamal cryptosystem. Hybrid cryptosystems
- The RSA cryptosystem. Some simple attacks to RSA. Randomized RSA
- Pseudorandom number generators
- Digital signature schemes
- Cryptographic hash functions
- Introduction to post-quantum cryptography
Prerequisites
Topics explained in mathematics courses held in the laurea degree in Informatics. It is useful - but not necessary - to have basic notions of theoretical computer science (in particular, Turing machines).
Teaching form
20 lessons of 2 hours held in the classroom, in delivery mode, in presence.
10 exercises of 2 hours held in the classroom, in delivery mode, in presence.
The expected teaching language is Italian. However, lectures and exercises may be provided in English if at least one of the following conditions is met:
- in the classroom there is at least one foreign student who does not speak Italian;
- the students request to attend lectures and exercises given in English.
All lectures and exercises made in the classroom will be recorded, and made available inside the Web page of the course.
Textbook and teaching resource
Textbooks:
- R.W. Hamming. Coding and Information Theory. Second edition, Prentice-Hall, 1986
- D.R. Stinson. Cryptography: Theory and Practice. Fourth Edition, CRC Press, 2018
Lecture notes provided by the teacher.
Semester
Second semester
Assessment method
The learning assessment is based on an oral interview, on the subjects exposed in class during the course. During the interview, the student's ability to explain the topics of the course, and to make brief thoughts on them, will be assessed.
There are no mid-term evaluations.
Office hours
On appointment
Sustainable Development Goals
Staff
-
Alberto Ottavio Leporati
