Origine (extra)

Chiamato così in onore degli inventori: Rivest, Shamir e Adleman (1978), e pubblicato dopo la sfida del 1976 lanciata da Diffie e Hellman.

La sicurezza dell’RSA si basa sulla difficoltà di fattorizzare numeri grandi.

Caratteristiche principali (extra)

• Le chiavi sono derivate da coppie di numeri primi grandi (con almeno 100 cifre ciascuno).
• È l’algoritmo di crittografia a chiave pubblica più famoso, utilizzato in applicazioni come PGP, PEM e SSL.

Funzionamento

1. Si definisce un numero $n$, composto e determinato dalla moltiplicazione di due numeri primi, noto sia al mittente che al destinatario.
2. Il testo in chiaro viene suddiviso in blocchi di $\lfloor \log_2(n) \rfloor$ bit, ciascuno rappresentante un numero $M$ tale che $M < n$.
3. La cifratura e la decifratura si definiscono come: $C = M^e \mod n$ $M = C^d \mod n = (M^e)^d \mod n = M^{ed} \mod n$

per alcuni valori scelti opportunamente di $e$ e $d$.

Chiavi

• Chiave pubblica: $\text{PU} = (e, n)$
• Chiave privata: $\text{PR} = (d, n)$

Requisiti per il corretto funzionamento dell'RSA

1. Devono esistere valori di $e$, $d$ e $n$ tali che $M^{ed} \mod n = M$ per ogni $M < n$. Matematicamente parlando la funzione dev’essere iniettiva ed ammettere una inversa in modo che l’algoritmo sia deterministico e si possa sempre tornare al testo in chiaro.