La crittografia RSA (Rivest-Shamir-Adleman) è uno dei sistemi di crittografia a chiave pubblica più utilizzati. È basata su problemi matematici complessi, come la fattorizzazione di numeri grandi, che la rende sicura per l’uso nella protezione dei dati. Ecco una panoramica dettagliata su come funziona RSA:
1. Generazione delle chiavi
La generazione delle chiavi è la fase iniziale e coinvolge i seguenti passaggi:
- Scelta dei numeri primi: Si scelgono due numeri primi grandi e distinti, ppp e qqq.
- Calcolo di nnn: Si moltiplicano ppp e qqq per ottenere nnn. n=p×qn = p \times qn=p×q
- Calcolo di ϕ(n)\phi(n)ϕ(n): Si calcola la funzione di Eulero di nnn, indicata come ϕ(n)\phi(n)ϕ(n), che è: ϕ(n)=(p−1)×(q−1)\phi(n) = (p-1) \times (q-1)ϕ(n)=(p−1)×(q−1)
- Scelta dell’esponente pubblico eee: Si sceglie un numero intero eee tale che 1<e<ϕ(n)1 < e < \phi(n)1<e<ϕ(n) e che sia coprimo con ϕ(n)\phi(n)ϕ(n) (ossia eee e ϕ(n)\phi(n)ϕ(n) non hanno divisori comuni diversi da 1).
- Calcolo dell’esponente privato ddd: Si calcola l’inverso moltiplicativo di eee modulo ϕ(n)\phi(n)ϕ(n), ovvero ddd deve soddisfare: d×e≡1mod ϕ(n)d \times e \equiv 1 \mod \phi(n)d×e≡1modϕ(n)
2. Chiavi pubbliche e private
- Chiave pubblica: Composta dalla coppia (e,n)(e, n)(e,n).
- Chiave privata: Composta dalla coppia (d,n)(d, n)(d,n).
3. Cifratura
Per cifrare un messaggio mmm (che deve essere un numero inferiore a nnn), si utilizza la chiave pubblica (e,n)(e, n)(e,n) e si esegue la seguente operazione:c=memod nc = m^e \mod nc=memodn
Dove:
- mmm è il messaggio in chiaro.
- ccc è il testo cifrato.
4. Decifratura
Per decifrare il testo cifrato ccc, si utilizza la chiave privata (d,n)(d, n)(d,n) e si esegue la seguente operazione:m=cdmod nm = c^d \mod nm=cdmodn
Dove:
- ccc è il testo cifrato.
- mmm è il messaggio in chiaro originale.
Esempio pratico
Supponiamo di avere i seguenti valori:
- p=61p = 61p=61
- q=53q = 53q=53
- n=p×q=61×53=3233n = p \times q = 61 \times 53 = 3233n=p×q=61×53=3233
- ϕ(n)=(61−1)×(53−1)=3120\phi(n) = (61-1) \times (53-1) = 3120ϕ(n)=(61−1)×(53−1)=3120
- Scegliamo e=17e = 17e=17 (che è coprimo con 3120)
- Calcoliamo ddd come l’inverso di 171717 modulo 3120, che risulta essere d=2753d = 2753d=2753
Le chiavi risultanti sono:
- Chiave pubblica: (e,n)=(17,3233)(e, n) = (17, 3233)(e,n)=(17,3233)
- Chiave privata: (d,n)=(2753,3233)(d, n) = (2753, 3233)(d,n)=(2753,3233)
Cifratura
Supponiamo di voler cifrare il messaggio m=65m = 65m=65:c=6517mod 3233=2790c = 65^{17} \mod 3233 = 2790c=6517mod3233=2790
Il testo cifrato è c=2790c = 2790c=2790.
Decifratura
Per decifrare c=2790c = 2790c=2790:m=27902753mod 3233=65m = 2790^{2753} \mod 3233 = 65m=27902753mod3233=65
Il messaggio originale è m=65m = 65m=65.
Sicurezza
La sicurezza di RSA si basa sulla difficoltà di fattorizzare il prodotto di due numeri primi grandi. Anche se nnn è noto (in quanto parte della chiave pubblica), la fattorizzazione di nnn per ottenere ppp e qqq è computazionalmente impraticabile per numeri sufficientemente grandi. La sicurezza può essere ulteriormente migliorata utilizzando numeri primi molto grandi (ad esempio, di 2048 bit o più).
Utilizzi
RSA è ampiamente utilizzato in:
- Comunicazioni sicure (come SSL/TLS per il web)
- Firma digitale
- Gestione delle chiavi
- Criptografia a chiave pubblica in generale
In sintesi, RSA è un metodo robusto per la crittografia a chiave pubblica, che si basa su solide fondamenta matematiche per garantire la sicurezza delle comunicazioni e dei dati.
