Corso di Informatica 6 (IN450 - Algoritmi per la Crittografia)

Le lezioni

Diario delle lezioni dell'anno accademico 2010-2011

• Introduzione al corso. Modalita' esame, orari, libri di testo. Funzioni one-way. Complessita' degli algoritmi. Classe PTIME e classe EXPTIME. Classe Non-deterministica polinomiale. Funzioni oneway con trapdoor. Crittositemi. Tipologie di cifrari: blocchi, funzioni hash crittografiche, cifrari a flusso.

• Crittosistemi classici: trasposizione, sostituzione, affine, Vigenere, Hill, permutazione. Cifrari a flusso. Generatori di numeri pseudo-casuali. Relazioni di ricorsione lineare.

• Crittoanalisi. Tipologie di attacchi a sistemi di cifratura: plaintext-only, known plaintext, chosen-plaintext, chosen ciphertext. Crittanalisi del cifrario affine. Crittoanalisi del cifrario per sostituzione. Crittoanalisi del cifrario di Vigenere: Kasiski test, indice di coincidenza.

• Crittoanalisi del cifrario di Hill. Crittoanalisi degli stream ciphers. Sicurezza dei sistemi di cifratura. Sicurezza Computazionale. Sicurezza dimostrabile. Sicurezza incondizionata.

• Variabili aleatorie discrete. Probabilita' congiunta. Probabilita' condizionata. Distribuzioni marginali. Teorema di Bayes. Variabili aleatori indipendenti. Segretezza perfetta. Definizione di sistema con PS. Proprieta' della PS per la cifratura per trasposizione. Condizioni generali per sistemi di cifratura con PS. Sistema OTP (one time pad).

• Definizione di entropia di una variabile aleatoria discreta. Entropia della distribuzione congiunta. Prime proprieta' dell'entropia. Codifiche di insiemi finiti. Semigruppo libero delle parole su un alfabeto. Homomorfismo. Estensione della codifica al semigruppo delle parole.Codici prefissi. Codice prefisso ottimale: codice di Huffman.

• Entropia Condizionata. Relazione tra Entropia della Distribuzione congiunta ed entropia condizionata. Relazione tra entropia di plaintext, ciphertext e keyspace. Ridondanza di una lingua.

• Definizione di Cifrario Iterato. Reti di sostituzioni e permutazioni. Cirari a blocchi di tipo Feistel. Cifratura e decifratura. Indipendenza dalla invertibilita' della sostituzione.

• Descrizione del DES. In particolare della funzione di round. Funzione di round del DES. S-Box, analisi dimensionale.

• Crittoanalisi lineare delle S-Box. Definzione di tavola di approssimazione lineare. Ricerca degli sbilanciamenti caratteristici. Attacco su una rete di sostituzione permutazione a partire dagli sbilanciamenti caratteristici delle S-box. Esempio di attacco di tipo known-plaintext, di una S-box di cui siano noti gli sbilanciamenti nella tavola di approssimazione lineare.

• Crittoanalisi differenziale. Tavola dei differenziali caratteristici. Attacco di tipo Known-plaintext pee una SPN di cui siano noti differenziali caratteristici per le S-box.

• Introduzione ai campi finiti. Anello dei Polinomi. Quezientamento rispetto alla riduzione modulo un polinomio irriducibile. Morfismo di Frobenius. Rappresentazione vettoriale e rappresentazione rispetto alla base normale. Somma e prodotto. Relazioni di ricorsione lineare su campi finiti.

• Calcolo della relazione ricorsiva minimale associata ad una sequenza. Algoritmo di Berlekamp-Massey. Esempio di applicazione dell'algoritmo. Prime definizioni di AES.

• Specifica dell'Advanced Encryption Standard. Descrizione della funzione di round: SubBytes, ShiftRows, MixColumns, AddKey. Specifica come operazioni algebriche. Analisi delle loro inverse. Descrizione del keyschedule di AES. Descrizione della cifratura e della decifratura.

• Descrizione algebrica delle funzioni utilizzate nella funzione di round di AES. Descrizione algebrica della funzione per il calcolo del keyschedule di AES.

• Versione algebrica di una funzione computabile, in particolare dell'inversa di una funzione computabile. A prescindere dalla complessita' ogni funzione si puo' descrivere come sistema di polinomi su un campo finito. Esempio della fattorizzazione di interi. Problema generale in crittografia: attacchi algebrici. Esempio di sistema di cifratura a flusso: combinatore di due registri a scorrimento. Calcolo del sistema di equazioni associato.

• Sistemi multivariati. Metodi per la ricerca di soluzioni di sistemi multivariati. Caso di una sola equazione con due incognite. Caso lineare. Caso di due equazioni e due incognite. Esempio di soluzione. Ideale generato da un insieme finito di polinomi. Varieta' associata all'ideale. Ideale associato alla varieta'. Radicale dell'ideale. Ideale monomiale. Relazioni d'ordine tra monomi. Condizione di compatibilita'. Condizione di buon ordine. Ordine lessicografico.

• Definizione di Base di Groebner di un ideale. Teorema di unicita' del resto. Forma normale rispetto ad una base. Algoritmo per il calcolo della forma normale. Utilizzo delle basi di Groebner per il calcolo delle radici di un sistema di equazioni multivariate.

• Soluzione di sistemi multivariati, analisi dei casi: sistema incompatibile, caso di dimensione 0, caso di dimensioni superiori. Algoritmo di Buchberger. Base di Groebner ridotta. Algoritmo di riduzione di una base di Groebner. Esempi di utilizzo nel caso della crittoanalisi algebrica.

• Funzioni di Hash. Integrita' dei dati, applicazioni delle funzioni di hash crittografiche. Sicurezza delle funzioni di hash. Resistenza alle controimmagine, alla seconda controimmagine, alla collisione.

• Modello dell'oracolo: algoritmi randomizzati di tipo Las Vegas. Esempi di utilizzo del random oracle model nel caso delle funzioni di hash. Paradosso del compleanno e resistenza alle collisioni. Confronto tra i diversi criteri di resistenza.

• Funzioni di Hash iterate. Costruzione di Merkle-Damgard. Resistenza alle collisioni della funzione di tipo MD costruita a partire da una funzione di compressione resistente alle collisioni.

• Svolgimento Esercizi Svolgimento di esercizi. Svolgimento di esercizi.