Il funzionamento dell’algoritmo di crittografia RSA
Il passo avanti rispetto al metodo di scambio delle chiavi secondo Diffie-Hellman-Merkle avvenne grazie allo sforzo congiunto di tre ricercatori: Ronald Rivest, Adi Shamir e Leonard Adleman, dalle cui iniziali deriva il metodo noto come RSA.
Il pregio di questo sistema rispetto al metodo Diffie-Hellman-Merkle è che non richiede uno scambio di informazioni tra Alice e Bob per la costruzione della chiave: questo sistema fa infatti uso di due chiavi, una detta “chiave pubblica” e una chiamata “chiave privata” e utilizza un metodo di cifratura asimmetrico.
In un sistema a chiave asimmetrica la chiave usata per cifrare e quella usata per decifrare non coincidono: è possibile quindi che Alice renda pubblica la chiave da usare per cifrare un messaggio (la sua chiave pubblica) e conservi segreta la chiave da usare per decifrare il messaggio (la sua chiave privata), per essere in grado solo lei di decifrare i messaggi a lei diretti.
Il cuore della cifratura asimmetrica sviluppata da Rivest, Shamir e Adlemann è una funzione unidirezionale basata sul concetto di modulo.
Il funzionamento del metodo RSA si può schematizzare con i seguenti punti:
- si scelgono due numeri primi, p e q;
- si calcola il loro prodotto N = p × q , chiamato modulo (datoche tutta l’aritmetica seguente è modulo N);
- si sceglie poi un numero e (chiamato esponente pubblico), più piccolo di N e primo rispetto a f (N ) = (p – 1)× (q – 1), dove f è la funzione di Eulero;
- si calcola il numero d (chiamato esponente privato) tale che e × d –> 1mod((p – 1)× (q – 1)).
La chiave pubblica è rappresentata dalla coppia di numeri (N , e), mentre la chiave privata è rappresentata da (N , d ).
Un messaggio m viene cifrato attraverso l’operazione me mod(N), mentre il messaggio c così ottenuto viene decifrato con cd = me×d = m1mod(N) . Il procedimento funziona solo se la chiave e utilizzata per cifrare e la chiave d utilizzata per decifrare sono legate tra loro dalla relazione e × d –> 1 mod(N ), e quindi quando un messaggio viene cifrato con una delle due chiavi (la chiave pubblica) può essere decifrato solo utilizzando l’altra (la chiave privata).
Per cifrare un messaggio, questo deve essere prima di tutto trasformato in un numero o in una serie di numeri, diciamo m1 , m2 ,…, mk . Questa operazione può essere effettuata utilizzando, ad esempio e per semplicità, il codice ASCII, e trasformando il numero binario ottenuto nel corrispondente in base dieci.
Vediamo dunque in pratica come sia possibile realizzare una cifratura RSA (esempio completo presente nel seguente documento pdf).
Il funzionamento dell’algoritmo di crittografia RSA con ESEMPIO
