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

Introduzione alla crittografia. Sistemi a chiave privata e a chiave pubblica. Esempi di cifrari storici: cifrario a traslazione, cifrario a sostituzione. Cifrari moderni. Dimostrazioni di sicurezza.

Teoria di Shannon. Sicurezza di Shannon e sicurezza perfetta. Equivalenza tra le due nozioni. One Time Pad. Teorema di Shannon.

Sicurezza computazionale. Algoritmi efficienti. Algoritmi probabilistici. 

Modello di avversario efficiente. Funzioni unidirezionali.

Difficoltà della fattorizzazione. Primalità. Numero dei primi e teorema di Chebyshev. Moltiplicazione di primi come funzione unidirezionale. Famiglie di funzioni unidirezionali.

Algoritmo di Euclide. Esponenziazione modulare. Rchiami di aritmetica modulare. Test di primalità di Miller-Rabin.

Problema del logaritmo discreto, problema RSA, problema di Rabin. Permutazioni con trapdoor. Teorema cinese dei resti. Radici quadrate mod p e mod N. Introduzione alle curve ellittiche e relativo problema del logaritmo discreto.

Indistinguibilità computazionale e sue proprietà. Pseudo casualita. Test del bit successivo. Generatori pseudo casuali. Bit hard-core. Esempi da RSA, Rabin, logaritmo discreto.

Sistemi di cifratura simmetrici sicuri. Funzioni casuali e pseudocasuali. Costruzione di un sistema sicuro mono-messaggio. Funzioni pseudo-random. Sistema sicuro multi-messaggio. Esempio di sistema simmetrico reale: AES, descrizione e proprietà.

Sistemi a chiave pubblica. RSA. Sistema di ElGamal. Problema decisionale di Diffie-Hellmann.

Autenticazione. MAC e firme digitali. Funzioni hash resistenti alle collisioni. Firma RSA e ElGamal.

 

Testi/Bibliografia

Raphael Pass, Abhi Shelat: A Course in Cryptography. Disponibile su Internet.

Per approfondimenti:

Katz, Lindell: Introduction to Modern Cryptography, Chapman & Hall/CRC, 2008.
D. Stinson, Criptography, Theory and Practice, Third Edition, CRC Press, 2005.
A. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997. Disponibile su 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