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