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:
- 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).
- 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).
- 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.
