Diario delle lezioni:
- 01/10 Introduzione al corso. Necessità di sicurezza: segretezza, autenticità dell'informazione, autenticità del mittente, condivisione... Esempi di protocolli: crittaggio, autenticazione, firma, scambio di chiavi, zero knowledge proof... Crittografia simmetrica VS asimmetrica. (Stinson Paterson Capitolo 1)
Definizione formale di protocollo di crittaggio. Esempio: cifrario di Cesare. Insicuro, non resiste all'attacco di ricerca esaustiva. Esempio: crittaggio per sostituzione (⚠️ a lezione potrei averlo chiamato "permutazione"⚠️). Se il testo (cifrato o in chiaro) è abbastanza lungo, è debole contro analisi delle frequenze e considerazioni linguistiche.
(Stinson Paterson Capitolo 2 da intro a 2.1.2, e 2.2.1, 2.2.2. )
-
03/10 Introduzione di probabilità sullo spazio dei messaggi e delle chiavi. Definizione di sicurezza perfetta e interpretazione euristica. Non-esempio: il cifrario di Cesare e quello per permutazione non hanno sicurezza perfetta. Esempio: Definizione del One-Time-Pad, che ha sicurezza perfetta ma ha chiavi lunghe. Teorema: Se un cifraggio ha sicurezza perfetta, allora l'insieme delle chiavi ha cardinalità maggiore o uguale a quello dei messaggi con probabilità non-nulla. Cifrario di Vigenère. Attachi statistici a Vigenère: cercare la lunghezza della chiave guardando stringhe ripetute oppure guardando la probabilità di uguaglianza; poi analisi delle frequenze. Teorema: se \(X\), \(Y\) sono variabili indipendenti equidistribuite a valori in un insieme finito e \(\sigma\) è una permutazione di tale insieme, allora \(\mathbb P(X=Y) \ge \mathbb P(X= \sigma \circ Y)\). (dimostrazione per esercizio). (Stinson Paterson 2.1.4, 2.2.3, e 3.3. Teorema sugli schemi con sicurezza perfetta in Boneh Shoup 2.1.3)
-
08/10 Spiegazione dettagliata dell'attacco a Vigenère con la probabilità di uguaglianza (per la spiegazione dettagliata fonte solo appunti). Definizione di sicurezza con gioco di attacco: un attaccante deve avere un obbiettivo (calcolare la chiave, decifrare un messaggio, ``guadagnare informazioni'') e una potenza di attacco (known/chosen plaintext/ciphertext); inoltre si suppone che l'attaccante abbia una certa potenza di calcolo e si guarda la probabilità di successo. Il One-Time-Pad ha sicurezza (perfetta) contro un known ciphertext, ma nessuna sicurezza contro un known plaintext e sicurezza parziale contro due o più known ciphertext. Definizione del cifraggio di Hill, modulo un numero primo. Caso particolare: cifraggio per permutazione. Il cifragio di Hill ha sicurezza perfetta con un known ciphertext diverso da zero. Non ha sicurezza contro abbastanza known plaintext. Percentuale che i known plaintext siano indipendenti e conteggio delle basi di \((\mathbb Z/N\mathbb Z)^L\).
(Stinson paterson 2.2 intro, 2.2.3, 2.2.4, 2.1.5)
-
10/10 Cifraggio per permutazione. Calcolo degli inversi modulo un primo. Generalizzazione del cifrario di Hill e di qualche nozione di calcolo matriciale su \(\mathbb Z/N\mathbb Z\) con \(N\) composto.
Dettaglio: Usare matrici di permutazione nel cifrario di Hill equivale al cifraggio per permutazione Stinson Paterson 2.1.6. Il cifraggio per permutazione è un'algoritmo diverso da quello per sostituzione.
Piccolo teorema di Fermat: se \(a,N\) sono interi coprimi e \(N\) è primo, allora \(a^{N-1} \equiv 1 \pmod N\) (la dimostrazione vista è anche su Wikipedia, altrimenti Stinson Paterson Sezione 6.2.6 e Corollary 6.6). Utilizzo del piccolo teorema di Fermat per il calcolo degli inversi (ovvero \(a^{-1} \equiv a^{N-2} \pmod N\)) usando il metodo ``square and multiply'' per elevare all \(N-1\) (si veda Wikipedia o Stinson Paterson Algorithm 6.5). Altro metodo per il calcolo degli inversi: teorema di Bézout e algoritmo euclideo (Stinson Paterson appendice A.2.67).
Cifrario di Hill modulo \(N\) composto: tutto torna, a patto di definire le matrici invertibili come le matrici con determinante coprimo con \(N\). Per dimostrare ciò abbiamo dato la definizione di anello commutativo con identità (ci serve soprattutto l'esempio \(\mathbb Z/N\mathbb Z\) e i campi, si trova una definizione generale in Stinson Paterson appendice A.3) e (ri)-definito il determinante per matrici con entrate in un anello per induzione usando lo svilupppo di Laplace. Teorema (con dimostrazione solo per i matematici): una matrice a coefficienti in un anello commutativo con identità è invertibile se e solo se il suo determinante è invertibile.
(Uso e definizioni in Stinson Paterson 2.1.5, dimostrazione ad hoc)
-
15/10 Cifrari a blocchi: Substitution-permutation networks e inizio di AES.
Dettaglio: Un cifrario a blocchi, da un punto di vista di teoria dell'informazione, corrisponde a una scelta, per ogni chiave \(k\), di una permutazione \(\sigma_k\) dell'insieme dei messaggi. Usare tutte le possibile permutazioni richiede troppa memoria per le chiavi (Boneh-Shoup I.4.1, inizio della sezione). Definizione generale di Substitution-permutation network (Stinson Paterson 4.2) e inizio di spiegazione di AES (Stinson Paterson 4.6 oppure Boneh-Shoup I.4.2.4)
-
17/10 Descrizione completa di AES (Stinson Paterson 4.6, meglio Boneh-Shoup I.4.2.4) senza dare la Key Schedule. Definizione e caratterizzazione dei campi finiti (Stinson Paterson appendice A.4, oppure i primi tre teoremi di queste note, oppure le note di Anne Canteau tra i testi suggeriti).
-
22/10 Campi finiti: Caratteristica di un campo, i campi finiti come estensioni di $\F_p$, definizione di polinomio minimo e esempi (note di Anne Canteau).
Dettaglio: Definizione di caratteristica di un campo. La caratteristica, quando diversa da zero è un primo. Se $K$ è un campo finito allora ha caratteristica prima $p$ e possiamo vedere $\F_p$ come un sottocampo di $K$. Inoltre $K$ è uno spazio vettoriale su $\F_p$ di dimensione finita. Definizione del polinomio minimo $\mu_\beta$ di un elemento $\beta\in K$: tale polinomio è unico ed irriducibile. Ogni elemento $\beta \in K$ determina un embedding $\F_p[x]/\mu_\beta$ in $K$, semplicemente mandando $x \mapsto \beta$, $x^2 \mapsto \beta^2$ e in generale $P(x) \mapsto P(\beta)$. In generale posso vedere un campo $K = \F_p[x]/\mu(x)$ come un'estensione $\F_p[\alpha]$ ottenuta prendendo $\F_p$ e ``aggiungendo/creando/definendo''' un elemento $\alpha$ (nuovo se $\deg \mu \ge 2$) tale che $\mu(\alpha)=0$.
Esempi in $\F_2[x]/x^2+x+1$ e in $\F_{25}:= \F_5[x]/x^2-2$ che ha 25 elementi. Possiamo vedere quest'ultima come estenzione di $\F_5$ a cui aggiungo un elemento che chiamo $\alpha$ che fa le veci di $\sqrt 2$. Enumerazione degli elementi in questi campi e alcuni calcoli di polinomi minimi. Utilizzo per dimostrare che $\F_5[x]/x^2-2$ è isomorfo a $\F_5[x]/x^2-3$.
-
24/10 Campi finiti: automorfismo di Frobenius (note di Anne Canteau). Idea generale degli attacchi lineari (Stinson Paterson sezione 4.3).
Definizione della mappa di Frobenius su un campo di caratteristica $p$, ovvero $\phi\colon a \mapsto a^p$. Questa mappa è lineare, quindi è una mappa di campi. Su un campo finito di ordine $p^n$ è una bigezione (quindi un automorfismo) di ordine $n$ (ovvero la composizione $\phi ^n$ è l'identità e $\phi ^k \neq \mathrm{Id}$ per $k=1, \ldots, n-1$). Se $\alpha$ appartiene a $K$ allora l'insieme $\{\phi^i(\alpha)\}$ è uguale all'insieme dei coniugati di $\alpha$, ovvero le radici del polinomio minimo $\mu_\alpha$.
-
29/10 DES e inizio esempio di attachi lineari.
Descrizione generale delle Feistel Network e di DES in particolare (Stinson Paterson 4.5).
Brute forcing di DES e la contromisura immediata usando Triple DES; double DES non funziona per via dell'attacco ``meet in the middle'' (Boneh-Shoup 4.2.3). Un'esempio di approssimazione lineare di una S-box. (a lezione abbiamo visto un'approssimazione di $S_5$ in DES, preso dalla sezione 4 dell'articolo di Matsui sopra linkato e espresso con un linguaggio a noi familiare; per chi non ha a disposizione appunti della lezione consiglio gli esempi in Stinson Paterson sezione 4.3).
- 31/10 Esempio completo di attachi lineari. (a lezione abbiamo attinto dall'articolo di Matsui sopra linkato; per chi non ha a disposizione appunti della lezione consiglio l'esempio in Stinson Paterson sezione 4.3).
Dall'approssimazione lineare di una S-box a una relazione lineare probabilistica tra gli ouput successivi $X_i, X_{i+1}$ dei vari round. Concatenazione di relazioni lineari probabilistiche. Stima della probabilità della concatenazione con il Piling-up lemma (la stima è euristica ma è supportata dagli esperimenti e genericamente buona per via del risultato di Kukorelly, per chi vuole l'articolo è sopra linkato). Come sfruttare la concatenazione: modo naif, guadagnando un bit di informazione, oppure approssimare $N-1$ round, in modo da ottenere una relazione che dipende da pochi bit della chiave e indovinare quei bit facendo delle prove delle statistiche.
-
5/11 No lezione
-
7/11 Funzioni polinomiali su campi finiti e interpolation attack.
Sia $\F_q$ un campo finito con $q$ elementi e $n$ un interpo positivo. Allora tutte le funzioni $ \F_q^n \to \F_q$ sono polinomiali: data $f$ una tale funzione esiste un'unico $P(x_1, \ldots, x_n) \in \F_q[x_1, \ldots, x_n]$ tale che $f(a_1, \ldots, a_n) = P(a_1, \ldots, a_n)$ per ogni $(a_1, \ldots, a_n)\in \F_q^n$ e tale che il grado di $P$ in ogni variabile $x_i$ soddisfi $\deg_{x_i} P \le q-1 $ (dimostrazione fatta contando tutte le funzioni $\F_q^n \to \F_q$ e i polinomi che hanno quella restrizione sul grado, vedendo che entrambi gli insiemi hanno $q^{q^n}$ elementi e che dati due polinomi distinti con quella restrizione dul grado definiscono funzioni distinte).
Extra: Idea di un interpolation attack ad una versione semplificata di AES, in cui si riesce a scrivere la funzione di encrypion come un quoziente di polinomi di grado basso, dipendenti dalla chiave, e quindi con abbastanza coppie (plaintext, cipertext) si possono ricostruire tali funzioni.
-
12/11 Hash functions (senza chiave).
Definizione di funzione hash resistente alle collisioni hash e motivazione (garantire corretta ricezione di un messaggio pur non garantendo l'identità del mittente). Birthday attack. Accenno alle altre definizioni di sicurezza, ovvero resistenza alla preimmagine e alla seconda preimmagine (In Stinson Paterson 5.1, 5.2 oppure Boneh-Shoup 8.1, 8.3, 8.11). Costruzione di Merkle-Damgard per hash function di messaggi lunghi (Questo è fatto in modoo diverso nei due libri: Boneh-Shoup 8.4 presenta la versione usata in SHA256, il penultimo standard che è anche in uso su internet in TLS; Stinson Paterson 5.3 presenta una costruzione più teorica che funziona con messaggi arbitrariamente lunghi). Accenno alla funzione di compressione usata in SHA256 (Boneh-Shoup 8.5.2)
-
14/11 Autenticazione di messaggi con chiave privata e mode of operation.
Alcuni mode of operation per AES: modalità ECB che è insicura, la modalità CBC che è vulnerabile a un padding-oracle attack e mocalità CTR (counter) che è analoga ad uno stream cipher. Padding-oracle attack al CBC mode (Stinson Paterson 5.7).
Motivazione dell'autenticazione e bitflipping attack contro stream-cipher.
Definizione di Message Authentication Code (MAC) e definizione di sicurezza per un MAC, ovvero resistenza al forgery (Nella parte introduttiva di Stinson Paterson 5.5, ma la definizione di sicurezza è più chiara in Boneh-Shoup 6.1).
Costruzione di MAC a partire da hash function: "Prepend the key" e "append the key" non sono sicuri, mentre Nested-Mac (o two key nest), Envelope Mac sono sicuri sotto opportuni ipotesi. Definizione di HMAC. (Boneh-Shoup 8.7, la sicurezza di Nested MAC in Stinson Paterson 5.5.1)
-
19/11 Gruppi (Stinson Paterson Appendice A.2 fino a A.2.4. Esempi fattibili per esercizi.)
Definizione di gruppo, di sottogruppo, morfismo di gruppi (omomorfismo sul libro). Gruppi ciclici e sottogruppo generato da un elemento. Esempi: Se $R$ è un campo o un anello allora $(R,+)$ è un gruppo. $(R, \cdot)$ non è un gruppo ma lo è $(R^\times , \cdot)$, dove $R^\times = \{ r \in R : \exists s \mbox{ tale che } sr = 1\}$.
L'insieme $S_n$ delle permutazioni, con l'operazione di composizione è un gruppo, che non è commutativo per $n\ge3$.
Per esercizio: i sottogruppi di $\Z/N\Z$ sono tutti e soli $(d\Z /N\Z) = \{(xd \bmod N): x\in \Z\} $ per $d$ che divide $N$; inoltre $d\Z /N\Z$ è ciclico e isomorfo a $\Z/ (\tfrac Nd \Z)$. Esempio di gruppo commutativo non ciclico: $(\Z/8\Z)^\times$.
-
21/11 Diffie-Hellmann e logaritmo discreto. (Stinson Paterson 7.1, 7.2.3, 12.2.)
Scambio di chiavi di Diffie-Hellmann e Crittaggio di El Gamal e definizione di encryption asimmetrico (nello Stinson Paterson El Gamal è enunciato sul gruppo $\F_p^\times$ ma l'idea può essere applicata in qualsiasi gruppo. Inoltre in 12.2 Diffie-Hellmann è presentato anche insieme a considerazioni di sicurezza con attacchi non passivi, che non abbiamo visto) Esempi. Definizione del problema di Diffie-Hellmann e del problema del di logaritmo discreto. Il logaritmo discreto è facile nel gruppo $\Z/N\Z$ additivo. Inizio dell'attacco di Pohlig-Hellmann: caso in cui $g$ ha ordine $q^n$ per $q$ primo piccolo.
-
26/11 Algoritmi per il logaritmo discreto 1 (Stinson Paterson 7.2.1, 7.2.3)
Il Diffie-Hellmann è insicuro se il gruppo ha ordine divisibile per primi piccoli: algoritmo di Pohlig-Hellmann. Dimostrazione effettiva del teorema cinese del resto, utile per Pohlig-Hellmann: dati $a,b$ interi positivi coprimi e $x \in \Z/a\Z$, $y\in \Z/b\Z$, algoritmo per trovare $c$ in $\Z$ che riduca a $x$ modulo $a$ e a $y$ modulo $b$. Algoritmo Baby-Step-Giant-Step (o Shanks) al logaritmo discreto.
-
28/11 Algoritmi per il logaritmo discreto 2 (Stinson Paterson 7.2.2, 7.2.4)
Algoritmo rho di Pollard. Index calculus in $\mathbb{F}_p^\times$.
-
03/12 Curve piane e curve ellittiche. (Per le curve piane valgono gli appunti, oppure inizio del capitolo 3 di "Algebraic Curves" di W. Fulton oppure, per chi conosce il piano proiettivo la sezione 5 delle note di Manetti. Nel primo capitolo di Silverman e in altri testi la lisciezza è definita con una definizione più generale e equivalente. Per le curve ellittiche il libro di Silverman, capitolo III)
Definizione di campo algebricamente chiuso e chiusura algebrica di un campo (Consiglio gli appunti, altrimenti Wikipedia o Sezione V.2 di "Algebra" di S. Lang). Esempi, tra cui una chiusura algebrica di $\F_p$. Definizione di curva piana (affine) su un campo $K$ come equazione polinomiale $F(x,y)=0$. Punti su una curva, eventualmente su una chiusura algebrica $\overline{K}$. Intersezione tra curve e rette, definizione di retta tangente in un punto e di punto liscio di una curva (se possiede una sola retta tangente). Criterio di lisciezza di un punto tramite le derivate parziali e definizione di curva liscia (= tutti i punti su una chiusura algebrica $\overline{K}$ sono lisci). Definizione di curva ellittica: una curva piana liscia definita da un'equazione $y^2 + axy +by = x^3+cx^2+dx+e$. Punti di una curva ellittica: le soluzioni dell'equazione più un punto "all'infinito" aggiunto ad hoc (equivalente a considerare i punti della curva $Y^2Z + aXYZ +bYZ^2 = X^3+cX^2Z+dXZ^2+eZ^3$ nel piano proiettivo, per chi conosce il piano proiettivo). Proposizione: esiste un polinomio $\Delta \in \mathbb{Z}[X_1, \ldots, X_5]$ tale che una curva $y^2 + axy +by = x^3+cx^2+dx+e$ su un qualsiasi campo $K$ è liscia se e solo se $\Delta(a,b,c,d,e)\neq 0$. In particolare $\Delta(0,0,0,A,B) = -16(27B^2+4A^3)$
-
05/12 Curve piane proiettive e legge di gruppo sulle curve ellittiche. (Per le curve proiettive piane valgono gli appunti oppure la sezione 5 delle note di Manetti. Per le curve ellittiche il libro di Silverman, capitolo III)
Definizione (dei punti) del piano proiettivo, $\mathbb P^2(K)$ e delle carte $U_0, U_1, U_2$, in bigezione con il solito $K^2$. Definizione di curva proiettiva tramite polinomi omogenei. Caso particolare: retta in $\P^2$. Definizione di molteplicità di intersezione tra una curva e una retta proiettiva usando il caso affine, ovvero restringendosi a una carta $U_i$. Esercizio: se $C: F(X,Y,Z)=0$ è una curva proiettiva e $r: L(X,Y,Z)=0$ è una retta non contenuta in $C$ (ovvero $L$ non divide $F$), allora $C\cap r$ contiene esattamente $d = \deg (F)$ punti in $\P^2(\ol K)$ contati con molteplicità, dove $\ol K$ è una chiusura algebrica del campo $K$ di partenza.
Definizione di punto all'infinito di una curva ellittica come intersezione con la retta $Z=0$. Definizione della somma su una curva ellittica e prime proprietà: il punto all'infinito è un elemento neutro, ogni punto ammette un inverso. Proposizione senza dimostrazione: la somma è associativa. Esempi di una curva su un campo finito. Formule di addizione per una curva ellittica della forma $y^2=x^3+cx^2+dx+e$. Corollario che vale per qualsiasi curca ellittica: se $P$ e $Q$ sono punti in $E(K)$ anche la loro somma è in $E(K)$, non solamente in $E(\ol K)$.
|