Crittografia 2025/26

Docente: Guido Lido email: lido [chiocciola] mat.uniroma2.it

Primo semestre

Orario: mercoledì 9-11, venerdì 14-16

Aula 19 (Sogene)

Modalità d'esame: Esame Orale. Per chi svolge gli esercizi durante il corso, l'esame orale potrà concentrarsi su un seminario concordato col docente e le basi teoriche degli esercizi consegati.

una curva ellittica in natura

⚠️AVVISO⚠️ Mercoledì 5 novembre non ci sarà lezione per sovrapposizione con PQCifris

Testi suggeriti:

D. R. Stinson, M. Paterson Cryptography: Theory and Practice - 4th Edition
D. Boneh, V. Shoup A Graduate Course in Applied Cryptography Scaricabile qui
Per i campi finiti: Anne Canteau Finite fields note scaricabili qui

Esercizi:

Le soluzioni vanno scritte individualmente.

Esercizi sulle prime settimane di cui consegnarne 3 entro il 22 ottobre
Esercizi su campi finiti e attacchi lineari. Consegnarne 2 svolti entro il 14 novembre

Risorse aggiuntive:

Cryptohack Esercizi e sfide di crittografia on-line, by Jack Pope
Hackaton crittografica organizzata dall'associazione De Cifris

Frequenze di caratteri e coppie di caratteri in alcuni testi italiani
Teorema di Eulero, generalizzazione del piccolo Teorema di Fermat
Advanced Encryption Standard descritto dagli autori (contiene le descrizioni matriciali e con matrici circolanti usate a lezione)

Differenza di notazione

un elemento di $\mathbb{F}_{2^8} = \mathbb{F}_{2}[x]/\mu$ noi lo scrivevamo come la classe di un polinomio $a_7x^7+\ldots + a_0$ mentre nella loro notazione lo stesso elemento è identificato con la stringa $a_7 \ldots a_0$ che è rappresentata con due cifre esadecimali
Data Encryption Standard Standard del NIST 1977-2005, su un'idea di Hernst Feistel
Attacco lineare al DES Versione estesa dell'articolo originale di Mitsuru Matsui e articolo di Kukorelly sul Piling-up lemma in media

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/cyphertext); 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 cyphertext, ma nessuna sicurezza contro un known plaintext e sicurezza parziale contro due o più known cyphertext. Definizione del cifraggio di Hill, modulo un numero primo. Caso particolare: cifraggio per permutazione. Il cifragio di Hill ha sicurezza perfetta con un known cyphertext 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.