Die vorliegende Arbeit befasst sich mit Effizienz- und Sicherheitsproblemen bei der Implementierung von Code-basierten Public-Key Verschlüsselungsverfahren. Diese Verfahren, obwohl derzeit nicht in Verwendung, sind von großem wissenschaftlichen Interesse, da kein Quantenalgorithmus bekannt ist, der diese entscheidend effizienter brechen kann als ein klassischer Algorithmus. Dies macht sie zu Kandidaten für die Quantencomputerära, in der die heute verwendeten Public-Key Verschlüsselungsverfahren unsicher werden.

Bezüglich der Effizienz wird eine Lösung für die Handhabung der bei dieser Art von Verfahren im Vergleich mit den heute im Einsatz befindlichen extrem großen öffentlichen Schlüsseln vorgestellt. Dabei liegt der Fokus auf ressourcenbeschränkten Geräten, die nicht in der Lage sind, den öffentlichen Schlüssel eines Kommunikationspartners im flüchtigen Speicher zu halten. Ferner wird eine Lösung aufgezeigt, mit der die Entschlüsselung auch ohne die Parity Check Matrix mit vertretbaren Geschwindigkeitseinbußen möglich ist. Dies ist ebenso von großer Bedeutung, da diese Matrix von vergleichbarer Größe ist wie der öffentliche Schlüssel, und somit eine Verwendung derselben auf speicherarmen Geräten nicht möglich oder mit hohen Kosten verbunden ist.

Es wird auch eine Untersuchung zur Verbesserung der Laufzeit der im Allgemeinen rechenintensivsten Teiloperation bei der Entschlüsselung, dem Finden der Nullstellen des Fehlerlokatorpolynoms, vorgestellt. Hierbei werden verschiedene bekannte algorithmische Varianten und neue Kombinationen derselben in Bezug auf Laufzeit und Speicheranforderungen verglichen. Obwohl die Geschwindigkeit reiner Softwareimplementierungen gerade als eine der Stärken der Code-basierten Verfahren angesehen werden muss, ist die Optimierung der Laufzeit sowohl auf ressourcenbeschränkten Plattformen als auch auf Servern von großer Relevanz.

Der zweite wesentliche Teil der Arbeit befasst sich mit der Seitenkanalsicherheit dieser Verfahren. Seitenkanalschwachstellen bedeuten, dass ein Angreifer während einer kryptographischen Operation durch die Messung physikalischer Größen wie der Laufzeit der Berechnung oder der Leistungsaufnahme des Geräts während der Operation Informationen über an der Berechnung beteiligte geheime Informationen erhält. Dabei werden Angriffe auf die Entschlüsselungsoperation betrachtet, die entweder auf die Rekonstruktion der Nachricht oder des geheimen Schlüssels abzielen, und in den meisten Fällen konkrete Gegenmaßnahmen vorgeschlagen und evaluiert. In diesem Zusammenhang werden eine Reihe von Laufzeitschwachstellen aufgezeigt, welche mit manchen der bereits oben erwähnten algorithmischen Varianten für das Finden der Nullstellen des Fehlerlokatorpolynoms zusammenhängen. Des Weiteren wird ein Laufzeitangriff gegen eine Schwachstelle des bei der Entschlüsselung verwendeten erweiterten Euklidischen Algorithmus zur Lösung der sogenannten Key Equation vorgestellt, der auf die Rekonstruktion der Nachricht abzielt. Hierzu wird auch eine praktische Leistungsaufnahmeattacke vorgeführt. Schließlich wird eine praktische Laufzeitattacke zur Rekonstruktion des geheimen Schlüssels vorgestellt, die auf der Kombination von drei Schwachstellen innerhalb der Syndrominvertierung, einer weiteren Teiloperation der Entschlüsselung, und der schon erwähnten Lösung der Key Equation beruht.

Die Angriffe, die die Rekonstruktion der Nachricht zum Ziel haben, werden mit ihrem Analogon für das RSA Public Key Verschlüsselungsverfahren verglichen, und es wird eine allgemeine Methodologie für das Auffinden der in solchen Fällen zugrunde liegenden Schwachstellen entwickelt.

Ferner werden zwei Implementierungen des Code-basierten McEliece Verschlüsselungsverfahrens vorgestellt: Eine Smartcard-Implementierung und eine auf einer quelloffenen PC Implementierung basierende flexible Implementierung. Die bestehende quelloffene Implementierung wurde dahingehend erweitert, dass sie plattformunabhänig wurde und für ressourcenbeschränkte Geräte optimiert wurde. Außerdem wurden dort alle in dieser Arbeit vorgestellten algorithmischen Varianten integriert, für die jeweils alle relevanten Performanzdaten wie Laufzeit, Code-Größe und Speicherverbrauch auf einem eingebetteten System vorgestellt werden. Ferner wurden die erarbeiteten Seitenkanalgegenmaßnahmen implementiert.

Zuletzt werden in dieser Arbeit offen bleibende Forschungsfragen vorgestellt, die Relevanz erhalten werden, sobald effiziente und sichere Implementierungen Code-basierter Verfahren von der Industrie für den Einsatz evaluiert werden.