CR3 - Curve Ellittiche in Crittografia

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(F_q) 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: y²+xy=x³+b₂x²+b₆, b₆¹ 0 e caso 2: y²+b₃y=x³+b₄x+b₆, b₃¹ 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(F_q) ® E(F_q), P®2P), grado di un endomorfismo, endomorfismi separabili e inseparabili, l'endomorfismo di Frobenius (F_q: E(F_q) ® E(F_q),¥®¥, (x,y)® (x^q,y^q)), 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) ® (R_n(x),S_n(x)y) ), allora R'_n/S_n = 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 y²=x³-x+1 su Z/25Z, E(Z/n₁n₂Z) @ E(Z/n₁Z)Å E(Z/n₂Z), 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]=n² per ogni n coprimo con la caratteristica, allora E[n]@ Z/nZÅ Z/nZ. La definizione dei polinomi di divisione y_m(x,y), f_m(x,y) e w_m(x,y), proprietà dei polinomi di divisione, enunciato del Teorema:[n](x,y)=(f_n(x)/y_n²(x),w_n(x,y)/y_n(x,y)³).
11. Giovedì 14 Ottobre ore 16: SEMINARI
12. Venerdì 15 Ottobre: (T) Generalità sulle intersezioni fra rette e curve in P_K² . 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 f_n(x) e y_n²(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: y² = x³+x+1 su F₇, E: y² = x³+2 su F₇, E: y² + xy + x³ +1 su F₂ e su F₄, Teorema di struttura per E(F_q), enunciato del Teorema di Hasse, proprietà dell'endomorfismo di Frobenius ( E(F_q^r)=Ker(F_q^r - 1)=deg( F_q^r - 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(F_q)-(q+1)| £ 2 Öq )
26. Giovedì 18 Novembre: (P) Il polinomio caratteristico di Frobenius (X²-a _q(E) X + q) e le sue radici (a e b ), ancora proprietà del Frobenius ( F_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(F_qⁿ) = qⁿ + 1 + aⁿ + bⁿ ), 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(F_qⁿ), esempi di calolo di #E(F_qⁿ), possibili campi finiti F_q per cui E(F_q) @ 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 a_q(E) mod l dove l varia in un isieme S che non contiene la caratteristica del campo con cardinalità maggiore si 4q^1/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

Testi specifici