Algebraische Kryptoverfahren – eine Alternative?

Ordnungsmerkmale

erschienen in: <kes> 2003^#4, Seite 35

Zusammenfassung: Algebraische Verfahren werden in der Praxis für kryptographische Zwecke kaum angewandt. In vielen Anwendungen und im Internet werden Verfahren basierend auf dem Faktorisierungsproblem oder auf elliptischen Kurven bevorzugt. Das liegt an den vielen Nachteilen von algebraischen Kryptoverfahren. Doch eine Eigenschaft könnte diesen Verfahren eine große Bedeutung verschaffen: Sie wären vermutlich auch im Zeitalter der Quantencomputer verwendbar. Daher sollen hier verschiedene algebraische Verfahren vorgestellt und bezüglich ihrer Funktionsweise, Sicherheitsaspekte, Praktikabilität und ihres Potenzials für die Zukunft beleuchtet werden.

Autor: Von Dr. Le Van Ly, BSI

Wenn man die Fülle der existierenden Public-Key-Kryptoverfahren mit der Monokultur der in der Praxis angewandten Verfahren vergleicht, stellt sich die Frage, ob diese Vielfalt nötig ist. Nun ist es vielleicht in der Kryptographie wie in der Evolutionsbiologie; nur große Variationsbreite garantiert das Überleben der Spezies und hier womöglich den Fortbestand der Public-Key-Kryptographie. Und während es in der Natur vielleicht Viren oder Klimaveränderungen sind, könnten hier mathematische Forschung und technische Entwicklungen die vorhandenen Systeme zur Anpassung zwingen.

Eine wichtige Klasse von Public-Key-Kryptoverfahren, die hier diskutiert werden soll, ist die der so genannten algebraischen Verfahren, deren Sicherheit auf algebraischen oder kombinatorischen Problemen beruht. Besonders interessant sind dabei die Verfahren, die sogar auf so genannten NP-harten Problemen basieren: NP-Härte ist ein Begriff aus der theoretischen Informatik, die Fragestellungen nach Komplexität und Rechenaufwand klassifiziert (s. Kasten). Bezeichnet man ein Problem, also eine Klasse von Fragestellungen als NP-hart, dann wird vermutet, dass Instanzen dieses Problems existieren, bei denen durch eine geringe Vergrößerung der Eingabeparameter erreicht wird, dass der Aufwand zur Lösung des Problems exponentiell stark wächst. Zum Beispiel ist die Frage der 3-Färbbarkeit eines Graphen (s. Kasten) ein NP-hartes Problem, während das Faktorisieren einer Zahl, also das Zerlegen einer Zahl in ihre Primfaktoren, es nicht ist.

Der Grund, warum man sich gerade für algebraische Verfahren interessiert, die auf NP-harten Problemen basieren, ist ihre erwartete Resistenz gegen Quantencomputer. Denn NP-harte Probleme sind vermutlich auch nicht mit Quantencomputern effizient lösbar. Dass algebraische Verfahren derzeit in der Praxis keine Rolle spielen, mag an bestimmten Eigenschaften liegen, die sie relativ unattraktiv gegenüber den häufig angewendeten zahlentheoretischen Verfahren wirken lassen. Zudem flößt die bisherige geschichtliche Entwicklung der algebraischen Verfahren vielen Anwendern wenig Zutrauen ein.

Public Keys

Nachdem Diffie und Hellman 1976 die Idee der Public-Key-Kryptographie (auch asymmetrische Kryptographie genannt) entwickelt hatten, startete die Suche nach der wesentlichen Ingredienz eines Public-Key-Verfahrens, einer so genannten Trapdoor-Einwegfunktion. So heißen Abbildungen, zu denen man ein Paar von Schlüsseln (öffentlicher und geheimer) finden kann, sodass gilt:

• Mit Kenntnis des öffentlichen Schlüssels soll jedermann Nachrichten leicht verschlüsseln können.
• Ohne Kenntnis des geheimen Schlüssels soll es keinen effizienten Algorithmus geben, um den Geheimtext zu entschlüsseln.
• Mit Kenntnis des geheimen Schlüssels soll die Entschlüsselung effizient durchführbar sein.

Ist eine solche Einwegfunktion gefunden, dann kann nach dem mittlerweile wohlbekannten Prinzip verschlüsselt miteinander kommuniziert werden: Nachdem Alice sich einen öffentlichen Schlüssel (Public Key, PK) und einen dazu passenden geheimen Schlüssel (Secret Key, SK) erzeugt hat, veröffentlicht sie PK. Um eine Nachricht verschlüsselt an Alice zu senden, berechnet Bob den Wert der Einwegfunktion mithilfe von Alices öffentlichem Schlüssel. Diesen Geheimtext kann dann nur Alice mit dem passenden geheimen Schlüssel wieder dechiffrieren (vgl. Abb. 1).

Abb. 1: Prinzip der Public-Key-Kryptographie

Man kann asymmetrische Verschlüsselung mit einem herkömmlichen Briefkasten vergleichen. Jedermann kann eine Nachricht einwerfen ("verschlüsseln mit PK"), aber nur der Besitzer des Schlüssels kann den Briefkasten öffnen ("entschlüsseln mit SK").

Public-Key-Verfahren sind heutzutage aus dem Alltag nicht mehr wegzudenken. Wird zum Beispiel eine sichere Verbindung im Internet aufgebaut, so sind häufig asymmetrische Mechanismen im Spiel. Dabei wird häufig das 1978 von Rivest, Shamir und Adleman [9] entwickelte RSA-Verfahren verwendet, zum Beispiel beim SSL-Apache-Server. Die Sicherheit von RSA basiert letztendlich auf der Schwierigkeit eine Zahl in ihre Primfaktoren zu zerlegen. Wie bereits erwähnt, ist Faktorisieren aber kein NP-hartes Problem, und es existieren auch schon Algorithmen, die mit Quantencomputern dieses Problem effizient lösen könnten. Ein weiteres beliebtes Verfahren ist die Elliptic Curve Cryptography (ECC) von N. Koblitz und V. Miller [2]. Ein wesentlicher Vorteil von ECC gegenüber RSA sind die kürzeren Schlüssellängen. Anstatt 1024 Bits benötigt man nur 160 Bits bei einer vergleichbaren Sicherheit. Aber auch dieses Verfahren könnte mit Quantencomputern gebrochen werden.

Merkle-Hellman-Knapsack

Das System Merkle-Hellmann-Knapsack ist eines der bekanntesten algebraischen kryptographischen Verfahren. Zugleich ist es auch eines der entmutigendsten Kapitel in der Geschichte der algebraischen Public-Key-Kryptographie: Merkle-Hellman-Knapsack wurde nur wenige Jahre nach seiner Veröffentlichung vollständig gebrochen.

Noch vor der Entdeckung von RSA schlugen Merkle und Hellman 1978 [7] ein Verfahren vor, das auf dem so genannten Subset-Sum-Problem basiert. Über dieses Problem ist gezeigt worden, dass es NP-vollständig ist. Mathematisch lässt es sich wie folgt beschreiben: Gegeben sind ganze Zahlen a₁, ..., a_n und eine Zahl s. Gefragt ist dann nach einer Auswahl der Zahlen a_i, sodass deren Summe s ergibt. Ein einfaches Beispiel ist: a₁ = 2, a₂ = 6, a₃ = 5, a₄ = 3, a₅ = 4 und s = 12. Dann ist eine Lösung des Problems die Auswahl a₁ + a₂ + a₅, aber auch a₃ + a₄ + a₅.

Um daraus eine Einwegfunktion zu konstruieren, startet man bei Merkle-Hellman-Knapsack mit einem Spezialfall des Problems, das effizient lösbar ist. Das gilt zum Beispiel für eine so genannte superwachsende Folge von Zahlen, das heißt jede Zahl ist größer als die Summe der vorangegangenen Zahlen. Ein Beispiel ist a₁ = 3, a₂ = 5, a₃ = 11, a₄ = 23, a₅ = 43. Wenn nun s = 14 ist, dann ist klar, dass man a₃ = 11 für die Lösung benötigt, da alle vorherigen Folgeglieder sich nicht zu 14 aufsummieren und die übrigen Zahlen zu groß sind. Man arbeitet dann mit 3 = s − a₃ weiter, geht die Folge von links nach rechts ab und findet iterativ die Auswahl a₁ + a₃. Alice beginnt folglich damit, dass sie sich eine superwachsende Folge a₁, ..., a_n wählt. Diese wandelt sie dann durch mathematische Operationen in eine nicht superwachsende Folge b₁, ..., b_n um. Ihr geheimer Schlüssel besteht nun aus der superwachsenden Folge a₁, ..., a_n und der Kenntnis, wie die Folgen a₁, ..., a_n und b₁, ..., b_n in Beziehung stehen. Dagegen ist die Folge b₁, ..., b_n der öffentliche Schlüssel. Von dieser Folge erhoffte man sich, dass sich aus ihr nicht mehr die ursprüngliche Folge a₁, ..., a_n herleiten lässt, und dass das Lösen des Subset-Sum-Problems für sie schwierig ist.

Bob verschlüsselt seine Nachricht dann als Summe s' einer Auswahl der b_i. Während Alice die Summe s' durch Kenntnis der mathematischen Operationen zu einer Summe s transformieren kann, für die sie zur Entschlüsselung der Nachricht nur das einfachere Subset-Sum-Problem für die superwachsende Folge a₁, ..., a_n lösen braucht, muss ein Angreifer mit der nicht superwachsenden Folge b₁, ..., b_n arbeiten.

Damit hätte ein Angreifer – so die Idee der Entwickler – ein NP-vollständiges Problem zu lösen, um das Verfahren zu brechen. Dass dies nicht stimmt und dass Merkle-Hellman-Knapsack unsicher ist, wurde 1982 von Adi Shamir [10] gezeigt. Die von Shamir ausgenutzte Schwachstelle ist die Tatsache, dass es auch für die abgeleitete Folge b₁, ..., b_n Algorithmen gibt, die das Subset-Sum-Problem effizient lösen. Folglich gehören die von Alice produzierten Instanzen zu einer Teilmenge von Instanzen des NP-vollständigen Problems, die einfach zu lösen sind.

Abb. 2: Angestrebte Situation

Der Wunsch war es, eine einfache Instanz (entspricht dem geheimen Schlüssel) durch die mathematischen Transformationen zu einer schweren Instanz (entspricht dem öffentlichen Schlüssel) umzuwandeln (vgl. Abb. 2). Die Rücktransformation ist dabei leicht, wenn man den geheimen Schlüssel besitzt. Bei Merkle-Hellman-Knapsack ist jedoch auch die transformierte Instanz effizient lösbar und damit das Verfahren unsicher (vgl. Abb. 3).

Abb. 3: Schwachstelle von Merkle-Hellman-Knapsack

NP-Vollständigkeit und Kryptographie

Das Fiasko mit Merkle-Hellman-Knapsack verdeutlicht die grundsätzlichen Schwierigkeiten bei der Verwendung von NP-vollständigen Problemen in der Public-Key-Kryptographie. Häufig ist die Grenze zwischen einfachen und schweren Instanzen nicht bekannt. Daher kann nur selten überprüft werden, ob eine erzeugte Instanz zu der Teilmenge der schweren Instanzen gehört oder nicht. Auch wenn gezeigt werden kann, dass die transformierten Instanzen alle Instanzen der Klasse erreichen, ist NP-Härte nur eine Aussage über den Worst-Case, was bedeutet: Es gibt Instanzen, die nur mit hohem Zeitaufwand zu lösen sind. Jedoch bräuchte man in der Kryptographie eine Aussage über den durchschnittlichen Fall (Average-Case); noch besser wäre die Aussage, dass sogar nur wenige Instanzen effizient lösbar sind.

Diese Problematik und das Scheitern von Merkle-Hellman-Knapsack führte schnell zur Frage, ob es überhaupt Verfahren geben kann, deren Sicherheit mit der Schwierigkeit der Lösung von NP-vollständigen Problemen äquivalent ist. Immerhin muss die Instanz ja so konstruiert werden, dass ein geheimer Schlüssel existiert, der es ermöglicht effizient zu entschlüsseln. Offen war, ob dies alleine schon die Existenz solcher Verfahren ausschließt.

Ein Theorem von Brassard aus dem Jahre 1979 führte lange Zeit zur Annahme, dass es solche algebraischen Verfahren nicht geben könne. Aus dem Theorem folgerte man irrtümlicherweise: "Wenn das Brechen eines Systems äquivalent zu dem Lösen eines NP-vollständigen Problems ist, dann ist NP = co-NP." Und das ist wiederum ähnlich unwahrscheinlich wie "NP = P" (vgl. Kasten). Erst im Jahre 1993 zeigten Neal Koblitz und Michael Fellows, dass die Folgerung nur für Verfahren mit ganz speziellen Eigenschaften gilt, aber nicht für alle Public-Key-Kryptoverfahren. Gleichzeitig stellten sie ein neues, allgemeines Verfahren vor, das auf NP-vollständigen Problemen basiert: Polly Cracker.

Polly Cracker

Fellows und Koblitz bezeichneten Polly Cracker [3] als ein allgemeines, kombinatorisch algebraisches Public-Key-Verfahren, weil man aus jedem NP-vollständigen Problem eine Instanz von Polly Cracker konstruieren kann. Deren Sicherheit bezüglich des geheimen Schlüssels, bewiesen sie, ist äquivalent zur Schwierigkeit der Lösung des NP-Problems selbst. Das liegt darin begründet, dass NP-vollständige Probleme sich immer durch multivariante, nicht-lineare algebraische Gleichungssysteme darstellen lassen. Dabei entspricht eine Lösung des NP-Problems genau einer Lösung eines assoziierten Gleichungssystems, oder anders ausgedrückt, einer Nullstelle von nicht-linearen Polynomen in vielen Variablen.

Das Verfahren Polly Cracker wird dann wie folgt durchgeführt. Alice beschreibt mit Polynomen f₁, ..., f_s ein NP-vollständiges Problem, von dem sie a priori eine Lösung per Konstruktion kennt. Dann ist ihr äquivalent auch eine Nullstelle x₀ der Polynome bekannt, somit gilt f_i(x₀) = 0 für alle Indizes i = 1, ..., s. Sie wählt dann die Folge der Polynome als öffentlichen Schlüssel und die Nullstelle als geheimen Schlüssel. Um nun eine Zahl a zu verschlüsseln, addiert Bob zu a ein Polynom f aus dem Ideal (f₁, ...,  f_s ) hinzu, d. h. f wird aus den Polynomen f₁, ..., f_s des öffentlichen Schlüssels erzeugt. Dieses Polynom f hat nun die Eigenschaft ebenfalls in der Nullstelle x₀ zu verschwinden. Daher setzt Alice beim Entschlüsseln des Geheimtextes f + a nur die Nullstelle x₀ in den Geheimtext ein und erhält den Klartext durch (f + a)(x₀) = f(x₀) + a = a. Obwohl bei Polly Cracker die Berechnung eines zum geheimen Schlüssel gleichwertigen Schlüssels äquivalent zur Konstruktion einer Lösung eines NP-vollständigen Problems ist, sind viele der konkreten Vorschläge für auf Polly Cracker basierende Verfahren gebrochen worden (z. B. EnRoot [1]). Die Schwäche liegt bei diesen Vorschlägen nicht in dem geheimen Schlüssel, sondern in der Verschlüsselung der Nachrichten, das heißt in der Wahl des Polynoms f.

Genau hier liegt gleichzeitig auch das Potenzial von Polly Cracker: Vom allgemeinen System kann man zeigen, dass es sehr sicher ist. Bei den gebrochenen Beispielen liegt es immer nur an der Ausführung der skizzierten Grundidee. Bislang gibt es zwei Varianten von Polly Cracker, die nicht gebrochen sind: Graph Perfect Code [3] und Polly Two [4]. Beide Verfahren sind aber relativ ineffizient, wenn man das Größenverhältnis von Klartext und Geheimtext betrachtet, die so genannte Nachrichtenexpansion.

McEliece

Ein weiteres interessantes algebraisches Public-Key-Verfahren mit Potenzial ist McEliece. Dieses wurde 1978 von R. McEliece [5] vorgestellt und verwendet Methoden der Codierungstheorie. Einen Bitstring zu kodieren bedeutet, ihn durch einen anderen, längeren Bitstring zu ersetzen, der Redundanz besitzt, damit er beim Auftreten von Fehlern korrigiert werden kann. Dabei sollte sowohl das Kodieren als auch das Dekodieren möglichst effizient durchführbar sein. Solche Mechanismen werden zum Beispiel bei CDs verwendet, um einzelne Bitfehler auszugleichen, die beim Pressen oder beim Lesen entstehen.

Eine wichtige Klasse von Codes sind dabei die linearen Codes. Diese sind durch drei Parameter n, k, t wie folgt charakterisiert: Ein Bitstring der Länge k wird in einen Bitstring der Länge n kodiert und beim Dekodieren erhält man den korrekten Bitstring zurück, wenn weniger als t Fehler aufgetreten sind. Mathematisch kann man solche Codes durch eine Matrix M mit n Zeilen und k Spalten darstellen.

Über das Dekodieren linearer Codes lässt sich beweisen, dass es sich um ein NP-vollständiges Problem handelt. Ähnlich wie beim Subset-Sum-Problem gilt das nicht für jede Instanz. Auch hier gibt es Codes, zu denen es effiziente Methoden für die Dekodierung gibt, beispielsweise Reed-Muller-Codes oder Goppa-Codes.

Um das Public-Key-Verfahren McEliece durchzuführen, startet Alice mit einem solchen effizient dekodierbaren Code M als geheimen Schlüssel. Dann verschleiert sie diesen durch mathematische Operationen, die auch Teil des geheimen Schlüssels sind (mathematisch gesehen besteht die Verschleierungsoperation aus einer Permutationsmatrix A und einer invertierbaren Matrix B und man setzt M' = A · M · B). Der resultierende Code M' bildet schließlich den öffentlichen Schlüssel.

Bob kodiert seinen Klartext a mit dem öffentlichen Schlüssel M' und verfälscht danach zusätzlich nicht mehr als t Bits. Für Alice ist es dann leicht, die mathematischen Operationen zur Verschleierung rückgängig zu machen und so den Geheimtext zu dekodieren, während ein Angreifer vor dem Problem steht, einen allgemeinen linearen Code dekodieren zu müssen.

Obwohl die Ver- und Entschlüsselung bei McEliece sehr schnell durchführbar ist und bislang nur wenige, sehr spezielle Angriffe bekannt sind, wird McEliece in der Praxis kaum verwendet. Ein Grund könnte darin liegen, dass der öffentliche Schlüssel, die Matrix M', mit ungefähr 64 Kilobytes sehr groß ist.

Hidden Field Equations

Ein weiterer bekannter Vertreter der multivarianten, algebraischen Public-Key-Verfahren ist das von J. Patarin 1995 entwickelte Hidden Field Equations System (HFE, [8], "versteckte körperdefinierende Gleichungen"). Hier startet Alice mit einer Abbildung f einer besonderen Struktur, zu der sie das Inverse kennt. Die Struktur ermöglicht ihr gleichzeitig, quadratische Polynome g₁, ..., g_n aus f herzuleiten, die genau f entsprechen, das heißt f(x) = (y₁, ..., y_n) und g₁(x) = y₁, ..., g_n(x) = y_n, wobei x und y_i Elemente von endlichen Körpern sind.

Diese quadratischen Polynome g₁, ..., g_n verschleiert Alice dann mit verschiedenen mathematischen Operationen zu quadratischen Polynomen h₁, ..., h_n, die den öffentlichen Schlüssel bilden. Der geheime Schlüssel besteht aus der Abbildung f und den Verschleierungsoperationen. Um nun eine Bitfolge a zu verschlüsseln, berechnet Bob z₁ = h₁(a), ..., z_n = h_n(a) und schickt (z₁, ..., z_n) an Alice. Die Entschlüsselung besteht aus der Umkehrung der Verschleierungsoperationen, wobei man aus (z₁, ..., z_n) einen Bitstring (y₁, ..., y_n) erhält, für den Alice den Klartext dann durch die Anwendung der Inversen, das heißt f⁻¹(y₁, ..., y_n) = a, berechnen kann.

Ein Angreifer steht vor der Aufgabe, ein quadratisches Gleichungssystem lösen zu müssen. Die Hoffnung der Entwickler von HFE ist hier, dass der Angreifer weder die Verschleierungsoperationen rückgängig machen kann, um das Polynom f zurückzugewinnen, noch das quadratische Gleichungssystem lösen kann. Denn auch schon das Lösen eines multivarianten, quadratischen Gleichungssystems im Allgemeinen ist NP-hart.

Doch ähnlich wie bei Merkle-Hellman-Knapsack scheint bei HFE der Pferdefuß darin zu liegen, dass die Verschleierungsmethoden vermutlich nur sehr spezielle Instanzen des NP-harten Problems liefern. Kürzlich wurde ein solches HFE-Gleichungssystem von Jean-Charles Faugère mithilfe eines ausgefeilten, an die Problemstellung angepassten Algorithmus gelöst. Nun wäre es interessant, auch mathematisch zu prüfen, ob HFE-Polynome im Allgemeinen genügend Struktur für erfolgreiche Angriffe enthalten.

Obwohl damit nicht bewiesen ist, dass alle Instanzen von HFE unsicher sind, fördert Faugères Angriff die Zweifel an der Sicherheit von HFE. Zudem ist bei HFE der öffentliche Schlüssel mit 28 Kilobyte sehr groß und die Entschlüsselung relativ langsam.

Fazit

Die Idee, NP-basierte, algebraische Verfahren in der Public-Key-Kryptographie zu verwenden, hat es schon in der Geburtsstunde der asymmetrischen Verschlüsselung gegeben. Sie ist einerseits äußerst reizvoll, da man hofft, Systeme entwickeln zu können, deren Sicherheit auf vermutlich schwereren Problemen basiert als dem Faktorisierungsproblem (RSA) oder dem Problem der Berechnung des diskreten Logarithmus (ECC). Andererseits hat die Vergangenheit gezeigt, dass man äußerst vorsichtig bei der Konstruktion vorgehen muss, um Sicherheitslücken zu vermeiden.

Darüber hinaus haben alle bislang entwickelten algebraischen Verfahren unattraktive Eigenschaften wie lange Schlüssel, hohe Nachrichtenexpansion oder langsame Ver- oder Entschlüsselung. Auch sind sie zumeist kompliziert zu implementieren, schwer zu verstehen und zu analysieren. Zudem sind sie noch zu wenig untersucht, und daher fehlt noch das Zutrauen in die Sicherheit der Verfahren. Angesichts der Bedrohung der heute verwendeten Verfahren RSA und ECC durch Quantencomputer sollte man aber algebraische Verfahren nicht aus den Augen verlieren. Vielleicht sind wir irgendwann auf sie angewiesen.

zurück zum Inhalt
© SecuMedia-Verlags-GmbH, 55205 Ingelheim (DE),
<kes> 2003^#4, Seite 35