McEliece-Kryptosystem Beispieldurchlauf

Dieser Artikel zeigt einen Beispieldurchlauf für dasMcEliece-Kryptosystem.

Beispieldurchlauf

Um einen Algorithmus besser verstehen zu können, hilft meist ein praktisches Beispiel. Nachfolgend soll ein Bespiel für ein sehr kleines $ (n,k,d)=(7,4,3) $ Kryptosystem durchgerechnet werden. Dieses Beispiel baut auf dem in [St95] auf.

Systemparameter

Die Systemparameter wurden mit $ n=7 $, $ k=4 $ und $ d=3 $ festgelegt. Damit werden 4 Klartext-Bit auf 7 Chiffre-Bit abgebildet. Weiter braucht der verwendete Code einen Hamming-Abstand von 3. Damit lassen sich $ t=(d-1)/2=1 $ Bitfehler korrigieren.

Schlüssel-Erzeugung

Um das nachfolgende Beispiel einfacher zu halten, erzeugt die Generator-Matrix $ G $ keinen Goppa-Code sondern einen Hamming-Code:

$ G=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} $

Hier sieht man, daß $ d=3 $ gilt, denn jede Zeile unterscheidet sich in mindesten 3 Werten voneinander.

Bob erzeugt weiter die zufälligen Matrizen $ S $ und $ P $:

$ S=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} $

$ P=\begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $

Der erste Teil $ \hat{G} $ des öffentlichen Schlüssels berechnet sich wie folgt:

$ \hat{G}=SGP $

$ \hat{G}=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}= $

$ =\begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}= $

$ =\begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix}=\hat{G} $

Bob’s öffentlicher Schlüssel lautet nun:

$ K_{pub}=(\hat{G},t)=\left(\begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix},1\right) $

Verschlüsselung

Alice möchte ihre Nachricht $ m=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix} $ nun verschlüsseln. Dazu muß noch ein beliebiger Fehlervektor $ z $ mit dem maximalen Gewicht $ t=1 $ und der Länge $ n=7 $ gewählt werden. In diesem Durchlauf soll $ z=\begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $ sein. Die Chiffre $ c $ berechnet sich nun mit

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

$ m=\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}= $

$ =\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}= $

$ =\begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix}=c $

Entschlüsselung

Nach dem Empfang der Chiffre muß Bob zuerst die Permutation rückgängig machen:

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

$ =\begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}= $

$ =\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} $

Anschließend wird der Hamming-Code dekodiert. Dazu wird für jede Zeile der Generator-Matrix $ G $ der Hamming-Abstand $ d $ berechnet. Von der ersten zur vierten Zeile beträgt der Abstand $ \begin{pmatrix} 1 & 3 & 3 & 2 \end{pmatrix} $. Damit ist der dekodierte Code $ \hat{m}=\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} $. Zuletzt wird der Klartext $ m $ berechnet:

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

$ =\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix}= $

$ =\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix} $

Damit wurde Alice’s Klartext $ \begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix} $ erfolgreich wiederhergestellt.