In questa pagina si trova materiale relativo al corso di
Crittografia 1
(CR410) per la Laurea e la Laurea Magistrale in Matematica,
Università di Roma Tre.
Avvisi:
Qui trovate l'elenco dei numeri di
matricola degli
studenti che hanno
superato lo scritto di settembre. Fatemi sapere cosa volete fare per
l'orale.
Qui
trovate l'elenco dei numeri di matricola degli studenti che hanno
superato lo scritto del 5/7. Fatemi sapere cosa volete fare per l'orale:
possiamo farlo il 9 o il 10, oppure dopo il 19.
Qui
trovate l'elenco dei numeri di matricola degli studenti che hanno
superato lo scritto del 21/6. L'orale è il 27 alle 10 (aula da
stabilire). Se volete fare l'orale mercoledì, sia che abbiate fatto
lo scritto il 21, sia che abbiate superato gli esoneri, per favore
mandatemi un'email.
Qui
trovate l'elenco dei numeri di matricola degli studenti che hanno
superato gli esoneri: il voto è quello finale complessivo.
Un primo orale è il 13 mattina (alle 9.30 nel mio studio);
oppure
potete fare l'orale dopo lo scritto del 21 (data precisa da decidere
durante lo scritto); oppure potete non fare l'orale secondo le
modalità qui sotto. Per favore fatemi sapere per email cosa volete
fare - in particolare se pensate di venire mercoledì.
Il secondo esonero è il 30 maggio alle 9.30 in aula G.
Il 18 maggio NON c'è lezione.
Vi segnalo il seminario di P. Malacaria
il 18 alle 11.30.
Qui
trovate l'elenco dei numeri di matricola degli studenti che hanno
superato il primo esonero. Se volete vedere il vostro compito
potete venire il 2 maggio in mattinata nel mio studio.
Il 27 aprile NON c'è lezione.
Il primo esonero è il 10 aprile alle 9.30 in aula G.
Vi segnalo il Colloquium
di Dipartimento di Massimiliano Sala l'11 aprile.
Martedì 13/3 NON ci sarà lezione; la prossima settimana le
lezioni saranno il 14 e il 16.
Venerdì 9/3 ci sarà esercitazione.
La didattica è sospesa causa maltempo, quindi la lezione del 27
febbraio non
avrà luogo. La prima lezione del corso si tiene il 28/2 alle 16.00
in aula G.
Venerdì 2/3 ci sarà lezione.
Modalità d'esame.
Qui
trovate il programma del corso.
Qui
trovate la pagina del corso dell'a.a. 2016-17.
Diario delle lezioni
- 28 febbraio:
Introduzione al corso. Definizione di crittosistema.
Cifrari additivi, a sostituzione, a trasposizione. Cenni di crittoanalisi.
Lucidi.
- 2 marzo:
Introduzione alla crittografia a chiave pubblica.
Cenni di complessità computazionale. Notazione O grande.
Lucidi.
- 6 marzo:
Algoritmi polinomiali e esponenziali.
Il problema dello zaino e il crittosistema di Merkle
e Hellman.
Lucidi.
- 7 marzo:
Complessità delle operazioni elementari e dell'algoritmo di
Euclide.
Esponenziazione modulare: square and multiply.
- 9 marzo:
Esercizi.
Alcune soluzioni (da controllare!). Si veda anche il capitolo 2, pp
85-99 del testo 'Aritmetica, Crittografia e Codici' di Baldoni et al.
- 14 marzo:
Il crittosistema RSA.
Lucidi.
- 16 marzo:
Numeri di Fermat, numeri di Mersenne.
Introduzione ai test di primalità. Test di Fermat.
Lucidi.
- 20 marzo:
Residui
quadratici e simbolo di Legendre.
- 21 marzo:
Legge di reciprocità quadratica e applicazioni al calcolo del
simbolo di Legendre e di Jacobi.
- 23 marzo:
Pseudoprimi di Eulero. Test di Solovay-Strassen.
Esercizi.
- 27 marzo:
Esercizi. Pseudoprimi forti.
- 28 marzo:
Test di Miller-Rabin.
Lucidi. La conoscenza
dell'esponente di decifratura porta alla fattorizzazione del modulo.
- 4 aprile: Cenni su frazioni continue e convergenti. Attacco di
Wiener
a RSA con esponente privato piccolo.
- 6 aprile:
Ancora su attacchi a RSA
Lucidi.
Esercizi.
Soluzioni (da controllare!).
- 17 aprile:
Fattorizzazione. Rho di Pollard.
- 18 aprile:
Ancora sull'algoritmo rho di Pollard. Algoritmo p-1 di Pollard.
- 20 aprile:
Basi di fattorizzazione. Dixon's random squares.
- 24 aprile:
Esercizi.
- 2 maggio:
Crittosistema di Rabin.
- 4 maggio:
Cenni sui campi finiti. Lucidi
- 8 maggio:
Il logaritmo discreto. Scambio della chiave di Diffie-Hellman.
Lucidi.
Il gruppo moltiplicativo di un campo finito è ciclico. Radici
primitive e loro ricerca.
- 9 maggio:
Crittosistema di Elgamal. Schemi di firma, schema di firma RSA.
Lucidi.
- 11 maggio:
Esercizi.
- 15 maggio:
Schema di firma Elgamal. Falsificazioni. Firme e funzioni hash.
Lucidi.
- 16 maggio:
Algoritmi per il DL:
algoritmo di Shanks,
algoritmo di Pohlig-Hellman.
- 22 maggio:
Algoritmi per il DL: Index Calculus. Il protocollodel doppio lucchetto e
il CS di Massey-Omura.
Lucidi.
- 23 maggio:
Alcuni protocolli crittografici.
Lucidi.
Cenni sui codici correttori e sul crittosistema di McEliece.
Lucidi
- 25 maggio:
Esercizi.
Soluzioni (da controllare!).
Esercizi
Link
da xkcd.