46686 - ALGORITMI DELLA TEORIA DEI NUMERI E CRITTOGRAFIA

Conoscenze e abilità da conseguire

Al termine del corso, lo studente acquisisce le conoscenze di base su test di primalità e algoritmi di fattorizzazione. Sa applicare tali conoscenze ai principali sistemi di crittografia a chiave privata e pubblica.

Contenuti

Stime temporali per l'esecuzione dei calcoli: la notazione O-grande. L'algoritmo di Euclide. Generazione dei numeri primi: metodo di divisione e il crivello di Eratostene. I teoremi di Fermat, Eulero e Wilson. La struttura degli interi modulo m. Radici primitive. Pseudoprimi e numeri di Carmichael. Alcuni test di primalita'. Il test probabilistico di Miller-Rabin. Teorema di Rabin. Algoritmi di fattorizzazione: il metodo di Pollard, il metodo p-1, il metodo di Fermat, basi di fattori.
Introduzione alle curve ellittiche. Test di primalità e fattorizzazione sullle curve ellittiche.

Introduzione alla crittografia. Schemi di cifratura, sistemi simmetrici e asimmetrici. Principali tipi di attacco ad un crittosistema. Alfabeti e parole. Cifrari a blocchi. Cifrari affini. Esempi storici: Vigenere, Hill, cifrari a permutazione. Crittoanalisi dei cifrari affini e dei cifrari a permutazione. Cifrario di Vernam. Sicurezza assoluta, teorema di Shannon.
Sistemi a chiave privata. Cifrari a blocchi. Il sistema AES. Modalità operative di un cifrario a blocchi.
Sistemi a chiave pubblica. Il sistema RSA: descrizione e problemi di sicurezza. Il problema del logaritmo discreto. Protocollo di Diffie - Hellmann per lo scambio delle chiavi. Sistema di ElGamal: descrizione e aspetti legati alla sicurezza. Funzioni hash, codici di autenticazione di messaggi. La sicurezza semantica e il modello dell'oracolo casuale.
La firma digitale. Realizzazione con RSA. Lo standard DSA. Implementazione sulle curve ellittiche (cenni). Infrastruttura a chiave pubblica e autorità di certificazione.

Testi/Bibliografia

Prima parte:
Dispense del corso.
Baldoni, Ciliberto, Piacentini Cattaneo; Aritmetica, Crittografia e Codici, Springer-Verlag, Milano, 2006
Kobliz; A Course in Number Theory and Cryptography, Springer, New York, 1987.

Seconda parte:
W.Trappe, L.C.Washington, Crittografia con elementi di teoria dei codici, Pearson-Pentice Hall, 2009.

Per approfondimenti:
D. Stinson, Criptography, Theory and Practice, Third Edition, CRC Press, 2005.
W. Stallings, Crittografia e sicurezza delle reti, Apogeo, 2006.
A. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997 (publicy available on the Internet).

Metodi didattici

Lezioni in classe. Il corso consiste di 6 cfu, pari a 48 ore di lezione, si svolge nel secondo semestre, e prevede alcune ore (solitamente 4) di esercitazioni di laboratorio (non obbligatorie) con il supporto del sistema di calcolo Matlab.

Modalità di verifica e valutazione dell'apprendimento

Esame orale.  E' possibile presentare e discutere all'orale programmi eventualmente realizzati nel corso delle esercitazioni in laboratorio

Strumenti a supporto della didattica

Sistema di calcolo simbolico Matlab, usato nelle esercitazioni.

Orario di ricevimento

Consulta il sito web di Davide Aliffi