Quelltext der Seite McEliece-Kryptosystem Beispieldurchlauf

{{Qualität
|correctness         =1
|extent              = 4
|numberOfReferences  = 5
|qualityOfReferences = 4
|conformance         = 4
}}

==Beispieldurchlauf für das [[McEliece-Kryptosystem]]==

Nachfolgend soll ein Bespiel für ein sehr kleines <math>(n,k,d)=(7,4,3)</math> [[McEliece-Kryptosystem]] durchgerechnet werden. Dieses Beispiel baut auf dem in [St95] auf.

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

===Schlüssel-Erzeugung===
Um das nachfolgende Beispiel einfacher zu halten, erzeugt die Generator-Matrix <math>G</math> keinen Goppa-Code sondern einen Hamming-Code:

:<math>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}</math> 

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

Bob erzeugt weiter die zufälligen Matrizen <math>S</math> und <math>P</math>:

:<math>S=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}</math> 

:<math>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}</math> 

Der erste Teil <math>\hat{G}</math> des öffentlichen Schlüssels berechnet sich wie folgt:

:<math>\hat{G}=SGP</math>

:<math>\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}=</math>
 
:<math>=\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}=</math>
 
:<math>=\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}</math>
 
Bob’s öffentlicher Schlüssel   lautet nun:

:<math>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)</math>

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

:<math>e_K(m,z)=c=m\hat{G}+z</math>

:<math>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}=</math>

:<math>=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}=</math>

:<math>=\begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 & 0 \end{pmatrix}=c</math>

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

:<math>\hat{c}=cP^{-1}=</math> 

:<math>=\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}=</math> 

:<math>=\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}</math> 

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

Damit wurde Alice’s Klartext <math>\begin{pmatrix} 1 & 1 & 0 & 1 \end{pmatrix}</math> erfolgreich wiederhergestellt.

==Quellen==
* [[McEliece-Kryptosystem]]
* [St95]	Douglas Stinson, Cryptography. Theory and Practice, CRC Press, 1995, ISBN: 0-84938-521-0, Seite 193 ff.
* [Sch96]	Bruce Schneier, Applied Cryptography, Protocols, Algorithms and Source Code in C, 2nd ed., John Wiley & Sons Inc., 1996, ISBN: 0-471-12845-7, Seite 479 ff.
* [WiME05]	Wikipedia, McEliece Cryptosystem, Wikipedia, The Free Encyclopedia, 23. Dec. 2005 10:39 UTC, http://en.wikipedia.org/w/index.php?title=McEliece_cryptosystem&oldid=32471204
* [En06]	ENTROPY, McEliece, Error-correcting Codes als Public Key Verfahren, 01.04.2006, http://entropy.stop1984.com/de/mceliece.html
* [MOV96]	Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press Inc., 1996, ISBN: 0849385237

[[Kategorie:Kryptographie]]
[[Kategorie:Beispiel]]