Course Syllabus
Obiettivi
Comprensione
dei principi di funzionamento dei codici per la correzione d’errore, e di
alcune semplici tecniche di compressione dati lossless (senza perdita di informazione).
Capacità di capire il funzionamento di un crittosistema o di un protocollo
crittografico. Capacità di scegliere gli strumenti crittografici adatti per proteggere
i dati durante la loro trasmissione e/o memorizzazione.
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
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
Lezioni ed esercitazioni in aula.
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.
Materiale didattico
- 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 A.A. 2021-2022
Modalità di verifica del profitto e valutazione
La verifica dell'apprendimento è
basata su un colloquio orale avente per oggetto gli argomenti svolti a lezione.
Orario di ricevimento
Su appuntamento
Aims
Understanding of the principles of operation of error-correcting codes, and of some simple techniques for lossless data compression. Ability to understand the functioning of cryptosystems and cryptographic protocols. Ability to choose the most suitable cryptographic tools to protect data during their transmission and/or storage.
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
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
Lectures and exercises in the classroom.
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.
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, Academic Year 2021-2022
Assessment method
The learning assessment is based on an oral colloquium, on the subjects exposed in class during the course.
During the Covid-19 outbreak, oral exams will be performed only by video conference, using the WebEx platform; a public link to the video conference will be published inside the Web page of the course, to allow any spectator to attend the exam.
Office hours
On appointment
Staff
-
Alberto Ottavio Leporati