McEliece-Kryptosystem

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.

VerfahrenBearbeiten

Erzeugung des öffentlichen und privaten SchlüsselsBearbeiten

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

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

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

Verschlüsseln von NachrichtenBearbeiten

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

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

Entschlüsseln von NachrichtenBearbeiten

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

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

Kryptographische EigenschaftenBearbeiten

KorrektheitBearbeiten

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.

SicherheitBearbeiten

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

Varianten des VerfahrensBearbeiten

Erreichen von IND-CPA SicherheitBearbeiten

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

Reduktion der SchlüsselgrößeBearbeiten

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

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  .

QuellenBearbeiten

  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).