ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-09052007-110632


Tipo di tesi
Tesi di laurea specialistica
Autore
Martinelli, Massimiliano
URN
etd-09052007-110632
Titolo
Progetto e realizzazione di primitive crittografiche a curva ellittica per reti di sensori
Dipartimento
INGEGNERIA
Corso di studi
INGEGNERIA INFORMATICA
Relatori
Relatore Dini, Gianluca
Parole chiave
  • curva ellittica
Data inizio appello
02/10/2007
Consultabilità
Completa
Riassunto

Le reti di sensori costituiscono un esempio di rete wireless formata da nodi sensore con caratteristiche peculiari: ridotte dimensioni dei nodi, potenza di elaborazione limitata, memoria (RAM e ROM) ridotta e necessità di un
ridotto consumo di energia. Tali nodi sono utilizzati con tre scopi principali:

• raccogliere dati dall’ambiente circostante, grazie ai sensori di cui sono dotati (tipicamente luce,umidità e temperatura);

• effettuare elaborazioni locali (operazioni sui dati raccolti);

• trasmettere e ricevere tali dati con altri nodi sensore nelle vicinanze o con la stazione base.

Gli ambiti applicativi dove possono essere utilizzate sono numerosi: monitoraggio ambientale, controllo medico, ambito militare oppure controllo di apparati domestici. In alcune di queste situazioni può nascere l’esigenza di dotare i sensori di un’ infrastruttura software di sicurezza che riesca a garantire:


• la generazione di segreti condivisi, da utilizzare in schemi a chiave simmetrica;

• la segretezza delle informazioni scambiate tra i nodi sensore;

• l’ autenticazione dei messaggi ricevuti da un nodo.

I tradizionali algoritmi a chiave pubblica (come RSA) sono ritenuti troppo costosi dal punto di vista computazionale per le reti di sensori, come è stato dimostrato da alcune implementazioni. Il tempo computazionale richiesto per l’ operazione di esponenziazione modulare, che è alla base delle operazioni di cifratura/decifratura e di firma digitale, può richiedere tempi compresi tra 5 e 10 minuti, rendendo estremamente improbabile la loro utilizzazione pratica. Recentemente la crittografia a curva ellittica è stata proposta come soluzione alternativa per cercare di ridurre i tempi di esecuzione a parità di livello di sicurezza garantito. Questo tipo di crittografia è particolarmente adatta ai dispositivi con risorse limitate, come i nodi sensore, in quanto consente operazioni più veloci di RSA e una minore occupazione di memoria (le chiavi della curva ellittica sono più piccole delle chiavi RSA). Questa tesi si è occupata del porting di una libreria crittografica a curva ellittica (EccM 2.0 [6])per reti di sensori su nodo sensore Tmote Sky della Moteiv [1] (8 Mhz, 48KB ROM, 10 KB RAM) che utilizza come sistema operativo Contiki [13] e come linguaggio di programmazione il C. Tale libreria era già stata implementata e testata su sensori Tmote Sky della Moteiv [1] che utilizzavano però un differente sistema operativo e un differente linguaggio di programmazione, rispettivamente TinyOS (1.1.11) e nesC.
Gli obiettivi che ci siamo prefissati sono stati:

• garantire il funzionamento della libreria e verificare la correttezza dei risultati;

• cercare di ridurre i tempi di esecuzione.

La libreria EccM 2.0 implementa:

• l’ algoritmo Diffie-Hellmann, per la generazione e lo scambio di chiavi;

• gli algoritmi di firma digitale ECDSA e Nyberg-Rueppel.
Tale libreria sul sensore Tmote Sky (TelosB) con sistema operativo TinyOs richiede;

• per Diffie-Hellmann, 51 secondi per l’operazione di generazione della chiave pubblica (moltiplicazione di un punto della curva per un intero) e 1 minuto e 40 secondi per l’esecuzione del protocollo completo (2 moltiplicazioni di un punto della curva per un intero);

• per Ecdsa e Nyberg-Rueppel, i tempi sono tra loro simili. Per la firma circa 51 secondi (moltiplicazione di un punto della curva per un intero) e per la verifica 1 minuto e 50 secondi (2 moltiplicazioni di un punto della curva per un intero).

I risultati che sono stati ottenuti sul sensore Tmote Sky (TelosB) con sistema operativo Contiki sono più elevati di circa 40 secondi per ogni operazione di moltiplicazione fra un punto e un intero:

• per Diffie-Hellmann, 92 secondi per l’operazione di generazione della chiave pubblica e 3 minuti e 4 secondi per l’ esecuzione del protocollo completo;

• per Ecdsa, 90 secondi per la firma e 3 minuti e 6 secondi per la verifica;

• per Nyberg-Rueppel, 92 secondi per la firma e 3 minuti e 5 secondi per la verifica.

La causa di tale peggioramento va probabilmente ricercata nell’ utilizzo di un sistema operativo e di un linguaggio di programmazione differente.

Si è potuto ridurre il tempo necessario per la moltiplicazione di un punto per un intero ricorrendo all’ utilizzo dell’ algoritmo di Karatsuba per rendere più efficienti le moltiplicazioni modulari sul campo.
Il tempo necessario per la generazione della chiave pubblica e per la firma digitale (entrambe richiedono una moltiplicazione di un punto per un intero) è sceso di circa 6 secondi. Il tempo per la verifica della firma (che richiede due moltiplicazioni di un punto per un intero) è sceso di circa 12 secondi.

In seguito si è lavorato per convertire alcune delle funzioni della libreria utilizzata, che lavora a 8 bit, a 16 bit. In questo modo possiamo sfruttare pienamente le caratteristiche del microcontrollore che abbiamo a disposizione. La conversione di alcune funzioni fondamentali ci ha permesso di abbassare i tempi di altri 2,4 secondi in fase di firma digitale e di circa 4 secondi nelle operazioni di verifica.

Infine si è deciso di provare ad utilizzare un differente algoritmo per eseguire la moltiplicazione fra un intero e un punto della curva. Il nuovo algoritmo utilizzato è quello di Montgomery. Per le moltiplicazioni modulari sul campo abbiamo continuato ad usare l’ algoritmo di Karatsuba sopra citato.
Si è avuto un netto miglioramento delle prestazioni. I tempi per l’ esecuzione di una moltiplicazione intero-punto sono scesi di 54 secondi. Per una operazione di firma digitale siamo quindi intorno ai 30 secondi. 60s invece per la verifica.
E questo senza utilizzare nessuna delle funzioni a 16 bit già presentate.
Il loro utilizzo permette di far scendere ulteriormente i tempi di circa 3 secondi in fase di firma e di circa 7 secondi in fase di verifica.
L’ utilizzo di Montgomery, Karatsuba e alcune funzioni a 16 bit fa si che i tempi per la firma digitale e per la verifica siano rispettivamente 26s e 53s.
Sono però emersi problemi di spazio, dovuti alla poca memoria disponibile sui nodi sensori. A causa di questa limitazione non è possibile caricare insieme su un nodo sensore il software per l’ esecuzione della firma digitale e quello necessario alla verifica della firma.
Perciò una soluzione può essere quella di utilizzare 2 nodi al posto di 1 per le operazioni. Un’ altra soluzione è cercare di ri-implementare la libreria provando a ridurre il numero dei componenti in modo da risparmiare memoria e poter caricare tutto il software su un unico nodo sensore.



File