www.wikidata.de-de.nina.az

McEliece Kryptosystem Das ist ein asymmetrischer Verschlüsselungsalgorithmus Es wurde 1978 vom Kryptographen Robert J Mc

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. Eine erste Implementierung im Bereich der angewandten Kryptographie erfolgte seit 2017 mit vier verschiedenen Moduli in dem quell-offenenen Instant Messenger Smoke. Es 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

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 , der private aus .

Verschlüsseln von Nachrichten Bearbeiten

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 Nachrichten 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 weiter das zu nächstgelegene Codewort und das nächstgelegene Nachrichtenwort .
  • Letztlich berechnet man die Nachricht als .

Kryptographische Eigenschaften Bearbeiten

Korrektheit 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:

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

als korrekte Entschlüsselung zurück.

Sicherheit 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

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

Reduktion der Schlüsselgröße 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 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 .

Quellen 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 (nasa.gov [PDF; 246 kB]).
  2. Rahmschmid, Claudia, Adams, David: McEliece Messaging: Smoke Crypto Chat - The first mobile McEliece-Messenger published as a stable prototype worldwide. Article TK Info Portal, 2023 (tarnkappe.info).
  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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das McEliece Kryptosystem ist ein asymmetrischer Verschlusselungsalgorithmus Es wurde 1978 vom Kryptographen Robert J McEliece vorgestellt 1 Das Verfahren wird nur selten praktisch eingesetzt da die Schlussel grosse Matrizen sind die Beschreibung eines Schlussels mit einem Sicherheitsniveau von 128 Bit benotigt in der Grossenordnung von 1 MB uber tausendmal mehr als vergleichbare RSA Schlussel Eine erste Implementierung im Bereich der angewandten Kryptographie erfolgte seit 2017 mit vier verschiedenen Moduli in dem quell offenenen Instant Messenger Smoke 2 Es ist selbst unter Verwendung von Quantencomputern kein effizienter Algorithmus bekannt der das McEliece Kryptosystem brechen kann was es zu einem vielversprechenden Kandidaten fur Post Quanten Kryptographie macht Inhaltsverzeichnis 1 Verfahren 1 1 Erzeugung des offentlichen und privaten Schlussels 1 2 Verschlusseln von Nachrichten 1 3 Entschlusseln von Nachrichten 2 Kryptographische Eigenschaften 2 1 Korrektheit 2 2 Sicherheit 3 Varianten des Verfahrens 3 1 Erreichen von IND CPA Sicherheit 3 2 Reduktion der Schlusselgrosse 4 QuellenVerfahren BearbeitenErzeugung des offentlichen und privaten Schlussels Bearbeiten Die Erzeugung des offentlichen und des privaten Schlussels funktioniert wie folgt Man wahlt einen n k t displaystyle n k t nbsp Goppa Code mit Generatormatrix G displaystyle G nbsp Weiter wahlt man eine invertierbare Matrix S 0 1 k k displaystyle S in 0 1 k times k nbsp und eine Permutationsmatrix P 0 1 n n displaystyle P in 0 1 n times n nbsp Man definiert G S G P displaystyle hat G SGP nbsp Der offentliche Schlussel besteht aus G displaystyle hat G nbsp der private aus S G P displaystyle S G P nbsp Verschlusseln von Nachrichten Bearbeiten Um eine Nachricht m 0 1 k displaystyle m in 0 1 k nbsp zu verschlusseln verfahrt man wie folgt Man wahlt z 0 1 n displaystyle z in 0 1 n nbsp zufallig mit Hamming Gewicht t displaystyle t nbsp d h genau t displaystyle t nbsp Koordinaten von z displaystyle z nbsp sind 1 und alle anderen sind 0 Man berechnet den Schlusseltext als c m G z displaystyle c m hat G z nbsp Entschlusseln von Nachrichten Bearbeiten Um einen Schlusseltext c displaystyle c nbsp zu entschlusseln verfahrt man folgermassen Man berechnet c c P 1 displaystyle c cP 1 nbsp Mittels der fehlerkorrigierenden Eigenschaften des verwendeten Goppa Codes berechnet man weiter das zu c displaystyle c nbsp nachstgelegene Codewort c displaystyle c nbsp und das nachstgelegene Nachrichtenwort c displaystyle c nbsp Letztlich berechnet man die Nachricht m displaystyle m nbsp als m c S 1 displaystyle m c S 1 nbsp Kryptographische Eigenschaften BearbeitenKorrektheit Bearbeiten Es ist leicht zu sehen dass Nachrichten immer korrekt entschlusselt werden Nach dem ersten Entschlusselungsschritt hat man c c P 1 m G z P 1 m S G z P 1 displaystyle c cP 1 m hat G z P 1 mSG zP 1 nbsp Da P displaystyle P nbsp eine Permutation ist hat z P 1 displaystyle zP 1 nbsp noch immer Hamming Gewicht t displaystyle t nbsp und daher erhalt man nach dem zweiten Entschlusselungsschritt c m S G displaystyle c mSG nbsp sowie c m S displaystyle c mS nbsp da der verwendete Goppa Code bis zu t displaystyle t nbsp Fehler korrigieren kann Da S displaystyle S nbsp invertierbar ist erhalten wir nun c S 1 m displaystyle c S 1 m nbsp als korrekte Entschlusselung zuruck Sicherheit Bearbeiten Unter der Learning Parity with Noise Annahme und der Annahme dass G displaystyle hat G nbsp ununterscheidbar von zufallig k n displaystyle k times n nbsp Matrizen ist besitzt das Verfahren die Einwegeigenschaft Varianten des Verfahrens BearbeitenErreichen von IND CPA Sicherheit Bearbeiten 2008 wurde gezeigt dass eine kleine Anderung des Verfahrens zu einem IND CPA sicheren Verschlusselungsverfahren fuhrt Anstatt bei der Verschlusselung eine Nachricht der Lange k displaystyle k nbsp zu verschlusseln werden lediglich Nachrichten der Lange b k displaystyle beta k nbsp fur ein positives b lt 1 displaystyle beta lt 1 nbsp z B b 9 10 displaystyle beta frac 9 10 nbsp verwendet Diese werden dann zufallig zu Nachrichten der Lange k displaystyle k nbsp erweitert Bei der Entschlusselung werden am Ende diese Positionen einfach ignoriert 3 Reduktion der Schlusselgrosse Bearbeiten In der ursprunglichen Beschreibung des Verfahrens betragt der Speicherbedarf fur G displaystyle hat G nbsp etwa k n 8 1024 displaystyle frac kn 8 cdot 1024 nbsp kB Fur die empfohlenen Parameter resultiert dies in Schlusselgrossen zwischen 253 kB und 701 kB was in der Praxis oft als zu gross angesehen wird Alternativ kann man die Matrix G displaystyle hat G nbsp durch das Gausssche Eliminationsverfahren auf die Form G E k G displaystyle tilde G E k hat G nbsp bringen wobei E k displaystyle E k nbsp die Einheitsmatrix der Dimension k displaystyle k nbsp bezeichnet Der Speicheraufwand fur den offentlichen Schlussel sinkt dann auf k n k 8 1024 displaystyle frac k n k 8 cdot 1024 nbsp oder fur die gegebenen Parameter auf 72 kB bis 189 kB Fur die Verschlusselung wird nun einfach G displaystyle tilde G nbsp verwendet Fur die Entschlusselung verwendet man die parallel zur Normierung mitberechnete Matrix N displaystyle N nbsp mit G N G displaystyle hat G N tilde G nbsp und multipliziert vor der Ausgabe der Nachricht noch von rechts mit N displaystyle N nbsp Quellen Bearbeiten 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 nasa gov PDF 246 kB Rahmschmid Claudia Adams David McEliece Messaging Smoke Crypto Chat The first mobile McEliece Messenger published as a stable prototype worldwide Article TK Info Portal 2023 tarnkappe info 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 Abgerufen von https de wikipedia org w index php title McEliece Kryptosystem amp oldid 238938146