Kryptographie auf Mehrkernprozessoren

Hintergrund

In den letzten Jahrzehnten konnte ein ständiger Anstieg der Rechenleistung von Prozessoren (CPU) beobachtet werden. Diese Performancegewinne werden mittlerweile nicht mehr ausschließlich durch eine Erhöhung der Taktfrequenz, sondern durch die Integration mehrerer Recheneinheiten (Prozessorkerne) erreicht. Dadurch können Berechnungen parallel ausgeführt werden, wodurch die Rechenleistung erhöht und die Durchführung immer komplexerer Berechnungen und die Ausführung immer mächtigerer Applikationen ermöglicht wird.

Um die zusätzliche Rechenleistung, die durch diese „neue“ Parallelität zur Verfügung steht, auch in der Praxis ausnutzen zu können, sind spezielle Algorithmen, die möglichst viele Rechenschritte parallel ausführen, notwendig. Besonders bei sehr rechenintensiven kryptographischen Verfahren scheint hier viel Potential vorhanden zu sein. Andererseits entsteht durch die Parallelisierung jedoch auch ein gewisser Mehraufwand. Dieser führt dazu, dass der Einsatz paralleler Algorithmen erst ab einer bestimmten Komplexität sinnvoll ist.

Zielsetzung

Ziel dieser Arbeit war es zu untersuchen, inwieweit sich die Performance bestehender kryptographischer Algorithmen durch den Einsatz von Mehrkernprozessoren verbessern lässt. Dazu wurde in einem ersten Schritt analysiert, auf welchen Abstraktionsebenen parallele Algorithmen existieren bzw. eingesetzt werden können. Anhand von konkreten Java-Implementierungen wurden diese Resultate für den praktischen Einsatz evaluiert. Dazu wurden Messungen auf drei verschiedenen Testsystemen durchgeführt.

Für die vorgenommenen Analysen wurden die kryptographischen Verfahren RSA-Schlüsselgenerierung, RSA-Verschlüsselung und ECDSA-Signaturverifikation exemplarisch betrachtet und einer manuellen Parallelisierung unterzogen. Dabei kamen zwei verschiedene Methoden zur Anwendung. Alle drei ausgewählten Algorithmen wurden jeweils mit beiden Methoden parallelisiert um die Effizienz der beiden Methoden vergleichen zu können. Die durch die vorgenommenen Adaptierungen erzielten Performancegewinne werden im Folgenden detaillierter beschrieben.

Resultate  

Abbildung 1 illustriert die Ergebnisse der Parallelisierung der RSA-Schlüsselgenerierung. Die drei Diagramme zeigen jeweils ein Ergebnis eines der drei Testsysteme. Die drei Kurven repräsentieren die verschiedenen Implementierungen des Algorithmus, die auf den Testsystemen getestet wurden. Auf die x-Achsen der Diagramme wurden jeweils die Anzahl der durchgeführten Operationen aufgetragen. Die korrespondierenden y-Werte zeigen die Berechnungsdauer, die für die Durchführung der Operationen benötigt wurde.

Auf allen drei Testsystemen zeigten sich eindeutige Performancegewinne bei Verwendung parallelisierter Implementierungen. Zwischen den beiden Parallelisierungsmethoden ließen sich jedoch keine eindeutigen Unterschiede bezüglich ihrer Effizienz feststellen.

Ähnliche Resultate ergaben sich auch für die beiden anderen parallelisierten Algorithmen. Für alle untersuchten kryptographischen Operationen konnten durch die manuelle Parallelisierung einzelner Berechnungsschritte eindeutige Performancegewinne auf allen Testsystemen erreicht werden. Die Wahl der verwendeten Parallelisierungsmethode spielte hingegen keine große Rolle, für beide evaluierten Methoden konnten vergleichbare Ergebnisse erzielt werden. Details können den nachfolgenden Abbildungen entnommen werden.

Abbildung 1 – Ergebnisse – RSA Schlüsselgenerierung

Abbildung 1: Ergebnisse – RSA-Schlüsselgenerierung

Abbildung 2 – Ergebnisse – RSA Verschlüsselung

Abbildung 2: Ergebnisse – RSA-Verschlüsselung

Abbildung 3 – Ergebnisse – ECDSA Signaturverifikation

Abbildung 3: Ergebnisse – ECDSA-Signaturverifikation

Wissenschaftliche Veröffentlichung

Die Ergebnisse dieses Projekts werden auf der 7th International Conference on Web Information Systems and Technologies (WEBIST) präsentiert und in den Conference Proceedings veröffentlicht.