CR3 - Curve Ellittiche in Crittografia

A.A. 2013/2014 - II Semestre - Crediti 6.


Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare

Informazioni Generali

Docente Francesco Pappalardi
Ricevimentolunedý 16-18
Ufficio 209
Telefono 06 57338243
E-mail pappa@mat.uniroma3.it
Lezioni:
Lunedý 09-11 (Aula 009)
Mercoledý 09-11 (Aula 009)
Giovedý 16-18 (Aula 009)
DESCRIZIONE DEL CORSO



Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare

Avvisi:

  • [23/04/2014] In data 6 Maggio 2014 si terranno i seguenti seminari (comunicheremo in seguito l'aula):
    - 9:30 - 10:30 : Christian Mauduit, "Prime numbers, determinism and pseudorandomness"
    - 10:30 - 11:30 : JoŰl Rivat, "On the digits of prime numbers"
  • [26/02/2014] link per il documento NIST citato oggi a lezione
  • [17/02/2014] La lezione prevista per il 27/02/2014 non avrÓ luogo
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare

    Diario delle Lezioni:

    1. Lunedý [17/02/09]: Introduzione al corso, Il problema delle palle di cannone, il problema dei numeri congruenti, Soluzione dell'Ultimo Teorema di Fermat nel caso n=3,4 usando curve ellittiche.
    2. Mercoledý [19/02/09]: L'equazione di Weierstrass, L'equazione di Weierstrass generalizzata. Richiami sullo spazio proiettivo e sui polinomi omogenei, Il punto all'infinito di un'equazione di Weierstrass. La definizione della somma di punti su una curva ellittica, Formule per la somma di punti.
    3. Giovedý [20/02/09]: La struttura del gruppo E(R) e E(C), enunciato del Teorema di struttura di E(Fq) e del Teorema di Hasse. La struttura del gruppo E(Q) e Enunciato del Teorema di Mordell-Weil. Pseudo codice per l'algoritmo dei quadrati successivi, Equazioni parametriche delle rette proiettive. MolteplicitÓ di intersezione tra retta e curva nel piano proiettivo. Retta tangente. Punti singolari. GeneralitÓ sulla Teoria classica delle curve proiettive.
    4. Lunedý [24/02/14]: ancora generalitÓ sulla Teoria classica delle curve proiettive. Preparazione alla dimostrazione dell'associativitÓ della somma di punti su curve ellittiche. Equazione di Legendre per curve ellittiche. Curve ellittiche definite da equazioni cubiche, curve ellittiche definite da equazioni quartiche.
    5. Mercoledý [26/02/14]: Curve ellittiche come intersezione di due quadriche. Altri sistemi di coordinate (coordinate proiettive, coordinate Jacobiane, coordinate di Edwards). Definizione di invariante j di una curva ellittica, curve ellittiche con invariante j = 0,1728, proprietÓ dell'invariante j.
    6. Lunedý [03/03/14]: Altre proprietÓ del invariante j. Automorfismi di una curva ellittica. Curve ellittiche in caratteristica 2, l'equazione di Weierstrass Ŕ singolare in caratteristica 2, i due tipi di equazioni di Weierstrass in caratteristica 2 (caso 1: y2+xy=x3+b2x2+b6, b6≠ 0 e caso 2: y2+b3y=x3+b4x+b6, b3≠ 0), operazione sui punti di una curva definita da un'equazione di Weierstrass generalizzata, inversione di punti su un equazione di Weierstrass generalizzata, formule per la duplicazione di punti per le curve ellettiche in caratteristica due. Endomorfismi (inizio)
    7. Mercoledý [05/03/14]: Endomorfismi (continua). forma ridotta degli endomorfismi, grado degli endomorfismi, endomorfismi separabili, esempi. il nucleo degli endomorfismi vs il grado. esempi. Endomorfismo di Frobenius.
    8. Giovedý [06/03/09]: ProprietÓ degli endomorfismi. Criteri per la separabilitÓ. SeparabilitÓ e endomorfismo di Frobenius, esempi.
    9. Lunedý [10/03/14]: Il gruppo dei punti non singolari di un equazione di Weierstrass Singolare. Classificazione dei possibili gruppi. Riduzione additiva, moltiplicativa split e moltiplicativa non split. Esempi.
    10. Mercoledý [12/03/14]: La struttura dei gruppi E[n] di n-torsione (inizio). Esempi: Calcolo della 2-torsione e della 3-torsione in tutti i casi. Definizione dei polinomi di divisione e loro proprietÓ. Definizione dei polinomi di divisione ψm(x,y), φm(x,y) e ωm(x,y), proprietÓ dei polinomi di divisione, enunciato del Teorema:[n](x,y)=(φn(x)/ψn2(x),ωn(x,y)/ψn(x,y)3).
    11. Giovedý [13/03/09]: Ancora sulla struttura dei gruppi E[n] di n-torsione. Inizio della dimostrazione del Teorema di Struttura: Data una curva ellittica E/K, se #E[n]=n2 e n Ŕ coprimo con la caratteristica, allora E[n]≅ Z/nZZ/nZ. I Polinomi di divisione e l'endomorfismo [n]. Il grado dei polinomi di n-torsione. Altre proprietÓ. Calcolo del grado e dei coefficienti dei termini di grado massimo di φn(x) e ψn2(x). Riduzione al calcolo del grado della moltiplicazione per n.
    12. Lunedý [17/03/14]: Fine dimostrazione del fatto che il grado per la moltiplicazione per nn Ŕ pari a n2. Spazio proiettivo su un anello. La nozione di curva ellittica su un anello. La nozione di Anello ACE (Adatto alle Curve Ellittiche), Z Ŕ ACE, I campi sono ACE, le formule di somma di punti per curve ellittiche definite su anelli ACE (solo cenni), esempio y2=x3-x+1 su Z/25Z, E(Z/n1n2Z) ≅ E(Z/n1Z)⊕ E(Z/n2Z), la mappa di riduzione,
    13. Mercoledý [19/03/14]: Curve ellittiche modulo n. L'accoppiamento di Weil.
    14. Giovedý [20/03/09]: Lezioni presentate da
      P. Stevenhagen (Leiden): Introduction to Elliptic Curves Cryptography
      P. Moreee (Bonn): Enumeration of RSA numbers
    15. Lunedý [24/03/14]: Accoppiamento di Weil. Conseguente delle proprietÓ dell'accoppiamento di Weil. Formula per il grado di aα+bβ dove α e β sono endomorfismi e a,b sono interi. Curve su campi finiti, esempi di curve: E: y2 = x3+x+1 su F7, E: y2 = x3+2 su F7, E: y2 + xy + x3 +1 su F2 e su F4, Teorema di struttura per E(Fq), enunciato del Dimostrazione del Teorema di Hasse ( |#E(Fq)-(q+1)| ≤ 2√q ). Il polinomio caratteristico di Frobenius (X2-aq(E) X + q) e le sue radici (α e β).
    16. Mercoledý [26/03/14]: ProprietÓ dell'endomorfismo di Frobenius ( E(Fqr)=Ker(Fqr - 1)=deg( Fqr - 1 ) ). Enunciato del Teorema di Waterhouse e di Ruck. Dimostrazione del Teorema di Hasse ( |#E(Fq)-(q+1)| ≤ 2√q).
    17. Giovedý [27/03/09]: Ancora proprietÓ del Frobenius ( Φq soddisfa il suo polinomio caratteristico ). Calcolo del numero dei punti razionali di una curva ellittica su un campo finito, il metodo del sottocampo ( #E(Fqn) = qn + 1 + αn + βn ). Il metodo dei simboli di Legendre. La nozione di curva twist.
    18. Venerdý [04/04/14]: INCONTRO PER DISCUSSIONE INFORMALE SULLO STATO DI SVOLGIMENTO DEGLI ESERCIZI. Aula F ore 14:30.
    19. Lunedý [07/04/14]: Teoremi vari sulla struttura del gruppo dei punti razionali: Teorema di Mestre Esempi. Il calcolo dell'ordine di un elemento. Introduzione. Algoritmo Baby Step - Giant Steps. BSGS per curve ellittiche (inizio)
    20. Mercoledý [09/04/14]: BSGS per curve ellittiche (fine). Dimostrazione della proposizione che afferma che tranne per un numero finito di q, l'esponente determina la struttura.
    21. Giovedý [10/04/09]: Inizio dimostrazione della formula per il numero dei punti di E: y2 = x3 +kx. Il caso p =3(4). Caratteri quadratici e somme di Jacobi.
    22. Lunedý [14/04/14]: Fine dimostrazione della formula per il numero dei punti di E: y2 = x3 +kx. Algoritmo di Schoof (inizio).
    23. Mercoledý [16/04/14]: Fine Algoritmo di Schoof. Curve supersingolari: definizione e caratterizzazioni.
    24. Mercoledý [23/04/14]: Curve Supersingolari (inizio)
    25. Giovedý [24/04/14]: Curve Supersingolari (fine)
    26. Lunedý [28/04/09]: Fattorizzazione con curve ellettiche alla Lenstra. Certificazione di PrimalitÓ di Goldwasser Kilian

    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare

    Testi consigliati:


    Testi specifici

  • Lawrence C. Washington, Elliptic Curves: Number Theory and Crptography. Chapman & Hall (CRC) 2003.
  • Alfred J. Menezes, Elliptic Curve Public Key Cryptosystems. The Kluwer International Series in Engineering and Computer Science, Vol. 234 Kluwer 1993.
  • Darrel Hankerson, Alfred J. Menezes and Scott Vanstone, Guide to Elliptic Curve Cryptography. Springer Professional Computing 2004.
  • Andreas Enge, Elliptic Curves and Their Applications to Cryptography. An Introduction. Springer Verlag 1999.
  • Ian Blake, Gadiel Seroussi and Nigel Smart, Elliptic Curves in Cryptography. Cambridge University Press 1999.
  • Michael Rosing, Implementing Elliptic Curve Cryptography. Manning Greenwich 1998.

    Testi generali

  • Alfred J. Menezes, Paul C. van Oorshot e Scott A. Vanstone, Handbook of Applied Cryptography. CRC Press 1997
  • Neal Koblitz, A Course in Number Theory and Cryptography. GTM 114, Springer Verlag 1994
  • Neal Koblitz, Algebraic Aspects of Cryptography. Algorithms and Computation in Mathematics Vol. 3, Springer Verlag 1998
  • Douglas R. Stinson, Cryptography: Theory and Practice. CRC Press 1995 (seconda edizione).




    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare

    Elenco degli esercizi da consegnare:

    1. Esercizi 1.1 - 1.5 (pagina 8 del libro di Washington) 3/03
    2. Esercizi 2.1 - 2.6 (pagina 71 e 72 del libro di Washington) 10/03
    3. Esercizi 2.7 - 2.17 (pagina 71 e 72 del libro di Washington) 24/03
    4. Esercizio: Verificare la correttezza delle formule sul libro di Washington sulle coordinate proiettive, Jacobiane e di Edwards consultando anche altri testi cone ad esempio BlSeSm e HaMeVa. Scrivere un resoconto di mezza pagina. 10/03
    5. Esercizio (facoltativo): scrivere in dettaglio la dimostrazione del Teorema 2.17 dal libro di Washington.
    6. Esercizi 2.18 - 2.24 (pagine 74, 75 e 76 del libro di Washingtom) 04/04
    7. Risolvere il seguente esercizio 24/03: Dato un primo dispari p e un elemento a in Fp. Dimostrare che
      - Per ogni x in Fp esistono u e v in in Fp tali che x=u2-av2.
      - Sia α in Fp2 radice quadrata di a, allora Fp[α]*Fp*, u+αv → u2-(αv)2 è un omomorfismo di gruppi moltiplicativi.
    8. Scrivere una relazione di poche righe sul contenuto degli articoli
    9. Esercizi 3.1 - 3.8 (pagina 92 e 93 del libro di Washington) 14/04
    10. Esercizi 4.1 - 4.7 (pagina 139 e 141 del libro di Washington) 23/04
    11. Esercizi 4.8 - 4.14 (pagina 141 e 142 del libro di Washington) 28/04
    12. Esercizi 5.1 - 5.12 (pagina 167 e 168 del libro di Washington) 05/05
    13. Esercizi 6.1 - 6.8 (pagina 187 e 188 del libro di Washington) 12/05
    14. Esercizi 7.1 - 7.4 (pagina 197 e 198 del libro di Washington) 19/05
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare