4 RSA

RSA (dai nomi dei tre ricercatori che lo proposero, Rivest, Shamir e Adleman) è probabilmente il più noto algoritmo crittografico asimmetrico, e può essere utilizzato sia per la cifratura che per la firma. I passi preliminari sono i seguenti (per alcune definizioni si veda il paragrafo precedente):

Bob sceglie due numeri primi molto grandi, $p$ e $q$ .
Bob calcola $n=pq$ e $\varphi \left( n\right) =\left( p-1\right) \left( q-1\right)$ (la funzione $\varphi \left( n\right) ,$ detta funzione fi di Eulero, indica il numero di elementi di $\mathbb{Z}_{n}$ primi rispetto a $n$ ).
Bob sceglie un numero $b$ , tale che $0\leq b\leq \varphi \left( n\right)$ , primo rispetto a $\varphi \left( n\right)$ .
Bob calcola $a=b^{-1} \bmod \varphi \left( n\right)$ (ovvero trova quel numero $a$ tale che $ab \equiv 1 \pmod{\varphi \left( n\right)}$ , per come è stato scelto $b$ tale numero esiste ed è unico, e si può calcolare con un algoritmo detto di Euclide).
Bob rende disponibili i valori $n$ e $b$ , che costituiscono la sua chiave pubblica, e tiene segreti i valori $p$ , $q$ e $a$ , che costituiscono la sua chiave privata.

A questo punto l'uso di RSA per la cifratura funziona come segue:

Sia $x$ il testo in chiaro del messaggio che Alice vuole mandare a Bob cifrandolo. Alice calcola $y=x^{b} \bmod n$ e lo manda a Bob.
Bob riceve $y$ da Alice, e può decifrare il messaggio calcolando $x=y^{a} \bmod n$ .

RSA può essere utilizzato per la firma nel modo seguente:

Sia $x$ il testo in chiaro del messaggio che Bob vuole mandare ad Alice firmandolo. Bob calcola la firma come $y=x^{a} \bmod n$ e la manda ad Alice.
Alice riceve $x$ e $y$ da Bob, e verifica che sia $x=y^{b} \bmod n$ . Se è così la firma è autentica, altrimenti è falsa.

La sicurezza di RSA si basa sulla congettura dell'intrattabilità del problema della scomposizione in fattori primi, per cui un intruso, noti $n$ e $b$ , non può calcolare $a$ perché non conosce $p$ e $q$ (e quindi $\varphi \left( n\right)$ ).