McEliece-Kryptosystem Beispieldurchlauf

aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Wechseln zu:Navigation, Suche

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

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

1.2 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]

1.3 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]

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

2 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

Dieser Artikel ist GlossarWiki-konform.
In diesem Artikel sollten die Quellenangaben überarbeitet werden.
Bitte die Regeln der GlossarWiki-Quellenformatierung beachten.