Classic McEliece: Der unbequeme Veteran der Post-Quantum-Kryptografie

Einführung

Wer über Post-Quanten-Kryptografie spricht, landet fast immer bei denselben Namen: ML-KEM, ML-DSA, SLH-DSA. Diese NIST-Standards sind frisch verabschiedet, modern und basieren größtenteils auf Gitterproblemen. Sie sind die Gegenwart, und daran wird sich so bald nichts ändern.

Und dann gibt es Classic McEliece.

Robert McEliece stellte das Verfahren 1978 vor. Von „Post-Quanten“ sprach damals noch niemand, Quantencomputer gab es nur auf dem Papier, und das Internet trug noch nicht einmal seinen heutigen Namen. Seitdem haben Dutzende Forschungsarbeiten versucht, es zu brechen, und keiner ist es gelungen. In mehr als 45 Jahren hat sich die Sicherheitsmarge gegenüber klassischen Angriffen um weniger als ein Prozent verschoben.

Das ist kein Marketing, sondern die dokumentierte Geschichte des Verfahrens.

Classic McEliece ist nicht der glamouröseste Algorithmus der PQC-Welt. Seine öffentlichen Schlüssel sind riesig, je nach Parametersatz zwischen 261 KB und 1,35 MB, und Kritiker nennen das meist als Erstes. Wer aber nur auf die Schlüsselgröße schaut, übersieht das Wesentliche. Classic McEliece ist der konservativste und am längsten untersuchte KEM der Post-Quanten-Kryptografie, und Sicherheitsbehörden empfehlen ihn ausdrücklich, darunter das BSI in seiner TR-02102-1 (Januar 2026) und die niederländische NLNCSA.

Warum er trotzdem relevant ist, und vielleicht gerade deshalb, sehen wir uns in diesem Artikel genauer an.

Deep Dive

Das Fundament: Fehlerkorrigierende Codes als Sicherheitsbasis

Um Classic McEliece zu verstehen, braucht es einen kurzen Ausflug in die Kodierungstheorie. Dieser Bereich der Mathematik wurde ursprünglich für ein ganz anderes Problem entwickelt: Daten zuverlässig über verrauschte Kanäle zu übertragen.

Die Grundidee ist, einer Nachricht gezielt redundante Information hinzuzufügen, einen sogenannten Code. Der Empfänger kann dann Übertragungsfehler erkennen und korrigieren, selbst wenn unterwegs einige Bits verfälscht wurden. Die theoretischen Grundlagen dafür legte Claude Shannon 1948. Robert McEliece stellte 1978 eine andere Frage: Was, wenn man diese Struktur nicht zur Fehlerkorrektur nutzt, sondern zur Verschlüsselung?

Classic McEliece beruht darauf, dass sich ein zufälliger linearer Code im Allgemeinen nur extrem schwer dekodieren lässt. Die besten bekannten Angriffe gehören zu einer Familie namens Information-Set Decoding (ISD). Wer die geheime mathematische Struktur nicht kennt, steht vor einem Problem, das auch Quantencomputer nicht effizient lösen können. Der Grover-Algorithmus bringt nur eine quadratische Beschleunigung, die sich mit moderat größeren Schlüsseln ausgleichen lässt.

Der private Schlüssel ist genau diese versteckte Struktur: ein binärer Goppa-Code, der sich effizient dekodieren lässt. Der öffentliche Schlüssel verrät, dass es einen Code gibt, aber nicht, welchen.

Schlüsselerzeugung: Das Herzstück des Systems

Ein Goppa-Code wird durch zwei Komponenten festgelegt.

Die erste ist ein monisches irreduzibles Polynom g vom Grad t über einem endlichen Körper $\mathbb{F}_{2^m}$. Irreduzibel heißt, dass sich das Polynom nicht in einfachere Faktoren zerlegen lässt, ähnlich wie eine Primzahl nicht in kleinere Faktoren.

Die zweite ist eine Folge α von n paarweise verschiedenen Elementen aus demselben Körper.

Aus diesen beiden Komponenten ergibt sich eine Paritätsprüfmatrix H. Der öffentliche Schlüssel ist diese Matrix in systematischer Form (I ∣ T), wobei I eine Einheitsmatrix ist und T der Teil, der tatsächlich veröffentlicht wird.

Ein technisches Detail betrifft die „f“-Varianten wie mceliece8192128f. Sie verwenden eine semi-systematische Form, durch die die Schlüsselerzeugung zuverlässiger gelingt und schneller abläuft. Für Implementierungen, die viele Schlüsselpaare erzeugen müssen, ist das relevant.

Der private Schlüssel hat eine nützliche Eigenschaft, die oft übersehen wird. Er lässt sich auf einen Seed von 32 bis 40 Bytes komprimieren, aus dem sich alle nötigen Polynome und Matrizen deterministisch rekonstruieren lassen. Neben dem riesigen öffentlichen Schlüssel ist das ein echter praktischer Vorteil.

Kapselung: Ein Syndrom statt Verschlüsselung

Die Kapselung funktioniert grundlegend anders, als man es von RSA oder elliptischen Kurven kennt. Es wird kein Schlüssel verpackt und verschickt. Stattdessen läuft Folgendes ab:

1. Der Sender erzeugt einen zufälligen Fehlervektor e der Länge n mit einem Hamming-Gewicht von genau t. e enthält also genau t Einsen, alle anderen Stellen sind null.
2. Der Ciphertext ist C=He, das Produkt aus der öffentlichen Paritätsprüfmatrix und dem Fehlervektor. In der Kodierungstheorie heißt dieses Ergebnis das Syndrom von e.
3. Der Sitzungsschlüssel K wird durch Hashen von e und C abgeleitet.

Ohne den privaten Goppa-Code ist es praktisch nicht machbar, aus dem Syndrom C den Fehlervektor e zu rekonstruieren, und damit auch nicht den Sitzungsschlüssel. Genau hier greift das oben beschriebene Dekodierungsproblem.

Entkapselung: Deterministisch und fehlerfrei

Der Empfänger nutzt g und α aus seinem privaten Schlüssel, um den Goppa-Dekodieralgorithmus anzuwenden. So rekonstruiert er e aus C und leitet denselben Sitzungsschlüssel K ab.

Classic McEliece ist deterministisch und scheitert bei gültigen Ciphertexten nie an der Entschlüsselung. Bei gitterbasierten Verfahren ist das anders: ML-KEM hat eine winzige, aber von null verschiedene Fehlerwahrscheinlichkeit, die durch sorgfältig gewählte Parameter vernachlässigbar klein gehalten wird. Classic McEliece hat dieses Problem schlicht nicht.

Sicherheitsanalyse: Jahrzehnte der Kryptoanalyse

Die Sicherheit von Classic McEliece stützt sich auf drei Säulen.

Eine stabile Härteannahme: Seit 1978 haben alle Verbesserungen an ISD-Angriffen zusammen die nötige Schlüsselgröße für ein bestimmtes Sicherheitsniveau um weniger als ein Prozent verändert. Das ist bemerkenswert stabil. Gitterbasierte Verfahren wie ML-KEM gibt es in ihrer modernen Form dagegen erst seit den frühen 2000er-Jahren, ihre langfristige Sicherheitsmarge ist entsprechend weniger erprobt.

Quantenresistenz: Der Grover-Algorithmus reduziert die Angriffskomplexität asymptotisch auf ihre Quadratwurzel. Bei Classic McEliece 8192128, dem Parametersatz mit dem höchsten Sicherheitsniveau, ist das in der Wahl der Schlüsselgröße bereits berücksichtigt.

IND-CCA2-Sicherheit: Dank der KEM-Konstruktion ist das Verfahren gegen adaptive Chosen-Ciphertext-Angriffe geschützt, das stärkste in der Praxis relevante Angreifermodell.

Stärken, Schwächen und ein unbequemer Kompromiss

Jede kryptografische Entscheidung ist ein Abwägen, und an Classic McEliece sieht man das deutlicher als an den meisten anderen Verfahren.

Was Classic McEliece gut kann

Die Ciphertexte sind winzig, je nach Parametersatz zwischen 128 und 208 Bytes, und passen problemlos in ein einzelnes Netzwerkpaket. Werden viele Nachrichten mit demselben Schlüsselpaar ausgetauscht, rechnet sich die Übertragung des großen öffentlichen Schlüssels schnell.

Außerdem ist das Verfahren sehr hardwarefreundlich. Weil es auf binären Matrixoperationen basiert, läuft es auf FPGAs extrem schnell, was für eingebettete Systeme und Hardware-Sicherheitsmodule den Ausschlag geben kann.

Die offensichtliche Schwäche

Die öffentlichen Schlüssel sind groß. Sehr groß: 261 KB bei mceliece348864 und bis zu 1,35 MB bei mceliece8192128. Deshalb passt Classic McEliece schlecht zu Protokollen wie TLS. Ein Handshake, der einen öffentlichen Schlüssel von mehr als einem Megabyte übertragen muss, skaliert einfach nicht.

Ein häufig diskutierter Ausweg ist das Zwischenspeichern öffentlicher Schlüssel. ISPs oder Netzwerkinfrastruktur könnten sie vorhalten und nur noch die kompakten Ciphertexte übertragen. In kontrollierten Umgebungen funktioniert das, macht Classic McEliece aber zu einem Verfahren für bestimmte Einsatzszenarien und nicht zu einem allgemeinen Ersatz für klassische KEMs.

Standardisierungsstatus: Warum Classic McEliece trotzdem zählt

Das NIST hat Classic McEliece nicht als finalen Standard ausgewählt, sondern zur weiteren Prüfung in eine vierte Runde geschickt. Das klingt nach einer Niederlage, ist bei genauerem Hinsehen aber differenzierter.

Das BSI führt das Verfahren in seiner Technischen Richtlinie TR-02102-1 als empfohlenen Algorithmus. Die niederländische NLNCSA empfiehlt es ausdrücklich für Anwendungen, bei denen maximale Sicherheit wichtiger ist als Effizienz. Zudem hat das Team hinter Classic McEliece einen Vorschlag zur ISO-Standardisierung (ISO/IEC 18033-2) eingereicht, und die ISO hat ein vorläufiges Arbeitsprojekt für PQC-KEMs genehmigt, das Classic McEliece ausdrücklich einschließt.

Im PQC-Ökosystem dient Classic McEliece als Sicherheitsanker. Gitterbasierte Verfahren beruhen auf verwandten mathematischen Grundlagen, eine strukturelle Schwäche in einem von ihnen könnte also auch die anderen treffen. Codebasierte Kryptografie steht dagegen auf einem völlig anderen mathematischen Fundament. Ein Angriff, der ML-KEM bricht, würde Classic McEliece nicht berühren.

Das ist keine rein theoretische Sorge, sondern das Prinzip der kryptografischen Diversifikation. Aus demselben Grund setzen wir heute hybride Verfahren ein, statt uns auf einen einzigen Algorithmus zu verlassen.

Fazit: Der unbequeme Veteran hat seinen Platz

Classic McEliece passt nicht zu jedem Anwendungsfall. Wer TLS-Handshakes oder ressourcenschwache IoT-Geräte absichern will, findet bessere Optionen. Die Schlüsselgrößen sind ein echter Nachteil, und daran führt kein Weg vorbei.

Wer aber konservative, gut erprobte Sicherheit braucht, etwa für langlebige Daten, kritische Infrastrukturen oder Szenarien, in denen Bandbreite weniger zählt als kryptografische Vorsicht, ist mit Classic McEliece gut bedient. Das Verfahren hat mehr als 45 Jahre Kryptoanalyse überstanden, ohne dass eine einzige strukturelle Schwäche gefunden wurde.

Diese Bilanz muss man erst einmal schlagen.