12.5 Das McEliece-Verfahren
Ein wichtiger Aspekt, den wir bisher außen vor gelassen haben (und den wir auch hier nur indirekt streifen), ist die Frage nach einer effizienten Kodierungs- bzw. Dekodierungsfunktion für einen Code. Je nach Anzahl der Codewörter ist es sicherlich unpraktikabel, ein empfangenes Wort mit jedem Codewort zu vergleichen und dasjenige mit minimalem Hammingabstand herauszusuchen. Wenn man nur irgendeine Erzeugermatrix \(G\) eines Codes kennt, sind die Möglichkeiten der schnellen Dekodierung (bei großen Codes) eingeschränkt. Das Kodieren geht aber relativ schnell, weil man hierzu nur ein Matrizenprodukt der Form \(wG\) (für ein zu versendendes Wort \(w\)) berechnen muss.
Dass es Codes gibt, bei denen es auch für große Codes schnelle Dekodierfunktionen gibt (zum Beispiel die sogenannten Goppa-Codes) macht sich das Verschlüsselungsverfahren von Robert McEliece zu Nutze, das wir hier skizzieren wollen. Es handelt sich um ein Public-Key-Verfahren, das auf Kodierungstheorie und Linearer Algebra basiert. Eine Besonderheit ist, dass es nach jetzigem Kenntnisstand nicht anfällig ist für Angriffe mit Quantencomputern (anders als die meisten Verfahren, die momentan gängig sind). Ein Nachteil ist, dass die Schlüssel, die man dafür speichern und versenden muss, relativ groß sind.
Unter einem Public-Key-Verfahren versteht man ein Verschlüsselungsverfahren, bei dem die spätere Empfänger∗in einer verschlüsselten Nachricht alle Informationen, die die Absender∗in der Nachricht zum Verschlüsseln benötigt, öffentlich zur Verfügung stellen kann (insbesondere könnte man diese Informationen über Kanäle verschicken, die von anderen abgehört werden können). Dieser »Public Key« muss natürlich die Eigenschaft haben, dass er zwar das Verschlüsseln, jedoch nicht das Entschlüsseln einer Nachricht erlaubt.
Die Empfängerin der verschlüsselten Nachricht, die wir wie in der Kryptographie üblich Alice nennen wollen, wählt die folgenden Informationen. Diese bilden den privaten Schlüssel, den sie geheim hält.
Einen (geeigneten) linearen \([n, k]\)-Code \(C\) über \(\mathbb F_2\), der bis zu \(t\) Fehler korrigieren kann. (Damit das Verfahren sicher ist, werden Werte von \(n=2048\), \(k=1751\), \(t=27\) empfohlen; für Sicherheit gegen Quantencomputerangriffe noch höhere Werte.) Sie wählt den Code so, dass sie eine schnelle Dekodierfunktion kennt. Sei \(G\) eine Erzeugermatrix dieses Codes in Standardform.
Alice wählt außerdem eine invertierbare Matrix \(S\in GL_k(\mathbb F_2)\) und eine Permutationsmatrix \(P\in GL_n(\mathbb F_2)\). Sie berechnet das Matrizenprodukt \(G^\prime :=SGP\) und veröffentlicht dann den folgenden
Während die Matrix \(G\) (in Standardform) in der Regel Rückschlüsse darauf zulassen wird, aus welcher Familie von Codes Alice ihren Code gewählt hat, und damit auf eine effektive Dekodierfunktion, ist das für die Matrix \(G^\prime \) nicht der Fall.
Bob, der Alice eine Nachricht schicken möchte, schreibt seine Nachricht im Klartext als Folge von Wörtern \(m\in \mathbb F_2^k\). Für jedes \(m\) bildet er \(c^\prime := m G^\prime \) (die »regulär« mit dem Code mit Erzeugermatrix \(G^\prime \) kodierte Nachricht), wählt zufällig ein Element \(z\in \mathbb F_2^n\) mit \(t\) Einsen und \(n-t\) Nullen, und schickt Alice die Nachricht \(c:= c^\prime +z\). Es werden durch die Addition von \(z\) also künstlich \(t\) Fehler eingefügt.
Alice berechnet aus \(c\) das Word \(cP^{-1} (= c^\prime P^{-1} + zP^{-1})\). Da \(P\) eine Permutationsmatrix ist, unterscheidet sich dieses Wort an genau \(t\) Stellen von \(mSG\). Mit der Dekodierfunktion für den Code mit Erzeugermatrix \(G\) kann Alice daraus \(mS\) berechnen, und findet damit die ursprüngliche Nachricht als \(m = (mS)S^{-1}\).
Die Sicherheit des Verfahrens beruht darauf, dass die Werte \(n\), \(k\) und \(t\) so gewählt werden, dass die Berechnung von \(m\) aus \(mG^\prime +z\) nicht in akzeptabler Zeit möglich ist. (Die Durchführbarkeit beruht darauf, dass es eben doch möglich ist, wenn man die zusätzlichen strukturellen Informationen kennt, die Alice zur Hand hat.)
Weitere Informationen: Wikipedia (English)