SICUREZZA INFORMATICA

(1)

IMPLEMENTAZIONI DIDATTICHE DI ALGORITMI DI CIFRATURA PER

SICUREZZA INFORMATICA

UNIVERSITÀ DEGLI STUDI DI UDINE

DIPARTIMENTO DI INGEGNERIA ELETTRICA, GESTIONALE E MECCANICA

CORSO DI LAUREA IN INGEGNERIA GESTIONALE

ANNO ACCADEMICO 2013/2014

Relatore:

Prof. Pier Luca Montessoro

Laureando:

Pierpaolo Basso

(2)

Scopo della tesi

Implementazione in linguaggio C e C++ degli algoritmi crittografici:

• Diffie-Hellman key exchange

• RSA

(3)

Strumenti utilizzati

• La libreria GMP (GNU Multiple Precision Arithmetic Library) che permette di lavorare con numeri interi, razionali e in virgola mobile ponendo come unico limite la memoria disponibile del calcolatore.

• La libreria udpsocketlib sviluppata dal prof.

Montessoro per la scrittura di applicazioni client/server con il protocollo UDP

• La libreria OpenSSL, utilizzata per generare numeri primi pseudo-casuali

(4)

Diffie-Hellman

• Whitfield Diffie e Martin E. Hellman, 1976

• soluzione innovativa al problema della distribuzione delle chiavi di cifratura.

• Scambio di una chiave di cifratura condivisa attraverso un canale di comunicazione insicuro (pubblico)

• La chiave può essere utilizzata per crittografare le comunicazioni mediante un algoritmo di cifratura simmetrica

(5)

Diffie-Hellman

I passaggi dell’algoritmo che portano allo scambio di una chiave di cifratura:

(6)

Diffie-Hellman

La sicurezza è basata sulla complessità computazionale del logaritmo discreto.

Una terza parte può intercettare i parametri p, g, A, B ma deve trovare a o b per calcolare la chiave K. Deve calcolare:

a = log_g A mod p

b = log_gB mod p

(7)

Diffie-Hellman

g deve essere tale da rendere elevata la complessità computazionale del logaritmo discreto:

•p sia un numero primo generato in modo casuale e sufficientemente grande

•il generatore g ha ordine r che è il più piccolo

intero per cui g

^r

= 1 mod p. Il più grande divisore

primo di r deve essere elevato

(8)

Diffie-Hellman

Queste due condizioni sono soddisfatte in questo modo:

•generando p come numero primo casuale di almeno 1024 bit e sicuro, cioè tale che q = (p-1)/2 sia anch’esso primo

•prendendo g come intero casuale compreso nell’intervallo (2, p-2). g avrà ordine r pari a q o 2q.

Poiché p è sufficientemente grande, anche q lo sarà e, quindi, l’ordine r del generatore sarà elevato

(9)

Diffie-Hellman

L’algoritmo Diffie-Hellman è vulnerabile all'attacco "Man in the middle”:

•una terza parte intercetta il parametro A del client

•genera, fingendosi il server, un suo numero B e lo invia al client scambiando così una chiave di cifratura

•fa lo stesso col server e, così, può intercettare e leggere tutta la corrispondenza tra i due

(10)

Classe Dh

La classe Dh implementa l’algoritmo Diffie-Hellman

14 class Dh 15 {

16 public:

17 mpz_class ReturnKey() const { return K; }

18 int SizeOfK() const { return mpz_sizeinbase(K.get_mpz_t(), 10);}

19 bool GenerateEncryptionKey_Client(int socket, string ipAddress, int udpPort);

20 bool GenerateEncryptionKey_Server(int socket);

21 string DhEncrypt(const string& toEncryptStr);

22 string DhDecrypt(const char* toDecrypt);

23

24 private:

25 mpz_class p, g, a, b, A, B;

26 mpz_class K; //key

27 mpz_class GetVariable(string varName);

28 mpz_class GeneratePrimeNumber(string name, unsigned numBits);

29 mpz_class FindGenerator();

30 void GetPgaAndSetA(int choice);

31 bool SendPGA(int socket, string ipAddress, int udpPort);

32 bool ReceiveBandComputeK(int socket);

33 bool ReceivePGA(int socket);

34 bool SendB(int socket);

35 void ComputeBandKey();

36 int rdtsc();

37 };

(11)

Classe Dh

GenerateEncryptionKey_Client()

GetPgaAndSetA()

SendPGA()

ReceiveBandComputeK()

GenerateEncryptionKey_Server()

ReceivePGA()

ComputeBandKey()

SendB()

client server

La successione delle chiamate alle funzioni di classe che realizzano lo scambio della chiave

(12)

Libreria DhDataLib

Libreria DhDataLib utilizza la classe Dh per cifrare le comunicazioni che avvengono attraverso la rete

1 #ifndef DHDATALIB_HPP 2 #define DHDATALIB_HPP 3

4 #include "ClassDh.hpp"

5 #include <fstream>

6

7 bool ReadAndSendData(Dh& srv, int socket, string ipAddress, int udpPort);

8 bool ReceiveAndDecryptData(Dh& srv, int socket);

9 void SendData(const string& data, Dh& srv, int socket);

10 string ReadFromFile();

11 string ReadMessage();

12 void printStrInDec(const string& toPrint);

13 void printStrInHex(const string& toPrint, bool crypted);

14

15 #endif

(13)

RSA

• R. Rivest, A. Shamir e L. Adleman , 1978

• Algoritmo di crittografia a chiave asimmetrica

• Per cifrare le comunicazioni in rete utilizza una coppia di chiavi crittografiche:

 chiave pubblica

 chiave privata

(14)

RSA

Nell’algoritmo RSA la generazione delle chiavi avviene nel seguente modo:

1)si scelgono due numeri primi casuali p e q sufficientemente grandi da garantire la sicurezza dell’algoritmo

2)si calcola n = p×q e φ = (p – 1)×(q – 1)

3)si sceglie un numero 1 < e < φ coprimo con φ

4)si calcola il numero d tale che e×d = 1 mod φ

(15)

RSA

• La chiave pubblica è costituita da (n, e)

• La chiave privata è costituita da (n, d)

(16)

RSA

La cifratura dei dati avviene attraverso l’operazione:

 c = m^e mod n la decifratura:

 c^d mod n = m

dove con m indichiamo i dati da cifrare e con c quelli cifrati.

(17)

RSA

La sicurezza è basata sulla difficoltà di scomporre in fattori primi i numeri interi molto elevati. Se si riuscisse a fattorizzare il numero n (noto pubblicamente), sarebbe possibile trovare p e q e da questi φ. Di conseguenza, conoscendo e, si potrebbe facilmente determinare d e violare l’algoritmo. Si devono utilizzare p e q di dimensioni tali per cui n sia un numero intero di almeno 200 cifre decimali.

(18)

Classe Rsa

La classe Rsa implementa l’algoritmo

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 };

(19)

Classe Rsa

La successione delle chiamate alle funzioni di classe che generano le chiavi di cifratura

GenerateEncryptionKeys()

2) FindE()

3) ComputeD()

GeneratePrimeNumber()

GetRandomE()

ComputeGCD() 1) GeneratePQandComputeNPhi()

(20)

Libreria RsaDataLib

Libreria RsaDataLib utilizza la classe Rsa per cifrare le comunicazioni in rete

1 #ifndef RSADATALIB_HPP 2 #define RSADATALIB_HPP 3

4 #include "ClassRsa.hpp"

5 #include <fstream>

6

7 void ReceiveAndDecryptData(Rsa& clt, int socket);

8 bool ReadAndSendData(Rsa& srv, int socket);

9 void SendData(const string& data, Rsa& srv, int socket);

10 string ReadFromFile();

11 string ReadMessage();

12 string RebuildData(string& decryptedStr);

13

14 #endif

(21)

Confronto col C

In C :

è stata mantenuta la stessa struttura della versione in C++ (stesse funzioni ma opportunamente tradotte)

non esiste il concetto di classe e, quindi, nemmeno l’Information Hiding

non è possibile sfruttare l’overloading degli operatori

la gestione delle stringhe è peggiore rispetto al C++

(22)

Conclusioni

In questa tesi, quindi:

 sono state create le classi e le librerie che implementano gli algoritmi crittografici Diffie-Hellman e RSA in linguaggio C e C++

 sono state realizzate le librerie e i programmi necessari al loro utilizzo per cifrare le comunicazioni che avvengono attraverso la rete