84235 - TEORIA DELL'INFORMAZIONE E CRITTOGRAFIA LM

Conoscenze e abilità da conseguire

Al termine del corso lo studente conosce i fondamenti della teoria dell’informazione: entropia, compressione, capacità dei canali di trasmissione. Analisi teorica dell’energia richiesta per la trasmissione delle informazioni. Codici a correzione d’errore per audio e video. Fondamenti della crittologia e della sicurezza nelle comunicazioni. Applicazioni: sistemi wireless, satelliti, memorizzazione dati, reti di sensori, cyber-physical systems, Internet of Things.

Contenuti

Part I: Cryptography

Introduction. Main security targets: confidentiality, integrity, availability, authentication. Encryption, Channel, Decryption, Symmetric and asymmetric ciphering.

Elements of number theory. Euclidean division between integers. Algoriths for the computation of the remainder. Greater Common Divisor. Beuzeot's theorem. The Euclidean algorithm. Modular arithmetic and its rules. The discrete logarithm problem. Finite Fields. GF(p) when p is prime. Addition, multiplication, power in GF(p). Generator elements. GF(p^m): the field elements as polynomials. Irreducible polynomials, primitive polynomials. Generation of the field with irreducible polynomials. The field elements as powers of a primitive element modulus a primitive polynomial.

Confidentiality. Block cipher as a family of indexed bijections between sets. General brute-force attack: time needed as a function of the n. of keys. Example: permutation of the alphabet, plaintext composed of characters and cyclic shift (Caesar's cipher). Number of keys, implementation with mod operator. Substitution of the alphabet with a generic permutation. Number of keys. Attack by analysis of character frequencies. The Leon Battista Alberti’s cipher disk. The Vigenere chiper: number of keys, possible attacks when the length of the key is known, when it is not known. Stream cipher: example with streams of bits and ex-or with key. The ideal case: key length as the message length, key completely random (one-time pad). Case of key with finite length, periodically reused. Practical block cipher schemes: DES and AES.

The Diffie-Helmann key exchange: algorithm and weaknesses.

The RSA: algorithm and rigorous proof of correctness. Computational issues, generation of the keys.

The basic ideas for elliptic curves cryptography (EC).

Comparison among AES, RSA, DH, ECDH.

Integrity. Cryptographic hash functions, Message Authentication Code. Digital signatures.

Authentication: passwords, salting and hashing, one-time passwords.

Challenge-response. Man-in-the-middle attack.

Applications: cellular systems, WiFi. The cryptography in the Transport Layer Security.

Part 2: Information Theory

Information, Uncertainty and Entropy. Entropy for Discrete Memoryless Sources. Source Coding. Mutual Information and Channel Capacity. Shannon's Theorem on Channel Coding. Capacity for Gaussian Additive Channels. The Hartley-Shannon Formula for the Band Limited Additive Gaussian Channel. Energy to noise spectral density ratio. Energy and spectral efficiency, minimum theoretical energy per transmitted bit.

Channel Coding. Decision theory: Maximum Likelihood and Maximum a Posteriori decoding. Linear Block Codes. Cyclic Codes. Convolutional Codes. The Viterbi algorithm. Coding for Correlated Channels: Interleaving. Punctured Codes. Concatenated Codes. Codes on Graphs and Iterative Decoding: Turbo Codes and LDPC Codes. Decoding with message passing and belief propagation algorithms.

Applications. Cryptography, error protection, and energy budget for transmission of information in Wireless Cellular Systems, Satellite Systems, Data Storage Systems, Wireless Sensor Networks, Cyber-Physical Systems, Internet of Things.

Testi/Bibliografia

Lecture notes available on AMS Campus. 

 

More material can be found in:

T. M. Cover, J. A. Thomas, Elements of Information Theory, Wiley-Interscience, New York.

W. Stallings, Cryptography and Network Security, Pearson.

F. Stajano, Security for Ubiquitous Computing, Wiley.

 

Metodi didattici

Lectures.
Computer experiments and programming in Matlab or C or Python.

Modalità di verifica e valutazione dell'apprendimento

La verifica dell'apprendimento avviene attraverso una prova scritta, durante la quale non è ammesso l'uso di libri, appunti, calcolatrici, supporti elettronici, e una successiva prova orale.
La prova scritta mira ad accertare le abilità acquisite nel risolvere problemi nell'ambito delle tematiche affrontate. Essa viene valutata attraverso un giudizio che deve risultare positivo per consentire l'accesso alla prova orale. La validità della prova scritta superata è limitata agli appelli di una stessa sessione d'esame. La prova orale mira a verificare l'acquisizione delle conoscenze previste dal programma del corso. Sia la prova scritta che quella orale hanno l'ulteriore scopo di verificare l'apprendimento dei metodi generali della teoria dell'informazione e della crittografia, e l'acquisizione di giudizio critico in relazione alle diverse implementazioni di sistemi di compressione e codifica di informazioni. Il voto finale, espresso in trentesimi, tiene conto delle valutazioni riportate in entrambe le prove.

Strumenti a supporto della didattica

Personal computer

Orario di ricevimento

Consulta il sito web di Marco Chiani