McEliece-Kryptosystem Beispieldurchlauf: Unterschied zwischen den Versionen

Aktuelle Version vom 20. Mai 2019, 13:31 Uhr

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)

Beispieldurchlauf für das McEliece-Kryptosystem

Nachfolgend soll ein Bespiel für ein sehr kleines $$ (n,k,d)=(7,4,3) $$ McEliece-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.

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

@@ Zeile 1: / Zeile 1: @@
-Dieser Artikel zeigt einen Beispieldurchlauf für das[[McEliece-Kryptosystem]].
+{{Qualität
+|correctness         =1
+|extent              = 4
+|numberOfReferences  = 5
+|qualityOfReferences = 4
+|conformance         = 4
+}}
-==Beispieldurchlauf==
+==Beispieldurchlauf für das [[McEliece-Kryptosystem]]==
-Um einen Algorithmus besser verstehen zu können, hilft meist ein praktisches Beispiel. Nachfolgend soll ein Bespiel für ein sehr kleines <math>(n,k,d)=(7,4,3)</math> Kryptosystem durchgerechnet werden. Dieses Beispiel baut auf dem in [St95] auf.
-==Systemparameter==
+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==
+===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]]

Anonym

Suche

McEliece-Kryptosystem Beispieldurchlauf: Unterschied zwischen den Versionen

Namensräume

Mehr

Seitenaktionen

Aktuelle Version vom 20. Mai 2019, 13:31 Uhr

Inhaltsverzeichnis

Beispieldurchlauf für das McEliece-Kryptosystem

Systemparameter

Schlüssel-Erzeugung

Verschlüsselung

Entschlüsselung

Quellen

Navigation

Navigation

Wikiwerkzeuge

Wikiwerkzeuge

Anonym

Suche

McEliece-Kryptosystem Beispieldurchlauf: Unterschied zwischen den Versionen

Aktuelle Version vom 20. Mai 2019, 13:31 Uhr

Beispieldurchlauf für das McEliece-Kryptosystem

Systemparameter

Schlüssel-Erzeugung

Verschlüsselung

Entschlüsselung

Quellen

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Kategorien