McEliece-Kryptosystem

Robert McEliece entwickelte 1978 eines der ersten asymmetrischen Public-Key-Verfahren.

Dieses baut auf allgemeinen binären linearen fehlerkorrigierenden Codes auf und versteckt absichtlich Fehler in der Chiffre, um damit die Kryptoanalyse erheblich zu erschweren.

Die Idee ist es, einen allgemeinen fehlerkorrigierenden Code zu verwenden. Die Dekodierung solcher Codes ist ein NP-Problem. Allerdings gibt es bestimmte Code-Untergruppen, die eine Lösung in polynomialer Zeit ermöglichen, unter anderen die auch von diesem Algorithmus verwendeten Goppa-Codes.

Der Klartext wird also über eine Generator-Matrix in einen Goppa-Code umgewandelt. Dieser wird durch Multiplikation mit zufälligen weiteren Matrizen als allgemeiner linearer Code getarnt.

Ohne das Wissen der einzelnen zur Herstellung des Codes benutzter Matrizen, kann nun die Chiffre nicht mehr in den ursprünglichen Goppa-Code zurückverwandelt werden, also auch nicht mehr dekodiert werden.

Der öffentliche Schlüssel beinhaltet eine Generator-Matrix, mit welcher man den Klartext direkt in den oben beschriebenen, allgemeinen linearen Code umwandeln kann. Zusätzlich enthält der Schlüssel, wie viele Fehler anschließend maximal in die Chiffre eingebaut werden sollen, also wie viele Bits invertiert werden sollen.

Der geheime, private Schlüssel enthält die Information, wie man den allgemeinen linearen Code wieder in einen Goppa-Code zurückverwandeln kann, der anschließend performant dekodiert werden kann und somit die eingebauten Fehler wieder korrigiert.

Der Algorithmus teilt sich in die drei folgenden Hauptbestandteile auf: Die Schlüssel-Erzeugung, das Verschlüsseln und das Entschlüsseln.

Zusätzliche Informationen

Douglas Stinson schreibt in [St95] eine sehr gute Erklärung des McEliece-Kryptosystems mit einem Beispiel. Weitere empfehlenswerte Literatur zu diesem Thema ist in [Sch96] und [WiME05]. Eine kurze deutsche Einführung in dieses Thema findet man in [En06].