RSA è lo schema di cifratura asimmetrica più utilizzato. Esso prende il nome dalle iniziali dei tre crittografi dell’MIT che l’hanno definito nel 1977: Rivest, Shamir e Adleman.
RSA si basa sull’operazione di elevamento a potenza di interi modulo numeri primi, e utilizza interi di grandi dimensioni (le dimensioni di questi interi si misurano in base al numero di bit necessario per codificarli, e attualmente si consigliano almeno 2048 bit). La sicurezza è garantita dal costo di fattorizzazione di numeri grandi.
Siccome RSA opera sui numeri interi (per la precisione sui numeri naturali), il primo passo per cifrare un messaggio è interpretare la sequenza di bit che lo codifica come un numero $M \in \N$. Da qui in poi, tutte le operazioni verranno eseuite su questo intero $M$ (e non su gruppi di bit del messaggio, come invece avveniva negli algoritmi simmetrici).
Per usare RSA si fissa un numero $n\in \N$ grande (ad esempio codificato in 2048 bit), ed è necessario che sia verificata la condizione
$$ 0 < M< n $$
Ciò significa che RSA è un algoritmo di cifratura a blocchi, con la lunghezza del blocco limitata dal valore di $n$. Di conseguenza, anche per RSA esiste un analogo delle modalità di funzionamento degli algoritmi simmetrici (ad esempio OAEP, Optimal Asymmetric Encryption Padding).
Oltre a $n$, la cifratura e la decifratura richiedono altri due parametri, tipicamente chiamati $e$ (da “encryption”, cifratura) e $d$ (da “decryption”, decifratura). Se si vuole garantire la segretezza/confidenzialità, cioè se $A$ vuole mandare a $B$ un messaggio $M$ (qui si considera già l’interpretazione del messaggio come numero intero) in modo che solo $B$ lo possa leggere, allora:
per cifrare il messaggio, $A$ computa
$$ C = M^e \text{ mod } n $$
ottenendo così il testo cifrato $C$, che è anch’esso un numero intero
per decifrare il messaggio, $B$ computa
$$ M = C^d \text{ mod } n $$
Per la segretezza si cifra con la chiave pubblica del ricevente $B$ e si decifra con la chiave privata di $B$, dunque:
i parametri che il mittente $A$ deve conoscere per la cifratura, ovvero $e$ e $n$, costituiscono la chiave pubblica di $B$:
$$ KP_B = \{e, n\} $$
i parametri che servono al ricevente $B$ per la decifratura, cioè $d$ e $n$, costituiscono la chiave privata di $B$:
$$ KR_B = \{d, n\} $$
Si osservi che il parametro $n$ è presente in entrambe le chiavi, dunque l’unica informazione che deve assolutamente rimanere segreta è $d$. invece, la lunghezza delle chiavi è data dal numero di bit necessari per codificare $n$, che come si vedrà più avanti è ciò che determina il costo degli attacchi, e quindi il livello di sicurezza fornito.
E’ anche possobile cifrare con la chiave privata e decifrare con la chiave pubblica.
$$ C = M^d \text{ mod } n \ \ \ \ \ \ M=C^e \text{ mod } n $$
al fine di realizzare l’autenticazione. Detto da un altro punto di vista, le operazioni di cifratura (con $e$) e decifratura (con $d$) sono intercambiabili: se si usano delle lettere che astraggono i significati di plaintext e ciphertext, le formule per la segretezza e per l’autenticazione sono identiche,