McEliece-Kryptosystem
# 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$.

## Quellen

* ↑ Robert J. McEliece: A Public-Key Cryptosystem Based on Algebraic Coding Theory. In: Deep Space Network Progress Report. Band 42, Nr. 44, 1978, S. 114–116 (nasa.gov [PDF; 246 kB]).
* ↑ Rahmschmid, Claudia, Adams, David: McEliece Messaging: Smoke Crypto Chat - The first mobile McEliece-Messenger published as a stable prototype worldwide. Article TK Info Portal, 2023 (tarnkappe.info).
* ↑ Ryo Nojima, Hideki Imai, Kazukuni Kobara, Kirill Morozov: Semantic Security for the McEliece Cryptosystem without Random Oracles. In: Designs, Codes and Cryptography. Band 49, Nr. 1–3. Springer, 2008, S. 289–305, doi:10.1007/s10623-008-9175-9.
