CR3 - Curve Ellittiche in Crittografia

A.A. 2008/2009 - II Semestre - Crediti 6.


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

Informazioni Generali

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



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

Avvisi:


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

    Diario delle Lezioni:

    1. Lunedì [23/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ì [25/02/09]: L'equazione di Weierstrass, L'equazione di Weierstrass generalizzata, La deifinizione della somma di punti su una curva ellittica, Formule per la somma di punti. 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,
    3. Giovedì [26/02/09]: Richiami sullo spazio proiettivo e sui polinomi omogenei, Il punto all'infinito di un'equazione di Weierstrass. Equazioni parametriche delle rette proiettive. Molteplicità di intersezione tra retta e curva nel piano proiettivo. Retta tangente. Punti singolari. Le equazioni di Weierstrass danno luogo a curve lisce.
    4. Lunedì [02/03/09]: Generalità sulla Teoria classica delle curve proiettive. Definizione di invariate j di una curva ellittica, curve ellittiche con invariante j = 0,1728, proprietà dell'invariante j.
    5. Mercoledì [04/03/09]: Endomorfismi. Proprietà degli endomorfismi, esempi, la moltiplicazione per 2 ([2]: E(Fq)→ E(Fq), P → 2P), grado di un endomorfismo, endomorfismi separabili e inseparabili, l'endomorfismo di Frobenius (Φq: E(Fq) → E(Fq), ∞→∞, (x,y)→ (xq,yq)), proprietà dell'endomorfismo di Frobenius (inseparabilità)
    6. Giovedì [05/03/09]: 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.
    7. Lunedì [09/03/09]: Teorema: Il nucleo di un endomorfismo separabile di una curva ellittica ha tanti elementi quanto è il suo grado mentre quello di un endomorfismo non separabile ha (strettamente) meno elementi del suo grado (in ogni caso il nugleo è finito). Dimostrazione del Teorema, Gli endomorfismi sono suriettivi, La moltiplicazione per n è un endomorfismo, se [n]:E(K) → E(K), PnP ( (x,y) → (Rn(x),Sn(x)y) ), allora R'n/Sn = n; dunque la moltiplicazione per n è separabile solo se la caratteristica del campo non divide n,
    8. Mercoledì [11/03/09]: Dimostrazione del criterio di separabilità di [n]. La nozione di gruppo dei punti razionali per una curva ellittica definita su un anello, esempi vari, spazio proiettivo su un anello (sequenze primitive).
    9. Giovedì [12/03/09]: 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,
    10. Lunedì [16/03/09]: Il sottogruppo di torsione di una curva E[n], enunciato del Teorema di classificazione dei sottogruppi di torsione, determinazione di E[2] in tutte le caratteristiche.
    11. Mercoledì [18/03/09]: Determinazione di E[3] in caratteristica diversa da due, Enunciato del Teorema di clasificazione dei gruppi abeliani finiti, dimostrazione dell' enunciato: Data una curva ellittica E/K, se #E[n]=n2 e n è coprimo con la caratteristica, allora E[n]≅ Z/nZZ/nZ. 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).
    12. Giovedì [19/03/09]: 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),
    13. Lunedì [23/03/09]: Accoppiamento di Weil. Conseguente delle proprietà dell'accoppiamento di Weil. Formula per il grado di a&alpha+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 Teorema di Hasse.
    14. Mercoledì [25/03/09]: Proprietà dell'endomorfismo di Frobenius ( E(Fqr)=Ker(Fqr - 1)=deg( Fqr - 1 ) ). Enunciato del Teorema di Waterhouse e di Ruck. Inizio dimostrazione del Teorema di Hasse ( |#E(Fq)-(q+1)| ≤ 2√q).
    15. Giovedì [26/03/09]: Fine 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. Lunedì [30/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.
    17. Mercoledì [01/04/09]: Teoremi vari sulla struttura del gruppo dei punti razionali: Teorema di Mestre Esempi.
    18. Giovedì [02/04/09]: Il calcolo dell'ordine di un elemento. Introduzione. Algoritmo Baby Step - Giant Steps.
    19. Lunedì [06/04/09]:
    20. Mercoledì [15/04/09]: Algoritmo di Schoof (inizio).
    21. Giovedì [16/04/09]: Fine Algoritmo di Schoof. Curve supersingolari: definizione e caratterizzazioni.
    22. Mercoledì [22/04/09]: Esempi pratici in laboratorio su come usare GP-Pari per fare calcoli su curve ellittiche: inizio applicazione algoritmo di schoof.
    23. Giovedì [23/04/09]: Esempi pratici in laboratorio su come usare GP-Pari per fare calcoli su curve ellittiche: fine applicazione algoritmo di schoof.
    24. Lunedì [27/04/09]:
    25. Mercoledì [29/04/09]:
    26. Giovedì [30/04/09]:
    27. Lunedì [04/05/09]: Lutz-Naggel (Marianna)
    28. Giovedì [07/05/09]: Accoppiamento di Weil (Micaela)
    29. Lunedì [11/05/09]: Pari (Gabriele)
    30. Mercoledì [13/05/09]: Sage (Fabrizio)
    31. Giovedì [14/05/09]: Funzione di Weierstrass (Martina)
    32. Lunedì [18/05/09]: Curve speciali (Alberto)
    33. Mercoledì [20/05/09]: COMPITO FINALE
    34. Giovedì [21/05/09]: FINE CORSO

    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. Esercizio 1.2 (pagina 8 del libro di Washington) 23/02
    2. Determinare le formule di somma e duplicazione di punti per curve definite da equazioni generalizzate di Weierstrass 25/02
    3. Determinare formule per la somma di punti in una curva ellittica in coordinate omogenee.
    4. Trovare una trasformazione affine che porta l'equazione y2=x(x+1)(2x+1)/6 in un equazione di Weierstrass.
    5. Dimostrare che E[3]≅C3xC3 in caratteristica 2.
    6. Esercizio 3.4 (pagina 92 del libro di Washington). 23/03
    7. Determinare l'ordine e la struttura di E(F2) per tutte le curve ellittiche su F2 definite da equazioni di Weierstrass. In ciascuno dei seguenti casi determinare anche la struttura di E(F4). 23/03
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare