Crittografia 2020/2021
Tutti gli studenti sono pregati di registrarsi sul canale Teams del corso
Ricevimento Studenti: data l'emergenza COVID, questo semestre il ricevimento sarà per appuntamento.
Orario Lezioni: Lunedì 17-19 (Aula 5 PP2), Giovedì 10,30-12,30 (Canale Teams)
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) .
Novità corso 2020/2021:
Dopo aver discusso con alcuni di voi, ho deciso che quest'anno il corso sarà arricchito da qualche esercizio ed esempio di codici in Python.
Vi saranno 6 fogli di esercizi facoltativi (alcuni dei quali richiedono l'uso di un computer) che potranno farvi totalizzare fino a 3 punti (da sommare al voto finale dell'esame, se sufficiente).
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:
Quest'anno sarete caldamente incoraggiati a implementare qualche programma in Python, un linguaggio open source (dunque completamente gratuito). Potete scaricare il programma da https://www.python.org/.
Potete trovare online vari editor per Python. Quello che uso io è la versione gratuita ("Community") di PyCharm. Potete scaricarlo da https://www.jetbrains.com/pycharm/download/#section=windows.
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 troverete delle note scritte da me su alcune delle lezioni tenute (aggiornate il 13/11).
Diario delle lezioni:
28 settembre 2020: Definizione di crittosistema ed esempi di cifrari classici (cifrario di Cesare, additivo, a sostituzione, a blocchi affini lineari) e cenni di crittoanalisi;
1 ottobre 2020: crash course in teoria della complessità: lunghezza binaria di un numero, della somma e del prodotto di due numeri, del complemento a 2 bit di un numero; complessità computazionale (definizione e calcolo dell'ordine di grandezza della complessità delle operazioni dell'aritmetica); algoritmi polinomiali ed esponenziali; complessità computazionale dell'algoritmo di Euclide;
5 ottobre 2020: crivello di Eratostene (e sua complessità computazionale), trial division algorithm (e sua complessità computazionale; richiami di Algebra 1: Teorema di Eulero e Piccolo Teorema di Fermat; pseudoprimi di Fermat (definizione, enunciato e dimostrazione del fatto che data una base esistono infiniti pseudoprimi di Fermat in tale base); definizione di pseudoprimi di Carmichael;
8 ottobre 2020: dimostrazione del fatto che il gruppo moltiplicativo degli interi modulo una potenza di un primo dispari è ciclico; caratterizzazione degli pseudoprimi di Carmichael; corollario di tale caratterizzazione: uno pseudoprimo di Carmichael è prodotto di almeno tre primi distinti; definizione della funzione di Carmichael e prime proprietà;
12 ottobre 2020: funzione di Carmichael del prodotto di due numeri coprimi; Teorema di Wilson (due dimostrazioni) e viceversa, costo del test di primalità corrispondente; residui quadratici (definizione, simbolo di Legendre, Criterio di Eulero, prime proprietà del simbolo di Legendre.
15 ottobre 2020: Lemma di Gauss; determinazione deiprimi dispari per i quali 2 è un quadrato (come corollario del Lemmadi Gauss); calcolo del simbolo di Legendre (a|p) per a dispari (tramite funzione tau(a,n)); Legge di Reciprocità Quadratica (enunciato, dimostrazione, esempio di applicazione per il calcolo di un simbolo di Legendre);
19 ottobre 2020: applicazione della Legge di Reciprocità Quadratica nel caso dei primi di Fermat e per la risoluzione del problema inverso; definizione del simbolo di Jacobi; proprietà di base del simbolo di Jacobi; Legge di Reciprocità Quadratica per il simbolo di Jacobi;
22 ottobre 2020: pseudoprimi di Eulero; un numero composto dispari n non è pseudoprimo di Eulero in base ogni numero coprimo con n; le possibili basi rispetto alle quali n è pseudoprimo di Eulero sono al più la metà dei numeri coprimi con n; in base al più la metà degli elementi coprimi con n; test probabilistico di Solovay-Strassen; costo del computo del simbolo di Jacobi;
26 ottobre 2020: costo dell'elevamento a potenza (metodo naif e metodo square and multiply); pseudoprimi forti (+lemma che ne motiva la definizione); osservazione che ogni pseudoprimo di Eulero ed ogni pseudoprimo forte sono pseudoprimi di Fermat (rispetto alla medesima base); ogni pseudoprimo forte è pseudoprimo di Eulero (rispetto alla medesima base); ogni pseudoprimo di Eulero =3 mod 4 è pseudprimo forte (nella medesima base); radici primitive mod n; indice di un numero rispetto a radice primitiva mod n;
29 ottobre 2020: proprietà dell'indice di un numero rispetto ad una radice primitiva mod n, numero di soluzioni distinte mod n di equazioni del tipo x^h=m mod n; Teorema di Rabin (enunciato e dimostrazione);
2 novembre 2020: test di primalità (probabilistico) di Miller-Rabin (pseudocodice e costo computazionale); generalizzazione del Piccolo Teorema di Fermat (condizione necessaria e sufficiente affinché un numero sia primo); lemmi preliminari al Teorema AKS (limitazione inferiore per mcm(1, ..., n); numero di monomi in m variabili e grado <=d; esistenza di un opportuno r la cui ricerca ha costo polinomiale);
5 novembre 2020: numeri introspettivi; enunciato e dimostrazione del teorema di AKS;
9 novembre 2020: algoritmo per determinare se un numero è potenza di un altro numero (con esponente almeno 2); algoritmo di AKS (pseudocodice e costo computazionale); metodo rho di Pollard (idea dell'algoritmo, esempio, probabilità di ripetizioni per funzioni generiche);
11 novembre 2020: versione efficiente dell'algoritmo rho di Pollard, operazioni bit sufficienti a individuare con alta probabilità un fattore non banale di un numero composto; metodo di Fermat (lemma preliminare, algoritmo, esempio); algoritmo polinomiale per la determinazione della parte intera della radice quadrata di un intero; metodo delle basi;
16 novembre 2020: scelta sbagliata di B-numeri; algoritmo del metodo delle basi, costo dell'algoritmo (senza dimostrazione); frazioni continue (definizione, esempi: la sezione aurea, radice quadrata di 2); definizione di quozienti parziali e convergenti; formula per i convergenti: ricorsione per numeratore e denominatore e relativi corollari;
18 novembre 2020:
23 novembre 2020:
25 novembre 2020: Crittosistema di El Gamal, l'algoritmo di Shank per il LD (Baby Steps Giant Steps), attacchi elementari all'RSA
30 novembre 2020:
2 dicembre 2020:
7 dicembre 2020:
9 dicembre 2020:
14 dicembre 2020:
16 dicembre 2020:
21 dicembre 2020:
?? gennaio 2021: eventuali seminari degli studenti della LM