Crittografia 2019/2020
Ricevimento Studenti: Lunedì, 14-16, oppure per appuntamento.
Orario Lezioni: Lunedì 16-18 (Aula 11), Martedì 16-18 (Aula 11)
Appelli sessione estiva anticipata: 4 febbraio, h.10; 27 febbraio, h.10
Appello straordinario: 6 aprile, h.9:30 annullato causa Emergenza Coronavirus
Appelli sessione estiva: 1 luglio, h.14; 29 luglio, h.14 L'esame si svolgerà in maniera telematica sul canale Teams del corso.
Appelli sessione autunnale: Gli appelli della sessione di settembre si terranno in presenza, nel rispetto delle misure di sicurezza stabilite dall'Ateneo:
1 settembre, h. 15:00 (Aula L3) . Scadenza prenotazione su Delphi: 26/08/2020.
22 settembre, h. 10:00 (Aula De Blasi). Scadenza prenotazione su Delphi: 16/09/2020.
È obbligatorio prenotarsi su Delphi, entro i termini stabiliti. Solo gli studenti prenotati avranno accesso all'aula e dovranno firmare una dichiarazione, che verrà fornita in seguito. Gli studenti che non possono sostenere l'esame in presenza (per comprovati motivi di necessità), sono pregati di contattare il docente entro la scadenza della prenotazione su Delphi, in modo che si possa valutare la possibilità di farlo sostenere per via telematica. Eventuali variazioni verranno tempestivamente comunicate su questa pagina web e - solo per gli studenti prenotati - attraverso l'indirizzo email istituzionale.
Programma di massima: Definizione di crittosistema e primi esempi (cifrari additivi, a sostituzione, a trasposizione), cenni di crittoanalisi, cenni di complessità computazionale (algoritmi polinomiali ed esponenziali, complessità delle operazioni elementari e dell'algoritmo di Euclide); crittosistema RSA, test di primalità; elementi di teoria dei numeri ( Numeri di Carmichael, residui quadratici, legge di reciprocità quadratica, pseudoprimi di Eulero, pseudoprimi forti); test di Solovay-Strassen, test di Miller-Rabin; fattorizzazione, algoritmo p-1 di Pollard, algoritmo rho di Pollard; campi finiti e il logaritmo discreto; scambio della chiave di Diffie-Hellman; crittosistema di ElGamal; schemi di firma; curve ellittiche e applicazioni in crittografia (Diffie-Hellman-Merkle, Massey-Omura, ElGamal, Lenstra) .
Testi di riferimento:
Baldoni, Ciliberto,Piacentini Cattaneo, "Aritmetica, Crittografia e Codici"
Fumagalli, Note del Corso di Crittografia, disponibili qui
Koblitz, "A course in number theory and cryptography"
Languasco, Zaccagnini, "Manuale di Crittografia"
Milne, "Elliptic Curves"
Silverman, Tate, "Rational Points on Elliptic Curves"
Ulteriore materiale:
Pagina web del corso di "Cryptography and Code Theory! tenuto da Katherine E. Stange: http://crypto.katestange.net/
(approccio al materiale tramite utilizzo di Sage. Provate a risolvere le varie "Missions"!)
Qui trovate delle note scritte da me su alcune delle lezioni tenute (aggiornate il 20/06). Preparando le lezioni per il corso 2020/2021 ho notato molti refusi che possono essere fuorvianti. Se state preparando l'esame vi consiglio di guardare anche le note aggiornate nella pagina del corso 2020/2021.
Diario delle lezioni:
30 settembre 2019: Definizione di crittosistema ed esempi di cifrari classici (cifrario di Cesare, additivo, a sostituzione, a blocchi affini lineari) e cenni di crittanalisi;
1 ottobre 2019: Intro alla crittografia a chiave pubblica; cenni di complessità computazionale (lunghezza binaria, operazioni bit, complessità computazionale delle 4 operazioni)
7 ottobre 2019: No lezione
8 ottobre 2019: No lezione
14 ottobre 2019: Teorema di Eulero, Piccolo Teorema di Fermat; pseudoprimi di Fermat, gli pseudoprimi di Fermat in una data base sono infiniti; numeri di Carmichael; il gruppo moltiplicativo di un anello Z/nZ con n potenza di un primo dispari è ciclico; caratterizzazione dei numeri di Carmichael (inizio dimostrazione);
15 ottobre 2019: caratterizzazione numeri di Carmichael (fine dimostrazione), uno pseudoprimo di Carmichael è divisibile per almeno tre primi distinti; proprietà della funzione di Carmichael; Teorema di Wilson (dimostrazione elementare e dimostrazione che usa Sylow) e viceversa; definizione di residuo quadratico e di simbolo di Legendre;
21 ottobre 2019: Criterio di Eulero, proprietà elementari del simbolo di Legendre, Lemma di Gauss, enunciato equivalente (per determinare se un numero dispari è residuo quadratico modulo un primo dispari), simbolo di Legendre per determinare se 2 è residuo quadratico modulo un primo dispari, Legge di reciprocità quadratica per il simbolo di Legendre, esempi;
22 ottobre 2019: Legge di Reciprocità quadratica e numeri primi di Fermat; simbolo di Jacobi; proprietà elementari del simbolo di Jacobi; Legge di Reciprocità quadratica per il simbolo di Jacobi, esempi; pseudoprimi di Eulero in base a; per ogni numero dispari positivo composto esiste una base per cui non è pseudoprimo di Eulero.
28 ottobre 2019: altri risultati su pseudoprimi di Eulero; complessità computazionale dell'algoritmo di Euclide, del calcolo del simbolo di Jacobi, elevamento a potenza (modulare); prime considerazioni sull'estrazione di radici quadrate modulo n;
29 ottobre 2019: estrazione radice quadrata modulare; algoritmo probabilistico per trovare residuo non quadratico; test di primalità di Solovay-Strassen; pseudoprimi forti; se un numero è pseudoprimo forte in base a allora è anche pseudoprimo di Eulero in tale base;
4 novembre 2019: uno pseudoprimo di Eulero in base a congruo a 3 mod 4 è uno pseudoprimo forte in tale base; radici primitive modulo n; esistenza di radici primitive modulo p^k e 2p^k (con p primo dispari); struttura del gruppo moltiplicativo di gruppi ciclici di cardinalità potenze di 2; determinazione degli n per cui non esistono di radici primitive modulo n; indici rispetto a radici primitive e residui h-upli; esistenza di soluzioni per equazioni congruenzali di tipo x^h-m modulo n.
5 novembre 2019: n è pseudoprimo forte rispetto a meno di 1/4 delle possibili basi; test di primalità probabilistico di Miller-Rabin e suo costo;
11 novembre 2019: motivazione algoritmo di AKS, analogo polinomiale del Piccolo Teorema di Fermat; esistenza di un r "buono"; enunciato e prima parte della dimostrazione del Teorema di Agrawal-Kayal-Saxena
12 novembre 2019: numeri introspettivi e loro proprietà elementari; numero di monomi di un dato grado; conclusione dimostrazione del Teorema di AKS.
18 novembre 2019: ultimi commenti su dimostrazione del Teorema di AKS; algoritmo per determinare se un numero è una potenza; fattorizzazione di un numero, algoritmo rho di Pollard, metodo di Fermat;
19 novembre 2019: algoritmo (di costo polinomiale) per calcolare la parte intera della radice di un intero; base di fattorizzazione, B-numeri modulo n, B-vettori ridotti modulo n, metodo di fattorizzazione delle basi; metodo p-1 di Pollard;
25 novembre 2019: il problema dello zaino e il protocollo di Merkle-Hellman; scambio di chiavi di Diffie-Hellman; RSA: algoritmo e prime osservazioni;
26 novembre 2019: attacchi elementari all'RSA (utenti con moduli diversi non coprimi, utenti con stesso modulo, punti fissi); definizione di frazione continua finita; un numero è razionale se e solo se ammette uno sviluppo in frazione continua finita; k-esimo convergente; esempi di frazioni continue infinite (sezione aurea, ...);
2 dicembre 2019: proprietà varie dei convergenti di una frazione continua; la definizione di frazione continua infinite come limite di convergenti è ben posta; una frazione continua infinita è un numero irrazionale; enunciato del teorema di Wiener; schema dell'attacco di Wiener e calcolo di un esempio di attacco;
3 dicembre 2019: ogni convergente dello sviluppo in frazione continua di un numero reale approssima il valore del numero meglio di una qualunque altra funzione (ridotta ai minimi termini) il cui denominatore supera quello del convergente; dimostrazione del Teorema di Wiener; accorgimenti per evitare attacco di Wiener;
9 dicembre 2019: firme digitali, idea e definizione di schema di firma digitale, esempi: RSA e DSA; il problema del logaritmo discreto per gruppi finiti; algoritmo di Shanks;
10 dicembre 2019: ripasso nozioni di base su curve piane (affini e proiettive): definizione di curve piane e punti razionali, punti singolari, curve lisce; curve ellittiche, forma canonica di Weierstrass
16 dicembre 2019: legge di gruppo su curva proiettiva cubica non singolare (approccio geometrico assumendo il Teorema di Bézout); commutatività, elemento neutro ed esistenza dell'inverso; se due cubiche proiettive passano per 9 punti ed una terza cubica passa per 8 di questi punti, deve anche passare per il nono (dimostrazione nel casoi punti siano in posizione generale); dimostrazione geometrica dell'associatività della legge di gruppo; caso di curva ellittica su campo di caratteristica diversa da due in forma di canonica di Weierstrass con punto all'infinito come elemento neutro: formula esplicita per l'inverso;
17 dicembre 2019: formula esplicita per la somma di due punti su una curva ellittica (in caratteristica diversa da 2); problema del logaritmo discreto per curve ellittiche, esempio; richiamo algoritmo square and multiply (cioè, raddoppia e somma in notazione additiva); l'operazione di calcolo di un multiplo di un punto ha costo polinomiale; variante con curve ellittiche dello scambio di chiavi di Diffie-Hellmann, variante con curve ellittiche del protocollo di Massey-Omura;
7 gennaio 2020: richiami su curve ellittiche e formule esplicite per la somma dei punti; crittosistema di ElGamal con curive ellittiche; come scegliere una curva ellittica ed un punto su di essa; introduzione al metodo delle curve ellittiche; riduzione modulo n di curve ellittiche; proposizione preliminare all'algoritmo di Lenstra (enunciato e dimostrazione di un'implicazione);
8 gennaio 2020: (Aula D'Antoni, 14:00-16:00): dimostrazione seconda implicazione della Proposizione preliminare al metodo di Lenstra; algoritmo di fattorizzazione di Lenstra; calcolo di un esempio (fattorizzazione di 2773 con curva ellittica Y^2=X^3+4X+4 e P=(1,3));
9 gennaio 2020: (Aula D'Antoni, 14:00-17:00): seminari integrativi degli studenti della LM