Vai al contenuto

RSA

La Storia Dietro la Matematica

Nel 1976, Whitfield Diffie e Martin Hellman proposero un'idea rivoluzionaria: e se cifratura e decifratura usassero chiavi diverse? Una chiave potrebbe essere pubblica, mentre solo il proprietario della chiave privata potrebbe decifrare i messaggi. Ma non avevano un sistema concreto.

La sfida fu raccolta da tre ricercatori al MIT: Ron Rivest, Adi Shamir e Leonard Adleman. Dopo mesi di tentativi falliti, Rivest ebbe l'illuminazione una notte dell'aprile 1977. Al mattino aveva un sistema completo. Elencò gli autori in ordine alfabetico: RSA.

L'intuizione chiave: Moltiplicare due numeri primi grandi è banale — un computer lo fa in microsecondi. Ma dato solo il prodotto, trovare i primi originali è straordinariamente difficile. Questa asimmetria tra moltiplicazione (facile) e fattorizzazione (difficile) è il fondamento di RSA.

Rivest, Shamir e Adleman ricevettero il Premio Turing 2002 per il loro contributo.

Perché È Importante

  • HTTPS/TLS — RSA protegge il traffico web, l'online banking e l'e-commerce
  • Firme digitali — Verifica di aggiornamenti software, documenti legali e autenticità email
  • SSH — L'accesso remoto sicuro ai server usa coppie di chiavi RSA
  • PGP/GPG — La cifratura email si basa su RSA

La Formula

Generazione delle Chiavi

  1. Scegli due primi grandi distinti \(p\) e \(q\)
  2. Calcola \(n = pq\)
  3. Calcola \(\phi(n) = (p-1)(q-1)\)
  4. Scegli \(e\) tale che \(1 < e < \phi(n)\) e \(\gcd(e, \phi(n)) = 1\)
  5. Calcola \(d \equiv e^{-1} \pmod{\phi(n)}\)

Chiave pubblica: \((n, e)\). Chiave privata: \((n, d)\).

Cifratura e Decifratura

\[ c \equiv m^e \pmod{n} \qquad \text{(cifratura)} \]
\[ m \equiv c^d \pmod{n} \qquad \text{(decifratura)} \]

Derivazione

Passo 1: Il Teorema di Eulero

Il teorema di Eulero afferma che per ogni intero \(a\) coprimo con \(n\):

\[ a^{\phi(n)} \equiv 1 \pmod{n} \]

dove \(\phi(n)\) è la funzione totiente di Eulero.

Passo 2: Calcolo di \(\phi(n)\) per \(n = pq\)

Per due primi distinti \(p\) e \(q\):

\[ \phi(n) = (p-1)(q-1) \]

Passo 3: Perché la Decifratura Recupera il Messaggio

Abbiamo scelto \(e\) e \(d\) tali che \(ed \equiv 1 \pmod{\phi(n)}\), cioè \(ed = 1 + k\phi(n)\):

\[ c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{1 + k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \cdot 1^k \equiv m \pmod{n} \]

Passo 4: Perché È Sicuro

Per rompere RSA, un attaccante deve fattorizzare \(n\) per trovare \(p\) e \(q\). I migliori algoritmi classici richiedono tempo sub-esponenziale:

\[ O\!\left(\exp\!\left(c \cdot (\ln n)^{1/3} (\ln \ln n)^{2/3}\right)\right) \]

Per una chiave a 2048 bit, questo è computazionalmente impossibile.

Variabili Spiegate

Simbolo Nome Descrizione
\(p, q\) Primi Due numeri primi grandi e distinti (segreti)
\(n\) Modulo \(pq\), parte di entrambe le chiavi
\(\phi(n)\) Totiente di Eulero \((p-1)(q-1)\)
\(e\) Esponente pubblico Tipicamente 65537
\(d\) Esponente privato \(e^{-1} \mod \phi(n)\), segreto
\(m\) Testo in chiaro Il messaggio come intero, \(0 \leq m < n\)
\(c\) Testo cifrato Il messaggio cifrato

Esempio Svolto

Generazione chiavi: \(p = 61\), \(q = 53\).

\[ n = 3233, \quad \phi(n) = 3120, \quad e = 17, \quad d = 2753 \]

Cifratura di \(m = 65\):

\[ c = 65^{17} \mod 3233 = 2790 \]

Decifratura:

\[ m = 2790^{2753} \mod 3233 = 65 \]

Errori Comuni

  • Usare primi piccoli: \(p\) e \(q\) devono essere almeno 1024 bit ciascuno.
  • Riutilizzare primi: Se due moduli RSA condividono un fattore primo, \(\gcd(n_1, n_2)\) rompe entrambi.
  • Cifrare senza padding: RSA grezzo è deterministico. In pratica servono schemi di padding come OAEP.
  • Pensare che RSA sia quantum-safe: L'algoritmo di Shor rompe RSA.

Formule Correlate

Riferimenti

  • Rivest, R. L., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.
  • Diffie, W., & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644–654.