Il funzionamento di RSA

L’algoritmo RSA (acronimo dei suoi inventori: Rivest, Shamir e Adleman) è uno dei più noti e utilizzati metodi di crittografia asimmetrica. La sua sicurezza si basa sulla difficoltà di fattorizzare numeri primi molto grandi, un problema matematico complesso da risolvere con i computer tradizionali.

Come funziona RSA: una panoramica

RSA utilizza una coppia di chiavi:

  • Chiave pubblica $(e, n)$: utilizzata per cifrare i messaggi.
  • Chiave privata $( d, n )$: utilizzata per decifrare i messaggi.

Queste chiavi sono legate da una relazione matematica, ma è computazionalmente difficile risalire alla chiave privata conoscendo solo la chiave pubblica.

Il processo di RSA passo passo

1. Generazione delle chiavi

Il primo passo consiste nel generare la coppia di chiavi pubblica e privata. Questo avviene in diverse fasi:

  1. Scegliere due numeri primi grandi, $ p $ e $ q $
    Ad esempio, supponiamo di scegliere: $ p = 61 $ e $ q = 53 $.

  2. Calcolare il prodotto $ n = p \cdot q $
    Questo numero sarà usato come parte della chiave pubblica e privata: $ n = 61 \cdot 53 = 3233 $.

  3. Calcolare $ \phi(n) = (p-1) \cdot (q-1) $
    $ \phi(n) $ è il numero di interi compresi tra 1 e $ n $ che sono coprimi con $n$. Due numeri sono detti coprimi (o relativamente primi) se il loro massimo comune divisore (MCD) è 1. In altre parole, due numeri sono coprimi se non hanno divisori comuni diversi da 1. La funzione di Eulero, indicata come $\phi(n)$, conta quanti numeri interi compresi tra 1 e $n$ sono coprimi con $n$. La funzione $\phi$ è moltiplicativa, il che significa che se $n$ può essere scritto come il prodotto di due numeri coprimi $a$ e $b$, allora $\phi(n) = \phi(a) \cdot \phi(b)$.

    Nel nostro esempio, avendo $p$ e $q$ due numeri primi, il numero di loro divisori non banali è 0 e quindi $\phi(p) = p-1$ e $\phi(q) = q-1$. Di conseguenza: $ \phi(n) = (61-1) \cdot (53-1) = 60 \cdot 52 = 3120 $.

  4. Scegliere un esponente pubblico $ e $
    $ e $ deve essere un numero intero positivo, minore di $ \phi(n) $, e coprimo con $ \phi(n) $. Spesso si sceglie $ e = 65537 $, un numero primo comunemente usato per le sue proprietà matematiche, ma possiamo anche scegliere: $ e = 17 $.

  5. Calcolare l’esponente privato $ d $
    $ d $ è l’inverso moltiplicativo di $ e $ modulo $ \phi(n) $, ovvero: $$ d \cdot e \equiv 1 \ (\text{mod } \phi(n)) $$ Nel nostro esempio, $ d = 2753 $.

Ora abbiamo:

  • Chiave pubblica: ($ e = 17, n = 3233 $)
  • Chiave privata: ($ d = 2753, n = 3233 $)

2. Cifratura

Per cifrare un messaggio, il mittente usa la chiave pubblica del destinatario. Il messaggio (rappresentato come un numero $ m $) viene cifrato con la formula: $$ c = m^e \ (\text{mod } n) $$ Ad esempio, se $ m = 65 $: $$ c = 65^{17} \ (\text{mod } 3233) = 2790 $$ Il messaggio cifrato è $ c = 2790 $.

3. Decifratura

Il destinatario usa la sua chiave privata per decifrare il messaggio. La decifratura avviene con la formula: $$ m = c^d \ (\text{mod } n) $$ Nel nostro esempio: $$ m = 2790^{2753} \ (\text{mod } 3233) = 65 $$ Il destinatario recupera il messaggio originale $ m = 65 $.

Perché RSA è sicuro?

La sicurezza di RSA si basa sul fatto che, conoscendo solo $ n $ ed $ e $, è estremamente difficile calcolare $ d $. Per farlo, sarebbe necessario fattorizzare $ n $ nei suoi fattori primi $ p $ e $ q $, un problema che diventa proibitivo man mano che i numeri $ p $ e $ q $ aumentano di dimensione.

Ad esempio:

  • Con numeri primi di 1024 o 2048 bit, il tempo richiesto per fattorizzare $ n $ con i computer tradizionali è dell’ordine di milioni di anni.

Un esempio pratico semplificato

Supponiamo che Alice voglia inviare a Bob un messaggio segreto utilizzando RSA.

  1. Bob genera la sua coppia di chiavi:

    • Chiave pubblica: ($ e = 7, n = 33 $)
    • Chiave privata: ($ d = 3, n = 33 $).

  2. Alice vuole inviare il messaggio $ m = 4 $. Usa la chiave pubblica di Bob per cifrare: $$ c = 4^7 \ (\text{mod } 33) = 16384 \ (\text{mod } 33) = 31 $$ Alice invia $ c = 31 $.

  3. Bob decifra il messaggio usando la sua chiave privata: $$ m = 31^3 \ (\text{mod } 33) = 29791 \ (\text{mod } 33) = 4 $$ Bob recupera il messaggio originale $ m = 4 $.

Limiti di RSA

  1. Lentezza: RSA è computazionalmente più lento rispetto agli algoritmi simmetrici, quindi viene spesso utilizzato solo per scambiare chiavi simmetriche.
  2. Dimensione dei messaggi: Il messaggio da cifrare deve essere numericamente più piccolo di $ n $. Per messaggi lunghi, è necessario suddividerli in blocchi.
  3. Vulnerabilità al calcolo quantistico: Gli algoritmi quantistici, come Shor, potrebbero in futuro rendere vulnerabile RSA fattorizzando numeri grandi in tempi ridotti.

Conclusione

RSA rappresenta uno dei pilastri della crittografia moderna, utilizzato in numerosi protocolli di sicurezza come HTTPS, firme digitali e email cifrate. Sebbene richieda risorse computazionali significative, il suo impatto ha rivoluzionato la sicurezza informatica, garantendo privacy e autenticità in un mondo sempre più connesso.