Analyse und Vorhersage des Flächen- und Energieverbrauches optimaler Hardware Polynom-Multiplizierer für GF(2ⁿ) für elliptische Kurven Kryptographie

Analysis and prediction of area- and energy-consumption of optimized polynomial multipliers in hardware for arbitrary GF(2ⁿ) for elliptic curve cryptography

  • Die Anwendung asymmetrischer Kryptosysteme, z.B. elliptische Kurven Kryptographie (ECC), erfordert große Rechenkapazität die normalerweise auf von mobilen Geräten bzw. drahtlosen Sensorknoten nicht zur Verfügung steht. Die Implementierung der ECC in Hardware reduziert den Zeit- und Energie-Aufwand. Die Optimierung der Hardware-Implementierungen dient nicht nur der weiteren Reduktion des Zeit- und Energieverbrauches sondern hilft darüber hinaus die Herstellungskosten zu verringern, so dass solche Lösungen auch für kostengünstige Geräte einsetzbar werden. Im Rahmen dieser Dissertation wurden Optimierungsmöglichkeiten für die Multiplikation der Polynome, die für EC-Operationen eingesetzt werden, untersucht. Ziel der Optimierungen war, dass die Multiplikation mit einer minimalen Anzahl von Additionen (also XOR-Gattern) und Multiplikationen (also AND-Gattern) durchgeführt werden kann. Im Rahmen dieser Arbeit wurde die iterative Bearbeitung von 10 Multiplikations-Methoden (MM) im Gegensatz zur üblichen rekursiven Bearbeitung untersucht.Die Anwendung asymmetrischer Kryptosysteme, z.B. elliptische Kurven Kryptographie (ECC), erfordert große Rechenkapazität die normalerweise auf von mobilen Geräten bzw. drahtlosen Sensorknoten nicht zur Verfügung steht. Die Implementierung der ECC in Hardware reduziert den Zeit- und Energie-Aufwand. Die Optimierung der Hardware-Implementierungen dient nicht nur der weiteren Reduktion des Zeit- und Energieverbrauches sondern hilft darüber hinaus die Herstellungskosten zu verringern, so dass solche Lösungen auch für kostengünstige Geräte einsetzbar werden. Im Rahmen dieser Dissertation wurden Optimierungsmöglichkeiten für die Multiplikation der Polynome, die für EC-Operationen eingesetzt werden, untersucht. Ziel der Optimierungen war, dass die Multiplikation mit einer minimalen Anzahl von Additionen (also XOR-Gattern) und Multiplikationen (also AND-Gattern) durchgeführt werden kann. Im Rahmen dieser Arbeit wurde die iterative Bearbeitung von 10 Multiplikations-Methoden (MM) im Gegensatz zur üblichen rekursiven Bearbeitung untersucht. Dabei wurde eine Reihenfolge der Operationen für jede der untersuchten MM ermittelt, die zu einer reduzierten Anzahl von XOR-Operationen führt. Der Einsatz der optimierten Reihenfolge kann die Komplexität der MM wesentlich reduzieren. Zum Beispiel bei der generalisierten Karatsuba-MM [18] beträgt die Reduktion des XOR-Aufwandes durchschnittlich 39 % für Polynom-Längen bis 600 Bits. Für die IHP 0,13μ-Technologie entspricht diese Reduktion des XOR-Aufwandes einer durchschnittlichen Flächen-Reduktion der Polynom-Multiplizierer um 35 %. Bei der 4-Segment-Karatsuba-MM wird nicht nur der XOR-Aufwand, sondern auch die Signal-Verzögerung im Vergleich zur rekursiven Anwendung der originalen Karatsuba-MM reduziert. Außerdem wurde ein Algorithmus zur Bestimmung einer flächen- und/oder energieoptimalen Kombination der Multiplikations-Methoden entwickelt. Mit dem vorgeschlagenen Algorithmus wurden die flächen- und die energie-optimalen Kombinationen der MM für Polynom-Längen bis 600 Bits bestimmt. Alle ECC-relevanten Polynom-Längen liegen in diesem Bereich. Die durchschnittliche Reduktion der Flächen im Vergleich zu den rekonstruierten Daten aus [30] beträgt 12 %. Zusätzlich wurde ein energieoptimaler serieller Mehr-Takt-Multiplizierer für 233-Bits Polynome auf Basis Karatsuba-ähnlicher Multiplikations-Methoden entwickelt. Dieser Multiplizierer nutzt die Winograd-MM und basiert auf einen flächenoptimierten 78-Bits-Teil-Multiplizierer. Die theoretischen Ergebnisse wurden mit Hilfe von Synthesedaten für die IHP Technologie erfolgreich verifiziert. Der Energieverbrauch und die Ausführungszeit des Designs sind um 24 % bzw. 28 % kleiner als die des Vergleichsdesigns aus [28].show moreshow less
  • During recent years elliptic curve cryptography (ECC) has gained significant attention especially for devices with scarce resources such as wireless sensor nodes. Hardware implementations are considered to be the key enabler for using ECC on this class of devices. Out of the operations needed to execute ECC the polynomial multiplication is the one which is investigated most since it is one of the most complex field operations and executed very often. The majority of research papers focuses on reducing the number of partial- multiplications while neglecting the increased effort for additions of the partial products. This thesis investigates how the latter can be optimized. A reduction of additions can be achieved by using pre-defined processing sequences for summing up partial products. In this work a method to find the optimized processing sequence is presented. It is applied to 10 multiplication methods of polynomials over GF(2ⁿ). For example when applied to the generalized Karatsuba multiplication [18] the optimized processingDuring recent years elliptic curve cryptography (ECC) has gained significant attention especially for devices with scarce resources such as wireless sensor nodes. Hardware implementations are considered to be the key enabler for using ECC on this class of devices. Out of the operations needed to execute ECC the polynomial multiplication is the one which is investigated most since it is one of the most complex field operations and executed very often. The majority of research papers focuses on reducing the number of partial- multiplications while neglecting the increased effort for additions of the partial products. This thesis investigates how the latter can be optimized. A reduction of additions can be achieved by using pre-defined processing sequences for summing up partial products. In this work a method to find the optimized processing sequence is presented. It is applied to 10 multiplication methods of polynomials over GF(2ⁿ). For example when applied to the generalized Karatsuba multiplication [18] the optimized processing sequence saves up to 39 per cent of XOR-gates in average for polynomials with a length up to 600 bits. In addition it is known that combining different multiplication methods reduced the total complexity of the multiplier. For example using the classical MM for calculation of small partial products in combination with other MMs can improve chip-parameters of the resulting multipliers. An optimal combination of several multiplication approaches for which the optimized processing sequence of XOR-operations is used reduces the area and energy consumption of the resulting multiplier significantly. This work presents an algorithm to determine the optimal combination of multiplication methods with pre-defined processing sequences for hardware implementation of an highly efficient polynomial multiplier in GF(2ⁿ). The combinations determined by this algorithm save in average 12 % of the chip-area for polynomials with a length up to 600 bits in comparison to data reconstructed from [30]. In addition the effect of the optimization techniques researched in this thesis was evaluated using the example of polynomial multiplier for 233 Bits long operands. The multiplier uses the Winograd-MM for segmentation of operands and executes partial multiplication using an optimized 78 bits partial multiplier. The theoretical results have been verified successfully by synthesizing this multiplier for the IHP 0.13 μm technology. In comparison to a synthesized version of the design given in [28] the optimized multiplier of this thesis reduces the energy consumption and execution time of the kP operation by 24 and 28 per cent, respectively.show moreshow less

Download full text files

Export metadata

Additional Services

Search Google Scholar Stastistics
Metadaten
Author: Zoya Dyka
URN:urn:nbn:de:kobv:co1-opus-27240
Referee / Advisor:Prof. Dr. Peter Langendörfer
Document Type:Doctoral thesis
Language:German
Year of Completion:2013
Date of final exam:2012/04/13
Release Date:2013/01/23
Tag:Elliptische Kurven Kryptographie; GF(2ⁿ); Hardware Implementierung; Optimierung; Polynom-Multiplikation
Elliptic curve cryptography; GF(2ⁿ); Hardware implementation; Optimization; Polynomial multiplication
GND Keyword:Hardwareentwurf; Kryptologie
Institutes:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Sicherheit in pervasiven Systemen
Institution name at the time of publication:Fakultät für Mathematik, Naturwissenschaften und Informatik (eBTU) / LS Sicherheit in pervasiven Systemen
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.