Criptosistemi asimmetrici

Introduzione alla crittografia asimmetrica

Il concetto principale che sta dietro alla crittografia asimmetrica è che esistono alcune operazioni che sono estremamente semplici da fare in una direzione, mentre sono estremamente difficili da fare in senso inverso. Per esempio, dati $p$ e $q$ due numeri primi, è semplicissimo calcolare

$n=p\cdot q$

ma è difficilissimo, trovare $p$ e $q$ a partire dal solo $n$. Tutta la sicurezza degli algoritmi di cifratura asimmetrici si basa proprio sul presupposto che, per risolvere certi problemi, gli algoritmi usati sono estremamente inefficienti; se un giorno uno di questi problemi dovesse essere risolto con un nuovo algoritmo efficiente, probabilmente tutta la sicurezza della crittografia che si basa su quel problema verrebbe meno.

Gli algoritmi di cifratura asimmetrici sono ordini di grandezza meno efficienti degli algoritmi simmetrici, il che è un problema fondamentale per il mondo moderno, dove si richiede ad una smartcard come può essere la carta regionale dei servizi di fare firme, usando crittografia asimmetrica.

Schema generale

Abbiamo due figure, Alice e Bob, che vogliono comunicare in maniera segreta, in modo tale che Trudy non sia in grado di interferire tra di loro.

L'idea è che Bob deve scrivere ad Alice e, per far questo, userà una chiave detta chiave pubblica, $k_{pub}$. Alice possiede una coppia di chiavi $<k_{pub},k_{priv}>$, di cui una, $k_{priv}$, deve essere mantenuta segreta.

Quello che accade è che Bob cifra un messaggio con una delle due chiavi di Alice, la chiave pubblica, dopodiché manda il messaggio ad Alice, la quale dovrà usare la sua chiave privata (segreta) per leggere il messaggio di Bob. Chiunque sia in possesso della chiave pubblica sarà anche in grado di mandare messaggi ad Alice, ma se non si ha la chiave privata non si deve essere in grado di ricevere i messaggi destinati ad Alice.

Alice, a sua volta, potrà usare la sua chiave privata per firmare dei messaggi, così chiunque abbia la sua chiave pubblica sarà in grado di verificare che Alice (e soltanto Alice) può aver firmato quel messaggio.

Definiamo $k1$ la chiave pubblica di Alice, $k2$ la chiave privata e l'insieme $<k1,k2>$ il keypair, la coppia di chiavi personale di Alice. Il messaggio in chiaro è $m$, il messaggio cifrato è $c$. L'algoritmo di cifratura asimmetrico è rappresentato da $E_{k1}$, mentre l'algoritmo per decifrare è $D_{k2}$.

Una delle proprietà fondamentali delle chiavi è che deve essere computazionalmente impossibile ricavare la chiave privata a partire dalla chiave pubblica. Uno dei problemi principali che ancora oggi affligge il mondo della crittografia è la distribuzione delle chiavi: in che modo Bob ha la garanzia di possedere la vera chiave pubblica di Alice, e non per esempio la chiave pubblica di Trudy che gliel'ha data facendo finta di essere Alice? infatti, lo scambio delle chiavi avviene nello stesso luogo (internet) in cui avviene lo scambio dei dati.

Come detto, la crittografia asimmetrica si basa su problemi irrisolti della matematica discreta. Si ha:

• Logaritmi discreti $\rightarrow$ Diffie-Hellman, ElGamal e DSS;
• Fattorizzazione discreta $\rightarrow$ RSA;

La crittografia asimmetrica si propone di risolvere tre diversi aspetti della comunicazione tra le persone:

• mantenere la confidenzialità tra due persone; l'algoritmo più usato a tal scopo è RSA. Scopi dei possibili attacchi sono:

• ottenere il messaggio $m$ partendo da $c$ senza conoscere le chiavi;
• ottenere la chiave privata a partire dalla chiave pubblica.

• generare firme digitali; le firme sono utili per l'autenticazione, per la protezione dell'integrità dei dati e per il non ripudio dei messaggi. Per questo scopo si possono usare gli algoritmi RSA, ElGamal e DSS. Lo scopo principale degli attacchi, ovviamente, sarà quello di falsificare le firme.
• derivare delle chiavi effimere da usare per comunicazioni segrete e non recuperabili; per questo obbiettivo si possono usare Diffie-Hellman ed RSA. Scopi degli attacchi possono essere:

• Calcolare le chiavi;
• Inserirsi in mezzo ad una comunicazione, man-in-the-middle.

Ad oggi, nessuno dei problemi su cui si basa la crittografia asimmetrica è mai stato risolto, tuttavia negli ultimi anni una gran quantità di studiosi e di fondi è stata dirottata proprio in questa direzione, dal momento che, con l'avvento dei calcolatori, la crittografia è diventata sempre più importante (quasi essenziale) per la comunicazione tra enti e persone. I risultati di questi sforzi ci sono, come per esempio il test di primalità dei numeri del 2002.

La crittografia è una disciplina molto giovane.

Teoria dei numeri

D'ora in avanti, lavoreremo soltanto con numeri interi in $\mathbb {N}$.

Definizione: Numero primo

Si dice numero primo un numero intero divisibile soltanto per se stesso e per $1$.

Definizione: Massimo comun divisore

Il massimo comun divisore, o greatest common divisor (gcd) è il più grande numero intero positivo che divide entrambi due numeri $x$ e $y$, con resto $0$.

Esempio:

Si ha:

• $gcd(9,21)=3$
• $gcd(24,12)=12$

Per definizione, vale

$gcd(0,x)=x$

Definizione: Numeri coprimi

Una coppia di numeri $x$ e $y$ è coprima se

$gcd(x,y)=1$

Esempio:

I numeri $5$ e $9$ sono coprimi tra loro.

Definizione: Relazione di congruenza

Due numeri $a$ e $b$ sono detti congruenti tra loro in modulo $n$,

$a\equiv b\mod {n}$

quando vale

$a-b=kn$

L'operatore$\mod {n}$ è quella funzione che restituisce il resto della divisione del numero $a$ per il numero $n$, che è il più piccolo numero non negativo $r$ tale per cui

$a=kn+r$

Il valore $r$ è detto resto. Allora, due numero $a$ e $b$ sono congruenti in modulo $n$ se, divisi per $n$, danno lo stesso resto; in questo caso, $a$ e $b$ sono detti equivalenti in modulo $n$.

Esempio:

Si ha:

• $13\mod {10}=3$
• $23\mod {10}=3$

da cui risulta che

$3\equiv _{n}13\equiv _{n}23$

Nota: a volte useremo come notazione $=$ al posto di $\equiv$ per semplicità.

Proprietà: Proprietà dell'operatore modulo

L'operatore modulo gode delle proprietà che ci si aspetta:

• $(a\mod {n})+(b\mod {n})=(a+b)\mod {n}$
• $(a\mod {n})\cdot (b\mod {n})=(a\cdot b)\mod {n}$

Definizione: Moltiplicativo inverso $\mod {n}$

Nelle congruenze, il moltiplicativo inverso $x^{-1}$ del numero $x$ è quel valore tale per cui

$x\cdot x^{-1}=1\mod {n}$

cioè

$x\cdot x^{-1}=kn+1$

Per definizione, l'inverso moltiplicativo di un numero $x$ esiste se, e solo se, esistono due valori $u$ e $v$ tali per cui

$x\cdot u+v\cdot n=1$

In questo caso, $u$ è l'inverso moltiplicativo di $x$. Più avanti vedremo che l'inverso moltiplicativo di $x\mod {n}$ esiste se, e solo se,

$gcd(x,n)=1$

cioè, soltanto quando i due numeri sono primi tra loro.

Teorema:

Si ha

$\gcd(x,y)=gcd(x,y\mod {x})$

Dimostrazione:

L'insieme dei numeri che dividono $(x,y)$ divide anche $x,r)$, dove

$r=y-kx$ (dalla definizione di $y\mod {x}$)

• se un numero $d$ divide sia $x$ che $y$, allora divide anche $r$,

${\frac {y}{d}}=a={\frac {r+kx}{d}}={\frac {r}{d}}+{\frac {kx}{d}}={\frac {r}{d}}+k{\frac {x}{d}}$

• se $d$ divide sia $x$ che $r$, allora divide anche $y$.

Definizione: Algoritmo di Euclide

L'algoritmo di Euclide serve per calcolare il massimo comun divisore di due numeri, applicando ricorsivamente il teorema precedente.

Definizione: Algoritmo di Euclide esteso

Questo algoritmo permette di calcolare

• $gcd(x,y)$
• $x^{-1}\mod {y}$
• $y^{-1}\mod {x}$

Funzionamento:

• $r_{n}=u_{n}\cdot x+v_{n}\cdot y$
• $r_{n}=r_{n-2}-r_{n-1}\cdot q_{n}$
• $u_{n}=u_{n-2}-u_{n-1}\cdot _{n}q$
• $v_{n}=v_{n-2}-v_{n-1}\cdot _{n}q$

Alla fine dell'algoritmo, se si ottiene $r_{n}=1\mod {n}$, allora

• $u_{n}=x^{-1}\mod {y}$
• $v_{n}=y^{-1}\mod {x}$

Definizione: L'insieme $\mathbb {Z} _{n}$

L'insieme $\mathbb {Z} _{n}$ è l'insieme di tutti i numeri $x\mod {n}$.

Per esempio, si ha

• $\mathbb {Z} _{8}=\{0,1,2,3,4,5,6,7\}$
• $\mathbb {Z} _{7}=\{0,1,2,3,4,5,6\}$

Definizione: L'insieme $\mathbb {Z} _{n}*$

L'insieme $\mathbb {Z} _{n}^{*}$ è l'insieme di tutti i numeri $x\mod {n}$ che sono anche primi con $n$.

Ad esempio, si ha:

• $\mathbb {Z} _{8}^{*}=\{1,3,5,7\}$
• $\mathbb {Z} _{7}^{*}=\{1,2,3,4,5,6\}$

È da notare che il numero $0$ non appartiene a $\mathbb {Z} _{n}^{*}$, perché per definizione vale

$gcd(0,n)=n$

quindi $n$ e $0$ non sono coprimi.

Proprietà:

Il gruppo $(\mathbb {Z} _{n}^{*},\cdot )$ è abeliano, cioè:

1. $a\in \mathbb {Z} _{n}^{*}\Leftrightarrow a^{-1}\in \mathbb {Z} _{n}^{*}$, cioè $\mathbb {Z} _{n}^{*}$ contiene anche l'inverso moltiplicativo di $a$ (per definizione);
2. l'operazione associata al gruppo, la moltiplicazione, è sia associativa che commutativa;
3. esiste l'elemento neutro, che è l'$1$: si ha $a\cdot 1=1\cdot a=a\forall a\in \mathbb {Z} _{n}^{*}$;

• l'insieme di definizione è chiuso, cioè $a,b\in \mathbb {Z} _{n}^{*}\Rightarrow a\cdot b\in \mathbb {Z} _{n}^{*}$

Teorema:

Un insieme $\mathbb {Z} _{n}^{*}$ moltiplicato per un elemento di $\mathbb {Z} _{n}^{*}$ stesso è ancora l'insieme di partenza $\mathbb {Z} _{n}^{*}$, soltanto che gli elementi sono stati rimescolati.

Teorema: Teorema del resto cinese

Sia

$N=\prod _{i=1}^{k}n_{i}$

con

$gcd(n_{i},n_{j})=1\forall i\neq j$

cioè, i valori $n_{i}$ e $n_{j}$ sono coprimi tra loro. Allora, la relazione tra $X$ e l'insieme $\{x_{1},x_{2},\cdots x_{k}\}$ con

$X\in \mathbb {Z} _{n}$

e con

$x_{i}=X\mod {}n_{i}\ \forall 1\leq i\leq k$

è una biiezione.

Dimostrazione:

Vogliamo dimostrare che la relazione descritta è una biiezione. La relazione tra $X\mod {N}$ e gli $x_{i}$ è iniettiva per costruzione, dal momento che vale

$x_{i}=X\mod {n_{i}}$

Dobbiamo dimostrare che anche la relazione $\{x_{i}\}\Rightarrow X$ è iniettiva, cioè, partendo dal singolo valore $x_{i}$ si deve poter ottenere il valore di $X$. Si ha

• $N_{i}:={\frac {N}{n_{i}}}$ per definizione;
• $y_{i}:=N_{i}^{-1}\mod {n_{i}}$

1. l'inverso moltiplicativo di $N_{i}\mod {n_{i}}$ deve esistere, dal momento che $N_{i}\in \mathbb {Z} _{n}$ per costruzione;
2. vale

• $N_{i}\cdot y_{i}=1\mod {n_{i}}$
• $N_{i}\cdot y_{i}=0\mod {n_{j}}\ \forall j\neq i$

• $X=\left(\sum _{j=1}^{k}x_{j}\cdot N_{j}\cdot y_{j}\right)\mod {N}$

A questo punto, la dimostrazione è finita se riusciamo a provare che $X$ è definita in modo tale da garantire

$x_{i}=X\mod {n_{i}}\ \forall i$

Questa proprietà deriva da una proprietà appena vista, cioè

• $X\mod {n_{i}}=x_{i}$

Questo teorema può essere formulato anche in altri modi.

• Qualsiasi grande numero $x\mod {N}$ può essere rappresentato da un insieme di numeri più piccoli $\{x_{i}=X\mod {n_{i}}\ \forall 1\leq i\leq k\}$
• La relazione che esiste tra $\mathbb {Z} _{n}$ ed il prodotto cartesiano

$\mathbb {Z} _{n_{1}}\times \mathbb {Z} _{n_{2}}\times \cdots \times \mathbb {Z} _{n_{k}}$

è una biiezione.

Il teorema del resto cinese è molto utile, perché permette di manipolare grandi numeri $X\mod {N}$ semplicemente lavorando su piccoli numeri $x_{i}\mod {n_{i}}$.

Esempio:

Si ha

• $n_{1}=3$
• $n_{2}=5$
• $n_{3}=8$
• $N=n_{1}\cdot n_{2}\cdot n_{3}=120$

Sia $X=19\in \mathbb {Z} _{120}$, da cui si hanno gli $x_{i}=X\mod {n_{i}}$

• $x_{1}=1$
• $x_{2}=4$
• $x_{3}=3$

Si hanno gli $N_{i}=N/n_{i}$,

• $N_{1}=40$
• $N_{2}=24$
• $N_{3}=15$

Si hanno gli $y_{i}=N_{i}^{-1}\mod {n_{i}}$,

• $y_{1}=1$
• $y_{2}=4(-1\mod {5})$
• $y_{3}=7(-1\mod {8})$

Si è ottenuto

$X=\left(\sum _{j=1}^{k}x_{j}N_{j}y_{j}\right)\mod {120}=40+384+315=739\mod {19}$

dove

• $40\mod {3}=1$
• $40\mod {5}=0$
• $40\mod {8}=0$

• $384\mod {3}=0$
• $384\mod {5}=1$
• $384\mod {8}=0$

• $315\mod {3}=0$
• $315\mod {5}=0$
• $315\mod {8}=1$

Definizione: La funzione di Eulero $\Phi$

Si definisce la funzione di Eulero $\Phi$ come quella funzione che, dato un numero $n$, restituisce la cardinalità dell'insieme dei valori inferiori ad $n$ e primi con $n$, cioè

$\Phi (n)=|\mathbb {Z} _{n}^{*}|$

Teorema:

Sia $n$ un numero primo. Allora, vale

$\Phi (n)=n-1$

cioè, per ogni numero $n$ primo, il numero dei numeri minori di $n$ e primi con $n$ è proprio $n-1$, cioè nessun numero inferiore ad $n$ divide $n$ (definizione di numero primo).

Teorema:

Siano $p$ e $q$ due numeri primi, e valga $n=p\cdot q$. Allora vale

$\Phi (n)=\Phi (p)\cdot \Phi (q)=(p-1)\cdot (q-1)$

Dimostrazione:

Si ha

$|\mathbb {Z} _{pq}^{*}|=\{1,3,\cdots ,(pq-1)\}$

I numeri

$\{p,2p,3p,\cdots ,(q-1)p\}(q-1)$

non appartengono all'insieme $|\mathbb {Z} _{pq}^{*}|$, così come anche non vi sono i numeri

$\{q,2q,3q,\cdots ,(p-1)q\}(p-1)$

Allora, si ha

${\begin{aligned}\Phi (n)&=\Phi (pq)\\&=|\mathbb {Z} _{pq}^{*}|\\&=(pq-1)-(q-1)-(p-1)pq-p-q+1\\&=(p-1)(q-1)\\&=\Phi (p)\cdot \Phi (q)\end{aligned}}$

Questo teorema è valido anche se $p$ e $q$ sono semplici coprimi, anziché essere numeri primi.

Teorema: Teorema di Eulero

Dato un qualsiasi numero $x\in \mathbb {Z} _{n}^{*}$, vale

$x^{\Phi (n)}=1\mod {n}$

Dimostrazione:

Sia

$y=\prod _{i=1}^{\Phi (n)}a_{i}\ \forall a_{i}\in \mathbb {Z} _{n}^{*}$

Dal momento che il gruppo $(\mathbb {Z} _{n}^{*},\cdot )$ è un gruppo abeliano, allora esiste l'insieme $I_{i}$ delle permutazioni di $a_{i}$,

$I_{i}=x\cdot a_{i}\ \forall a_{i}\in \mathbb {Z} _{n}^{*}$

Si definisce la grandezza

$J=\prod _{i=1}^{\Phi (n)}I_{i}=x\cdot a_{1}\cdot x\cdot a_{2}\cdots x\cdot a_{\Phi (n)}=x^{\Phi (n)}y$

Si ottiene, quindi, che

$\prod _{i=1}^{\Phi (n)}I_{i}=\prod _{i=1}^{\Phi (n)}a_{i}$

da cui si ottiene

$x^{\Phi (n)}y=y\Rightarrow x^{\Phi (n)}yy^{-1}=yy^{-1}$

Corollario:

Per qualsiasi $x\in \mathbb {Z} _{n}^{*}$, per qualsiasi $k\geq 0$, vale

$x^{k\Phi (n)+1}=x\mod {n}$

Infatti, vale

$x^{k\Phi (n)+1}=\left(x^{\Phi (n)}\right)^{k}x=1^{k}x\mod {n}=x\mod {n}$

Un risultato di tutto questo è l'equazione

$x^{1\mod {\Phi (n)}}=x\mod {n}$

Nel caso in cui valga $n=pq$ con $p$ e $q$ numeri primi, allora per qualunque $x\in \mathbb {Z} _{n}^{*}$ e per qualunque $k\geq 0$ vale

$x^{k\Phi (n)+1}=x\mod {n}$

Esempio:

Siano

• $n_{1}=5$
• $n_{2}=3$
• $n=n_{1}\cdot n_{2}=15$

da cui si ottiene

$\Phi (n)=\Phi (n_{1})\cdot \Phi (n_{2})=\Phi (5)\cdot \Phi (3)=4\cdot 2=8$

Si definisce $e=3$, da cui

$e^{-1}\mod {\Phi (n)}=3$

Si impone $x=6$ e si ottiene

$x^{e}=216$

$x^{ee^{-1}\mod {\Phi (n)}}=10'077'696=6\mod {15}$

Il protocollo Diffie-Hellman

Il protocollo Diffie-Hellman è stato pubblicato nel 1976 a firma di Whitfield Diffie e Martin Hellman, ed è il primo protocollo di cifratura asimmetrica delle storia. A dir la verità, pare che l'United Kingdom communications electronic security group avesse già inventato prima lo stesso meccanismo, ma non pubblicarono i risultati dei loro studi.

L'obbiettivo che si propone il protocollo Diffie-Hellman è quello di impostare una chiave temporanea, detta chiave di sessione K, senza alcun parametro di partenza. L'idea è che si vuole scambiare una chiave, attraverso una rete insicura, senza conoscersi e senza essersi messi d'accordo preventivamente.

L'algoritmo Diffie-Hellman poggia le proprie fondamenta sulla difficoltà con cui si riesce a calcolare un logaritmo discreto; infatti, calcolare il valore

$b=a^{i}\mod {p}$

è facile, ma nessuno è ancora stato in grado di individuare un metodo semplice per ricavare $i$ a partire da $a$, $b$ e $p$.

Ipotizzando che sia Alice a iniziare il protocollo, Alice sceglie

• un numero $p$ primo;
• un numero $g$ che sia generatore dello spazio $|\mathbb {Z} _{p}^{*}|$, cioè

$g^{k}\mod {p}\equiv \mathbb {Z} _{p}^{*}\ \forall 1\leq k\leq (p-1)$

• $Sa$, un numero casuale compreso in $[1,p]$

Una volta scelti questi tre numeri, trasmette

• $p$
• $g$
• $Ta=g^{Sa}\mod {p}$

Bob, ricevuti questi numeri, sceglie a sua volta un numero casuale $Sb\in [1,p]$ e manda ad Alice il numero $Tb=g^{Sb}\mod {p}$. Giunti a questo punto, Alice che Bob saranno in grado di calcolare rispettivamente

• $K=Tb^{Sa}\mod {p}$
• $K=Ta^{Sb}\mod {p}$

Questo tipo di protocollo, di per sé, è in grado di proteggere in maniera efficace uno scambio di chiavi $K$; anche se un attaccante vede passare i numeri $Ta$ e $Tb$, infatti, non riuscirà ad usarli per calcolare il valore giusto della chiave. Questo protocollo, comunque, diventa molto più sicuro se il numero primo $p$ è anche un primo sicuro, cioè se il numero

$q={\frac {p-1}{2}}$

è a sua volta primo.

Il protocollo Diffie-Hellman diventa completamente insicuro se Trudy diventa, da semplice osservatore, un attaccante attivo: se è in grado di diventare man-in-the-middle, Alice e Bob deriveranno delle chiavi (anche diverse) con Trudy invece che tra di loro, senza aver alcuno strumento per accorgersene. Si deduce che il protocollo Diffie-Hellman non può essere usato se non viene affiancato da altri strumenti di autenticazione.

Infine, bisogna considerare il fatto che calcolare $g$ e $p$ è un compito oneroso.

Il protocollo RSA

Il protocollo RSA è il più vecchio protocollo asimmetrico ancora in funzione, inventato nel 1977 pubblicato l'anno successivo. Come per il protocollo Diffie-Hellman, anche questo fu inventato già nel 1973 dall'United Kingdom communications electronic security group, ma venne tenuto segreto.

Gli scopi di questo protocollo sono la confidenzialità dei dati, le firme digitali e la creazione di chiavi effimere per comunicazioni che non devono essere recuperabili, una volta dimenticate le chiavi.

RSA si basa sul teorema di Eulero, dove:

• $p$, $q$ sono numeri primi da più di 512 bit, generati casualmente
• $n=p\cdot q$
• $\Phi (n)=\Phi (p)\Phi (q)=(p-1)(q-1)$
• $e$ è un numero coprimo con $\Phi (n)$
• $d$ è il numero moltiplicativo inverso di $e\mod {\Phi (n)}$, cioè

$d=e^{-1}\mod {\Phi (n)}$

• $K_{priv}=\{d,n\}$ è la chiave privata
• $K_{pub}=\{e,n\}$ è la chiave pubblica

I parametri privati, quindi, saranno $p$, $q$, $\Phi (n)$, $d$ e la chiave privata $K_{priv}$, mentre i parametri pubblici saranno $n$ e $e$, cioè la chiave pubblica $K_{pub}$.

Confidenzialità

Il testo cifrato si ottiene con l'equazione

$c_{i}=m_{i}^{e}\mod {n}$

da cui, attraverso il teorema di Eulero, si può riottenere il messaggio originale facendo

$c_{i}^{d}\mod {n}=m_{i}^{ed}\mod {n}=m_{i}^{1\mod {\Phi (n)}}\mod {n}=m_{i}$

Tutto questo, però, è valido soltanto se il messaggio $m_{i}$ è più piccolo di $n$, da cui si evince che è necessario imporre

$2^{b}<n$

dove $b$ è il numero di bit del blocco del messaggio.

Qui si presenta il fondamentale problema della distribuzione delle chiavi: Alice manda a Bob la sua chiave pubblica, ma come può Bob autenticare la chiave pubblica che ha ricevuto, per esser sicuro che sia davvero la chiave pubblica di Alice? Se la chiave pubblica è sbagliata, Bob cifrerà un messaggio che potrà leggere soltanto Trudy, invece che Alice.

Firma digitale

È lo stesso principio che porta alla confidenzialità, soltanto che è usato al contrario: Alice usa la sua chiave privata per cifrare un testo (che non può essere più lungo di $b$ bit) e tutti coloro che hanno la possibilità di recuperare la sua chiave pubblica saranno in grado di decifrare il testo, con la garanzia che può esser stata soltanto Alice a cifrare tutto. Quello che accade è che si va a firmare il digest del messaggio, calcolato con un qualche algoritmo MDC; in questo caso, Alice manderà a Bob la coppia

$\{m,f(MDC(m))\}$

In questo caso, il messaggio è firmato, ma non viene mandato cifrato. Si noti l'importanza che assume, a questo punto, l'algoritmo MDC: se trovo un altro messaggio $m'$ che abbia lo stesso digest del messaggio originale, potrò affermare che Alice ha firmato il secondo messaggio, oltre al primo.

È importante notare come la firma digitale introduca il concetto di non ripudio del dato: infatti, chi verifica l'autenticità della firma non ha bisogno della chiave privata: si garantisce che soltanto Alice è in possesso dei bit necessari per generare quella particolare firma.

Impostazione di chiavi effimere

Vogliamo generare delle chiavi effimere; sia Alice che Bob hanno, ovviamente, la chiave pubblica di Alice. A questo punto, Bob sceglierà un numero casuale $r$ e manderà ad Alice il valore

$c=r^{e}\mod {n}$

da cui Alice sarà in grado di ricavare

$r=c^{d}\mod {n}$

ma l'osservatore esterno, senza conoscere il valore $d$, non potrà ricavare il valore di $r$ che potrà essere usato, a questo punto, come chiave effimera per cifrare con un qualsiasi algoritmo simmetrico, per esempio DES.

La cifratura delle sessioni viene fatta attraverso chiavi effimere per due motivi fondamentali:

• una volta che entrambi hanno dimenticato $r$, tutta la sessione cifrata, anche se registrata, non sarà recuperabile nemmeno entrando in possesso delle chiavi pubblica e privata.
• la cifratura simmetrica è molto meno impegnativa, dal punto di vista computazionale: i tempi di attesa prima della trasmissione dei dati si accorciano, ed i calcolatori possono essere meno potenti.

Ad oggi, RSA è usato semplicemente per stringhe di bit corte, attorno a 200 bit. Questo perché:

• è estremamente inefficiente dal punto di vista computazionale;
• può essere usato soltanto con le modalità ECB e CBC.

I parametri $p$ e $q$

Perché RSA sia sicuro, $n$ deve essere il più grande possibile. Una dimensione minima di $n$ può essere compresa tra i 512 e i 1024 bit, che significa un numero attorno alle 150 cifre decimali; questo significa che anche $d$ ed $e$ devono essere adeguatamente grandi.

$p$ e $q$ sono dei numeri primi che devono essere sufficientemente grandi, in modo tale da generare un $n$ grande. Il problema è che devono essere due numeri scelti casualmente: l'algoritmo migliore, ad oggi, è:

• scegliere un numero sufficientemente grande;
• verificare se è un numero primo; se no, ricominciare.

Questo meccanismo, che è il migliore, è molto inefficiente: non possiamo far altro che sperare che, prima o poi, il generatore di numeri casuali ci restituisca un numero primo. La probabilità che un numero $x$ sia primo è pari a

$prob=\left(\log _{e}x\right)^{-1}$

il che significa che, se $x$ è di 512 bit, la probabilità che $x$ sia primo è attorno a ${\frac {1}{230}}$, cioè lo $0,4\%$.

Test di primalità

Come detto, $p$ e $q$ devono essere due numeri primi. Per verificarlo, possiamo usare seguente teorema:

Teorema: Piccolo teorema di Fermat

Dato un numero primo $x$, allora è verificato che, per qualsiasi numero $y$, vale

$y^{x-1}=1\mod {x}$

C'è un problema, però: la stessa equazione è verificata, con $x$ di 100 cifre digitali non primo, con probabilità $10^{-13}$: quindi, esiste una probabilità, anche se piccola, che il numero scelto con questo criterio non sia comunque primo. Anche i numeri di Carmichael soddisfano il piccolo teorema di Fermat, senza però essere numeri primi. Esistono altri test di primalità, tutti non deterministici, che permettono di ridurre la probabilità di errore, come il test di Miller-Rabin.

Nel 2002, alcuni ricercatori indiani hanno pubblicato un test deterministico per verificare la primalità dei numeri, ma è di elevata complessità (polinomiale).

La chiave pubblica $e$

Il valore di $e$, di solito, è una costante. Si può scegliere

• $e=3$
• $e=17$
• $e=65537=(2^{16}+1)$

Scegliere un numero piccolo per $e$ porta con sé dei vantaggi:

• la cifratura e la validazione delle firme diventa più performante per numeri grandi;
• $e$ deve essere un numero coprimo con $\Phi (n)=(p-1)(q-1)$; dal momento che già trovare $p$ e $q$ è difficile, è utile avere un numero piccolo per verificare la coprimalità.

Scegliere $e=3$, però, comporta due problemi da tenere presente.

• Se il messaggio da cifrare è

$m<{\sqrt[{3}]{n}}$

allora accadrà che

$c=m^{3}\mod {n}=m^{3}$

quindi, per ritrovare il testo originale basterà calcolare la radice cubica del testo cifrato,

$m={\sqrt[{3}]{m^{3}}}$

Questo fatto è molto comune per il testo, quindi nelle implementazioni di RSA è fondamentale che venga aggiunto, in automatico, del testo di padding in modo tale da rendere il messaggio adatto alla cifratura.

• Supponiamo che Alice mandi lo stesso testo $m$ cifrato con tre chiavi pubbliche diverse, cioè mandi i cifrati $c_{1}$, $c_{2}$ e $c_{3}$. Trudy ha la possibilità di intercettare
• $(m^{3}\mod {n_{1}})$
• $(m^{3}\mod {n_{2}})$
• $(m^{3}\mod {n_{3}})$

che sono i tre messaggi cifrati. Usando il teorema del resto cinese, si può calcolare

$m^{3}\mod {n_{1}n_{2}n_{3}}$

Questo numero sarà esattamente $m^{3}$, se è verificata le ipotesi

• $m<n_{i}\forall i$
• $n_{1}n_{2}n_{3}>m^{3}$

Generare le chiavi pubblica e privata

Cerchiamo un metodo per generare questo paio di chiavi.

1. scegliere $e$, per esempio prendendolo $e=3$;

2. generare un numero dispari $y$ casuale, con dimensione maggiore di 512 bit; si impone poi $x=3y+2$, in modo tale che $x$ sia coprimo con $e$.

3. verificare che $x$ è un numero primo

• controllo che i primi 100 numeri primi non dividano $x$;
• faccio un controllo di primalità non deterministico, oppure deterministico se voglio la sicurezza assoluta della bontà della chiave;
• se il test di primalità fallisce, si torna al secondo punto.

4. si impone $p=x$;

5. si ripetono i punti dal 2. in avanti, in modo da ricavare anche un numero primo $q$;

6. si calcolano i valori derivati da $p$ e $q$,

• $n=pq$
• $\Phi (n)=(p-1)(q-1)$

7. si usa il teorema di Euclide per calcolare il valore $d=e^{-1}\mod {\Phi (n)}$;

8. si etichettano

• $k_{priv}=\{d,n\}$
• $k_{pub}=\{e,n\}$

Attacchi al protocollo

Nonostante esista da circa 30 anni, all'interno di RSA non sono mai stati trovati dei bug importanti,

Calcolo della chiave privata

Il metodo più semplice è la ricerca esaustiva in tutto lo spazio delle $d$. Per risolvere i problemi legati a questo attacco, bisogna scegliere un numero $n$ il più grande possibile; il problema è che, scegliendo $n$ grande, la velocità dell'algoritmo diminuisce.

L'attaccante potrebbe cercare di fattorizzare $n$, ma questo tipo di attacco, ad oggi, è improponibile: con la potenza computazionale moderna, servirebbero migliaia di anni per fattorizzare un numero più grande di 150 cifre decimali. Non è dimostrato, però, che sia necessario fattorizzare $n$ per calcolare il valore corretto di $d$.

Per semplificare, si potrebbe cercare di calcolare $\Phi (n)=\Phi (p)\Phi (q)$, ma è matematicamente dimostrato che la difficoltà computazionale è la stessa che serve per fattorizzare $n$.

Nonostante queste difficoltà, se si prevede di usare una chiave per molto tempo, come accade spesso, conviene portarsi su lunghezze di $n$ di almeno 1024 bit, dal momento che la potenza computazionale aumenta e, come dimostrato dalle recenti tecniche inventate per fattorizzare i numeri, la ricerca è aperta e i risultati, prima o poi, potrebbero arrivare.

Confronto del testo

Una possibile falla nella sicurezza deriva dal messaggio che si sta proteggendo. Se il messaggio $m$ può assumere soltanto pochi valori finito, Trudy potrebbe cifrare le possibili stringhe con la chiave pubblica di Alice e, una volta ottenuto il cifrato, confrontarlo con ciò che transita nel canale. Questo tipo di attacco è possibile con pressoché tutti gli algoritmi, quindi è bene tenerlo sempre in considerazione.

La soluzione più semplice è quella di inserire, in coda al messaggio, un pattern casuale di dati in modo tale da rendere il messaggio più lungo.

Smooth numbers

Gli smooth numbers sono dei numeri prodotto di pochi e piccoli numeri primi. Definiamo la firma RSA di Alice sul messaggio $m_{i}$ come la grandezza

$f_{i}=m_{i}^{d}\mod {n}$

Allora, a partire dalla firma $f_{i}$, Trudy può calcolare la firma di Alice anche sul messaggio $m_{i}^{k}$. Allo stesso modo, con due firme $f_{i}$ e $f_{g}$, Trudy può calcolare le firme dei messaggi

• $m_{i}\cdot m_{g}$
• ${\frac {m_{i}}{m_{g}}}$

e tutti i composti di questi messaggi. Se Trudy riesce a collezionare tutta una serie di firme di Alice che, composte tra di loro con moltiplicazioni e divisioni, danno come risultato un numero primo, allora sarà in grado di calcolare la firma corretta di Alice per qualsiasi numero che abbia quel numero primo come fattore. Ovviamente, al crescere delle osservazioni, Trudy sarà in grado di calcolare un numero sempre maggiore di numeri primi con cui comporre i suoi messaggi.

Se ne deduce che, al crescere delle osservazioni, la sicurezza con cui i messaggi vengono firmati decresce, esponendo sempre di più Alice al rischio di falsificazione della firma. Per prevenire questo problema, il PKCS (l'insieme di standard che riguardano la crittografia asimmetrica) prevede che si aggiungano sempre, in coda ai messaggi, delle stringhe casuali, per prevenire la possibilità che venga firmato uno smooth number.

Osservazioni temporali, o timing attack

Si tratta di un attacco che nessuno si aspetterebbe e che nessuno si aspettava, quando fu standardizzato il protocollo. Si tratta, di fatto, di analizzare quanto tempo ci mette un algoritmo a decifrare una firma. Esiste, infatti, una stretta correlazione tra la chiave privata e la difficoltà computazionale richiesta per cifratura e decifratura: basta osservare quanto tempo serve ad un algoritmo per decifrare un messaggio (con la chiave pubblica) per avere alcune informazioni sulla chiave privata.

Per ovviare a questo problema, le implementazioni commerciali di RSA, ad oggi, inseriscono delle attese casuali nel software, in modo da annullare la correlazione tra la firma ed il tempo necessario per decifrare i messaggi.

Attacco attivo

L'unico attacco attivo che si può pensare è il man-in-the-middle, cioè c'è la possibilità che Trudy si inserisca nelle comunicazioni tra Alice e Bob nel momento dello scambio delle chiavi pubbliche: questo accade perché le chiavi, di per sé, non sono autenticate.

Public Key Cryptograpy Standard

Il PKCS è un insieme di regole standard della RSADSI, la RSA Data Security Inc., su come si devono usare gli algoritmi di cifratura asimmetrici, allo scopo di migliorare la loro sicurezza. Vengono definite le modalità con cui si deve:

• codificare le chiavi pubbliche e private;
• codificare una firma digitale;
• inserire del padding per i messaggi corti;
• cifrare i messaggi.

Lo scopo del PKCS è fornire una serie di regole che massimizzino la sicurezza dell'algoritmo RSA, per minimizzare la probabilità che gli attacchi abbiano successo. La sicurezza dell'algoritmo RSA, che di per sé è ottimo, dipende moltissimo dall'applicazione di queste regole.

Digital Signature Standard

Il DSS è uno standard di cifratura standardizzato dal NIST americano, ed approvato dall'NSA, quindi si presume che possano esistere delle backdoor ignote, esattamente come per l'algoritmo DES.

Il DSS è un protocollo che ha lo scopo di permettere la firma dei documenti; trova le sue fondamenta matematiche su ElGamal, invece che su RSA. Questo tipo di firma digitale, al contrario di RSA, è libera dai brevetti software e, quindi, liberamente utilizzabile in tutto il mondo; al contrario, con RSA, per le aziende che risiedono nelle nazioni che prevedono i brevetti software (come gli USA, ma non l'EU), sarebbe stato necessario acquistare delle licenze. Dal 2000, comunque, il brevetto su RSA è decaduto, quindi si possono usare sia RSA che ElGamal senza dover acquistare licenze di utilizzo.

È dimostrato che, con un calcolatore da 25 milioni di dollari, una firma DSS può essere falsificata in meno di un anno; questo perché la chiave è forzata ad essere di 512 bit, troppo poco. Si tratta, inoltre, di un protocollo molto giovane, quindi molto meno crittanalizzato del suo predecessore RSA.

DSS è stato pensato per le smart card: generare una firma, infatti, è un'operazione che richiede poche risorse; al contrario, la verifica delle firme è più computazionalmente impegnativo.

Elliptic Curve Cryptography

L'algoritmo ECC è un'evoluzione degli algoritmi a chiave asimmetrica.

Gli algoritmi standard, come RSA, DH e DSS, sono basati su una classe di problemi per cui esistono delle soluzioni che prevedono algoritmi di complessità inferiore all'esponenziale; non solo, ma questa complessità, nel tempo, sta scendendo e ci si può aspettare che continui a scendere.

Al contrario, l'algoritmo ECC si basa su problemi le cui soluzioni non prevedono ancora algoritmi con complessità sotto l'esponenziale, quindi ci si può permettere di avere delle chiavi più corte; in particolare, ad oggi, ECC è in grado di fornire la stessa sicurezza di RSA, ma con una chiave 10 volte più piccola.

Utilizzi degli algoritmi asimmetrici

Come già detto per RSA, tutti gli algoritmi asimmetrici possono essere usati soltanto nelle configurazione ECB o CBC, ma non possono essere usati come OFB, CFB o CTR; questo perché i primi due metodi di utilizzo prevedono di usare una funzione diretta $E_{k}$ ed una funzione inversa $D_{k}$, mentre per gli altri tre metodi si utilizza sempre la stessa funzione in senso diretto, quindi sarebbe necessario fornire a tutti la chiave privata del mittente dei messaggi.

In generale, è meglio non usare gli algoritmi asimmetrici per cifrare dati che vadano oltre la dimensione $n$, dal momento che tendono a fornire informazioni utili a Trudy per rompere i protocolli. Infatti, quello che accade di solito è che si usano gli algoritmi asimmetrici per proteggere una chiave simmetrica, eventualmente temporanea, usata per cifrare i dati.

Altri progetti

Altri progetti

Wikipedia

Wikimedia Commons

• Wikipedia contiene informazioni su crittografia asimmetrica
• Wikimedia Commons contiene immagini o altri file su crittografia asimmetrica