View syllabus
MATHEMATICAL METHODS IN CRYPTOGRAPHY
DAVIDE LOMBARDO
Academic year2020/21
CourseMATHEMATICS
Code147AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
METODI MATEMATICI DELLA CRITTOGRAFIA/aMAT/02LEZIONI42
PATRIZIA GIANNI unimap
DAVIDE LOMBARDO unimap
CARLO TRAVERSO unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

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.

Knowledge

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.

Modalità di verifica delle conoscenze

Si valuterà l'abilità dello studente di discutere con competenza e chiarezza i contenuti principali del corso.

Metodo:

* Esame orale finale

Assessment criteria of knowledge

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

Capacità

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.

Skills

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.

Modalità di verifica delle capacità

Verifica nel corso dell'esame orale finale, che comprenderà anche una breve relazione tecnica su un argomento a scelta

Assessment criteria of skills

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.

Comportamenti

Gli studenti sono consigliati a frequentare le lezioni e a studiare gli argomenti via via presentati.

Behaviors

Students are advised to follow the lessons, study the subjects discussed.

Modalità di verifica dei comportamenti

Nessuna

Assessment criteria of behaviors

None

Prerequisiti (conoscenze iniziali)

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.

Prerequisites

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.

Corequisiti

Il corso è indipendente da altri corsi, anche se sinergie sono possibili.

Co-requisites

The course is indipendent of other courses, although synergies are possible.

Prerequisiti per studi successivi

Indicazioni su studi utili per la continuazione delle ricerche illustrate nel corso saranno date a lezione o in documentazione resa disponibile.

Prerequisites for further study

Indications on further studies useful to forward the researches described in the course will be given inj the lessons, or through documentation provided.

Programma (contenuti dell'insegnamento)

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.

Syllabus

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.

Bibliografia e materiale didattico

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/

Bibliography

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

Non-attending students info

Students are invited to take part to meeting the teachers, also by individual appointment

Modalità d'esame

Esame orale

Assessment methods

Oral exam

Stage e tirocini

A richiesta, anche per conto di altri corsi.

Work placement

Upon request, also for other courses.

Updated: 20/09/2020 21:52