CR410 - Crittografia I

1. Lezione [19/02/13] Presentazione del corso, informazioni varie. Espansione binaria, numero delle cifre. La nozione di operazione bit tipo somma. Tempo di calcolo per una funzione (o complessità).
2. Lezione [20/02/13] La nozione di operazione bit. La complessità di somma, sottrazione, prodotto e divisione. La notazione "O grande". Esempi vari.
3. Lezioni [21/02/13] Esempi e esercizi sul calcolo delle complessità: Il fattoriale, il prodotto e somma di polinomi, Moltiplicazione alla Karatsuba e analisi della sua complessità. Cambio di base.
4. Lezioni [27/02/13] Algoritmi con complessità polinomiale, esponenziale e subesponenziale. Algoritmo per il calcolo della parte intera della radice quadrata. divisibilità di interi. distribuzione dei numeri primi. Inizio Algorimo di Euclide Algoritmo di Euclide binario. Esempi
5. Lezioni [28/02/13] Analisi dell'Algoritmo di Euclide. Algoritmo di Euclide esteso. Calcolo dei coefficienti di Bezout mediante formule ricorsive. Esempi.
6. Lezioni [05/03/13] Ultimi commenti sull'algoritmo di Euclide. Stime per i coefficienti di Bezout. Numeri coprimi. Funzione di Eulero. Proprietà ed esempi. Algoritmo dei quadrati successivi. Pseudo codice per l'algoritmo dei quadrati successivi e analsi dell'algoritmo.
7. Lezioni [06/03/13] ESERCIZI SVOLTI DAGLI ANNI PASSATI
8. Lezioni [07/03/13] Soluzione di congruenze lineari, Teorema Cinese dei resti e applicazioni. Piccolo Teorema di Fermat e Teorema di Eulero. L'algoritma RSA. Esempi. L'ipotesi RSA.
9. Lezioni [12/03/13] ESERCIZI SVOLTI DAGLI ANNI PASSATI
10. Lezioni [13/03/13] Rsa didattico. Generazione di numeri primi. Algoritmi probabilistici Las Vegas Distribuzione dei numeri primi e applicazione all'analisi di algoritmi Las Vegas.
11. Lezioni [19/03/13] Inizio dei test di primalità. Probabili primi e pseudo primi. Pesudo primi di Fermat. Infinità degli pseudo primi di Fermat for ogni fissata base. Numeri di Carmichael e loro proprietà.
12. Lezioni [20/03/13] ESERCIZI SVOLTI DAGLI ANNI PASSATI
13. Lezioni [21/03/13] ESERCIZI SVOLTI DAGLI ANNI PASSATI
14. Lezioni [03/04/13] PRIMA PROVA IN ITINERE
15. Lezioni [09/04/13] Basi forti e pseudo primi forti. Numerazione delle basi forti per numeri dispari composti. Esempi.
16. Lezioni [10/04/13] Test di primalità di Miller Rabin. Test di primalità probabilistici.
17. Lezioni [16/04/13] Metodi di fattorizzazione con complessità esponenziale. Fattorizzazione alla Fermat. Fattorizzazione alla Lehman. Metodo di Pollard (inizio). Il paradosso del compleanno.
18. Lezioni [17/04/13] Metodi di fattorizzazione con complessità esponenziale. Il metodo di Pollard (fine). Certificazione di primalità: Certificazione alla Lucas, Criterio di Pepin, Teorema di Pocklington. Esempi.
19. Lezioni [18/04/13] I simboli di Legendre e metodi per calcolarli. Applicazioni dei simboli di Legendre in Crittografia - Pseudo primi di Eulero.
20. Lezioni [23/04/13] Fine Solovay - Strassen. Inizio Campi finiti.
21. Lezioni [24/04/13] Campi Finiti. La cardinalit� di un campo finito. ciclcità del gruppo moltiplicativo. Esistenza e unicitÃ. Proprietà fondamentali e esempi. Struttura dl reticolo dei i sottocampi.
22. Lezioni [30/04/13] Campi Finiti. Esempi. Ancora proprietÃ. Enumerazione dei polinomi irriducibili. Radici dei polinomi.
23. Lezioni [02/05/13] Test di irriducibilità. Enumerazione polinomi primitivi.complessità delle operazioni nei campi finiti. Esercizi sui campi finiti dagli anni passati.
24. Lezioni [08/05/13] Esercizi sui campi finiti dagli anni passati. campi con 125 elementi
25. Lezioni [09/05/13] Applicazioni dei campi finiti in crittografia. Il protocollo dello scambio chiavi di Diffie Hellmann. Il crittosistema Massey Omura. Il crittosistema ElGamal,
26. Lezioni [14/05/13] Esempi con GP-Pari al computer. Algoritmi per il calcolo di logaritmi discreti: Forza Bruta e BabyStepGiantStep
27. Lezioni [15/05/13] Ancora sui logaritmi discreti. Esempi con BSGS Algoritmo Silver-Polhig-Hellman. Esempi. Analisi dell'Algoritmo Pohlig - Hellman. Curve ellittiche sui campi finiti.
28. Lezioni [16/05/13] Generalità sulle curve ellittiche sui campi finiti. Somma di punti e punto all'infinito. La struttura di gruppo nell'insieme dei punti razionali. Formule per la somma e la duplicazione. Esempi. Equazioni di Weierstass (generali e in caratteristica maggiore di 3). Le formule per la somma.
29. Lezioni [21/04/13] Curve ellittiche. Curve ellittiche in caratteristica 2. Enunciato del Teorema di Hasse e del Teorema di Struttura per il gruppo dei punti razionali.
30. Lezioni [22/04/13] Ancora sulle curve ellittiche. Curve definite sui sottocampi. Calcolo dell'ordine del gruppo. Il metodo Baby Step Giant Step per calcolare il numero dei punti. Esempi e esercizi.
31. Lezioni [23/04/13] Problemi vari sulle curve ellittiche dai testi di esame degli anni passati.
32. Lezioni [28/05/13] SECONDA PROVA IN ITINERE

Testi consigliati: