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 moulo m. Radici primitive. Pseudoprimi e numeri di Carmichael. Alcuni test di primalita'. Il test probabilistico di Miller-Rabin La legge di reciprocita' quadratica (dal testo di Bressoud). Algoritmi di fattorizzazione: il metodo di Pollard, il metodo p-1, il metodo di Fermat, il crivello quadratico.
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. Sicurezza perfetta e Teorema di Shannon. Cifrario di Vernam. Sistemi a chiave privata: AES.
Sistemi a chiave pubblica. Il sistema RSA: descrizione e problemi di sicurezza. Il sistema di Rabin. Il problema del logaritmo discreto, calcolo dell'indice. 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 firma digitale. Realizzazione con RSA e con ElGamal.

Testi/Bibliografia

Baldoni, Ciliberto, Piacentini Cattaneo; Aritmetica, Crittografia e Codici, Springer-Verlag, Milano, 2006
W.Trappe, L.C.Washington, Crittografia con elementi di teoria dei codici, Pearson-Pentice Hall, 2009.
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.

Modalità di verifica e valutazione dell'apprendimento

Esame orale.

Orario di ricevimento

Consulta il sito web di Davide Aliffi