Crittografia asimmetrica (a chiave pubblica): RSA

Chiavi asimmetriche

La crittografia asimmetrica usa due chiavi matematicamente collegate: la chiave pubblica, nota a tutti, cifra; la chiave privata, segreta, decifra.

• Chiave pubblica: chiunque può chiudere il messaggio.
• Chiave privata: solo il proprietario può aprirlo.

Alice scarica la chiave pubblica di Bob, cifra e invia; solo Bob con la sua chiave privata recupera il messaggio. Non serve scambiare segreti e non si può ricavare praticamente la chiave privata da quella pubblica.

RSA

RSA (Rivest, Shamir, Adleman) è il sistema asimmetrico più usato. Si scelgono i primi $p$ e $q$; $n=p \times q$ e $\phi(n)=(p-1)(q-1)$; $e$ è coprimo con $\phi(n)$ e $d$ soddisfa $(e \times d) \pmod{\phi(n)}=1$. Chiave pubblica $(n,e)$, privata $(n,d)$. La sicurezza dipende dalla difficoltà di fattorizzare $n$ nel prodotto dei suoi fattori primi.

Cifratura e decifratura

Cifratura: $C=M^e \pmod n$ Decifratura: $M=C^d \pmod n$ Con $p=3$, $q=11$, $n=33$, $\phi(n)=20$, $e=3$, $d=7$: se $M=2$, $C=2^3 \pmod{33}=8$ e $8^7 \pmod{33}=2$.