McEliece-Kryptosystem

Das McEliece-Kryptosystem ist ein asymmetrischer Verschlüsselungsalgorithmus. Es wurde 1978 vom Kryptographen Robert J. McEliece vorgestellt. Das Verfahren wird nur selten praktisch eingesetzt, da die Schlüssel große Matrizen sind; die Beschreibung eines Schlüssels mit einem Sicherheitsniveau von 128 Bit benötigt in der Größenordnung von 1 MB, über tausendmal mehr als vergleichbare RSA-Schlüssel. Eine erste Implementierung im Bereich der angewandten Kryptographie erfolgte seit 2017 mit vier verschiedenen Moduli in dem quell-offenenen Instant Messenger Smoke. Es ist selbst unter Verwendung von Quantencomputern kein effizienter Algorithmus bekannt, der das McEliece-Kryptosystem brechen kann, was es zu einem vielversprechenden Kandidaten für Post-Quanten-Kryptographie macht.

Verfahren

Erzeugung des öffentlichen und privaten Schlüssels

Die Erzeugung des öffentlichen und des privaten Schlüssels funktioniert wie folgt.

• Man wählt einen $(n,k,t)$-Goppa Code mit Generatormatrix $G$.
• Weiter wählt man eine invertierbare Matrix $S\in \{0,1\}^{k\times k}$ und eine Permutationsmatrix $P\in \{0,1\}^{n\times n}$.
• Man definiert ${\hat {G}}=SGP$.

Der öffentliche Schlüssel besteht aus ${\hat {G}}$, der private aus $(S,G,P)$.

Verschlüsseln von Nachrichten

Um eine Nachricht $m\in \{0,1\}^{k}$ zu verschlüsseln, verfährt man wie folgt:

• Man wählt $z\in \{0,1\}^{n}$ zufällig mit Hamming-Gewicht $t$, d. h., genau $t$ Koordinaten von $z$ sind 1 und alle anderen sind 0.
• Man berechnet den Schlüsseltext als $c=m{\hat {G}}+z$.

Entschlüsseln von Nachrichten

Um einen Schlüsseltext $c$ zu entschlüsseln, verfährt man folgermaßen:

• Man berechnet $c'=cP^{-1}$.
• Mittels der fehlerkorrigierenden Eigenschaften des verwendeten Goppa-Codes berechnet man weiter das zu $c'$ nächstgelegene Codewort $c''$ und das nächstgelegene Nachrichtenwort $c'''$.
• Letztlich berechnet man die Nachricht $m$ als $m=c'''S^{-1}$.

Kryptographische Eigenschaften

Korrektheit

Es ist leicht zu sehen, dass Nachrichten immer korrekt entschlüsselt werden. Nach dem ersten Entschlüsselungsschritt hat man

$c'=cP^{-1}=(m{\hat {G}}+z)P^{-1}=mSG+zP^{-1}$.

Da $P$ eine Permutation ist, hat $zP^{-1}$ noch immer Hamming-Gewicht $t$, und daher erhält man nach dem zweiten Entschlüsselungsschritt:

$c''=mSG$, sowie $c'''=mS$,

da der verwendete Goppa-Code bis zu $t$ Fehler korrigieren kann. Da $S$ invertierbar ist, erhalten wir nun:

$c'''S^{-1}=m$

als korrekte Entschlüsselung zurück.

Sicherheit

Unter der Learning-Parity-with-Noise-Annahme und der Annahme, dass ${\hat {G}}$ ununterscheidbar von zufällig $k\times n$ Matrizen ist, besitzt das Verfahren die Einwegeigenschaft.

Varianten des Verfahrens

Erreichen von IND-CPA Sicherheit

2008 wurde gezeigt, dass eine kleine Änderung des Verfahrens zu einem IND-CPA-sicheren Verschlüsselungsverfahren führt. Anstatt bei der Verschlüsselung eine Nachricht der Länge $k$ zu verschlüsseln, werden lediglich Nachrichten der Länge $\beta k$ für ein positives $\beta <1$, z. B. $\beta ={\frac {9}{10}}$ verwendet. Diese werden dann zufällig zu Nachrichten der Länge $k$ erweitert. Bei der Entschlüsselung werden am Ende diese Positionen einfach ignoriert.

Reduktion der Schlüsselgröße

In der ursprünglichen Beschreibung des Verfahrens beträgt der Speicherbedarf für ${\hat {G}}$ etwa ${\frac {kn}{8\cdot 1024}}$kB. Für die empfohlenen Parameter resultiert dies in Schlüsselgrößen zwischen 253 kB und 701 kB, was in der Praxis oft als zu groß angesehen wird. Alternativ kann man die Matrix ${\hat {G}}$ durch das Gaußsche Eliminationsverfahren auf die Form ${\tilde {G}}=(E_{k}|{\hat {G}}')$ bringen, wobei $E_{k}$ die Einheitsmatrix der Dimension $k$ bezeichnet. Der Speicheraufwand für den öffentlichen Schlüssel sinkt dann auf ${\frac {k(n-k)}{8\cdot 1024}}$, oder für die gegebenen Parameter auf 72 kB bis 189 kB.

Für die Verschlüsselung wird nun einfach ${\tilde {G}}$ verwendet. Für die Entschlüsselung verwendet man die parallel zur Normierung mitberechnete Matrix $N$ mit ${\hat {G}}=N{\tilde {G}}$, und multipliziert vor der Ausgabe der Nachricht noch von rechts mit $N$.