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. Jedoch 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle P\in \{0,1\}^{n\times n}} .
• Man definiert Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {\hat {G}}=SGP} .

Der öffentliche Schlüssel besteht aus Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {\hat {G}}} , der private aus Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle c'''} .
• Letztlich berechnet man die Nachricht $m$ als Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat{G}=N\tilde{G}} , und multipliziert vor der Ausgabe der Nachricht noch von rechts mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} .