Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Didattica
Teoria dell'informazione e crittografia

Codice insegnamento F1801Q122

Docente:
 
Alberto Leporati 

Contenuti:
Il corso consente di affrontare alcuni argomenti avanzati di Teoria dell’Informazione e di Teoria dei Codici, e di acquisire le nozioni e i concetti che sono alla base della Crittografia moderna. 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 presente nel canale.

Obiettivi formativi:
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.

Prerequisiti:
Argomenti trattati nei corsi di matematica del I e del II anno della laurea triennale in Informatica. Nozioni di base di informatica teorica (macchine di Turing).

Metodi didattici:
Lezioni frontali ed esercitazioni in aula.

Programma dettagliato:

  1. Definizione di sorgente, canale, codifica.
  2. Codici per il riconoscimento di errori. Controlli di parità.
  3. Codici a correzione d'errore. Approccio geometrico e approccio algebrico. Codici di Hamming.
  4. Codifica di sorgente. Codici istantanei e loro costruzione. Disuguaglianze di Kraft e di McMillan. Codici di Huffman.
  5. L’entropia e sue proprietà. Codici di Shannon-Fano e primo teorema di Shannon. Definizione di canale e mutua informazione. Capacità di canale. Il canale binario simmetrico. Secondo teorema di Shannon.
  6. Codifica lineare. Matrici di codifica e di decodifica. Codici sistematici. Tabella dei laterali e sindrome. Codici lineari accorciati. Codici di Reed-Muller.
  7. Codici ciclici. Relazione fra codici ciclici e codici lineari. Costruzione di codici ciclici.
  8. Codici convoluzionali. Rappresentazione a traliccio e tramite automi a stati finiti. Descrizione polinomiale. Codici convoluzionali e codificazione lineare. Codici convoluzionali e distanza di Hamming. Algoritmo di Viterbi.
  9. Introduzione alla Crittografia: definizione di crittosistema, modelli di attacco, crittosistemi storici.
  10. Crittosistemi simmetrici standard: DES, 3DES e AES.
  11. Modi di funzionamento dei crittosistemi simmetrici.
  12. Fondamenti teorici dei crittosistemi simmetrici. Confusione e diffusione. Reti di permutazione e sostituzione. Struttura di Feistel.
  13. Crittoanalisi lineare e differenziale.
  14. Cifrari a flusso: RC4. Registri a scorrimento con feedback lineare.
  15. Sicurezza incondizionata e One-Time Pad.
  16. Funzioni one-way. Logaritmi discreti e il problema della fattorizzazione.
  17. Generatori di numeri pseudocasuali, e loro costruzione. Lo standard ANSI X9.17.
  18. Crittografia a chiave pubblica. Protocollo di Diffie-Hellman. Il crittosistema ElGamal. Crittosistemi ibridi.
  19. Il crittosistema RSA. Alcuni semplici attacchi ad RSA. RSA randomizzato.
  20. Firme digitali: definizione e proprietà, uso dei crittosistemi a chiavi pubblica per le firme digitali, lo schema di firme di ElGamal. Lo standard DSA.
  21. Funzioni di hash. Teoria e costruzione delle OWUHF (One-Way Universal Hash Functions). Il paradosso del compleanno. Le funzioni MD5 e SHA-1.
  22. Cenni alle infrastrutture a chiave pubblica (PKI) e alle Certification Authorities.
  23. Test di primalità: criterio di Eulero, test di Solovay-Strassen, test di Miller-Rabin.
  24. Algoritmi per la fattorizzazione: metodo p–1 di Pollard, metodo ρ di Pollard, cenni al Number Field Sieve

Testi di Riferimento
R.W. Hamming, Coding and Information Theory, Second edition, Prentice-Hall, 1986. 
D.R. Stinson, Cryptography: Theory and Practice, Third Edition, CRC Press, 2005.
Appunti forniti dal docente.

Tipo esame:
Orale

Tipo valutazione:
Voto finale

Contents:
The course allows to address some advanced issues of Information and Coding Theory, as well as introduce the notions and the basic concepts of modern Cryptography. It also provides conceptual and theoretical tools that allow students to understand the advanced techniques used nowadays to protect the transmission and storage of information, in presence of either hostile adversaries or noise into the channel.

Learning outcomes:
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.

Prerequisites:

Topics explained in mathematics courses that are held in the first and in the second year of the laurea degree in Informatics. Basic notions of theoretical computer science (Turing machines).

Didactic methods:

Lectures and exercises in the classroom.

Program details:

  1. Definition of source, channel, encoding.
  2. Error-detecting codes. Parity checks.
  3. Error-correcting codes. Geometric and algebraic approach. Hamming codes.
  4. Source encoding. Prefix-free codes and their construction. Kraft and McMillan inequalities. Huffman codes.
  5. Entropy and its properties. Shannon-Fano codes and Shannon’s Noiseless Coding Theorem. Formal definition of channel and mutual information. Channel capacity. The Binary Symmetric Channel. Shannon’s Main Theorem.
  6. Linear encoding. Decoding and encoding matrices. Systematic codes. Table of cosets and syndrome. Shortened linear codes. Reed-Muller codes.
  7. Cyclic codes. Relations between cyclic and linear codes. Construction of cyclic codes.
  8. Convolutional codes. Trellis diagram and representation through finite state automata. Polynomial representation. Convolutional codes and linear encoding. Convolutional codes and Hamming distance. Viterbi’s algorithm.
  9. Introduction to Cryptography: definition of cryptosystem, attack models, historical cryptosystems.
  10. Standard symmetric cryptosystems: DES, 3DES and AES.
  11. Modes of operation of symmetric cryptosystems.
  12. Theoretical foundations of symmetric cryptosystems. Confusion and diffusion. Permutation and substitution networks. The Feistel structure.
  13. Linear and differential cryptanalysis.
  14. Stram ciphers: RC4. Linear feedback shift registers.
  15. Unconditional security and One-Time Pad.
  16. One-way functions. Discrete logarithms and the factorization problem.
  17. Pseudorandom number generators, and their construction. The ANSI X9.17 standard.
  18. Public-key cryptography. The Diffie-Hellman protocol. The ElGamal cryptosystem. Hybrid cryptosystems.
  19. The RSA cryptosystem. Some simple attacks to RSA. Randomized RSA.
  20. Digital signatures: definition and properties, use of public-key cryptosystems to produce and verify digital signatures, the ElGamal signature scheme. The DSA standard.
  21. Hash functions. Theory and construction of OWUHF (One-Way Universal Hash Functions). The birthday paradox. The functions MD5 and SHA-1.
  22. Basic notions on Public Key Infrastructures and Certification Authorities.
  23. Primality testing: Euler criterion, Solovay-Strassen test, Miller-Rabin test.
  24. Factorization algorithms: Pollards p–1 and ρ methods, outline of Number Field Sieve.

Textbooks
R.W. Hamming,Coding and Information Theory, Second edition, Prentice-Hall, 1986.
D.R. Stinson,Cryptography: Theory and Practice, Third Edition, CRC Press, 2005.
Lecture notes provided by the teacher.

Type of examination:

Oral exam

Type of evaluation:
Final mark

 

 

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 10/10/2011