Crittosistemi ellittici (CR510)
Anno accademico 2018/19 - Secondo semestre
Docente: Giulio Codogni

Schedule:  Monday 14:00-16:00 room M6, and Thursday , 11:00 to 13:00 room M4

No class on Thursday 9th of May

On Monday the 13th of May there will be a talk by Dr. Efstathia Katsigianni (Escrypt) about applications of Elliptic Curve Cryptography from 11:00 to 12:00, and a research talk by Luca De Feo from 12:00 to 13:00, room M3

No class on Monday 13th afternoon

Final presentations: 

• Monday 3rd of June, form 9:00 to 12:00 room M4 Examples of safe curves and their j-invariant. Side attacks.
• Thursday 6th of June form 14:00 to 17:00 room M4. Lenstra's factorization algorithm 
• Friday 7th of June from 9:00 to 13:00 room M4. Post quantum cryptography
• Thursday 4th of July from 10:00 to 12:00, room M4, Schoof's algorithm, supersingular curves

Office hours: Monday from 11:00  to 13:00, office 302, or by appointment

Language: English

Bibliography:

1. Lawrence C. Washington, Elliptic curves: Number Theory and Criptography, Chapman & Hall (CRC),first edition 2003, second edition 2008 
2.  The Arithmetic of Elliptic Curves, di J. H. Silverman.

Exam: Homeworks, presentation of at least one execrcise at the blackboard, and final presentaton in the form of a seminar. Date appelli: 24/6 and 16/7.

Deadlines for homeworks (all exercises are from Whasington, second edition):

• 21st of March: exercises from 2.1 to 2.12, except 2.7 and 2.9
• 25th of March: excersises 2.13, 2.18, 2.20
• 15th of April: all exercises from chapter 2, except 2.7. Chapter 7, exercise 7.1. Extra excersie of linear algebra. Chapter 3, exercises 3.4, 3.7 and start trying 3.2.
• 16th of May: all exercises from chapter 3 except 3.8. Chapter 4, exercises 4.1, 4.2 (hint: use thm 4.12), 4.7 and 4.10.

Possible topics for the final presentation (and references in brackets):

• Quantum cryptography (L. De Feo, Mathematics of Isogeny Based Cryptography (pdf))
• Side attacks to the discrete logarithm problem on elliptic curves (Handbook of Elliptic and Hyperelliptic Curve Cryptography, pages 673-680, and references therein)
• Weierstrass P function (Whashington Chapter 9)
• Associativity of the group law and criterion for flexes - intersection theory (Whashington Section 2.4 and somehting more)
• Cryptowars 2018
• more about the j-invariant, and possibly writing a popularization paper.
• Diophantine equations
• more about elliptic curves over a ring and Lenstra algorithm
• Somehting about the number of K-points of an elliptic curve, where K is a finite field (to be made precise)

Additional bibliography:

1. L. De Feo, Mathematics of Isogeny Based Cryptography (pdf) 
2. Baldoni, Ciliberto, Piacentini Cattaneo, Elementary Number Theory, Crypthography and Codes, Universitex, Sringer, 2009 
3. I. Blake, G. Seroussi and N. Smart, Elliptic Curves in Cryptography, LMS 265, 1999 
4. D. Hankerson, S. Vanstone e A. J. Menezes, Guide to Elliptic Curve Cryptography, Springer, 2004
5. R. Schoof , The discrete logarithm problem (pdf)
6. G. Frey and T. Shaska, Curves, Jacobians and Cryptography (pdf)
7. slide del colloqui5o di G. Frey
8.  Handbook of Elliptic and Hyperelliptic Curve Cryptography, 1st edition, 200
9. A website about cryptographically secure curves

cfu/ECTS: 7 

Other information:

Lunedì 8 e Martedì 9 aprile l'associazione romana di teoria dei numeri organizzerà l'Atelier Pari/GP presso l'Università Roma Tre. Pari/GP è un sistema algebrico per computer in grado di manipolare (tra le altre cose) le curve ellittiche.

Mercoledì 8 maggio l'associazione De Componendis Cifris organizzerà un evento di crittografia militare a Roma che potrebbe essere di interesse per gli studenti.

Programma definitivo: Definizione e prime proprietà delle curve ellittiche: richiami sulle curve algebriche piane, cubiche lisce, legge di gruppo. Invrainte j. Anello degli endorfismi di una curva ellittica: la somma e la composizione di isogenie è un'isogenia, l'annelo degli endomorfismi ha caratteristica zero.  Curve ellittiche su un anello e algoritmo di fattorizzazione di Lenstra. Punti di torsione, curve ellittiche ordinarie e supersingolari. Morfismo di Frobenius, polinomio minimo del morfismo di Frobenius. Forma quadratica sull'anello degli endomorfismi, teorema di Hasse. Accoppiamento di Weil. Applicazioni delle curve ellittiche alla crittografia: scambio delle chiavi di Diffie-Helman, attaco MOV, backdoor nel genaratore di numeri primi basato sulle curve ellittiche.  Cenni alla crittografia basate sulle isogenie (in particolare su SIDH), formula di Vélu.

Pagina ufficiale del corso. 

Diario delle lezioni:

(Chapters numbers are from the book by Washington)

1.  Mon 25/2: introduction to the course. Diffie-Helman key exchange, Massey-Omura encryption, Elgamal Digital signature

2. Thu 28/2: Weierstrass equation, Weierstrass model of an elliptic curve, group law (chapters 2.1 and 2.2)

3. Mon 4/3: more about the group low in Weierstrass form. Projective space and hypersurfaces in projective space (chapters 2.2, 2.3 and 2.4)

4. Thu 7/3: Hypersurfaces in the projective line and plane; intersections, multiplicities, smoothness and tangents

5. Mon 11/3: definition of elliptic curve as cubic hypersurface in the projective plane

6. Thu 14/3: comparison between Weierstrass and projective model of an elliptic curve

7. Mon 18/3 (4 hours): j-invariant (section 2.7); elliptic curves over a ring and Lenstra factorization alghoritm (Sections 2.6, 2.10 and 7.1) + Excersises session
    
8.  Thu 21/3: isogenies, definition and examples (section 2.8)
9. Mon 25/3 (4 hours): isogenies, more examples, normal form, addition and composition (section 2.8). Excersies session
10.  Thu 28/3: Frobenius; surjectivity of an isogeny (section 2.8)
11. Mon 1/4 degree and separability of an isogeny, propetries and examples
12. Thu 4/4: torsion points and division polynomials (Sections 3.1 and 3.2)
13. Mon 15/4 Backdoor in the NIST specified Dual_EC_DRBG cryptographically secure pseudorandom number generator, see also this and this. Exercise session.
14. Thu 18/4 Lenstra primality test (Section 7.2). Exercise session.
15. Mon29/04 Weil pairing (Section 3.3)
16. Thu 2/5 MOV attack (Section 5.3)
17. Mon 6/5 Hasse Theorem (Section 4.2); Legendre symbols (Section 4.3.2)
18. Thu 9/5 no class
19. Mon 13/5 seminars by L. De Feo and E. Katsigianni
20. Thu 16/5 Characteristic polynomial of the Frobenius morphism. Exercises
21. Mon 20/5 Exercises
22. Thu 23/5 Exercises
23. Mon 27/5 Vélu's formulae
24. Thu 30/5 Preparation of final presentations