ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| METODI MATEMATICI DELLA CRITTOGRAFIA/a | MAT/02 | LEZIONI | 42 |
|
Verranno sviluppate alcune nozioni di base relative alla teoria delle curve ellittiche, con una particolare attenzione al caso in cui il campo di definizione sia un campo finito.
Gli studenti acquisiranno inoltre le conoscenze degli algoritmi e degli strumenti di base della crittografia, con particolare riferimento ai metodi basati sulla teoria delle curve ellittiche.
The course will also include some basic notions on elliptic curves, with an emphasis on the case of the field of definition being a finite field.
The students will moreover get acquainted with the basic algorithms and tools of cryptography, with a focus on methods based on the theory of elliptic curves.
Si valuterà l'abilità dello studente di discutere con competenza e chiarezza i contenuti principali del corso.
Metodo:
* Esame orale finale
The student will be assessed on his/her ability to discuss with competence and clarity the main points of the syllabus.
Methods:
* Final oral exam
Gli studenti acquisiranno le conoscenze necessarie per partecipare alla ricerca nel campo della crittografia matematica, specialmente in riferimento a metodi basati sulla conoscenza delle curve ellittiche. Sapranno anche collaborare all'implementazione di algoritmi in questo campo, compresi algoritmi di crittanalisi. Acquisiranno in particolare la capacità di utilizzare la teoria delle curve ellittiche come strumento per la risoluzione di problemi matematici e crittografici.
The students will acquire the knowledge necessary to do research on mathematical cryptography, especially on methods involving elliptic curves. They will also become able to implement algorithms in this field, including cryptanalysis. They will, in particular, acquire the necessary abilities to use the theory of elliptic curves as a tool for the solution of mathematical and cryptographic problems.
Verifica nel corso dell'esame orale finale.
Verification during the final oral exam, including a short technical presentation on a theme chosen by the student and a discussion of the contents of the lectures.
Gli studenti sono consigliati a frequentare le lezioni e a studiare gli argomenti via via presentati.
Students are advised to follow the lessons, study the subjects discussed.
Nessuna
None
I prerequisiti di aritmetica, fondamenti di algebra, algebra polinomiale, campi finiti, algebra lineare sono insegnati nei corsi del primo anno, e saranno comunque ripresi a lezione.
I prerequisiti necessari di carattere crittografico e algebro-geometrico insegnati in altri corsi saranno richiamati e saranno date precise indicazioni bibliografiche.
The prerequisites of arithmetic, algebraic foundations, polynomial algebra, finite fields, linear algebra are taught in the courses of the first year of bachelor, and will anyway be recalled.
The prerequisites of cryptography and algebraic geometry taught in other courses will be recalled with precise bibliographic informations.
Il corso è indipendente da altri corsi, anche se sinergie sono possibili.
The course is indipendent of other courses, although synergies are possible.
Indicazioni su studi utili per la continuazione delle ricerche illustrate nel corso saranno date a lezione o in documentazione resa disponibile.
Indications on further studies useful to forward the researches described in the course will be given inj the lessons, or through documentation provided.
CURVE ELLITTICHE
Richiami sulle varietà algebriche.
Curve ellittiche su un campo, equazioni di Weierstrass, legge di gruppo sui punti di una curva ellittica, differenziale invariante.
Isogenie: grado di un'isogenia, isogenia duale. L'isogenia di moltiplicazione per un intero. Anello degli endomorfismi di una curva ellittica. Accoppiamento di Weil.
Punti di torsione e modulo di Tate di una curva ellittica.
Curve ellittiche su campi finiti: azione del Frobenius, teorema di Hasse-Weil.
CRITTOGRAFIA
I concetti e i protocolli crittografici base: crittografia simmetrica , crittografia a chiave pubblica: cifra, KEM (key establishment methods),firma. hash, successioni pseudo casuali. Criteri di sicurezza, zero-knowledge proofs.
Protocolli a chiave pubblica "classici": RSA, Diffie Helman, El Gamal e corrispondenti problemi matematici (fattorizzazione, logaritmo discreto).
ARITMETICA
Calcolo della radice quadrata su un campo finito: algoritmi di Cipolla e Tonelli-Shanks. Equivalenza del calcolo della radice quadrata modulo N composto e della fattorizzazione di N.
Test di primalita': Test di Miller Rabin. Test di Pocklington–Lehmer. Algoritmo di Agrawal–Kayal–Saxena. Ricerca di numeri primi.
Fattorizzazione di interi: algoritmi p-1 e Rho di Pollard. Algoritmi di Fermat, di Dixon, quadratic sieve e algebraic number sieve.
Logaritmo discreto: Algoritmi Rho e Lambda(algoritmo del canguro) di Pollard. Algoritmo di Pohlig-Hellmann, algoritmi di Index Calculus.
Algoritmo di Shor (cenni). Calcolo quantistico dell'ordine di un elemento mod N, e tramite questo fattorizzazione e Logaritmo discreto.
ALGORITMI ARITMETICI CHE USANO CURVE ELLITTICHE
Fattorizzazione di Lenstra (generalizzazione dell'algoritmo p-1 di Pollard alle curve ellittiche) Algoritmo di Goldwasser-Killian come generalizzazione del test di Pocklington-Lehmer.
ALGORITMI CRITTOGRAFICI SULLE CURVE ELLITTICHE
Logaritmo discreto sulle curve ellittiche. Attacchi e protocolli basati su accoppiamenti.
Algoritmi per calcolare il numero di punti di una curva ellittica: Baby-step-giant-step, Schoff, Schoof–Elkies–Atkin
Crittografia basata sulle curve ellittiche: protocolli, attacchi e problemi. Confronto con RSA, Diffie-Hellmann su campi finiti. Problemi di certificazione e trusted third party.
Cenni su altri protocolli crittografici basati su diversi problemi algebrici.
ELLIPTIC CURVES
Preliminaries on algebraic varieties.
Elliptic curves over a field, Weierstrass equations, group law on the points of an elliptic curve. Invariant differential.
Isogenies: degree, dual isogeny. Multiplication by an integer m. Endomorphism ring of an elliptic curve. Weil pairing. Torsion points and Tate module of an elliptic curve. Elliptic curves over finite fields: Frobenius, the Hasse-Weil theorem.
CRYPTOGRAPHY
Basic notions and fundamental protocols. Symmetric key cryptography, basic public-key cryptosystems (RSA, Diffie Helman, El Gamal), hash, pseudo-random sequences, security criteria, zero-knowledge proofs.
ARITHMETIC
Computation of square roots in finite fields: the algorithms of Cipolla and Tonelli-Shanks. Equivalence between the problems of computing square roots modulo a composite integer N and factoring N.
Primality tests: Miller-Rabin, Pocklington–Lehmer. The Agrawal–Kayal–Saxena algorithm. Searching for prime number.
Integer factorization: the p-1 algorithm and Pollard's Rho algorithm. The algorithms of Fermat and Dixon, quadratic sieve, algebraic number sieve.
Discrete logarithm: Pollard's Rho and Lambda (the Kangaroo algorithm). Shor's algorithm. Factoring N and computing the order of an element modulo N. Discrete logarithm
ARITHMETIC ALGORITHMS USING ELLIPTIC CURVES
Lenstra factorization (a generalization of Pollard's p-1 algorithm to elliptic curves). Goldwasser-Killian as a generalisation of the Pocklington-Lehmer test.
ALGORITHMS ON ELLIPTIC CURVES
Discrete logarithm on elliptic curves (impossibility of generalizing the sieve methods; the MOV attack reduces the Elliptic Curve Discrete Logarithm Problem to a Discrete Logarithm Problem in a finite extension of the ground field)
Algorithms to compute the number of points of an elliptic curve: Baby-step-giant-step, Schoff, Schoof–Elkies–Atkin
Cryptography on elliptic curves: Diffie Hellman, El Gamal, and others.
Special cryptographic algorithms.
N. Koblitz A course in number theory and cryptography
S. Goldwasser and M. Bellare Lecture Notes on Cryptography (MIT notes) https://cseweb.ucsd.edu/~mihir/papers/gb.html
J. Silverman, The Arithmetic of Elliptic Curves
Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Allpied Cryptography, http://cacr.uwaterloo.ca/hac/
N Koblitz A course in number theory and cryptography
N. Koblitz Algebraic aspects of cryptography
S. Goldwasser and M. Bellare Lecture Notes on Cryptography (MIT notes) https://cseweb.ucsd.edu/~mihir/papers/gb.html
J. Silverman, The Arithmetic of Elliptic Curves
Students are invited to take part to meeting the teachers, also by individual appointment
Esame orale
Oral exam
A richiesta, anche per conto di altri corsi.
Upon request, also for other courses.
