Crittografia asimmetrica e algoritmo RSA. Parte I
3 December 2009 da Francesco
La crittografia asimmetrica, o crittografia a chiave pubblica, e' un particolare tipo di crittografia nel quale vengono utilizzate, al posto della singola chiave privata utilizzata nella crittografia simmetrica, una coppia di chiavi di cui una pubblica (per cifrare il messaggio) ed una privata (per decifrarlo).
Uno dei problemi principali da risolvere quando si utilizza la crittografia simmetrica e' infatti quello dello scambio della chiave: utilizzando la stessa chiave per cifrare e decifrare il messaggio, le parti comunicanti devono in qualche modo entrare in contatto prima di scambiarsi il messaggio proprio per scambiare la chiave con cui, successivamente, operare. In pratica, bisogna trovare un canale sicuro per comunicarsi la chiave, altrimenti esiste sempre il rischio che essa possa essere carpita dall'esterno.
L'idea di base della crittografia a chiave pubblica serve proprio a porre fine a questo inconveniente e a rendere non piu' necessaria una comunicazione preliminare (e sicura) tra le parti per scambiarsi una chiave. In un algoritmo a chiave asimmetrica vengono infatti create due chiavi anziche' una: quella pubblica verra' usata da chi vuole cifrare un messaggio da inviare al possessore di quella chiave, quella privata verra' utilizzata dallo stesso per decifrare il messaggio ricevuto. La chiave pubblica di ognuno viene, insomma, resa disponibile a chiunque voglia inviargli un messaggio, che sara' poi decifrabile solamente usando la chiave privata, tenuta segreta.
Chiaramente le due chiavi devono essere correlate in qualche modo per avere la proprieta' sopra descritta, e cioe' che si possa crittografare un testo con una chiave (quella pubblica) e decriptarlo con un'altra (quella privata) ottenendo lo stesso testo di partenza. In particolare, esistendo questa relazione tra le chiavi bisogna evitare che dalla chiave pubblica, che tutti possono leggere, si possa risalire a quella privata. Bisogna cioe' trovare un modo per generarla che sia facile da percorrere in un verso (cioe' generare la chiave), ma che sia quasi impossibile da percorrere nell'altro, cioe' trovare i dati usati per generarla partendo dalla chiave pubblica (altrimenti, una volta ottenuti i dati, si potrebbe generare la chiave privata ad essa associata).
I primi ad inventare un tale sistema furono W. Diffie e M. Hellman nel 1976, ma fu nel '77 che Rivest, Shamir e Adleman, tutti studenti del MIT, realizzarono uno degli algoritmi a chiave pubblica piu' utilizzato al giorno d'oggi e che prende il nome di RSA. La sicurezza dell'algoritmo RSA si basa sulla difficolta' di fattorizzare in tempi accettabili il prodotto di due grandi numeri primi: infatti, mentre e' facilissimo calcolare il prodotto di questi due numeri, non esiste un algoritmo che possa fattorizzarlo velocemente. Nel resto di questo articolo vedremo a grandi linee come opera l'algoritmo RSA mentre nella seconda parte vedremo un'implementazione in Java.
In linea generale possiamo distinguere tre "fasi" dell'algoritmo: generazione delle chiavi, criptaggio, decriptaggio (si, lo so che suonano malissimo).
Generazione delle chiavi
- Si generano due grandi numeri primi p, q tali che il loro prodotto n = pq ha la lunghezza in bit che desideriamo.
- Si calcola n = pq, e phi = (p-1)(q-1)
- Si sceglie un intero positvo e < phi e coprimo con phi (cioe' MCD(e, phi) = 1)
- Si calcola un intero positivo d < phi tale che ed ≡ 1 (mod phi)
- La coppia (n, e) forma la chiave pubblica, la coppia (n, d) quella privata.
Criptaggio
Per criptare un messaggio si ottiene la chiave pubblica del destinatario e, dopo aver trasformato il messaggio di testo in un numero intero, si utilizza la formula c = me mod n, dove m e' il messaggio.
Decriptaggio
Partendo dal testo criptato si usa la formula m = cd mod n, dove c e' il testo cifrato.
L'unico modo per decriptare un messaggio, come e' evidente dall'algoritmo, e' quello di essere a conoscenza dell'esponente segreto d e del modulo, n. Mentre l'esponente e' segreto, il modulo e' pubblico poiche' e' utilizzato anche per criptare il messaggio: ad ogni modo, per risalire a d, che permetterebbe di accedere al contenuto del messaggio, abbiamo bisogno non di n, ma di p e q, i due grandi numeri primi usati per generarlo. Se i numeri primi sono abbastanza grandi, e' impossibile fattorizzare n in tempi accettabili con gli algoritmi attuali.
In questo articolo non abbiamo visto una prova teorica del funzionamento dell'RSA e cioe' una prova del fatto che criptando un messaggio con la chiave pubblica e decriptandolo con la chiave privata si ottiene sempre di nuovo il messaggio in chiaro, ma potete trovare una dimostrazione (in inglese) a questo link: http://www.di-mgt.com.au/rsa_theory.pdf. Per comprenderla sono necessarie nozioni (non troppo avanzate) di teoria dei numeri.
Pubblicato in Informatica | Commenti (1)
15 August 2011 alle 15:40
[...] vedremo come implementare l’algoritmo RSA di cui si era precedentemente discusso in quest’altro articolo solamente in linea teorica. Il linguaggio di programmazione usato sara’ Java, poiche’ [...]