L'algoritmo RSA

RSA (Rivest, Shamir, Adleman, 1977; pubblicato nel 1978) basa la propria sicurezza su due fatti:

• È facile moltiplicare due primi grandi e ottenere un numero $n$;
• È difficilissimo (con i computer attuali, impraticabile per primi di $300$ cifre) fattorizzare $n$ ritrovando $p$ e $q$.

Schema operativo.

1. Alice sceglie due primi $p,q$ grandi e calcola $n=pq$ e $\varphi(n) = (p-1)(q-1)$.
2. Sceglie $e$ coprimo con $\varphi(n)$ (chiave pubblica di codifica).
3. Calcola $d$ tale che $ed\equiv 1\pmod{\varphi(n)}$ (chiave privata di decodifica). $d$ è l’inverso modulare di $e$.
4. Pubblica $(n,e)$. Tiene segreti $d$, $p$, $q$.
5. Bob, per inviare il messaggio $m\in\{0,\ldots,n-1\}$, calcola $c = m^e\bmod n$ e invia $c$.
6. Alice decodifica: $m = c^d\bmod n$, grazie a Eulero $c^d \equiv m^{ed} \equiv m^{1+k\varphi(n)} \equiv m\cdot 1 \equiv m\pmod n$.

Osservazione — Perché funziona in pratica

Tutte le operazioni di codifica/decodifica si fanno in tempo polinomiale ($O(\log^3 n)$ con esponenziazione veloce). L’unico passo che richiederebbe tempo esponenziale è fattorizzare $n$: con primi $p,q$ di $1024$ bit ciascuno ($\approx 300$ cifre decimali) nessun calcolatore conosciuto può farlo in tempi ragionevoli. La sicurezza di RSA poggia su questa asimmetria. Lo scenario cambierà se e quando il calcolo quantistico renderà praticabile l’algoritmo di Shor: è una delle ragioni dello sviluppo della crittografia post-quantistica.

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Crittografia rsa · Funzione di eulero
Competenze: Modellizzare
Persone: Adleman · Rivest · Shamir