IN450 - Algoritmi per la Crittografia

Le lezioni si tengono nel I semestre con il seguente orario:

• [-] lunedì ore 9.00-11.00 (lezione, Aula 211/Laboratorio Informatico);
• [-] lunedì ore 14.00-16.00 (esercitazioni, Laboratorio Informatico);
• [-] giovedì ore 14.00-16.00 (lezione, Aula 311/Laboratorio Informatico).

Lezione n. 1 - Monday 22 September 2014

Presentazione del corso. Prime definizioni. Modello di Shannon. Classificazione della cifratura a chiave simmetrica. Funzioni di Codifica come One-Way functions with trapdoor. Classi di complessita` PTIME ed NPTIME. Crittografia a chiave pubblica. Cifrari a flusso. Cifrari a blocchi. Modi Operativi nell`uso dei cifrari a blocchi: ECB (electronic code book), CBC (cipher-block chaining), CTR (counter). Permutazioni. Cifratura a chiave simmetrica e cifratura a chiave pubblica. Sistemi di cifratura classici. Shift cipher, substitution cipher, affine cipher.

Lezione n. 2 - Thursday 25 September 2014

Introduzione alla programmazione funzionale con Wolfram Mathematica. Schema Generale per l'implementazione di schemi di cifratura.

Lezione n. 3 - Monday 29 September 2014

Sistemi di Cifratura Classici. Distinzione tra sistemi Monoalfabetici e Sistemi Polialfabetici. Shift cipher, substitution cipher, affine cipher, Vigenere cipher, Hill cipher. Cifrario per trasposizione. Osservazione che il cifrario per trasposizione e' un caso particolare del cifrario di Hill. Cifrari a flusso. Composizione di Cifrari. La composizione di due cifrari di Vigenere e` ancora un cifrario di Vigenere. Esercizi sull`utilizzo dei modi operativi. Cifrari a flusso.

Lezione n. 4 - Thursday 2 October 2014

lassificazione 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.

Lezione n. 5 - Monday 6 October 2014

Cifrari a flusso. LFSR. Periodo massimale di un LFSR. Matrice associata ad un LFSR. LFSR su campi finiti. Crittoanalisi del cifrario affine. Calcolo dell'indice di coincidenza di un testo e del suo cifrato. Implementazione di un LFRS. Implementazione di alcune funzioni di cifratura e decifratura (sistemi classici).

Lezione n. 6 - Thursday 9 October 2014

Programmazione del calcolo dell'indice di coincidenza. Crittoanalisi del cifrario di Hill. Crittoanalisi del cifrario di Vigenere.

Lezione n. 7 - Monday 13 October 2014

Definizione di Probabilita' Discreta. Variabili Aleatorie Indipendenti. Probabilita' Condizionata. Teorema di Bayes. Introduzione alla Teoria dell'Informazione. Definizione di Sicurezza Perfetta. Teorema di Sicurezza Perfetta per lo Shift Cipher. Definizione di Codice Huffmann. Esercizio su codice Huffmann. Esercizio su probabilita' condizionate per il ciphertext. Esempi di calcolo dell'entropia condizionata. Esercizi sull'analisi di cifrari a flusso basati su LFSR.

Lezione n. 8 - Thursday 16 October 2014

lassificazione 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.

Lezione n. 9 - Monday 20 October 2014

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. 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.

Lezione n. 10 - Thursday 23 October 2014

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.

Lezione n. 11 - Monday 27 October 2014

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) Crittoanalisi Algebrica: metodo di linearizzazione. Matrice di Macaulay. Metodo delle Basi di Groebner. Cube Attack: fase offline e fase online. Cube Attack: definizione di superpolinomio associato ad un termine. Determinazione dei coefficienti del superpolinomio. Test di linearita` del polinomio.

Lezione n. 12 - Thursday 30 October 2014

lassificazione 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.

Lezione n. 13 - Monday 3 November 2014

ore 9.30 esonero in aula B3

Lezione n. 14 - Monday 17 November 2014

Cifrari Iterati. Reti di Sostituzione-Permutazione. Esempio di cifrario SPN. Cifrario di tipo Feistel. Cifrario di Feistel Generalizzato.

Lezione n. 15 - Thursday 20 November 2014

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.

Lezione n. 16 - Monday 24 November 2014

Crittoanalisi Lineare dei cifrari di tipo SPN iterato. Piling-up Lemma. Esempio di crittoanalisi lineare. Implementazione della fase online del Cube Attack Implementaione del calcolo della tabella di approssimazione lineare.

Lezione n. 17 - Thursday 27 November 2014

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

Lezione n. 18 - Monday 1 December 2014

Crittoanalisi Differenziale di cifrari iterati di tipo SPN. Definizione di differenziale di una sostituzione. Calcolo delle Tabelle dei Differenziali. Applicazione dei Differenziali per realizzare un attacco known-plaintext.

Lezione n. 19 - Thursday 4 December 2014

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.

Lezione n. 20 - Thursday 11 December 2014

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.

Lezione n. 21 - Monday 15 December 2014

Descrizione di Advanced Encritption Standard. Confronto sul dimensionamento di Rijndael e AES. Descrizione algebrica delle funzioni: SubBytes, ShiftRows, MixColumns, AddKey. Descrizione algebrica. Addizione, prodotto e Inversione in nel campo finito GF(2^8). Descrizione del KeyScheduler di AES. Descrizione dell'implementazione di AES. Esercitazione sul disegno di AES.

Lezione n. 22 - Thursday 18 December 2014

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.

Lezione n. 23 - Monday 22 December 2014

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. Svolgimento Esercizi. Svolgimento Esercizi.

Lezione n. 24 - Friday 9 January 2015

Seconda prova in itinere