Chiave pubblica e chiave privata nell'algoritmo RSA vengono generate insieme e sono strettamente collegate, perché, come abbiamo ampiamente discusso, servono per le due operazioni opposte di cifratura e decifratura. Il punto è che, pur essendo collegate, deve essere impossibile ricavare una dall'altra, cioè un eventuale assalitore non deve essere in grado di risalire alla chiave privata partendo dalla chiave pubblica.

Diamo qui un breve esempio molto semplificato di come potrebbe funzionare un sistema del genere e del perché è così difficile ricavare una chiave dall'altra. Tutto comincia dalla scelta di due numeri primi (i numeri primi sono quelli che non hanno altri divisori a parte 1 e il numero stesso). Come sarà più chiaro nel seguito i numeri primi hanno un ruolo fondamentale nella generazione delle chiavi di cifratura.

Supponiamo che i due numeri scelti siano:

P = 11        Q =3

Sia N = 11 * 3 = 33 il prodotto di questi due numeri e R = (11-1)*(3-1) = 10*2 = 20 il prodotto dei due numeri diminuiti di una unità.

A questo punto bisogna trovare un terzo numero casuale E di valore inferiore a R, tale che E e R siano primi fra loro (cioè non abbiano divisori in comune a parte l'unità). Il numero più piccolo che ha queste proprietà nel nostro caso è 3. Scegliamo dunque:

E = 3

(di solito nella applicazioni pratiche si sceglie E = 2¹⁶ + 1 = 65537 per ragioni che sarebbe troppo complicato discutere qui; nel nostro esempio abbiamo usato E = 3 per semplificare i calcoli).

Ora dobbiamo trovare un numero D, tale che 1 < D < R (cioè nel nostro caso compreso fra 1 e 20). Questo numero D deve avere la proprietà che la divisione di E*D diviso R deve dare resto 1. Si può dimostrare che esiste un solo numero D che ha queste proprietà.

Nel nostro caso (indicando l'operazione resto con MOD) abbiamo:

E*D mod R = 1 → 3*D mod 20 = 1

Con qualche tentativo si vede che l'unico numero D che soddisfa alla relazione precedente è D = 7. Infatti 7*3 = 21 e 21 diviso 20 produce come resto 1.

A questo punto la chiave pubblica è formata dalla coppia di valori E,N (nel nostro caso: 3,33) e la chiave privata è formata dalla coppia di valori D,N (nel nostro caso: 7,33).

Come si vede le due chiavi, pubblica e privata, condividono il valore di N e tale valore è fondamentale per le operazioni di cifratura e decifratura.

 

Vediamo ora come avviene la cifratura prendendo come esempio un semplicissimo messaggio costituito da un unico numero M = 6. Il valore 6 potrebbe per esempio essere il codice che rappresenta una singola lettera di un messaggio da cifrare. Naturalmente l'esempio è del tutto irrealistico e non ha nessun interesse pratico: serve solo per illustrare il funzionamento del metodo per generare la coppia di chiavi.

Ora per cifrare il nostro messaggio usiamo la chiave pubblica (cioè la coppia 3,33) nel seguente modo (C rappresenta il messaggio cifrato):

C = M^E mod N

ovvero

C = 6³ mod 33 = 216 mod 33 = 18

 

L'operazione di decifratura avviene usando allo stesso modo la chiave privata (cioè la coppia 7,33 nel nostro esempio). Abbiamo dunque

M = C^D mod N = 18⁷ mod 33 = 612220032 mod 33 = 6

 

Chi conosce la chiave pubblica sa i valori di E e di N (nel nostro esempio 3 e 33). Per ricostruire da questa la chiave privata, dal momento che N è noto e comune alle due chiavi, un ipotetico attaccante dovrebbe riuscire a calcolare il valore di D (nel nostro esempio 7 - supponendo, come accade di solito, che il numero E sia fisso e noto).

Per ottenere questo risultato egli potrebbe partire da N che è il prodotto di P e Q, i due numeri usati all'inizio per generare le chiavi. Tuttavia in generale, dato un numero intero, non è semplice scomporlo nei fattori che lo hanno generato, a meno di non voler fare tutte le prove con tutti i numeri.

Per comprendere il problema, si consideri il numero N = 142283. Esso è il prodotto di due numeri primi, ma quali sono questi numeri? L'unico modo per scoprirlo è usare un computer che provi a dividere 142283 per tutti i numeri primi noti. Nel caso di un numero relativamente piccolo come questo, non occorre molto tempo per un moderno computer per scoprire che 142283 = 263 * 541

Se però i due numeri primi P e Q scelti all'inizio sono molto grandi, il compito per un eventuale assalitore si rivela praticamente impossibile.

La fattorizzazione di un numero intero in fattori primi è un altro esempio di quello che i matematici chiamano funzioni unidirezionali o one-way trapdoor function. Come abbiamo già accennato, una one-way trapdoor function è una funzione che è facile da calcolare in una direzione, ma è molto difficile da calcolare nell'altra (nel caso specifico è facile calcolare il prodotto di due primi ma è difficile scomporre il prodotto nei suoi due fattori). Si confronti questo esempio con una normale funzione invertibile, come è per esempio il quadrato di un numero. In questo caso l'operazione inversa è immediata: la radice quadrata.

Si noti che conoscendo uno dei due numeri (P o Q) la fattorizzazione sarebbe semplicissima, poiché basterebbe dividere il prodotto per il numero noto per conoscere l'altro fattore. Se le normali funzioni invertibili assomigliano a delle serrature a chiave singola, che possono essere aperte o chiuse con uguale facilità, le one-way trapdoor function possono essere assimilate a dei lucchetti a scatto: chiuderli è semplice, ma non si riescono ad aprire se non si dispone della relativa chiave.

Se il lettore si sta chiedendo perché i due numeri P e Q devono essere primi, la risposta è che scegliendo due numeri non primi la scomposizione in fattori risulta semplificata, in quanto si trovano dei divisori più piccoli che consentono di ridurre il risultato. Per esempio moltiplicando 500 * 1000 si ottiene un numero abbastanza grande, 500000, ma tale numero è immediatamente divisibile per 10, per 100, per 1000 etc. cioè si riesce molto facilmente a fattorizzare.

 

precedente - successiva

Sito realizzato in base al emplate offerto da

http://www.graphixmania.it

Segui @ElePrograMania