3 Algoritmo RSA 3.1 Descrizione
4. si calcola il numero d tale che e×d = 1 mod φ
3.2 Generazione delle chiavi di cifratura: classe Rsa
Analizziamo, quindi, l’implementazione dell’algoritmo RSA realizzata in questa tesi. Nella versione in linguaggio C++, la classe Rsa è stata creata per la generazione delle chiavi di cifratura pubblica e privata e per la gestione delle operazioni di criptazione e di decriptazione dei dati, secondo le modalità appena descritte. Come vedremo, sono presenti, inoltre, le due funzioni necessarie per la condivisione e per la ricezione della chiave pubblica.
L’interfaccia della classe Rsa e l’implementazione dei suoi metodi sono interamente riportate in appendice, rispettivamente in ClassRsa.hpp e ClassRsa.cpp. Tuttavia, per semplicità di consultazione, ne richiamiamo di seguito la dichiarazione.
14 class Rsa
15 {
16 public:
17 mpz_class N() const { return n;}
18 int SizeOfN() const { return mpz_sizeinbase(n.get_mpz_t(), 10);}
19 mpz_class E() const { return e;}
20 mpz_class D() const { return d;}
21 void GenerateEncryptionKeys();
22 bool SendPublicKey(int socket, string ipAddress, int udpPort);
23 bool ReceivePublicKey(int socket);
24 void RsaEncrypt(string& toEncryptStr);
25 string RsaDecrypt(const char* toDecrypt);
26
27 private:
28 mpz_class p, q, phi;
29 mpz_class n, e, d; //keys
30 mpz_class ComputeGCD(const mpz_class& x, const mpz_class& y);
31 mpz_class GetRandomE();
32 void GeneratePQandComputeNPhi();
33 mpz_class GeneratePrimeNumber(string name, unsigned numBits);
34 void FindE();
35 void ComputeD();
36 int rdtsc();
37 };
Innanzitutto notiamo che, come già visto per la classe Dh, le variabili dell’algoritmo (ovvero p, q e phi) e le chiavi di cifratura (costituite da n, e e d) sono di tipo
mpz_class e sono inserite nella parte privata della classe. Questo garantisce una
maggior sicurezza poiché le chiavi non sono direttamente accessibili a chi usa la classe e, quindi, possono essere generate e modificate solo dalle funzioni della classe stessa. In particolare, la chiave pubblica e quella privata vengono create dalla funzione GenerateEncryptionKeys() (linea 21). Quest’ultima, come si evince dal codice (linee 131, 132 e 133 in appendice), sfrutta i metodi privati della classe Rsa per impostare i valori delle variabili dell’algoritmo e ottenere, infine, le chiavi crittografiche.
Il dettaglio delle funzioni di classe chiamate all’interno di GenerateEncryptionKeys() è riportato nella figura sottostante.
Come indicato in figura 3.1, la prima funzione che viene chiamata in
GenerateEncryptionKeys() è GeneratePQandComputeNPhi(). L’algoritmo RSA,
infatti, ha inizio con la generazione di due numeri primi elevati p e q e con il calcolo di n e φ (nel codice quest’ultima variabile è stata indicata con phi).
Questo è esattamente il compito svolto da GeneratePQandComputeNPhi() che, come si può notare nel codice (linee 22, 23, 26 e 27 in appendice), utilizza la funzione
GeneratePrimeNumber() per generare i due numeri primi casuali p e q e, infine,
calcola n = p×q e phi = (p – 1) × (q – 1). La funzione GeneratePrimeNumber() è la stessa utilizzata nella classe Dh; si rimanda, quindi, al punto 2.2 del capitolo 2 per maggiori dettagli.
Da notare, invece, come la dimensione scelta per p e q sia di 512 bit. In questo modo
n sarà un numero intero di circa 308 cifre decimali tale, quindi, da garantire la
sicurezza dell’algoritmo: la condizione di 200 cifre decimali indicata nell’articolo [7] risulta, infatti, ampiamente soddisfatta.
A questo punto viene chiamata la funzione FindE() per calcolare il numero intero e che costituisce, in coppia con n, la chiave pubblica e che, come visto in precedenza, deve essere coprimo e minore di phi. La funzione FindE(), quindi, trova il numero e nel seguente modo. Innanzitutto viene chiamata la funzione GetRandomE() (linea 64
GenerateEncryptionKeys() 2) FindE() 3) ComputeD() GeneratePrimeNumber() GetRandomE() ComputeGCD() 1) GeneratePQandComputeNPhi()
in appendice) che assegna ad e un numero intero casuale compreso tra il max(p, q) e
(phi – 1). Dopodiché, come si può notare nel codice (linee 65÷72 in appendice),
viene calcolato il massimo comun divisore fra e e phi tramite la funzione
ComputeGCD() che implementa l’algoritmo di Euclide:
• se è pari ad 1, i due numeri sono coprimi e quindi e è corretto.
• se è diverso da 1, allora i due numeri non sono coprimi. Si diminuisce e di 1 e si ricalcola il massimo comun divisore fino ad ottenere un valore corretto per
e. Se quest’ultimo dovesse diventare pari a p o a q, allora il ciclo si
ripeterebbe ricominciando dalla chiamata a GetRandomE().
La funzione FindE() converge molto rapidamente ad un valore corretto per il numero
e, cioè tale per cui 1 < e < phi ed è coprimo con phi. Inoltre, e viene individuato
all’interno di un insieme molto ampio poiché il max(p, q) e (phi – 1) differiscono di molti ordini di grandezza. Ciò significa che la sicurezza dell’algoritmo RSA è garantita.
A questo punto viene chiamata la funzione ComputeD() per calcolare il numero d e ottenere, quindi, la chiave privata costituita dalla coppia (d, n). Come detto in precedenza, d deve essere calcolato in modo tale che e×d = 1 mod φ ovvero d è l’inverso moltiplicativo di e. La funzione ComputeD() sfrutta, quindi, l’algoritmo di Euclide esteso per determinare d; senza entrare nei dettagli matematici, utilizziamo l’implementazione ripotata nel sito [9] ma opportunamente modificata per poter lavorare con numeri interi molto grandi, ovvero con dati di tipo mpz_class. Trovato
d, la funzione GenerateEncryptionKeys() giunge al termine. Sono state generate,
quindi, entrambe le chiavi di cifratura: la chiave pubblica (n, e) e quella privata (n, d).
Tuttavia, per poterle utilizzare nella cifratura di una comunicazione che avviene tra due parti, è necessario condividere la chiave pubblica. Per questo motivo la classe Rsa comprende le due funzioni SendPublicKey() e ReceivePublicKey() che possono essere usate rispettivamente per inviare e ricevere la chiave pubblica. Come si vede
dal codice (linee 142÷147 in appendice), la prima non fa altro che convertire n ed e
in due stringhe che poi vengono inviate grazie alla funzione udp_send(); la seconda
(linee 165÷173 in appendice) esegue l’operazione inversa ricevendo le due stringhe
tramite udp_receive() e convertendole in numeri interi mpz_class. Un esempio di utilizzo delle funzioni della classe Rsa verrà proposto nel seguito del capitolo.
La classe Rsa comprende, infine, i due metodi pubblici RsaEncrypt() e RsaDecrypt()
(line 24 e 25) per la cifratura e la decifratura dei dati.
La prima riceve in ingresso la stringa toEncryptStr da criptare, la converte nel
numero intero encrypted di tipo mpz_class e calcola, grazie alla funzione
mpz_powm() della libreria GMP, encrypted = encryptede mod n (linee 187 e 190 in
appendice). È importante notare come la funzione RsaEncrypt() richieda che
toEncryptStr contenga il valore numerico dei dati da cifrare e che questo sia minore
di n (come visto in precedenza nel capitolo). Di conseguenza, per poter utilizzare correttamente tale funzione, è necessario che i dati siano già stati convertiti in decimale e opportunamente suddivisi. A questo punto encrypted, dopo essere stato
tradotto in una stringa, viene memorizzato in toEncryptStr (linea 192 in appendice)
Per decifrare i dati, la funzione RsaDecrypt() deve necessariamente svolgere l’operazione inversa. Essa riceve in ingresso la stringa toDecrypt che viene convertita nel numero intero decrypted (linea 200 in appendice). Dopodiché la
funzione calcola, per mezzo di mpz_powm(), decrypted = decryptedd mod n e
restituisce il risultato di tale operazione sotto forma di stringa di caratteri. Poiché i dati vengono convertiti in decimale e suddivisi prima di essere cifrati, dopo la decifratura dovrà essere gestita la loro ricostruzione. Di seguito vedremo come tutte queste operazioni siano realizzate dalle funzioni della libreria RsaDataLib.