- Number Theory and Criptography
- Summary
Course Syllabus
Obiettivi
Coerentemente con gli obiettivi formativi del Corso di Studio, l'insegnamento si propone di fornire alcuni concetti e alcune tecniche di Teoria dei numeri, fondamentali per introdurre lo studente alla comprensione del funzionamento dei principali sistemi crittografici a chiave pubblica, che fanno uso dell'aritmetica modulo n e delle curve ellittiche su campi finiti.
I risultati di apprendimento attesi comprendono: la conoscenza di classici test di primalità di tipo probabilistico e deterministico, la conoscenza della struttura di gruppo di una curva ellittica su un campo finito e applicazioni al problema del logaritmo discreto e della firma digitale, e al problema della fattorizzazione di un numero intero; la capacità di analizzare e riproporre le dimostrazioni presentate durante le lezioni e di risolvere alcuni facili problemi facendo uso delle tecniche presentate; la capacità di approfondire, anche in maniera autonoma, alcuni dei risultati presentati durante il corso
Contenuti sintetici
ll Corso presenta alcuni risultati di Teoria dei numeri, con particolare riguardo a test di primalità, metodi di fattorizzazione e problema del logaritmo discreto, usando argomenti classici di Teoria dei numeri e le curve ellittiche.
Programma esteso
- Richiami sui numeri interi e sui campi finiti, aritmetica modulare, funzione di Eulero, teorema cinese del resto.
- Introduzione ai sistemi crittografici; chiave pubblica e chiave privata.
- Numeri primi: cenni sul Teorema di Dirichlet e sul Teorema dei numeri primi.
- Primalità e fattorizzazione: conseguenze del Piccolo Teorema di Fermat; numeri pseudoprimi, alcuni test di primalità (Fermat, Jacobi, Miller-Rabin, AKS), metodo (p-1) di Pollard per la fattorizzazione.
- Cenni sulla funzione zeta. Fattorizzazione di EuleroI; Ipotesi di Riemann; funzioni L(s,Χ) e ipotesi generalizzata di Riemann; ripercusssioni sui test di primalita
- Crittosistema di Diffie ed Hellman. Il problema del logaritmo discreto.
- Curve ellittiche: equazione di Weierstrass, gruppo dei punti di una curva ellittica, curve ellittiche su campi (e anelli) finiti.
- Endomorfismi di curve ellittiche.
- Punti di torsione e Weil pairing
- Teorema di Hasse
- Cenni su crittosistemi basati sulle curve ellittiche.
- Il problema del Logaritmo discreto. Attacco MOV
- Firma digitale (DSA e ECDSA)
Prerequisiti
Conoscenze di base sulle strutture algebriche, generalmente acquisite nei corsi di Algebra di un corso di Laurea di Primo Livello, con particolare riguardo ai gruppi, gruppi abeliani e ai campi finiti.
Modalità didattica
A seguito della corrente emergenza sanitaria legata a Covid-19, al momento (A/A 2020/21) si prevede che le lezioni del presente insegnamento verranno comunque videoregistrate ,sia nel caso siano in presenza sia nel caso siano tenute da remoto, e saranno rese disponibili agli studenti sulla piattaforma e-learning.
Materiale didattico
- N. Koblitz, A course in Number Theory and Cryptography, volume 114 of Graduate texts in Mathematics, Springer-Verlag, second edition, 1994.
- A. Languasco, A. Zaccagnini, Introduzione alla Crittografia, Hoepli Editore, 2004.
- H.E. Rose, A course in Number Theory, II edizione, Oxford: Clarendon press, 1994
- Lawrence C. Washington, Elliptic Curves, Number Theory and Criptogtaphy CRCPress
- Maria Welleda Baldoni, Ciro Ciliberto, Giulia Maria Piacentini Cattaneo, Elementary Number Theory, Cryptography and Codes, 2009 Springer-Verlag Berlin Heidelberg
- Graham Everest, Thomas Ward Introduction to Number Theory, Springer-Verlag London Limited 2005
Periodo di erogazione dell'insegnamento
II semestre.
Modalità di verifica del profitto e valutazione
Esame scritto e orale
Fino all’esaurimento della corrente emergenza sanitaria, la prova orale dell’esame si svolgerà da remoto mediante piattaforma WebEx o analoga, con accesso reso disponibile sulla pagina e-learning dell’insegnamento.
Le modalità di svolgimento della prova scritta verranno precisate in seguito.
- Durante lo svolgimento del corso, verranno assegnati alcuni esercizi, che, consegnati per via telematica, concorreranno alla valutazione finale dell'esame.
- La prova scritta consiste in alcuni esercizi da cui si evinca la capacita' dello studente a usare gli strumenti introdotti nelle lezioni
- Per quanto riguarda l'orale, obbligatorio per tutti, questo consiste in due parti:
- discussione dello scritto (e degli esercizi eventualmente consegnati);
- lo studente puo' scegliere se fare una classica prova orale in cui mostri la conoscenza e la padronanza degli argomenti trattati durante il corso, spiegando le motivazioni che hanno portato a trattare alcuni argomenti teorici, ma con risvolti applicativi, dando gli enunciati e le dimostrazioni dei teoremi, oppure dare un seminario in cui si approfondisca un argomento solo accennato durante il corso.
Valutazione dell’esame: Voto in trentesimi 18-30/30
Lo studente è ammesso a sostenere la prova orale se raggiunge la votazione di 18/30 nello scritto
La discussione dello scritto e la prova orale concorrono alla valutazione finale, che è ottenuta dalla media tra la votazione ottenuta nello scritto+discussione (accorpati) e dalla seconda parte dell’orale.Orario di ricevimento
Su appuntamento. A causa dell'emergenza sanitaria, il ricevimento si svolgerà in modalità telematica mediante piattaforma WebEx o analoga.
Aims
The student is expected to have knowledge of main probabilistic and deterministic primality tests, of the structure of the group of elliptic curves over finite fields, with applications to the problems of discrete logarithm, of the digital signature, and of factorisation. It is also expected to have the ability to give proofs presented in the course, using given techniques to solve easy problems and the ability to study some more details of results presented during the course.
Contents
Some classical results in Number Theory are presented, with particular regard to factorizzation methods, primality tests and discrete logarithm , using modular arithmetic and Elliptic Curves.
Detailed program
- Integers and finite fields; Euler function; modular arithmetic
- Definition of a Cypher: public and private key
- Some topics about Prime numbers: Dirichlet's Theorem; Number Prime Theorem
- Prime numbers and factorization: pseudoprimes; primality tests (Fermat, Jacobj, Miller-Rabin AKS); (p-1)-pollard method for factorization; complexity of the alghoritms.
- Some remark about Riemann's zeta function. Euler'sFactorization. Riemann's hypothesis. L(s,Χ) funcions and extended Riemann hypothesis; some consequence on primality tests.
- Diffie-Hellman cypher; discrete logarithm
- Elliptic curves; group of the points of an elliptic curve on a finite field (and rings).
- Endomorphisms.
- Torsion points and Weil pairing.
- Hasse Theorem
- Cryptosystems on elliptic curves.
- Discrete Logarithm on Elliptic Curves
- Digital Signature: DSA, ECDSA
Prerequisites
Basic Algebra: algebraic structure; abelian groups; finite fields.
Teaching form
The cours consists of Lectures for 8 credits. They will give knowledge of basic definitions, relevant results and theorems. On the other side, we intend to give skills to use results and knowledge in solving exercises and analysing problems
Because the evolution of Covid-19 health emergency, at the moment (A / A 2020/21) it is not possible to say if the lectures will be in presence; in any case the lectures of this course will be videotaped and will be available to students on the e-learning platform.
Textbook and teaching resource
- N. Koblitz, A course in Number Theory and Cryptography, volume 114 of Graduate texts in Mathematics, Springer-Verlag, second edition, 1994.
- A. Languasco, A. Zaccagnini, Introduzione alla Crittografia, Hoepli Editore, 2004.
- H.E. Rose, A course in Number Theory, II edizione, Oxford: Clarendon press, 1994
- Lawrence C. Washington, Elliptic Curves, Number Theory and Criptogtaphy CRCPress
- Maria Welleda Baldoni, Ciro Ciliberto, Giulia Maria Piacentini Cattaneo, Elementary Number Theory, Cryptography and Codes, 2009 Springer-Verlag Berlin Heidelberg
Semester
II term.
Assessment method
Pending the current health emergency, the oral exam will be held online through WebEx or analogous, with access made available on the e-learning website. The procedures for carrying out the written test will be established later on.
It will be possible to give oral and written exam not in presence, via webex or analogues platforms.
- Some exercises will be proposed in the lectures. If they will be uploaded on e-learning website (or sent by mail) they will be considered for the final valuation.
- The written part consists of exercises where the students show their ability in using methods and tools introduced in the course.
- The oral part consists of two parts:
- discussion about written part;
- the student may decide to have a classical oral exam, where he must show his competence about subjects considered in the lectures, also giving motivations for applications of theoretical topics; alternatively, one student may give a talk about a particular subject, which was considered not very deeply in the course. The final result is achieved considering the average between the mark obtained in written+discussion (together), and the mark obtained in the subsequent oral part.
Mark range: 18-30/30.
Office hours
By appointment. Due to the current health emergency, student reception will be carried out online through WebEx or analogous.
Key information
Staff
-
Francesca Dalla Volta