Un algoritmo crittografico a chiave asimmetrica è RSA (dalle iniziali dei creatori: Rivest, Shamir, Adleman).

Questo algoritmo si basa sulla difficoltà di fattorizzare i numeri molto grandi, anche di 300 cifre (10^300).

In questo sistema crittografico la chiave pubblica è composta da due numeri (pub, n), serve per codificare i messaggi e deve essere resa pubblica. Anche la chiave privata è composta da due numeri (pri, n), serve per decodificare i messaggi e deve essere tenuta segreta.

Supponendo di avere a disposizione le precedenti chiavi, per cifrare un testo in chiaro con RSA si deve usare la seguente funzione:

c = (m^pub)  mod  n

m rappresenta un carattere (o meglio un blocco) del messaggio in chiaro trasformato in forma numerica binaria, mentre c rappresenta la versione codificata. Il simbolo mod è l'operatore modulo e calcola il resto della divisione.

 

Per decodificare il testo cifrato con RSA si deve usare la seguente funzione:

m = (c^pri)  mod  n

 

Il metodo per costruire le chiavi pubbliche e private consiste nello scegliere due numeri primi grandi a, b. A partire da questi si calcola il valore di n e z nel seguente modo:

n = a * b

z = (a - 1) * (b - 1)

Il valore n rappresenta il secondo numero della coppia di chiavi. Il primo numero della chiave privata pri viene scelto in modo tale che non abbia fattori in comune con z.

Il primo numero dalla chiave pubblica pub viene scelto in modo tale che soddisfi la seguente equazione:

(pub * pri)  mod  z = 1

Il seguente esempio mostra come viene costruita una coppia di chiave usando RSA. Si scelgono inizialmente due numeri  primi a=17 e b=5 (i numeri sono piccoli per rendere semplice la spiegazione). A partire da questi valori si ottiene n=85 e z=64. Si sceglie pri = 5 perchè non ha fattori in comune con z e successivamente si sceglie pub in modo tale che (pub * 5) mod 64 = 1. Si ottiene pub=13.

Riassumento la chiave pubblica è (13, 85) mentre la chiave privata è (5, 85).

Utilizzando la precedente chiave pubblica si possono cifrare i messaggi in modo tale che possono essere decifrati soltanto da chi conosce la chiave privata.

Il seguente esempio mostra come cifrare la parola "EUROPA" usando la chiave pubblica (13, 85). L'operazione di codifica considera una lettera per volta m trasformata in forma numerica binaria (A=1,..Z=21) e applica la funzione (m^pub)  mod  n, cioè (m^13)  mod  85.

Testo in chiaro m m^13 (m^13)  mod  85
E 5 1220703125 20
U 19 42052983462257059 49
R 16 4503599627370496 16
O 13 302875106592253

13

P                    14 793714773254144    39                     
A 1 1 1

Il testo cifrato corrisponde alla sequenza di numeri 20,49,16,13,39,1.

Soltanto chi conosce la chiave privata (5,85) può decifrare il messaggio applicando la funzione (c^5) mod  n, dove c rappresenta un carattere cifrato.

Testo cifrato (c) c^5 (c^5) mod 85 Testo in chiaro
20 3200000 5 E
49 282485249 19 U
16 1048576 16 R
13 371293 13 O
39                    90224199  14                 P                   
1 1 1 A