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

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

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

  • Man wählt einen -Goppa Code mit Generatormatrix .
  • Weiters wählt man eine invertierbare Matrix und eine Permutationsmatrix .
  • Man definiert .

Der öffentliche Schlüssel besteht aus , der private aus .

Die derzeit empfohlenen Parameterwerte liegen zwischen für das Jahr 2013, und für Sicherheit bis zum Jahr 2050.[2]

Verschlüsseln von Nachrichten[Bearbeiten | Quelltext bearbeiten]

Um eine Nachricht zu verschlüsseln, verfährt man wie folgt:

  • Man wählt zufällig mit Hamming-Gewicht , dh., genau Koordinaten von sind 1 und alle anderen sind 0.
  • Man berechnet den Schlüsseltext als .

Entschlüsseln von Nachrichten[Bearbeiten | Quelltext bearbeiten]

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

  • Man berechnet .
  • Mittels der fehlerkorrigierenden Eigenschaften des verwendeten Goppa-Codes berechnet man weiters das zu nächstgelegene Codewort und das nächstgelegene Nachrichtenwort .
  • Letztlich berechnet man die Nachricht als .

Kryptographische Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Korrektheit[Bearbeiten | Quelltext bearbeiten]

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

.

Da eine Permutation ist, hat noch immer Hamming-Gewicht , und daher erhält man nach dem zweiten Entschlüsselungsschritt:

, sowie ,

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

als korrekte Entschlüsselung zurück.

Sicherheit[Bearbeiten | Quelltext bearbeiten]

Unter der Learning Parity with Noise-Annahme und der Annahme, dass ununterscheidbar von zufällig Matrizen ist, besitzt das Verfahren die Einwegeigenschaft.

Varianten des Verfahrens[Bearbeiten | Quelltext bearbeiten]

Erreichen von IND-CPA Sicherheit[Bearbeiten | Quelltext 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 zu verschlüsseln, werden lediglich Nachrichten der Länge für ein positives , z.B. verwendet. Diese werden dann mit zufällig zu Nachrichten der Länge erweitert. Bei der Entschlüsselung werden am Ende diese Positionen einfach ignoriert.[3]

Reduktion der Schlüsselgröße[Bearbeiten | Quelltext bearbeiten]

In der ursprünglichen Beschreibung des Verfahrens beträgt der Speicherbedarf für etwa 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 durch das Gaußsche Eliminationsverfahren auf die Form bringen, wobei die Einheitsmatrix der Dimension bezeichnet. Der Speicheraufwand für den öffentlichen Schlüssel sinkt dann auf , oder für die gegebenen Parameter auf 72kB bis 189kB.

Für die Verschlüsselung wird nun einfach verwendet. Für die Entschlüsselung verwendet man die parallel zur Normierung mitberechnete Matrix mit , und multipliziert vor der Ausgabe der Nachricht noch von rechts mit .

Quellen[Bearbeiten | Quelltext bearbeiten]

  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. Robert Niebuhr, Mohammed Meziani, Stanislav Bulygin, Johannes Buchmann: Selecting parameters for secure McEliece-based Cryptosystems. In: International Journal of Information Security. Band 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. Band 49, Nr. 1–3. Springer, 2008, S. 289–305, doi:10.1007/s10623-008-9175-9 (pdf, 236kB).