Vai al contenuto principale
Oggetto:
Oggetto:

Crittografia e Codici Correttori (DM 509) - a.a. 2010/11

Oggetto:

Anno accademico 2010/2011

Codice dell'attività didattica
MFN0145
Docente
Prof. Umberto Cerruti (Titolare del corso)
Corso di studi
Laurea in Matematica
Anno
3° anno
Periodo didattico
Secondo semestre
Tipologia
D.M. 509
Crediti/Valenza
5
SSD dell'attività didattica
MAT/02 - algebra
Oggetto:

Sommario insegnamento

Oggetto:

Obiettivi formativi

Tra le infinite applicazioni della Matematica moderna, sono particolarmente importanti, sia per l'impatto che hanno nella vita di ogni giorno sia per la profondità e la novità dei risultati teorici, la Crittografia e la Teoria dei Codici Correttori di Errore. La finalità del corso è duplice: 1) Mostrare che la Matematica è in grado di offrire metodi e algoritmi che permettono di trasmettere su canali insicuri informazioni risevate, in modo tale che: - solo gli utenti abilitati possano accedere ad esse - sia certa l'identità del mittente (firma elettronica) - il contenuto del messaggio non possa essere alterato da nessuno. 2) Studiare alcune tecniche di base per correggere gli errori dovuti alla trasmissione di un messaggio su un canale disturbato. Vale la pena di osservare che, mentre tutti ormai sono al corrente dell'esistenza della crittografia, e ne riconoscono facilmente la necessità (evidente quando comunicano, per esempio, con una banca), pochi conoscono i codici correttori, dei quali si parla poco. In realtà essi sono indispensabili ad ogni forma di comunicazione digitale. Senza di essi non si potrebbe nemmeno ascoltare un CD, non parliamo di vedere le foto di Marte! Lo studente, al termine del corso, è in grado di comprendere meglio il funzionamento effettivo delle comunicazioni digitali. Matematicamente ha imparato la differenza tra il vedere se un numero è primo e il fattorizzarlo (differenza attualmente abissale). Possiede alcuni strumenti fondamentali della teoria dei numeri, come la Legge di Reciprocità Quadratica. Ha esperienza effettiva dei campi finiti e di certi importantissimi quozienti dell'anello dei polinomi. Conosce protocolli crittografici recenti e efficaci codici di correzione di errori.

Oggetto:

Risultati dell'apprendimento attesi

Metodi di fattorizzazione, test di primalità, campi finiti, teoria elementare dei numeri, crittografia e protocolli crittografici, fondamenti della teoria dei codici correttori con esempi efficaci.

Oggetto:

Programma

 

 

Parte prima: i fondamenti della Crittografia

 

Storia breve della crittografia.

Cifrari monoalfabetici. Crittoanalisi statistica dei cifrari monoalfabetici.

Cifrari polialfabetici.

Crittoanalisi statistica dei cifrari polialfabetici. Teorema di Friedman.

Macchine a rotori (Enigma).

Codici perfetti (Vernam).

Realizzazione dei codici perfetti. Cenni sui generatori di numeri pseudocasuali.

Il problema dello scambio delle chiavi. Doppio lucchetto e sue debolezze.

La crittografia a chiave pubblica e i suoi vantaggi.

 

Parte seconda: i metodi matematici

 

Simbolo di Legendre e legge di reciprocità quadratica.

Simbolo di Jacobi.

Successioni ricorrenti lineari di secondo grado e loro proprietà di divisibilità.

Soluzione delle equazioni di secondo grado modulo p e modulo pq.

Problemi difficili: logaritmo discreto, estrazione di radice, residuosità quadratica.

Criteri di primalità (Lucas, Pocklington, Soloway - Strassen).

Pseudoprimi (Fermat, Eulero, Miller).

Fattorizzazione: metodi p-1, p+1, Pollard, Dixon.

 

Parte terza: i protocolli crittografici

 

Diffie - Hellman.

RSA.

ElGamal.

Shamir e altri.

Autenticazione e firma digitale.

Firma cieca.

Secret splitting e secret sharing.

Cena dei crittografi.

Lancio della moneta digitale.

Poker mentale e giochi in rete.

Autenticazione e dimostrazioni a conoscenza nulla.

Denaro digitale.

Voto digitale.

 

Parte quarta: i codici correttori, le basi della teoria

 

Generalità, distanza di Hamming, sfere e loro volume, quantità di informazione e efficienza.

Limite di Hamming.

(n,k)-codici e posti di informazione. Limite di Singleton.

Codici lineari e loro vantaggi.

Matrice di controllo, teorema di Hamming.

I codici di Hamming.

Metodo di decodifica per i codici lineari (metodo della sindrome).

Cenni sui codici che provengono dai piani proiettivi.

Algebra R(n,q) e codici ciclici.

Divisori e zeri dei codici. Polinomio generatore.

Codici BCH con distanza minima garantita.

 

Parte quinta: approfondimenti sui codici correttori

 

Laterali e classi ciclotomiche.

La struttura dell'algebra R(n,q), idempotenti e ideali.

Decomposizione interna ed esterna di R(n,q).

Codici di Reed - Solomon.

Codici estesi, proiezione dei codici.

Correzione delle raffiche di errore e codici utilizzati nei CD.

Congiunzione di codici.

Codici di Reed - Muller.

Codici quadratici.

 

Brief history of Cryptography. Mono and polyalphabetic codes.

 Statistical analysis. Friedman’s theorem.

Rotor machines and perfect codes.

Introduction to PRNG (Pseudo Random Numbers Generators).

Key exchange and public key cryptography.

Legendre and Jacobi symbols. The quadratic reciprocity law.

Recurrent linear sequences of second order, and their divisibility properties.

Second order equations Mod p and Mod pq.

Primality testing and pseudoprimes.

Factorization.

Cryptographic protocols.

Digital cash. Electronic voting.

The essentials of ECC (Error Correcting Codes).

Hamming and Singleton limits.

Perfect and optimal codes.

Linear and cyclic codes.

BCH codes.

Reed-Solomon and Reed-Muller codes.

Quadratic codes.

 

Testi consigliati e bibliografia

Oggetto:

A. Languasco – A. Zaccagnini, Introduzione alla crittografia , Hoepli L. Berardi, Algebra e teoria dei codici correttori , FrancoAngeli D. R. Hankerson ... [et al.] , Coding theory and cryptography : the essentials, Marcel Dekker A. J. Menezes - P. C. van Oorschot - S. A. Vanstone , Handbook of Applied Cryptography, CRC Press



Oggetto:

Note

CRITTOGRAFIA E CODICI CORRETTORI, MFN0145 (DM509), 5 CFU: 5 CFU, MAT/02, TAF G (CFU di sede), Ambito aggregato per crediti di sede Modalità di verifica/esame: Esame orale costituito dalla discussione di una relazione e interrogazione sugli argomenti del corso. Viene dato un voto.

 

Modalità dell'esame  

Lo studente deve scrivere una relazione di 10-12 pagine su un argomento che concorda prima con me (per evitare troppe sovrapposizioni). La relazione mi deve essere inviata, come allegato a una e-mail,  almeno due giorni prima dell'esame.

Durante l'esame lo studente espone la sua relazione. Successivamente viene interrogato su alcuni argomenti trattati nel corso.

Si veda questo file per l'elenco dettagliato degli argomenti e le regole dell'esame:

Elenco degli argomenti e modalità dell'esame

 

Oggetto:

Altre informazioni

http://www.matematica.unito.it/cgi-bin/home.pl/View?doc=Orario_LT.html
Oggetto:
Ultimo aggiornamento: 30/04/2013 13:19

Non cliccare qui!