McEliece-Kryptosystem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das McEliece-Kryptosystem ist ein asymmetrischer Verschlüsselungsalgorithmus. Es wurde 1978 vom Kryptographen Robert J. McEliece vorgestellt.[1]

Verfahren[Bearbeiten]

Erzeugung des öffentlichen und privaten Schlüssels[Bearbeiten]

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

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

Die derzeit empfohlenen Parameterwerte liegen zwischen (n,k,t)=(1702, 1219, 45) für das Jahr 2013, und (n,k,t)=(2804,2048,66) für Sicherheit bis zum Jahr 2050.[2]

Verschlüsseln von Nachrichten[Bearbeiten]

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, dh., 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[Bearbeiten]

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 weiters 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[Bearbeiten]

Korrektheit[Bearbeiten]

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 genau t Fehler korrigieren kann. Da S invertierbar ist, erhalten wir nun:

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

als korrekte Entschlüsselung zurück.

Sicherheit[Bearbeiten]

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[Bearbeiten]

Erreichen von IND-CPA Sicherheit[Bearbeiten]

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 mit zufällig zu Nachrichten der Länge k erweitert. Bei der Entschlüsselung werden am Ende diese Positionen einfach ignoriert.[3]

Reduktion der Schlüsselgröße[Bearbeiten]

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 253kB und 701kB, 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 72kB bis 189kB.

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[Bearbeiten]

  1.  Robert J. McEliece: A Public-Key Cryptosystem Based on Algebraic Coding Theory. In: Deep Space Network Progress Report. 42, Nr. 44, 1978, S. 114–116 (pdf, 246kB).
  2.  Robert Niebuhr, Mohammed Meziani, Stanislav Bulygin, Johannes Buchmann: Selecting parameters for secure McEliece-based Cryptosystems. In: International Journal of Information Security. 11, Nr. 3, Springer, 2012, S. 137–147, doi:10.1007/s10207-011-0153-2 (pdf, 393kB).
  3.  Ryo Nojima, Hideki Imai, Kazukuni Kobara, Kirill Morozov: Semantic Security for the McEliece Cryptosystem without Random Oracles. In: Designs, Codes and Cryptography. 49, Nr. 1–3, Springer, 2008, S. 289–305, doi:10.1007/s10623-008-9175-9 (pdf, 236kB).