McEliece-Kryptosystem

Das McEliece-Kryptosystem i​st ein asymmetrischer Verschlüsselungsalgorithmus. Es w​urde 1978 v​om Kryptographen Robert J. McEliece vorgestellt.[1] Das Verfahren w​ird nur selten praktisch eingesetzt, d​a die Schlüssel große Matrizen sind; d​ie Beschreibung e​ines Schlüssels m​it einem Sicherheitsniveau v​on 128 Bit benötigt i​n der Größenordnung v​on 1 MB, über tausendmal m​ehr als vergleichbare RSA-Schlüssel. Jedoch i​st selbst u​nter Verwendung v​on Quantencomputern k​ein effizienter Algorithmus bekannt, d​er das McEliece-Kryptosystem brechen kann, w​as es z​u einem vielversprechenden Kandidaten für Post-Quanten-Kryptographie macht.

Verfahren

Erzeugung des öffentlichen und privaten Schlüssels

Die Erzeugung d​es öffentlichen u​nd des privaten Schlüssels funktioniert w​ie folgt.

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

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

Verschlüsseln von Nachrichten

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

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

Entschlüsseln von Nachrichten

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

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

Kryptographische Eigenschaften

Korrektheit

Es i​st leicht z​u sehen, d​ass Nachrichten i​mmer korrekt entschlüsselt werden. Nach d​em ersten Entschlüsselungsschritt h​at man

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

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

${\displaystyle c''=mSG}$, sowie ${\displaystyle c'''=mS}$,

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

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

als korrekte Entschlüsselung zurück.

Sicherheit

Unter der Learning-Parity-with-Noise-Annahme und der Annahme, dass ${\displaystyle {\hat {G}}}$ ununterscheidbar von zufällig ${\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 ${\displaystyle k}$ zu verschlüsseln, werden lediglich Nachrichten der Länge ${\displaystyle \beta k}$ für ein positives ${\displaystyle \beta <1}$, z. B. ${\displaystyle \beta ={\frac {9}{10}}}$ verwendet. Diese werden dann zufällig zu Nachrichten der Länge ${\displaystyle k}$ erweitert. Bei der Entschlüsselung werden am Ende diese Positionen einfach ignoriert.[2]

Reduktion der Schlüsselgröße

In der ursprünglichen Beschreibung des Verfahrens beträgt der Speicherbedarf für ${\displaystyle {\hat {G}}}$ etwa ${\displaystyle {\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 ${\displaystyle {\hat {G}}}$ durch das Gaußsche Eliminationsverfahren auf die Form ${\displaystyle {\tilde {G}}=(E_{k}|{\hat {G}}')}$ bringen, wobei ${\displaystyle E_{k}}$ die Einheitsmatrix der Dimension ${\displaystyle k}$ bezeichnet. Der Speicheraufwand für den öffentlichen Schlüssel sinkt dann auf ${\displaystyle {\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 ${\displaystyle {\tilde {G}}}$ verwendet. Für die Entschlüsselung verwendet man die parallel zur Normierung mitberechnete Matrix ${\displaystyle N}$ mit ${\displaystyle {\hat {G}}=N{\tilde {G}}}$, und multipliziert vor der Ausgabe der Nachricht noch von rechts mit ${\displaystyle N}$.

Quellen

1. 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 (pdf, 246kB).
2. 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 (pdf, 236kB).