McEliece-Kryptosystem

Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:

Korrektheit: 1
(nur rudimäntär überprüft)

Umfang: 4
(unwichtige Fakten fehlen)

Quellenangaben: 5
(vollständig vorhanden)

Quellenarten: 4
(sehr gut)

Konformität: 4
(sehr gut)

Robert McEliece entwickelte 1978 eines der ersten asymmetrischen Public-Key-Verfahren.

Dieses baut auf allgemeinen binären linearen fehlerkorrigierenden Codes auf und versteckt absichtlich Fehler in der Chiffre, um damit die Kryptoanalyse erheblich zu erschweren.

Die Idee ist es, einen allgemeinen fehlerkorrigierenden Code zu verwenden. Die Dekodierung solcher Codes ist ein NP-Problem. Allerdings gibt es bestimmte Code-Untergruppen, die eine Lösung in polynomialer Zeit ermöglichen, unter anderen die auch von diesem Algorithmus verwendeten Goppa-Codes.

Der Klartext wird also über eine Generator-Matrix in einen Goppa-Code umgewandelt. Dieser wird durch Multiplikation mit zufälligen weiteren Matrizen als allgemeiner linearer Code getarnt.

Ohne das Wissen der einzelnen zur Herstellung des Codes benutzter Matrizen, kann nun die Chiffre nicht mehr in den ursprünglichen Goppa-Code zurückverwandelt werden, also auch nicht mehr dekodiert werden.

Der öffentliche Schlüssel beinhaltet eine Generator-Matrix, mit welcher man den Klartext direkt in den oben beschriebenen, allgemeinen linearen Code umwandeln kann. Zusätzlich enthält der Schlüssel, wie viele Fehler anschließend maximal in die Chiffre eingebaut werden sollen, also wie viele Bits invertiert werden sollen.

Der geheime, private Schlüssel enthält die Information, wie man den allgemeinen linearen Code wieder in einen Goppa-Code zurückverwandeln kann, der anschließend performant dekodiert werden kann und somit die eingebauten Fehler wieder korrigiert.

Der Algorithmus teilt sich in die drei folgenden Hauptbestandteile auf: Die Schlüssel-Erzeugung, das Verschlüsseln und das Entschlüsseln.

Definitionen

Um die oben genannten drei Verfahren anwenden zu können, müssen zuerst einige Definitionen erfolgen:

Code

Sei $$ C $$ ein binärer $$ (n, k) $$ Goppa-Code, der $$ t $$ Fehler effizient korrigieren kann.

Systemparameter

Um den Aufbau eines McEliece-Kryptosystems eindeutig zu beschreiben, sind die beiden Systemparameter $$ m $$ und $$ t $$ notwendig. $$ m $$ gibt indirekt die Blockgrößen an und $$ t $$ die maximale Anzahl der Fehler, die der verwendete Goppa-Code $$ C $$ noch fehlerfrei korrigieren kann.

Ein McEliece-Kryptosystem ist also wie folgt definiert:

$ McEliece:=(m,t) $

Daraus lassen sich drei weitere Parameter berechnen:

Die Chiffretext-Blocklänge $$ n $$ :

$ n=2^m $

Die Plaintext-Blocklänge $$ k $$ :

$ k=n-mt $

Der minimale Hamming-Abstand $$ d $$ des Codes $$ C $$ :

$ d=2t+1 $

In der Literatur werden die Kryptosysteme meist durch eine der drei, inhaltlich äquivalenten, Notationen beschrieben:

$$ (n,k,d) $$ z.B. in [St95]
$$ (n,k,t) $$ z.B. in [Sch96]
$$ (n,t,k) $$ z.B. in [WiME05]

Nachfolgend verwende ich die erste Notation mit $$ (n,k,d) $$ .

McEliece selbst schlug in seinem Original-Papier ein System mit $$ (1024, 524, 101) $$ vor, also $$ (m = 10, t = 50) $$ als minimale Konfiguration eines sicheren Algorithmus. In [MOV96] wird ein etwas unsicheres, dafür aber effizienteres System mit $$ (1024, 644, 77) $$ , also $$ (m = 10, t = 38) $$ vorgestellt.

Schlüssel-Erzeugung

Angenommen Alice möchte Bob eine verschlüsselte Nachricht senden. Um sein Schlüsselpaar (öffentlicher und privater Schlüssel) zu erzeugen, muß Bob folgende Schritte ausführen:

Zuerst wird eine $k \times n$ Generator-Matrix $$ G $$ für den Goppa-Code $$ C $$ erzeugt. Dies ist eine Matrix, mit der man aus einem binären Klartext der Bitlänge $$ k $$ , die Chiffre mit der Länge $$ n $$ berechnen kann.
Anschließend erzeugt er eine zufällige, binäre, nicht singuläre $k \times k$ Scramble-Matrix $$ S $$ , die über $\mathbb{Z}_2$ invertierbar ist. Nicht singulär bedeutet, daß sie regulär ist. Ihre Determinante muß also ungleich Null sein, denn nur solche Matrizen lassen sich invertieren. Eine binäre Matrix besitzt nur Elemente aus $\mathbb{Z}_2$ .
Danach erzeugt er eine ebenfalls zufällige $n \times n$ Permutations-Matrix $$ P $$ . Eine Permutationsmatrix ist eine binäre Matrix, die in jeder Zeile und Spalte nur genau eine 1 enthält.
Abschließend wird die $k \times n$ Matrix $\hat G$ berechnet:

\hat{G}=SGP

Der komplette Schlüssel K ist nun:

K:=(G,S,P,\hat{G},t)

Bob’s öffentlicher Schüssel Kpub ist:

K_{pub}:=(\hat{G},t)

Sein privater Schüssel Kprv ist:

K_{prv}:=(G,S,P)

Verschlüsselung

Sind die Schlüssel erzeugt, kann Alice mit Hilfe des öffentlichen Schlüssels eine Nachricht verschlüsseln und an Bob senden.

Dazu teilt sie zuerst ihre Nachricht in binäre Blöcke $m \in (\mathbb{Z}_2)^k$ der Länge $$ k $$ auf. Anschließend verschlüsselt sie die Blöcke mit der Verschlüsselungsfunktion:

e_K(m,z)=c=m\hat{G}+z

wobei $z \in (\mathbb{Z}_2)^n$ ein beliebiger Vektor der Länge $$ n $$ ist, der ein maximales Gewicht von $$ t $$ aufweist. Das bedeutet, $$ z $$ besitzt maximal $$ t $$ Einsen. Durch diesen Fehlervektor wird der Chiffretext an maximal $$ t $$ Stellen verändert, also invertiert.

Entschlüsselung

Zum Entschlüsseln nimmt Bob die empfangene Chiffre und berechnet zuerst ein $\hat{c}$ mit:

\hat{c}=cP^{-1}

Anschließend wird die Dekodierungsfunktion $$ decode(c) $$ des Goppa-Codes auf $\hat{c}$ angewandt, um das passende $\hat{m}$ zu finden. Dafür muß der Hamming-Abstand $d_H(\hat{m}G,\hat{c}) \le t$ werden. Der Vorteil an Goppa-Codes ist, daß diese Operation, im Gegensatz zu linearen Codes, effizient berechnet werden kann.

Zuletzt ermittelt Bob den ursprünglichen Klartext $$ m $$ mit:

m=\hat{m}S^{-1}

Die komplette Entschlüsselungsfunktion sieht dann so aus:

d_K(c)=decode(cP^{-1}) \cdot S^{-1}

Zusammenfassung

Systemparameter
$$ m $$	$$ =10 $$	Größe, definiert, Vorgabe von McEliece
$$ t $$	$$ =50 $$	Max. Fehleranzahl , definiert, Vorgabe von McEliece


$$ n $$	$$ =2^m $$	Chiffretext-Blocklänge
$$ k $$	$$ =n-mt $$	Plaintext-Blocklänge
$$ d $$	$$ =2t+1 $$	Hamming-Abstand


Schlüssel-Erzeugung
$$ G $$		$k \times n$ Generator-Matrix (erzeugt $$ C $$ )
$$ S $$		$k \times k$ Scramble-Matrix (zufällig, nicht singulär)
$$ P $$		$n \times n$ Permutations-Matrix (zufällig)


$\hat{G}$	$$ =SGP $$	$k \times n$ Matrix


$K_{pub}$	$=(\hat{G},t)$	Public Key
$K_{prv}$	$$ =(G,S,P) $$	Private Key


Verschlüsselung
$$ m $$	$\in (Z_2)^k$	Klartext
$$ z $$	$\in (Z_2)^n$	Fehlervektor (zufällig, maximal $$ t $$ Einsen)


$$ e_K(m,z) $$	$=c=m\hat{G}+z$	Verschlüsselungsfunktion


Entschlüsselung
$\hat{c}$	$=cP^{-1}$	Inverse Permutation
$\hat{m}$	$=decode(\hat{c})$	Goppa-Code dekodieren
$$ m $$	$=\hat{m}S^{-1}$	Klartext


$$ d_K(c) $$	$=m=decode(cP^{-1}) \cdot S^{-1}$	Gesamte Entschlüsselungsfunktion

Vorteile, Nachteile und Probleme

Der McEliece Algorithmus war einer der ersten Public-Key-Verfahren und bis heute gab es keine erfolgreichen Angriffe dagegen. Zudem ist die Geschwindigkeit etwa um zwei bis drei Größenordnungen höher als bei RSA [Sch96].

Dass dieses System nie wirklich im praktischen Einsatz verwendet wurde, liegt an den schwerwiegenden Nachteilen. Gehen wir von dem von McEliece definierten Kryptosystem mit $$ (1024, 524, 101) $$ aus:

Zum einen ist der öffentliche Schlüssel extrem lang. $\hat{G}$ ist eine Matrix der Größe $k \times n$ . Damit ist der Public Key $k \cdot n$ =536576 Bit lang, dies sind immerhin 65.5 kB.

Zum anderen ist die Chiffre fast doppelt so groß wie der Klartext. Pro 524 Bit Klartext entstehen 1024 Bit Chiffre. Das ist eine Gesamtlänge von 195%.

Beispieldurchlauf

Um einen Algorithmus besser verstehen zu können, hilft meist ein praktisches Beispiel:

McEliece-Kryptosystem Beispieldurchlauf

Zusätzliche Informationen

Douglas Stinson schreibt in [St95] eine sehr gute Erklärung des McEliece-Kryptosystems mit einem Beispiel. Weitere empfehlenswerte Literatur zu diesem Thema ist in [Sch96] und [WiME05]. Eine kurze deutsche Einführung in dieses Thema findet man in [En06].

Quellen