Introduzione
-------------
Ecco come funziona il famoso algoritmo a chiave pubblica RSA; è un algoritmo asimmetrico quindi c'è una chiave che codifica e una che decodifica, il punto di forza di RSA è nella quasi impossibilità pratica di fattorizzare numeri di grandissime dimensioni(c'è una soluzione con computer quantistici, ma delle dimensioni necessarie non esistono ancora).
Le chiavi solitamente hanno una dimensione di 1024 bits, ma può capitare che vengano utilizzare chiavi da 2024 adirittura; il fatto di avere chiavi così grandi in parte spiega il perchè gli algoritmi asimmetrici siano anche 1000 volte più lenti di uno simmetrico(che in media va sui 56 bits, 128 bis, 256 bits e simili), infatti spesso i due sistemi vengono usati in un'accoppiata molti efficente: usando una chiave di sessione(testo codificato simmetricamente, chiave simmetrica dodificata asimmetricamente).

Passiamo ora ad analizzare in particolare l'algoritmo di RSA, vedendo come si creano le chiavi, come si codifica e come si decodifica; premetto che l'articolo sarà essensialmente teorico, se volete un pò di codice nella sezione Java ci sono programmi che usano RSA per codificare file.

Creare la coppia di chiavi, codificare, decodificare
---------------------------------------------------
L'algoritmo per creare la coppia di chiavi è il seguente:

p = numero primo
q = numero primo
n = p*q
f(n) = (p-1)*(q-1)
e = primo rispetto f(n)
d = e ^ -1 mod f(n)
chiave pubblica = {n, e}
chiave privata = {n, d}

La codifica si fa così:

C = M ^ e mod n

La decodifica così:

M = C ^ d mod n

Direi semplice, bisogna tenere conto che per essere efficente i numeri p e q devono essere molto grandi, ma per fare delle prove useremo numeri piccoli.

Prima di passare all'RSA il messaggio deve essere elaborato con un padding che gli da le dimensioni appropriate e convertito in un numero intero, per non andare fuori tema trattando altri algoritmi noi avremo già il valore intero, mettiamo caso che venga fuori 42(42 è il messaggio in chiaro numerico), quindo, per prima cosa generiamo le chiavi:

p = 7
q = 13
n = 7*13 = 91
f(n) = 6 * 12 = 72
e = primo riepstto a f(n) =5
d = 5 ^ -1 mod 72 = 29
chiave pubblica = {91, 5}
chiave privata = {91, 29}

Quindi proviamo a codificare:

M = 42
C = 42 ^ 5 mod 91 = 130691232 mod 91 = 35
C = 35

Quindi sapremo che un intero che rappresenta il cifrato è 35.

Per decifrare si ottiene

C = 35
M = 35 ^ 29 mod 91 = 5.997541836x10^44 mod 91 = 42

Come si può vedere già con i numeri piccoli si ottengono grandi numeri con 54 cifre anche, sicuramente in un linguaggio di programmazione con gli operatori e i tipi di dato tradizionali sarebbe impossibile gestire numeri così grandi, sopratutto quando si fa sul serio con chiavi da 253 cifre e numeri risultanti anche maggiori!!
Per risolvere questo In Java esiste la classe BigInteger C++ c'è il template complex ad esempio e così via.

Disponibile su forum e via email.