Crittografia a curva ellittica
NYBERG RUEPPEL
3. Applica ricorsivamente lo stesso metodo per calcolare i prodotti F0G0, F1G1,
5.4 Algoritmo di Montgomery (kP)
5.4 Algoritmo di Montgomery (kP)
Un miglioramento significativo delle prestazioni è possibile ottenerlo utilizzando un differente algoritmo per il calcolo della moltiplicazione fra un intero e un punto della curva. Il metodo adottato dalla libreria EccM 2.0 è quello “double and add”. A questo si è provato a sostituire l’ algoritmo di Montgomery, che viene presentato di seguito usando le coordinate proiettive, preferibili a quelle affini quando il tempo per eseguire le inversioni è superiore a quello che serve per le moltiplicazioni. Nella nostra implementazione sono state usate le coordinate affini, anche se si verifica la situazione sopra esposta. L’ algoritmo comunque rimane sostanzialmente quello presentato.
Algoritmo di Montgomery
5.4 Algoritmo di Montgomery (kP) Consideriamo e con Poi prendiamo e
A questo punto è possibile verificare che
1
y
1Q
= (
x
1,
)
2Q
= (
x
2,
y
2)
1Q
±
Q
2 4y
( , 1Q
2Q
- =x
4 ) 4x
3x
= + 1x
2x
1x
+ + 1x
2x
1x
+ 2(1)
3x
(
2Q
y
3 1Q
+
=
,
)
5.4 Algoritmo di Montgomery (kP)
Perciò, la coordinata x di può essere calcolata dalle coordinate x di , e - .
La j-esima iterazione dell’ algoritmo per determinare il kP calcola
Tj = (lP,(l+1P)
dove l è l’ intero dato dai j bits più a sinistra of k. In seguito osserviamo che
Tj+1 = (2lP,(2l+1)P or ((2l+1)P,(2l+2)P)
se il (j+1)-esimo bit più a sinistra di k è rispettivamente 0 o 1.
Ciascuna iterazione richiede un raddoppio e una addizione utilizzando la formula (1) precedente.
Dopo l’ ultima iterazione, avendo calcolato la coordinata x del kP = (x1, y1) e (k+1)P = (x2, y2), la coordinata y del kP può essere ottenuta nel modo seguente:
y1 = x 1 − ( x1+ x ) [ ( x1+ x ) ( x2+ x ) + x 2 + y ] + y
L’ implementazione dell’ algoritmo di Montgomery che abbiamo utilizzato è quella presente nella libreria MIRACL, come per l’ algoritmo di Karatsuba.
La funzione principale che esegue la moltiplicazione è la ecurve2_mult_montg.
1
Q
+ Q
21
5.4.1 Prestazioni
Ovviamente, come già discusso nei paragrafi precedenti, si è dovuto convertire parte delle funzioni che ci sono state fornite in modo da poter lavorare con word di 8 bit invece che di 32, come di base la MIRACL fa.
Le funzioni che non hanno avuto bisogno di alcuna conversione sono quelle fondamentali che compongono la moltiplicazione di Montgomery, e di cui eravamo già in possesso:
• moltiplicazione modulare di Karatsuba (kara_modmult2); • elevamento al quadrato (square);
• somma fra polinomi tramite XOR (f_add).
5.4.1 Prestazioni
Terminata l’ implementazione delle funzioni e impostati i parametri caratteristici della nostra curva siamo passati alla fase di test.
In questa fase abbiamo riscontrato un netto miglioramento della prestazioni con un significativo calo dei tempi di esecuzione.
Il tempo necessario per calcolare la firma digitale secondo il protocollo ECDSA (una moltiplicazione di un intero per un punto della curva) utilizzando l’ algoritmo di Montgomery dotato dell’ algoritmo di Karatsuba per le moltiplicazioni sul campo è sceso del 64,3%, 54 secondi. Del 62,1%, 108 secondi, è invece il miglioramento in fase di verifica (due moltiplicazioni intero-punto della curva).
L’ implementazione discussa non prevede lo sfruttamento delle funzioni a 16 bit presentate nei paragrafi precedenti. L’ utilizzo delle 2 funzioni a 16 bit (per il calcolo
5.4.1 Prestazioni
di Karatsuba e della moltiplicazione classica x*y) comporterebbe un ulteriore calo dei tempi di esecuzioni.
Infatti la funzione che esegue Karatsuba viene invocata per 970 volte, poco più del doppio rispetto alla implementazione precedente (454 volte). Se prima avevamo un calo di 1,4 secondi, adesso possiamo stimare un miglioramento di circa 3 secondi per ogni kP. Per la funzione che esegue invece la moltiplicazione classica rimane tutto invariato, non essendo coinvolta nei cambiamenti apportati all’ algoritmo. Il miglioramento che il suo utilizzo comporta rimane di 1 secondo.
E’ quindi possibile stimare un ulteriore miglioramento del 13,3%, 4 secondi (3+1), nel calcolo della firma digitale (1 kP) e dell’ 10,61%, 7 secondi (6+1), per la verifica della firma (2 kP).
L’ utilizzo di Montgomery, Karatsuba e delle funzioni a 16 bit permette quindi un miglioramento, in fase di calcolo della firma digitale, del 71,1%, rispetto alla libreria EccM 2.0 standard di cui si è fatto inizialmente il porting. Per la verifica si ha un miglioramento del 68,28%. Questi dati sono evidenti dall’ osservazione della tabella 5.1.
Poiché solitamente il calcolo della chiave pubblica viene eseguito offline, su un nodo è necessario avere soltanto il codice per il calcolo della firma digitale e quello per la verifica della firma.
E’ emerso però un problema di spazio: la memoria di cui dispongono i nodi sensori non ci permette di caricare su una mote questi 2 tipi di software.
Una soluzione può essere quella di utilizzare quindi 2 nodi al posto di 1.
Un’ altra strada è provare a implementare la libreria in modo differente, riducendo il numero di componenti per risparmiare memoria e riuscire a caricare tutto il software necessario su un unico nodo sensore.
5.5 Conclusioni
5.5 Conclusioni
La tabella sottostante mostra tutti i tempi ottenuti con le varie implementazioni utilizzate, e evidenzia i buoni risultati ottenuti dalla situazione iniziale (EccM 2.0 standard) fino all’ ultima implementazione che prevede la modifica della libreria mediante l’ algoritmo di Montgomery, quello di Karatsuba e l’ utilizzo di alcune funzioni a 16 bit.
ECDSA EccM 2.0 EccM 2.0
+ Karatsuba EccM 2.0 + Karatsuba + 16 bit functions EccM 2.0 + Karatsuba + Montgomery EccM 2.0 + Karatsuba + Montgomery + 16 bit functions Digital Signature (1 kP) 90s 84s 81,6s 30s 26s Signature Verification (2 kP) 186s 174s 170s 66s 59s
Tabella 5.1: Riepilogo risultati
I progressi sono evidenti. In particolare risulta decisivo l’ utilizzo del nuovo algoritmo di Montgomery per la moltiplicazione intero-punto della curva.
5.5 Conclusioni
Come già accennato nei paragrafi precedenti, nei quali viene discussa la conversione da 8 a 16 bit di alcune funzioni, un ulteriore miglioramento lo si può indubbiamente ottenere lavorando per convertire totalmente la libreria a word di 16 bit. Diminuendo in questo modo il numero delle operazioni, i cicli e gli accessi in memoria.
Dalla collaborazione con l’ Università di Siena è emersa anche la possibilità di utilizzare differenti rappresentazioni delle curve e differenti algoritmi che usano poche inversioni. In tal caso i risultati potrebbero essere molto interessanti.
Una nota preoccupante è però la scarsa memoria di cui questi sistemi dispongono. E’ emerso chiaramente applicando Montgomery. E’ sì possibile ottimizzare l’ uso della memoria andando a implementare in maniera differente la libreria riducendo il numero dei componenti, ad esempio utilizzando un unico componente per il calcolo del kP in firma e in verifica (dimezzando così il codice per tale moltiplicazione), ma 48K rimangono sempre troppo pochi in previsione di possibili sviluppi futuri. Il nodo sensore mette a disposizione degli sviluppatori un buon microcontrollore a 16 bit, ma qualche K di memoria in più offrirebbe maggiori possibilità implementative.
E’ possibile provare ad utilizzare anche porzioni di codice scritte in assembler. Questo linguaggio era già stato usato nei test effettuati in passato sui Tmote Sky con TinyOs come sistema operativo su una libreria di algoritmi a curva ellittica chiamata TinyEcc. I risultati sono stati notevoli.
Anche Contiki fornisce la possibilità di lavorare in assembler. Sostituire parti di sorgente in C con parti scritte in assembler potrebbe aiutare a ottenere prestazioni ancora più buone.
5.5 Conclusioni
Ultima possibilità ma non meno importante è provare a tornare al vecchio sistema operativo, TinyOs, e testare la libreria EccM 2.0 con i nuovi algoritmi sviluppati in questa tesi.
Dalla tabella 5.1 emerge che dal porting iniziale della libreria fino all’ ultima implementazione con Montgomery, Karatsuba e alcune funzioni a 16 bit, si è avuto un miglioramento delle prestazioni intorno al 70% sia per quanto riguarda la firma digitale sia per quanto riguarda la verifica della firma. Ovvero rispettivamente un calo dei tempi di 64 secondi in firma e 126 secondi in verifica. Con TinyOs il tempo per calcolare una firma digitale era circa 50 secondi, mentre si impiegava 1 minuto e 50 secondi per una verifica. Migliorare del 70% significherebbe andare intorno ai 15 secondi per la firma e ai 30 secondi per la verifica, circa la metà di quanto impiega il nodo sensore attualmente.
Bibliografia
Bibliografia
[1] Moteiv corporation. http://www.moteiv.com.
[2] Ian F. Blake, G. Seroussi, and Nigel P. Smart. “Elliptic curves in cryptography”, volume 265 of London Mathematical Society lecture note series. pub-CUP, pub-CUP:adr, 1999.
[3] W. Diffie and M. Hellman. “New Directions in Cryptography”. IEEE Transactions on Information Theory, 22(6):644–652, November 1976.
[4] Neal Koblitz. “Elliptic Curve Cryptosystems”. j-MATH-COMPUT, 48(177):203–209, January 1987.
[5] Dragongate Technologies Limited. “jBorZoi 0.90”. http://dragongate- technologies.com/products.html, Agosto 2003.
[6] David J. Malan, Matt Welsh, and Michael D. Smith. “A Public-Key Infrastructure for Key Distribution in TinyOS”, August 23 2004. First IEEE International Conference on Sensor and Ad Hoc Communications and Networks. Santa Clara, California. http://citeseer.ist.psu.edu/713889.html "http://airclic. eecs.harvard.edu/publications/secon04.pdf.
Bibliografia
[7] Victor Miller. “Use of Elliptic Curves in Cryptography”. In Advances in Cryptology: Proceedings of CRYPTO ’85, Santa Barbara CA, volume 218 of Lecture Notes in Computer Science, pages 417–426, Berlin, 1986. Springer- Verlag.
[8] Certicom Reasearch. “Sec 2: Recommended Elliptic Curve Domain Parameters”. Technical Report Standards for efficient Cryptography Version 1.0, September 2002. Available from: http://www.secg.org/collateral/sec2.pdf.
[9] Certicom Research. “GEC 2: Test vector for SEC 1”. (Working draft, Version 0.3), September 1999. Available from: http://www.secg.org/download/aid- 390/gec2.pdf.
[10] R. L. Rivest, A. Shamir, and L. Adleman. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Comm. of the ACM, 21(2):120, February 1978.
[11] S. Vanstone. “Responses to NIST’s Proposal”. Communications of the ACM, 35:50–52, July 1992.
[12] Ronald Watro, Derrick Kong, Sue fen Cuti, Charles Gardiner, Charles Lynn, and Peter Kruus. “TinyPK: securing sensor networks with public key technology”. In SASN ’04: Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, pages 59–64, New York, NY, USA, 2004. ACM Press.
Bibliografia