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

Le lezioni

Diario delle lezioni dell'anno accademico 2012-2013

• Introduzione al corso di algoritmi per la crittografia. Crittologia: crittografia + crittoanalisi. Modello di Shannon: teoria dell'informazione. Sistemi di cifratura. Permutazioni. Cifratura a chiave simmetrica e cifratura a chiave pubblica. Sistemi di cifratura classici. Shift cipher, substitution cipher, affine cipher, Vigenere cipher, Hill cipher. Crittoanalisi del cifrario di Vigenere.

• Kasiski test. Indice di coincidenza di un testo. Indice di coincidenza di una lingua. Test del Key-Guess rispetto alle frequenze caratteristiche per l'alfabeto. Cifrario per permutazione. Precisazione sul concetto di crittoanalisi. Principio di Kerkhoff.

• Cifrario per trasposizione. Osservazione che il cifrario per trasposizione e' un caso particolare del cifrario di Hill. Cifrari a flusso. LFSR. Periodo massimale di un LFSR. Matrice associata ad un LFSR. LFSR su campi finiti. Crittoanalisi del cifrario affine.

• Tipologie di attacchi. Crittoanalisi del cifrario di Hill. Crittoanalisi del cifrario di Vigenere. Attacchi di tipo statistico. Classificazione della sicurezza di un sistema di cifratura: sicurezza computazionale, sicurezza condizionata, sicurezza incondizionata. Cenni sul linguaggio funzionale utilizzato in matematica. Calcolo delle frequenza caratteristiche della lingua a partire da un corpus di testo. Tavola delle frequenze della lingua italiana. Calcolo dell'indice di coincidenza dell'italiano.

• Richiami di probabilita'. Variabili aleatorie discrete. Probabilita' congiunta, probabilita' condizionata. Teorema di Bayes. Definizione di segretezza perfetta di un crittosistema. Dimostrazione che lo shift cipher ha la proprieta' di segretezza perfetta se la chiave e' scelta con distribuzione uniforme. Teorema di caratterizzazione dei cifrari con segretezza perfetta sotto le ipotesi che gli alfabeti di plaintext, ciphertext e il keyspace abbiano stessa cardinalita'.

• Definizione di Entropia. Prime proprieta' dell'entropia. Variabili aleatorie congiunte e proprieta' dell'entropia. Codifica di Huffman. Decodifica di un codice prefisso. Proprieta' di efficienza della codifica di Huffman. Implementazione di alcune funzioni di cifratura e decifratura (sistemi classici). Calcolo dell'indice di coincidenza di un testo e del suo cifrato. Implementazione di un LFRS.

• Funzioni concave e funzioni convesse. Disuguaglianza di Jensen. Applicazioni alla funzione logaritmo. Dimostrazione sul massimo valore dell'entropia di un dato alfabeto in funzione della cardinalita'. Maggiorazione dell'entropia di una distribuzione congiunta.

• Definizione di entropia condizionata. Maggiorazione dell'entropia condizionata. Entropia del Keyspace condizionato al Ciphertext. Esempio di calcolo dell'entropia di un crittosistema. Entropia di un linguaggio. Ridondanza di un linguaggio. Chiavi spurie e distanza di unicita'. Crittosistemi prodotto. Crittoanalisi di un cifrario a flusso basato su LFSR. Crittoanalisi di un sistema derivato dal cifrario di Hill.

• 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. Definizione di tavola di approssimazione lineare. Ricerca degli sbilanciamenti caratteristici. Implementazione del calcolo della tabella di approssimazione lineare per una funzione di sostituzione. Applicazione alla crittoanalisi lineare (ricerca delle tracce caratteristiche nel caso iterato)

• 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. Calcolo delle caratteristiche differenziali di una S-Box. Ricerca delle caratteristiche componibili.

• Crittoanalisi differenziale di una rete di permutazioni e sostituzioni. Descrizione del DES.

• 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. 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. Sistema di equazioni associato ad una funzione di cifratura. Implementazione delle funzioni di cifratura dell'AES.

• Esempio di Riduzione di AES su un campo finito binaro di grado 3. Esempio di cifratura nel sistema a 3 bit.

• Cube attack, calcolo dei coefficienti del super-polinomio. Cube attack: descrizione della ricerca dei maxterm. Analisi della complessita' del cube attack. Crittoanalisi differenziale (esempio). Crittoanalisi Lineare (esempio).

• Definizione di Hash-family. Proprieta' delle funzioni di hash crittografiche. Algoritmi randomizzati. Random Oracle Model. Prove di sicurezza di funzioni hash nel quadro ROM.

• 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. Calcolo delle caratteristiche differenziali della S-Box (AES-SubBytes) dell'AES. Ricerca delle caratteristiche che possono essere composte su piu' round.

• 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 Esercizi. Calcolo delle caratteristiche della funzione MixColumn. Visualizzazione delle caratteristiche trovate.

• Svolgimento Esercizi. Svolgimento Esercizi.