CR3 - Curve Ellittiche in Crittografia

A.A. 2004/2005 - I Semestre - Crediti 6.


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

Informazioni Generali

Docenti Francesca Tartarone Francesco Pappalardi
Ricevimento martedì 11-12 martedì 16-17
Ufficio309 209
Telefono 06 54888228 06 54888243
E-mailtfrance@mat.uniroma3.it pappa@mat.uniroma3.it
Lezioni:
Martedì 14-16 (Aula C)
Giovedì 11-13 (Aula 100)
Venerdì 16-18 (Aula C)
DESCRIZIONE DEL CORSO



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

Avvisi:

  • Il corso è stato attivato come corso regolare e non di letture come originariamente previsto
  • Ai fini della valutazione gli studenti dovranno presentare un seminario su un argomento inerente al programma del corso e consegnare la soluzione di esercizi che saranno proposti durante le lezioni (vedi elenco)
  • Giovedì 14 Ottobre alle 16:00 in aula 100 si terrà la prima serie di seminari.
  • Durante la settimana che inizia il 18 Ottobre, le lezioni verranno interrotte e riprenderanno regolarmente la settimana successiva.
  • La lezione del giorno Giovedì 4 Novembre è stata rimandata.
  • L'ultima lezione di Francesco Pappalardi (interrotta a metà giovedì 2 dicembre) è stata recuperata giovedì 9 dicembre alle 11:00.
  • programma dei prossimi seminari:
    - Giovedì 16 Dicembre ore 11:00 (Aula 100)
    Angela Pesce, Divisori e l'accoppiamento di Weil
    - Venerdì 17 Dicembre ore 14:00 (Aula 100 - da confermare)
    Fabrizio Araimo - Filomena Di Berardo, Calcolo del numero di punti delle curve del tipo: E: y2 = x3 - kx.
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare Elenco proposte seminari

    Diario delle Lezioni:

    1. Martedì 21 Settembre 2004: (P) 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. Giovedì 23 Settembre: (P) 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, Enunciato del Teorema di Mordell-Weil.
    3. Martedì 28 Settembre: (P) La struttura del gruppo E(R) e E(C), enunciato del Teorema di struttura di E(Fq) e del Teorema di Hasse, Pseudo codice per l'algoritmo dei quadrati successivi, Richiami sullo spazio proiettivo e sui polinomi omogenei, Il punto all'infinito di un'equazione di Weierstrass, definizione di invariate j di una curva ellittica, curve ellittiche con invariante j = 0,1728, proprietà dell'invariante j.
    4. Giovedì 30 Settembre: (P) L'invariante j e le classi di isomorfismo di curve ellittiche su campi algebricamente chiusi, 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, Definizione di endomorfismo, prime proprietà degli endomorfismi.
    5. Venerdì 1 Ottobre: (P) 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 (Fq: E(Fq) ® E(Fq),¥®¥, (x,y)® (xq,yq)), proprietà dell'endomorfismo di Frobenius (inseparabilità)
    6. Martedì 5 Ottobre: (P) 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), P ® nP ( (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,
    7. Giovedì 7 Ottobre: LEZIONE RIMANDATA
    8. Venerdì 8 Ottobre: (P) 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. Martedì 12 Ottobre: (P) 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, 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.
    10. Giovedì 14 Ottobre: (P) 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 per ogni n coprimo con la caratteristica, allora E[n]@ Z/nZÅ Z/nZ. La definizione dei polinomi di divisione ym(x,y), fm(x,y) e wm(x,y), proprietà dei polinomi di divisione, enunciato del Teorema:[n](x,y)=(fn(x)/yn2(x),wn(x,y)/yn(x,y)3).
    11. Giovedì 14 Ottobre ore 16: SEMINARI
    12. Venerdì 15 Ottobre: (T) Generalità sulle intersezioni fra rette e curve in PK2 . Risultati preparatori alla dimostrazione dell'associatività dei punti sulle curve ellittiche.
    13. Martedì 19 Ottobre: LEZIONE RIMANDATA
    14. Giovedì 21 Ottobre: LEZIONE RIMANDATA
    15. Venerdì 22 Ottobre: LEZIONE RIMANDATA
    16. Martedì 26 Ottobre: (T) Dimostrazione dell'associatività della somma per i punti di una curva ellittica.
    17. Giovedì 28 Ottobre: (T) Il problema del Logaritmo Discreto. Algoritmi per il calcolo del logaritmo discreto:  metodo dell'Indice e Rho di Pollard.
    18. Venerdì 29 Ottobre: LEZIONE RIMANDATA
    19. Martedì 2 Novembre: LEZIONE RIMANDATA
    20. Giovedì 4 Novembre: LEZIONE RIMANDATA
    21. Venerdì 5 Novembre: LEZIONE RIMANDATA
    22. Martedì 9 Novembre: (P) Riepilogo sulle proprietà dei polinomi di divisione (da utilizzare per la dimostrazione del teorema di struttura dei gruppi di n-torsione), calcolo del grado e dei coefficienti dei termini di grado massimo di fn(x) e yn2(x), Enunciato del TCGAF, dimostrazione del Teorema di struttura (3.2) per E[n] nel caso in cui la caratteristica del campo non divide n (i.e. l'endomorfismo [n] è separabile).
    23. Giovedì 11 Novembre: (P) fine dimostrazione dimostrazione del Teorema di struttura (3.2) per E[n] nel caso in cui la caratteristica del campo divide n (i.e. l'endomorfismo [n] non è separabile), 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, proprietà dell'endomorfismo di Frobenius ( E(Fqr)=Ker(Fqr - 1)=deg( Fqr - 1 ) ).
    24. Venerdì 12 Novembre: (T) Attacco MOV.
    25. Martedì 16 Novembre: (P) Enunciato dei Teoremi di Waterhouse e di Ruck . Proprietà dell'endomorfismo di Frobenius, Dimostrazione del Teorema di Hasse ( |#E(Fq)-(q+1)| £ 2 Öq )
    26. Giovedì 18 Novembre: (P) Il polinomio caratteristico di Frobenius (X2-a q(E) X + q) e le sue radici (a e b ), ancora proprietà del Frobenius ( Fq 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 + an + bn ), il metodo dei simboli di Legendre
    27. Venerdì 19 Novembre: (T) Metodi Baby-Step  Giant-Step e di Polig-Hellman.
    28. Martedì 23 Novembre: (P) Ordine dei punti di E(Fqn), esempi di calolo di #E(Fqn), possibili campi finiti Fq per cui E(Fq) @ Z/nZÅZ/nZ, Introduzione dell'algoritmo Baby step Giant Step.
    29. Giovedì 25 Novembre: (P) L'algoritmo Baby step Giant Step, Analisi e Complessità, Esempi, Introduzione all'algoritmo di Schoof, come verificare se un polinomio ha radici in un campo finito.
    30. Giovedì 25 Novembre: SEMINARIO
    31. Venerdì 26 Novembre: (T) Attacco sulle curve anomale. Schema di Firma di El Gamal.
    32. Martedì 30 Novembre: LEZIONE RINVIATA CAUSA DIFFICOLTA' NEI TRASPORTI
    33. Giovedì 2 Dicembre: (P) L'algoritmo di Schoof (prima parte) - riduzione del problema del calcolo del numero dei punti al problema di calcolare aq(E) mod l dove l varia in un isieme S che non contiene la caratteristica del campo con cardinalità maggiore si 4q1/2. Caso l=2. LEZIONE INTERROTTA A META'
    34. Venerdì 3 Dicembre:  (T) Crittosistemi  sulle curve ellittiche basati sul problema della fattorizzazione. Un crittosistema basato sull'accoppiamento di Weil.
    35. Martedi 7 Dicembre: (T) SEMINARIO + esercitazione al computer su Pari
    36. Giovedì 9 Dicembre: (P) Pesudo codice per l'algoritmo di Schoof, esempio esplicito di un applicazione dell'algoritmo di Schoof, Discussione teorica dell'algoritmo. FINE CORSO

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

    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 proposte seminari

    Elenco degli esercizi da consegnare:

    1. Esercizio 2.4 (pagina 67 del libro di Washington)
      (28/09)
    2. Esercizio 2.12 (pagina 68 del libro di Washington)
      (28/09)
    3. Esercizio (facoltativo) Usare un pacchetto per la manipolazione formale (Maple, Mathematica, ....) per calcolare le formule per la somma dei punti su una curva ellittica definita da una equazione di Weierstrass generalizzata
      (30/09)
    4. Esercizio 2.14 (pagina 68 del libro di Washington)
      (1/10)
    5. Esercizio Dimostrare che se alpha è un ensomorfismo di una curva ellittica E/K e se scriviamo a (x,y) = (p(x)/q(x),yp1(x)/q1(x)), con (p(x),q(x)) = 1 e (p1(x),q1(x)) = 1, allora i polinomi p, q, p1, q1 sono univocamente determinati da a
      (5/10)
    6. Esercizio Dimostrare che EndK(E) è un anello con unità
      (8/10)
    7. Esercizio Sia ED y2=x3+Dx, D ¹ 0. Dimostrare che EndQ(E) contiene un sottoanello isomorfo a Z[e2pi/3]
      (8/10)
    8. Esercizio Sia ED y2=x3+D, D ¹ 0. Dimostrare che EndQ(E) contiene un sottoanello isomorfo a Z[i]
      (8/10)
    9. Esercizio Determinare tutti i punti "all'infinito" di una curve ellittica definita da un'equazione di Weierstrass su Z/nZ
      (12/10)
    10. Esercizio (facoltativo) Dimostrare che Z/nZ è ACE
      (12/10)
    11. Esercizio 3.1 (pagina 86 del libro di Washington)
      (14/10)
    12. Dimostrare il Teorema 3.6 (pagina 79 del libro di Washington) nel caso n=2 e n=3
      (9/11)
    13. Sia E: y2 = x3 + 2. Determinare la struttura di E(F7) e di E(F25) determinando in ciascun caso la decomposizione come prodotto di gruppi ciclici
      (11/11)
    14. Determinare tutti i possibili ordini dei gruppi E(Fq) per tutte le curve E/Fq e per q = 2, 3, 5, 7, 9.
      (16/11)
    15. Determinare una coppia di valori (a,q) tali che il Teorema 4.4 del libro di Washington valga per due diverse coppie (n1,n2).
      (16/11)
    Informazioni Generali Avvisi Diario delle Lezioni Testi Consigliati ProgrammaElenco degli esercizi da consegnare Elenco proposte seminari

    Elenco proposte seminari:

    1. Classificazione della curve singolari definite da equazione di Weierstrass. (paragrafo 2.9 del libro di Washington)
      (Filippo Morabito, 14/10)
    2. Altre Equazione per curve ellittiche. (paragrafo 2.5 del libro di Washington)
      (Angela Pesce, 14/10)
    3. Formule per la somma di punti per curve ellittiche su anelli ACE. (paragrafo 2.10 del libro di Washington e referenze)
      (non assegnato)
    4. Tate-Lichtenbaum Pairing. (paragrafo 5.5 del libro di Washington)
      (Stefano Mazzia, 19/11)
    5. Dimostrazione del Teorema 2.6 del libro di Washington.
      (non assegnato)
    6. Congettura di Goldbach e firme digitali.
      (Davide Liberti, 25/11)
    7. Calcolo del numero di punti delle curve del tipo: E : y2 = x3 - kx . (paragrafo 4.4 del libro di Washington)
      (Fabrizio Araimo - Filomena Di Berardo, 17/12)
    8. Scambio di Chiavi di Diffie-Hellman. Crittosistemi di Massey Omura e El Gamal.
      (Silvia Roverato, 2/12)
    9. Fattorizzare gli interi utilizzando le curve ellittiche. (paragrafo 7.1 del libro di Washington)
      (Alessandro Russo, 7/12)
    10. Divisori e l'accoppiamento di Weil. (paragrafi 11.1 e 11.2 del libro di Washington)
      (Angela Pesce, 16/12)
    11. Curve Supersingolari. (paragrafo 4.6 del libro di Washington)
      (Filippo Morabito, 14/12)
    12. L'agoritmo di Satoh e derivati
      (Paolo Tranquilli, TBA)