di Sergio Mauri

L’algoritmo RSA è un algoritmo crittografico a chiave pubblica utilizzato per la crittografia e la firma digitale. È basato sull’aritmetica modulare e sulla difficoltà del problema di fattorizzazione dei numeri primi. La sua formula si basa sui concetti di esponenziazione modulare e calcolo dell’inverso moltiplicativo.

Ecco le formule principali utilizzate nell’algoritmo RSA:

1. Generazione delle chiavi:
   • Scegliere due numeri primi grandi e distinti p e q.
   • Calcolare il modulo n=p×q.
   • Calcolare la funzione di Eulero di n: ϕ(n)=(p−1)(q−1).
   • Scegliere un esponente pubblico e tale che 1<e<ϕ(n) e e sia coprimo con ϕ(n).
   • Calcolare l’inverso moltiplicativo di e modulo ϕ(n), chiamato esponente privato d, tale che d×e≡1(modϕ(n)).
   • La chiave pubblica è data da (n,e) e la chiave privata da (n,d).
2. Crittografia:
   • Data la chiave pubblica (n,e) e un messaggio M, si calcola il messaggio crittografato C utilizzando l’esponenziazione modulare: C≡M^e(mod n).
3. Decrittografia:
   • Data la chiave privata (n,d) e il messaggio crittografato C, si calcola il messaggio originale M utilizzando l’esponenziazione modulare: M≡C^d(modn).

L’algoritmo RSA si basa sull’assunzione che sia computazionalmente difficile fattorizzare il prodotto di due numeri primi grandi. Pertanto, la sicurezza dell’algoritmo RSA dipende dalla scelta di p e q e dalla lunghezza delle chiavi utilizzate.