Mathematics for cryptography
Insegnamento: Mathematics for cryptography
Titolo insegnamento in inglese: Mathematics for cryptography
Lingua: italiano
Anno di corso: 1
Semestre: 1
CFU: 6
Insegnamenti propedeutici previsti: Nessuno.
Docenti:
- Maurizio Laporta
Obiettivi Formativi
Scopo del corso è introdurre gli studenti ad argomenti di teoria dei numeri, sia antichi che molto moderni, i quali sono al centro dell’interesse nella crittografia contemporanea, soprattutto nei più noti crittosistemi a chiave pubblica quali RSA; si tiene un approccio algoritmico, ponendo l’accento su stime dell’efficienza delle tecniche derivanti dalla teoria.
Programma
1. Teoria elementare dei numeri: notazioni e proprietà di base; divisibilità e algoritmo euclideo; congruenze; aritmetica modulare; funzioni aritmetiche di base; teorema cinese del resto; congruenze polinomiali modulo un numero primo; residui quadratici; simbolo di Legendre; simbolo di Jacobi; legge di reciprocità quadratica; campi finiti.
2. Teoria computazionale dei numeri: stime temporali per aritmetica elementare; nozioni di base su complessità computazionale e classificazione degli algoritmi; stima del numero di operazioni su bit necessarie ad eseguire al computer operazioni di teoria dei numeri, quali l’algoritmo euclideo, il metodo del ripetuto elevamento al quadrato e l’algoritmo di Jacobi; il problema del logaritmo discreto; la distribuzione dei numeri primi con applicazioni alla complessità computazionale.
3. Primalità: pseudoprimi; test di primalità (Solovay–Strassen e Miller–Rabin); stime temporali per test di primalità.
4. Fattorizzazione: nozioni di base sul problema della fattorizzazione; metodo di Eratostene; metodo di Fermat; metodo di Pollard; numeri smooth; metodo del crivello quadratico.
5. Aritmetica delle curve ellittiche: nozioni di base sulle curve ellittiche; test di primalità; metodo di Lenstra; problema del logaritmo discreto (DLP) sulle curve ellittiche.
6. Crittografia: chiavi simmetriche; crittografia a chiave pubblica; problema di Diffie–Hellman; protocollo RSA; crittosistemi basati su curve ellittiche.
Modalità didattiche
Lezioni ed esercitazioni.
Materiale didattico
N.Koblitz, A Course in Number Theory and Cryptography, Springer Verlag
N.Koblitz, Algebraic Aspects of Cryptography, Springer Verlag
A. Languasco & A. Zaccagnini, Introduzione alla Crittografia, Hoepli
D.R. Stinson, Cryptography: Theory and Practice, Chapman and Hall Ed.
Modalità di esame
L'esame si articola in prova scritta ed orale.
In caso di prova scritta i quesiti sono a risposta libera ed esercizi numerici.